EUVIMEDEUVIMED entdecken
Crossref

A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization

Weijie Zheng, Yan Gao, Benjamin Doerr

IEEE Transactions on Evolutionary Computation · 2026-10 · 30 (5) · 2082-2092

DOI: 10.1109/tevc.2025.3638306 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Evolutionary Computation, 2026-10. Verfasst von Weijie Zheng und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 41 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Basic and Applied Basic Research Foundation of Guangdong Province, Science, Technology and Innovation Commission of Shenzhen Municipality.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Recent mathematical runtime analyses have shown that the crowding distance used by the nondominated sorting genetic algorithm II (NSGA-II) multiobjective optimizer does not well reflect how isolated, and hence worth keeping, solutions are. This has provably led to drastic difficulties when the number of objectives is three or more. Based on the insights of these works, we design a variant of the crowding distance, called truthful crowding distance, and analyze the resulting truthful NSGA-II with mathematical means: 1) we show that it solves the many-objective versions of theOMM, COCZ, LOTZ, and ${\text {OJZJ}}_{k}$ problems in the same (polynomial) asymptotic runtimes as the NSGA-III and the SMS-EMOA, contrasting the exponential lower bounds for the classic NSGA-II; 2) for the bi-objective versions of these problems, our NSGA-II maintains the good performance of the classic NSGA-II, but is successful already with population sizes smaller by a constant factor; and 3) for the bi-objective OMM problem, we observe a (minimally) better performance in approximating the Pareto front. These results indicate that our truthful crowding distance is an interesting alternative to the classic crowding distance.

Förderung

  • National Natural Science Foundation of China
  • Basic and Applied Basic Research Foundation of Guangdong Province
  • Science, Technology and Innovation Commission of Shenzhen Municipality
  • FMJH Program PGMO

Zitieren

APA

Zheng, W., Gao, Y., & Doerr, B. (2026). A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 30(5), 2082-2092. https://doi.org/10.1109/tevc.2025.3638306

Vancouver

Zheng W, Gao Y, Doerr B. A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization. IEEE Transactions on Evolutionary Computation. 2026;30(5):2082-2092. doi:10.1109/tevc.2025.3638306

BibTeX
@article{Zheng2026,
  author = {Zheng, Weijie and Gao, Yan and Doerr, Benjamin},
  title = {A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization},
  journal = {IEEE Transactions on Evolutionary Computation},
  year = {2026},
  volume = {30},
  number = {5},
  pages = {2082--2092},
  doi = {10.1109/tevc.2025.3638306}
}
Kostenlos starten →