Computing the Consensus Permutation in Mallows Distribution by Using Genetic Algorithms
2013 - Juan A. Aledo, Jose A. Gámez, David Molina
Lecture Notes in Computer Science 7906,102-111 (2013)
Resumen
We propose the use of a genetic algorithm in order to solve the rank aggregation problem, which consists in, given a dataset of rankings (or permutations) of n objects, finding the ranking which best represents such dataset. Though different probabilistic models have been proposed to tackle this problem (see e.g. [12]), the so called Mallows model is the one that has more attentions [1]. Exact computation of the parameters of this model is an NP-hard problem [19], justifies the use of metaheuristic algorithms for its resolution. In particular, we propose a genetic algorithm for solving this problem and show that, in most cases (specially in the most complex ones) we get statistically significant better results than the ones obtained by the state of the art algorithms.