Computational Cost Reduction of Nondominated Sorting Using the M-Front

Abstract

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.