An Adaptive Biased Random-key Genetic Algorithm for Rank Aggregation with Ties and Incomplete Rankings

Abstract

The Rank Aggregation problem has applications in several fields of science like Information Retrieval, Social Sciences, Bioinformatics, among others. In this problem, the objective is to create a consensus ranking given a set of input rankings. This paper considers a variant of this problem, in which the set of input rankings may contain ties and may be incomplete. An Adaptive Biased Random-key Genetic Algorithm (A-BRKGA) is proposed to solve this problem, and the results are compared to an integer linear programming model previously introduced in the literature. Since the fitness evaluation of the A-BRKGA is its most time-consuming component, a partial fitness evaluation was derived and used in the local search component created for this problem. The partial evaluation reduces the time complexity from quadratic to linear. In the experiments, the efficiency of the A-BRKGA with the local search was evaluated against the A-BRKGA without the local search component and the integer linear programming introduced in the literature. The experimental results show that the proposed technique achieved superior results in terms of quality when compared to the A-BRKGA without the local search component, achieved similar results in terms of quality and better results in terms of computational time when compared to the integer linear programming model.