# Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2025.

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

- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of σ-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.