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

arXiv: https://arxiv.org/abs/2407.17687 · HTML: https://mlsanity.com/paper/2407.17687/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 25 Jul 2024.

## Builds on (most cited first, 16 of 16)

- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2112.08581/) (2021)
- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives](https://mlsanity.com/paper/2211.13084/) (2022)
- [Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation](https://mlsanity.com/paper/2301.13687/) (2023)
- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [Runtime Analysis of the SMS-EMOA for Many-Objective Optimization](https://mlsanity.com/paper/2312.10290/) (2023)
- [Runtime Analyses of NSGA-III on Many-Objective Problems](https://mlsanity.com/paper/2404.11433/) (2024)
- [Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2404.12746/) (2024)
- [A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)](https://mlsanity.com/paper/2406.16116/) (2024)
- [Analysing the Robustness of NSGA-II under Noise](https://mlsanity.com/paper/2306.04525/) (2023)
- [Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2203.02693/) (2022)

## Built on by (most cited first, 1 of 1)

- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)

## Abstract (arXiv)

Recent theoretical works have shown that the NSGA-II can have enormous difficulties to solve problems with more than two objectives. In contrast, algorithms like the NSGA-III or SMS-EMOA, differing from the NSGA-II only in the secondary selection criterion, provably perform well in these situations. To remedy this shortcoming of the NSGA-II, but at the same time keep the advantages of the widely accepted crowding distance, we use the insights of these previous work to define a variant of the crowding distance, called truthful crowding distance. Different from the classic crowding distance, it has for any number of objectives the desirable property that a small crowding distance value indicates that some other solution has a similar objective vector. Building on this property, we conduct mathematical runtime analyses for the NSGA-II with truthful crowding distance. We show that this algorithm can solve the many-objective versions of the OneMinMax, COCZ, LOTZ, and OJZJk problems in the same (polynomial) asymptotic runtimes as the NSGA-III and the SMS-EMOA. This contrasts the exponential lower bounds previously shown for the classic NSGA-II. For the bi-objective versions of these problems, our NSGA-II has a similar performance as the classic NSGA-II, gaining however from smaller admissible population sizes. For the bi-objective OneMinMax problem, we also observe a (minimally) better performance in approximating the Pareto front. These results suggest that our truthful version of the NSGA-II has the same good performance as the classic NSGA-II in two objectives, but can resolve the drastic problems in more than two objectives.