Solving Rank Aggregation Problems through Memetic Algorithms

The rank aggregation problem can be encountered in many scientific areas (such as economics, social sciences, computer science, just to cite a few) when the problem is to aggregate a set of individual preferences (rankings or ratings), over a set of alternatives, to find a consensus. The detection of the consensus or median ranking is the identification of the ordering of n items that best synthesizes the preferences of k different judges. The median ranking is defined as a ranking that minimizes the sum of distances between itself and all input rankings. The search space of the median ranking is formed by all the possible permutations of the items to be ranked with ties (occurring when a judge assign the same preference to an object). The distance to be minimized is the Kemeny distance. Since finding a consensus ranking is a Non-deterministic Polynomial-time (NP) hard problem, in the last years Evolutionary Algorithms (EA) are emerging as a suitable methodology to address the complexity of the problem. However, these meta-heuristics are characterized by a slow convergence. To overcome this drawback, in this paper we propose a Memetic Algorithm (MA) to solve the rank aggregation problem. The proposed MA is a combination between genetic algorithms and the stochastic version of the hill climbing search. As shown by a set of experiments performed by exploiting well-known real datasets, our proposal outperforms the evolutionary state-of-the-art algorithms for the rank aggregation problem.