Merge Nondominated Sorting Algorithm for Many-Objective Optimization
2021
Many Pareto-based multiobjective evolutionary algorithms require ranking the solutions of the population in each iteration according to the dominance principle, which can become a costly operation particularly in the case of dealing with many-objective optimization problems. In this article, we present a new efficient algorithm for computing the nondominated sorting procedure, called merge nondominated sorting (MNDS), which has a best computational complexity of
$O(N\log N)$
and a worst computational complexity of
$O(MN^{2})$
, with
$N$
being the population size and
$M$
being the number of objectives. Our approach is based on the computation of the
dominance set
, that is, for each solution, the set of solutions that dominate it, by taking advantage of the characteristics of the merge sort algorithm. We compare MNDS against six well-known techniques that can be considered as the state-of-the-art. The results indicate that the MNDS algorithm outperforms the other techniques in terms of the number of comparisons as well as the total running time.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
0
Citations
NaN
KQI