EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Approximation Guarantees for the Nondominated Sorting Genetic Algorithm II (NSGA-II)

Weijie Zheng, Benjamin Doerr

IEEE Transactions on Evolutionary Computation · 2025-08 · 29 (4) · 891-905

DOI: 10.1109/tevc.2024.3402996 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Evolutionary Computation, 2025-08. Verfasst von Weijie Zheng und 1 weiteren Autor:innen. Die Arbeit wurde bisher 28-mal zitiert (Crossref) und nennt 67 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: National Natural Science Foundation of China, Science, Technology and Innovation Commission of Shenzhen Municipality, Basic and Applied Basic Research Foundation of Guangdong Province.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Recent theoretical works have shown that the NSGA-II efficiently computes the full Pareto front when the population size is large enough. In this work, we study how well it approximates the Pareto front when the population size is smaller. For the OneMinMax benchmark, we point out situations in which the parents and offspring cover well the Pareto front, but the next population has large gaps on the Pareto front. Our mathematical proofs suggest as reason for this undesirable behavior that the NSGA-II in the selection stage computes the crowding distance once and then removes individuals with smallest crowding distance without considering that a removal increases the crowding distance of some individuals. We then analyse two variants not prone to this problem. For the NSGA-II that updates the crowding distance after each removal [Kukkonen and Deb (2006)] and the steady-state NSGA-II [Nebro and Durillo (2009)], we prove that the gaps in the Pareto front are never more than a small constant factor larger than the theoretical minimum. This is the first mathematical work on the approximation ability of the NSGA-II and the first runtime analysis for the steady-state NSGA-II. Experiments also show the superior approximation ability of the two NSGA-II variants.

Förderung

  • National Natural Science Foundation of China
  • Science, Technology and Innovation Commission of Shenzhen Municipality
  • Basic and Applied Basic Research Foundation of Guangdong Province
  • Investissement d’avenir Project

Zitieren

APA

Zheng, W., & Doerr, B. (2025). Approximation Guarantees for the Nondominated Sorting Genetic Algorithm II (NSGA-II). IEEE Transactions on Evolutionary Computation, 29(4), 891-905. https://doi.org/10.1109/tevc.2024.3402996

Vancouver

Zheng W, Doerr B. Approximation Guarantees for the Nondominated Sorting Genetic Algorithm II (NSGA-II). IEEE Transactions on Evolutionary Computation. 2025;29(4):891-905. doi:10.1109/tevc.2024.3402996

BibTeX
@article{Zheng2025,
  author = {Zheng, Weijie and Doerr, Benjamin},
  title = {Approximation Guarantees for the Nondominated Sorting Genetic Algorithm II (NSGA-II)},
  journal = {IEEE Transactions on Evolutionary Computation},
  year = {2025},
  volume = {29},
  number = {4},
  pages = {891--905},
  doi = {10.1109/tevc.2024.3402996}
}
Kostenlos starten →