SPEA2+: New Algorithm Fixes Diversity Gap in Multi-Objective Optimization

The Strength Pareto Evolutionary Algorithm 2 (SPEA2) is a widely used evolutionary algorithm for multi-objective optimization. Despite its popularity, theoretical analyses have only recently emerged, and they often ignore how SPEA2 handles dominated solutions. A new paper from researchers at the University of Oxford (Dang, Opris, Sudholt) provides the first runtime analysis of SPEA2 that includes these components. They prove that SPEA2 fails to efficiently cover the Pareto front of the OneTrapZeroTrap benchmark when using constant population size and duplicate elimination—a problem not shared by rivals like NSGA-II, NSGA-III, or SMS-EMOA. The root cause: SPEA2's k-th nearest-neighbor distance metric provides an insufficient diversity signal among dominated individuals.

To fix this, the authors propose SPEA2+, which replaces the k-th nearest neighbor with all pairwise distances in the density estimation step. This simple change gives SPEA2+ provable runtime guarantees matching those of NSGA-II and SMS-EMOA on OneTrapZeroTrap, while retaining the original SPEA2's performance on simpler benchmarks. Experimental results confirm the theoretical findings. The work will appear at PPSN 2026 and represents a significant step in making SPEA2's theoretical underpinnings as strong as its practical reputation.