SPEA2$^+$: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees
2026-06-10 • Neural and Evolutionary Computing
Neural and Evolutionary ComputingArtificial Intelligence
AI summaryⓘ
The authors studied SPEA2, a popular algorithm for solving problems with multiple goals, and found that its way of handling less important solutions doesn't work well on a specific test problem called OneTrapZeroTrap. They showed that SPEA2 can't efficiently find all the best trade-offs because it uses a limited method to keep diverse solutions. To fix this, the authors created an improved version called SPEA2+, which looks at all distances between solutions rather than just the nearest ones. SPEA2+ performs better on challenging problems while keeping up with the original on simpler ones. They backed up their theory with experiments.
SPEA2multi-objective optimisationPareto frontruntime analysisdominated solutionsdiversity preservationk-th nearest neighbourOneTrapZeroTrap benchmarkevolutionary algorithmsfitness assignment
Authors
Duc-Cuong Dang, Andre Opris, Dirk Sudholt
Abstract
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.