A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization
<|reference_start|>A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization: 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 OJZJ$_k$ 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.<|reference_end|>
@article{zheng2024a,
    title={A Crowding Distance That Provably Solves the Difficulties of the NSGA-II
  in Many-Objective Optimization},
    author={Weijie Zheng, Yao Gao, Benjamin Doerr},
    journal={arXiv preprint arXiv:2407.17687},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.17687},
    primaryClass={cs.NE cs.AI}
}