Proceedings

The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III)

Renzhong Deng, Weijie Zheng, Benjamin Doerr

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8867-8875.

https://doi.org/10.24963/ijcai.2025/986

Keywords

  • Search: S: Evolutionary computation

Abstract

This work conducts a first theoretical analysis studying how well the NSGA-III approximates the Pareto front when the population size N is less than the Pareto front size. We show that when N is at least the number Nr of reference points, then the approximation quality, measured by the maximum empty interval (MEI) indicator, on the OneMinMax benchmark is such that there is no empty interval longer than ⌈(5-2√2)n/(Nr-1)⌉. This bound is independent of N, which suggests that further increasing the population size does not increase the quality of approximation when Nr is fixed. This is a notable difference to the NSGA-II with sequential survival selection, where increasing the population size improves the quality of the approximations. We also prove two results indicating approximation difficulties when N<Nr. These theoretical results suggest that the best setting to approximate the Pareto front is Nr=N. In our experiments, we observe that with this setting the NSGA-III computes optimal approximations, very different from the NSGA-II, for which optimal approximations have not been observed so far.

Renzhong Deng, Weijie Zheng, and Benjamin Doerr. 2025. The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III). In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8867–8875. https://doi.org/10.24963/ijcai.2025/986
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards