PROJECT TITLE :

Computational Cost Reduction of Nondominated Sorting Using the M-Front

ABSTRACT:

Several multiobjective evolutionary algorithms depend upon the nondominated sorting procedure to see the relative quality of people with respect to the population. During this paper, we propose a replacement technique to decrease the cost of this procedure. Our approach is to work out the nondominated individuals at the start of the evolutionary algorithm run and to update this information because the population changes. In order to do this efficiently, we propose a special data structure referred to as the M-front, to hold the nondominated half of the population. The M-front uses the geometric and algebraic properties of the Pareto dominance relation to convert orthogonal vary queries into interval queries employing a mechanism based on the closest neighbor search. These interval queries are answered using dynamically sorted linked lists. Experimental results show that our technique can perform considerably faster than the state-of-the-art Jensen-Fortin's algorithm, particularly in several-objective eventualities. A important advantage of our approach is that, if we modification a single individual in the population we tend to still know that people are dominated and that don't seem to be.