# The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 74 references that are in the map.
- First posted on arXiv 22 May 2023.

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

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/1711.07214/) (2017)
- [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)
- [Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables](https://mlsanity.com/paper/2109.05799/) (2021)
- [A Tight Runtime Analysis for the (μ + λ) EA](https://mlsanity.com/paper/1812.11061/) (2018)
- [Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation](https://mlsanity.com/paper/2301.13687/) (2023)
- [An Efficient Evolutionary Algorithm for Minimum Cost Submodular Cover](https://mlsanity.com/paper/1908.01029/) (2019)
- [The (1+(λ,λ)) Global SEMO Algorithm](https://mlsanity.com/paper/2210.03618/) (2022)

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

- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems](https://mlsanity.com/paper/2306.03409/) (2023)
- [A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization](https://mlsanity.com/paper/2407.17687/) (2024)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)
- [Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination](https://mlsanity.com/paper/2605.17454/) (2026)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most prominent algorithms to solve multi-objective optimization problems. Recently, the first mathematical runtime guarantees have been obtained for this algorithm, however only for synthetic benchmark problems. In this work, we give the first proven performance guarantees for a classic optimization problem, the NP-complete bi-objective minimum spanning tree problem. More specifically, we show that the NSGA-II with population size N ≥ 4((n-1) wmax + 1) computes all extremal points of the Pareto front in an expected number of O(m2 n wmax log(n wmax)) iterations, where n is the number of vertices, m the number of edges, and wmax is the maximum edge weight in the problem instance. This result confirms, via mathematical means, the good performance of the NSGA-II observed empirically. It also shows that mathematical analyses of this algorithm are not only possible for synthetic benchmark problems, but also for more complex combinatorial optimization problems. As a side result, we also obtain a new analysis of the performance of the global SEMO algorithm on the bi-objective minimum spanning tree problem, which improves the previous best result by a factor of |F|, the number of extremal points of the Pareto front, a set that can be as large as n wmax. The main reason for this improvement is our observation that both multi-objective evolutionary algorithms find the different extremal points in parallel rather than sequentially, as assumed in the previous proofs.