# Runtime Analysis of the SMS-EMOA for Many-Objective Optimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2023.

## 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)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

This paper conducts the first rigorous runtime analysis of the SMS-EMOA for many-objective optimization. To this aim, we first propose a many-objective counterpart of the bi-objective OJZJ benchmark. We prove that SMS-EMOA computes the full Pareto front of this benchmark in an expected number of O(μ M nk) iterations, where n denotes the problem size (length of the bit-string representation), k the gap size (a difficulty parameter of the problem), M=(2n/m-2k+3)m/2 the size of the Pareto front, and μ the population size (at least the same size as the largest incomparable set). This result together with the existing negative result for the original NSGA-II shows that, in principle, the general approach of the NSGA-II is suitable for many-objective optimization, but the crowding distance as tie-breaker has deficiencies. We obtain three additional insights on the SMS-EMOA. Different from a recent result for the bi-objective ojzj benchmark, a recently proposed stochastic population update often does not help for its many-objective counterpart. It at most results in a speed-up by a factor of order 2k / μ, which is Theta(1) for large m, such as m>k. On the positive side, we prove that heavy-tailed mutation irrespective of the number m of objectives results in a speed-up of order k0.5+k-β/ek. Finally, we conduct the first runtime analyses of the SMS-EMOA on the classic OMM and LOTZ and show that the SMS-EMOA has a performance comparable to the GSEMO and the NSGA-II. Our main technical insight, a general condition ensuring that the SMS-EMOA does not lose Pareto-optimal objective values, promises to be useful also in other runtime analyses of this algorithm.