# SSTNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems
## 2 Related Work
Different from OFAA, the realization process of OSAA is to assign solutions to fronts one by one, and every individual needs to be compared with ones that have already been sorted [6; 7; 19]. Efficient non-dominated sorting strategy-sequential strategy (ENS-SS) and its improved version Efficient non-dominated sorting strategy-binary strategy (ENS-BS) [7], Best Order Sort (BOS) [6] and its improved version (BBOS) [19], are representative algorithms. The key preparing process in these methods is to sort the population with one or multiple objectives in an ascending order, and the lexicographic order is used in case any solutions have the same values. ENS [7] can reduce the time complexity in the best case to \(O(MN\sqrt{N})\) but it remains \(O(MN^{2})\) in the worst case. BOS [6] performs better than the abovementioned methods with more objectives, and its time complexity in the best case and the worst case are \(O(MN\log N)\) and \(O(MN^{2}+MN\log N)\). The search strategy to find the front of solutions also influences the efficiency of the algorithm which is shown in the proposed method and its improved versions. Based on the BOS algorithm, combined with the development of high performance computing systems, paper [23] proposes two efficient parallel BOS algorithms, which are based on high performance processing units, one based on multicore processors (MCs), called MC-BOS and the other one based on GPUs, called GPU-BOS. MC-BOS runs on multicore processors, while GPU-BOS utilizes the GPU architecture to implement parallelism. Different from the proposed MC-BOS and GPU-BOS, two other different parallel BOS versions considering the PRAM CREW model are proposed in [24] from a theoretical point of view. The best-case and worst-case time complexity is \(O(log^{3}N)\) and \(O(logM+N^{2})\), and the relevant space complexity is \(O(MN^{2})\). Inspired from the production-grade sorting algorithm, a hybrid approach which combines the divide-and-conquer strategy and BOS is proposed to improve performance, and a heuristic mechanism is designed to determine when to use the BOS algorithm to solve the subproblem [25]. Based on the divide-and-conquer mechanism [26], some researchers proposed recursive non-dominated sorting approaches, which is another means of achieving OSAA [10; 26; 27; 28]. [PERSON]'s algorithm [27] is used to find the maxima of a set of vectors. [PERSON] [28] extends [PERSON]'s algorithm--the time complexity with bi-objectives is \(O(MN\log N)\), while \(O(Nlog\ (M-1)\ N)\) is more than or equal to three objectives. When the population has a large number of objectives, the proposed algorithm will work inefficiently. To decrease redundancy comparisons, a dominance tree is presented in [10] which is used to record the dominant relations between solutions, and this dominance tree is combined with the divide-and-conquer algorithm to acquire the fronts of solutions. Similar to [24], a parallel NDS based on a divide-and-conquer mechanism considering the PRAM-CREW model is proposed in [29]. This paper also explores parallelism from the angle of theory. The best time complexity is proved to be \(O(logM+N)\) and the space complexity is also \(O(MN^{2})\). A tree-based non-dominated sorting algorithm, termed T-ENS, an extension of the ENS algorithm, is proposed in paper [16]. Similar to the most basic algorithm FNDS, the algorithm finds the non-dominated solutions that belongs to the first front, and then deletes them and then the second front, until the population is empty. A tree structure which is formed of unrelated solutions can help to reduce the number of comparisons as the non-domination relationships between solutions have been saved in the tree. The best- and worst-case time complexities of T-ENS are \(O(MNlnN/lnM)\) and \(O(MN^{2})\). To quicken the domination check process and reduce unnecessary comparisons, paper [17] gives another way to improve and extend the ENS-BS algorithm, named Efficient Non-Dominated Sort with Non-dominated Tree (ENS-NDT).