Incremental Non-Dominated Sorting algorithms based on Irreducible Domination Graphs
Pedro M. Mateo, D. Lahoz, I. Alberto · Applied Soft Computing · 2022
Non-Dominated Sorting process, NDS, plays an important role in Pareto based Evolutionary Multi-Objective 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.