Sequence sort: A new non-dominated sorting algorithm for evolutionary multi-objective optimization

Non-dominated sorting is a crucial component of multi-objective evolutionary algorithms. However, most existing non-dominated sorting algorithms suffer from low computational efficiency and high complexity, especially as the number of objectives increases. This is mainly because many algorithms require comparing a solution with almost all other solutions to determine the Pareto front, leading to numerous redundant comparisons and wasted runtime. Therefore, efficient and straightforward Pareto-based non-dominated sorting algorithms remain scarce. To address this issue, this paper introduces a new non-dominated sorting algorithm, called Sequence Sort. The algorithm achieves a best-case computational complexity of [Formula: see text], where N is the population size and M is the number of objectives. Sequence Sort combines the strategies of presorting and solution marking. In our experiments, we compare the performance of Sequence Sort with Fast Non-dominated Sorting, Deductive Sorting, HNDS, Corner Sorting, and MNDS, and employ statistical tests to validate the significance of the results. The results demonstrate that, while ensuring sorting outcomes consistent with reference methods, Sequence Sort provides significant computational efficiency advantages. Therefore, Sequence Sort offers an efficient, reliable, and promising alternative for solving multi-objective optimization problems.