Tackling the rank aggregation problem with evolutionary algorithms

Probabilistic reasoning and learning with permutation data has gained interest in recent years because its use in different ranking-based real-world applications. Therefore, constructing a model from a given set of permutations or rankings has become a target problem in the machine learning community. In this paper we focus on probabilistic modelling and concretely in the use of a well known permutation-based distribution as it is the Mallows model. Learning a Mallows model from data requires the estimation of two parameters, a consensus permutation pi(0) and a dispersion parameter theta. Since the exact computation of these parameters is an NP-hard problem, it is natural to consider heuristics to tackle this problem. An interesting approach consists in the use of a two-step procedure, first estimating pi(0), and then computing theta for a given pi(0). This is possible because the optimal pi(0) does not depend on theta. When following this approach, computation of pi(0) reduces to the rank aggregation problem, which consists in finding the ranking which best represents such dataset. In this paper we propose to use genetic algorithms to tackle this problem, studying its performance with respect to state-of-the-art algorithms, specially in complex cases, that is, when the number of items to rank is large and there is few consensus between the available rankings (which traduces in a low value for theta). After a series of experiments involving data of different type, we conclude that our evolutionary approach clearly outperforms the remaining tested algorithms. (C) 2013 Elsevier Inc. All rights reserved.