SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems
Non-dominated sorting, used to find pareto solutions or assign solutions to different fronts, is a key but time-consuming process in multi-objective evolutionary algorithms (MOEAs). The best-case and worst-case time complexity of non-dominated sorting algorithms currently known are <i>O(MNlogN...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/10/19/6858 |
| _version_ | 1797552251919663104 |
|---|---|
| author | Lingling Xue Peng Zeng Haibin Yu |
| author_facet | Lingling Xue Peng Zeng Haibin Yu |
| author_sort | Lingling Xue |
| collection | DOAJ |
| description | Non-dominated sorting, used to find pareto solutions or assign solutions to different fronts, is a key but time-consuming process in multi-objective evolutionary algorithms (MOEAs). The best-case and worst-case time complexity of non-dominated sorting algorithms currently known are <i>O(MNlogN)</i> and <i>O(MN<sup>2</sup>)</i>; M and N represent the number of objectives and the population size, respectively. In this paper, a more efficient SET-based non-dominated sorting algorithm, shorted to SETNDS, is proposed. The proposed algorithm can greatly reduce the number of comparisons on the promise of ensuring a shorter running time. In SETNDS, the rank of a solution to be sorted is determined by only comparing with the one with the highest rank degree in its dominant set. This algorithm is compared with six generally existing non-dominated sorting algorithms—fast non-dominated sorting, the arena’s principle sort, the deductive sort, the corner sort, the efficient non-dominated sort and the best order sort on several kinds of datasets. The compared results show that the proposed algorithm is feasible and effective and its computational efficiency outperforms other existing algorithms. |
| first_indexed | 2024-03-10T15:57:21Z |
| format | Article |
| id | doaj.art-ecc3658567164c1fa495f9505d9a2cdc |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T15:57:21Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-ecc3658567164c1fa495f9505d9a2cdc2023-11-20T15:33:42ZengMDPI AGApplied Sciences2076-34172020-09-011019685810.3390/app10196858SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization ProblemsLingling Xue0Peng Zeng1Haibin Yu2Key Laboratory of Networked Control System, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, ChinaKey Laboratory of Networked Control System, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, ChinaKey Laboratory of Networked Control System, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, ChinaNon-dominated sorting, used to find pareto solutions or assign solutions to different fronts, is a key but time-consuming process in multi-objective evolutionary algorithms (MOEAs). The best-case and worst-case time complexity of non-dominated sorting algorithms currently known are <i>O(MNlogN)</i> and <i>O(MN<sup>2</sup>)</i>; M and N represent the number of objectives and the population size, respectively. In this paper, a more efficient SET-based non-dominated sorting algorithm, shorted to SETNDS, is proposed. The proposed algorithm can greatly reduce the number of comparisons on the promise of ensuring a shorter running time. In SETNDS, the rank of a solution to be sorted is determined by only comparing with the one with the highest rank degree in its dominant set. This algorithm is compared with six generally existing non-dominated sorting algorithms—fast non-dominated sorting, the arena’s principle sort, the deductive sort, the corner sort, the efficient non-dominated sort and the best order sort on several kinds of datasets. The compared results show that the proposed algorithm is feasible and effective and its computational efficiency outperforms other existing algorithms.https://www.mdpi.com/2076-3417/10/19/6858dominant setset theorySET-based non-dominated sorting algorithm (SETNDS), time complexity |
| spellingShingle | Lingling Xue Peng Zeng Haibin Yu SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems Applied Sciences dominant set set theory SET-based non-dominated sorting algorithm (SETNDS), time complexity |
| title | SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems |
| title_full | SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems |
| title_fullStr | SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems |
| title_full_unstemmed | SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems |
| title_short | SETNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems |
| title_sort | setnds a set based non dominated sorting algorithm for multi objective optimization problems |
| topic | dominant set set theory SET-based non-dominated sorting algorithm (SETNDS), time complexity |
| url | https://www.mdpi.com/2076-3417/10/19/6858 |
| work_keys_str_mv | AT linglingxue setndsasetbasednondominatedsortingalgorithmformultiobjectiveoptimizationproblems AT pengzeng setndsasetbasednondominatedsortingalgorithmformultiobjectiveoptimizationproblems AT haibinyu setndsasetbasednondominatedsortingalgorithmformultiobjectiveoptimizationproblems |