Incremental Non-Dominated Sorting algorithms based on Irreducible Domination Graphs

Non-Dominated Sorting process, NDS, plays an important role in Pareto based Evolutionary MultiObjective Optimization Algorithms and it is one of the most time consuming tasks, mainly when steady-state Evolutionary Algorithms are considered, i.e. algorithms in which the updating of the Pareto layers must be accomplished every time a new solution is generated. In this paper we present a general framework to carry out the NDS process and three implementations based on a modification of the Irreducible Domination Graph structure, IDG, presented in Alberto and Mateo (2004) for accomplishing this task. The proposed algorithms are compared with other NDS algorithms designed specifically for the incremental update of the Pareto layers. The experiments carried out show that the proposed algorithms reduce, in general, the time needed as well as the number of Pareto comparisons when compared with the competitors. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

Non-Dominated Sorting process (NDS) is crucial in Pareto-based evolutionary multi-objective optimization algorithms, especially in steady-state evolutionary algorithms where the Pareto layers need to be updated for each new solution. This paper presents a general framework and three implementations based on a modified Irreducible Domination Graph structure (IDG) to carry out the NDS process efficiently. The proposed algorithms are compared with other NDS algorithms specifically designed for incremental updates of Pareto layers, showing reduced time and Pareto comparisons.