Paper Overview
Field: Machine Learning Authors: Duc-Cuong Dang, Andre Opris, Dirk Sudholt Published: 2026-06-10 arXiv: 2606.12382
Summary
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, and these analyses focus exclusively on how SPEA2 handles non-dominated solutions, disregarding the algorithmic components responsible for handling dominated solutions.
The authors conduct a first runtime analysis of SPEA2 in which these components are analysed. They 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 efficiently cover the Pareto front of the OneTrapZeroTrap benchmark.
Their results indicate that using the k-th nearest-neighbor distance in fitness assignment provides an insufficient signal for maintaining diversity among dominated individuals.
To address this, the paper proposes an improved variant, SPEA2+, which considers all pairwise distances. The new algorithm achieves the same performance guarantees as the other prominent algorithms on OneTrapZeroTrap, while matching the original SPEA2's performance on simpler problems. Experimental results complement the theoretical findings.
Key Points
- First runtime analysis of SPEA2 covering the components that handle dominated solutions.
- SPEA2 fails to efficiently cover the OneTrapZeroTrap Pareto front, unlike NSGA-II, NSGA-III, and SMS-EMOA under identical settings.
- Root cause: k-th nearest-neighbor density estimation gives insufficient diversity signals for dominated individuals.
- SPEA2+ uses all pairwise distances and restores performance guarantees comparable to leading algorithms, while retaining SPEA2's performance on simpler problems.