# SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 42 references that are in the map.
- First posted on arXiv 10 Jun 2026.

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

- [pymoo: Multi-objective Optimization in Python](https://mlsanity.com/paper/2002.04504/) (2020)
- [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)
- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation](https://mlsanity.com/paper/2301.13687/) (2023)
- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [Runtime Analysis of the SMS-EMOA for Many-Objective Optimization](https://mlsanity.com/paper/2312.10290/) (2023)
- [Runtime Analyses of NSGA-III on Many-Objective Problems](https://mlsanity.com/paper/2404.11433/) (2024)
- [Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2404.12746/) (2024)
- [A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)](https://mlsanity.com/paper/2406.16116/) (2024)
- [Analysing the Robustness of NSGA-II under Noise](https://mlsanity.com/paper/2306.04525/) (2023)
- [Speeding Up the NSGA-II With a Simple Tie-Breaking Rule](https://mlsanity.com/paper/2412.11931/) (2024)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis](https://mlsanity.com/paper/2405.13572/) (2024)
- [The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2504.21552/) (2025)
- [Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II](https://mlsanity.com/paper/2505.01323/) (2025)
- [Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds](https://mlsanity.com/paper/2511.07125/) (2025)
- [Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm](https://mlsanity.com/paper/2505.01266/) (2025)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy](https://mlsanity.com/paper/2507.03666/) (2025)
- [Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer](https://mlsanity.com/paper/2511.07150/) (2025)

## Abstract (arXiv)

The Strength Pareto Evolutionary Algorithm 2 (SPEA2) is a popular and prominent evolutionary algorithm for solving multi-objective optimisation problems. Despite its popularity, theoretical analyses of SPEA2 have only appeared recently. Moreover, these analyses focus exclusively on how SPEA2 handles non-dominated solutions and disregard the algorithmic components responsible for handling dominated solutions. We conduct a first runtime analysis of SPEA2 for which these components are analysed. We prove that, unlike other prominent algorithms, including NSGA-II, NSGA-III and SMS-EMOA under the same setting of constant population size and duplicate elimination, SPEA2 is unable to cover the Pareto front of the OneTrapZeroTrap benchmark efficiently. Our results indicate that using k-th nearest-neighbour distance in the fitness assignment provides an insufficient signal to maintain diversity among dominated individuals. To address this issue, we propose an improved variant, SPEA2^+, that considers all pairwise distances. The new algorithm achieves the same performance guarantees as the other prominent algorithms on OneTrapZeroTrap, while matching the performance of the original SPEA2 on simpler problems. Experimental results complement our theoretical findings.