# SSTNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems
## 2 Related Work  
In this section, we will discuss and analyze the methods for non-dominated sorting that have been researched and utilized in MOPs. Through reviewing lots of broad research on non-dominated sorting [2; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19], the common methods for sorting multi-objective solutions can be classified into two classes: one front after another (OFAA) and one solution after another (OSAA). The basic idea of OFAA is to compare each solution with others to obtain non-dominated solutions, then assign them to the current rank and remove them temporarily. This process is repeated until the population is empty. Some of the general methods are basic non-dominated sorting algorithm (BNDS) [2], improved version fast non-dominated sorting algorithm (FNDS) [2], quick non-dominated sorting algorithm (QNDS) [8], the arena's principle (AP) [9], deductive sort (DS) [12] and climbing sort (CLS) [12], corner sort (CS) [11] and so on. BNDS [20] compares a solution to others to judge whether it is dominated or not, if there is no solution dominating it, it will be added to the current rank. The time complexity of this method is \(O(MN^{3})\) because of lots of redundancy comparisons. FNDS [2] is proposed in reference to basic insertion sorting algorithms, which reduces the time complexity to \(O(MN^{2})\), but its space complexity increases to \(O(N^{2})\). In order to reduce the negative impact of multiple conflicting objectives on the running efficiency of the evolutionary algorithms, parallelization is introduced to the non-dominated sorting process, e.g., paper [21] develops three parallel NDS versions based on FNDS, a multicore, a Graphic Processing Unit (GPU) and a hybrid, respectively. QNDS [8] adopts the realization idea of  
Figure 1: An example with eight points in a bi-objective minimization problem. quick sort, and can reduce the best-case time complexity to \(O(MN\sqrt{N})\). It is better than FNDS, but the worst-case time complexity remains \(O(MN^{2})\). The AP [9] is shown to be a more effective algorithm than other OSAA algorithms in empirical evaluations. The idea of AP is to select a solution as the \"arena host\" randomly (always choose the first solution of the population) and for the remaining solutions to challenge the arena one by one. If the challenger wins then the challenger is better and it will be the new \"arena host\"--the old arena will be eliminated. The challenger who is worse than the arena host will be removed. The new arena host will compare with the rest of the solutions until the last one. Best-case time complexity can be enhanced to \(O(MN\sqrt{N})\), yet it is still \(O(MN^{2})\) in the worst case. CS [11] first proposes to sort the population with one or multiple objectives as the solution with the best objective values are non-dominated. The under-compared solution is always dominating or unrelated to the remaining solutions. The dominated solutions are removed and unrelated solutions are reserved as the AP method. Its time complexity is the same as the FNDS and space complexity is \(O(N)\). Two non-dominated sorting methods to solve the multi-objective solutions, DS and CLS, are proposed in [12]. The former is shown to be better than CLS. DS records the comparison result for avoiding unnecessary comparisons. DS also gives \(O(MN\sqrt{N})\) and \(O(MN^{2})\) for the best case and worst case, respectively. A new data structure, which is composed of a K-d tree and M-list called M-front, is proposed in [22] and used to decrease the computational cost of non-dominated sorting. In M-front, utilizing the over-non-domination phenomenon as an advantage with the increase in the number of objectives. To hold the invariance property of the M-front, an interval query is used to reduce the scope of query and speed up the selection of the non-dominated individual. The best-case time complexity is \(O(MN)\) or \(O(MN\ln N)\) when the K-d tree is used, and the worst-case time complexity is \(O(MN^{2})\).