# Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2024.

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

- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization](https://mlsanity.com/paper/2407.17687/) (2024)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [Benchmarking MOEAs for solving continuous multi-objective RL problems](https://mlsanity.com/paper/2505.13726/) (2025)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing performance guarantees for classic MOEAs on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we consider a large class of MOEAs including the (global) SEMO, SMS-EMOA, balanced NSGA-II, NSGA-III, and SPEA2. For these, we prove near-tight runtime guarantees for the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Most of our bounds depend only linearly on the size of the largest incomparable set, showing that MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Most of our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of MOEAs. For the runtime of the SEMO on the LOTZ benchmark in m ≥ 6 objectives, our runtime guarantees are even smaller than the size of the largest incomparable set. This is again the first time that such runtime guarantees are proven.