Abstract
We present an algorithm for incremental non-dominated sorting, a procedure to use with steady-state multiobjective algorithms, with the complexity of O(N(log N)^M−2) for a single insertion, where N is the number of points and M is the number of objectives. This result generalizes the previously known O(N) algorithm designed for two objectives.
Our experimental performance study showed that our algorithm demonstrates a superior performance compared to the competitors, including various modifications of the divide-and-conquer non-dominated sorting algorithm (which significantly improve the performance on their own), and the state-of-the-art Efficient Non-domination Level Update algorithm. Only for M = 2 the specialized algorithm for two dimensions outperforms the new algorithm.
Our experimental performance study showed that our algorithm demonstrates a superior performance compared to the competitors, including various modifications of the divide-and-conquer non-dominated sorting algorithm (which significantly improve the performance on their own), and the state-of-the-art Efficient Non-domination Level Update algorithm. Only for M = 2 the specialized algorithm for two dimensions outperforms the new algorithm.
| Original language | English |
|---|---|
| Title of host publication | GECCO '17 |
| Subtitle of host publication | Proceedings of the Genetic and Evolutionary Computation Conference |
| Publisher | Association for Computing Machinery |
| Pages | 649-656 |
| Number of pages | 8 |
| ISBN (Print) | 978-1-4503-4920-8 |
| DOIs | |
| Publication status | Published - 01 Jul 2017 |
| Externally published | Yes |
Keywords
- divide-and-conquer
- non-dominated sorting
- steady-state algorithms