A Review of Non-dominating Sorting Algorithms

The concept of non-dominated sorting (NDS) involves organizing a population’s solutions based on the Pareto dominance principle, a critical element influencing the computational efficiency of various multi-objective evolutionary algorithms. The roots of multi-objective optimization using a non-dominated sorting scheme can be traced back to the early days of Goldenberg’s book. Over time, enhancements have been made to non-dominated sorting methods, achieving a best-case complexity of \(\mathcal {O}(MN\log N)\) , with N representing the population size and M denoting the number of objectives. This study presents a comprehensive literature review, examining existing papers on non-dominated sorting and categorizing methods into tree-based NDS, first objective sorted list-based NDS, full objective sorted lists-based NDS, divide-and-conquer-based NDS, and labeling and deleting-based NDS. Additionally, the exploration includes a detailed division between front-by-front procedure-based NDS and solution-by-solution procedure-based NDS. The review assesses the strengths and weaknesses of these methods, concluding with suggestions for promising avenues in future research on non-dominated sorting.