Computational Cost Reduction of Nondominated Sorting Using the M-Front

Many multiobjective evolutionary algorithms rely on the nondominated sorting procedure to determine the relative quality of individuals with respect to the population. In this paper, we propose a new method to decrease the cost of this procedure. Our approach is to determine the nondominated individuals at the start of the evolutionary algorithm run and to update this knowledge as the population changes. In order to do this efficiently, we propose a special data structure called the M-front, to hold the nondominated part of the population. The M-front uses the geometric and algebraic properties of the Pareto dominance relation to convert orthogonal range queries into interval queries using a mechanism based on the nearest neighbor search. These interval queries are answered using dynamically sorted linked lists. Experimental results show that our method can perform significantly faster than the state-of-the-art Jensen-Fortin's algorithm, especially in many-objective scenarios. A significant advantage of our approach is that, if we change a single individual in the population we still know which individuals are dominated and which are not.