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

Researchers present SPEA2+, an improved variant of the Strength Pareto Evolutionary Algorithm 2 that addresses limitations in handling dominated solutions during multi-objective optimization. The original SPEA2 struggles with diversity maintenance compared to competing algorithms, a problem solved by replacing k-th nearest-neighbor distance metrics with all-pairwise distance calculations.

This research addresses a fundamental gap in the theoretical understanding of SPEA2, one of the most widely adopted evolutionary algorithms for multi-objective optimization problems. While SPEA2 has enjoyed substantial practical success since its introduction, theoretical runtime analyses have historically focused only on non-dominated solution management, leaving a blind spot regarding how the algorithm handles dominated individuals. The researchers' runtime analysis reveals a critical weakness: SPEA2's fitness assignment mechanism, which relies on k-th nearest-neighbor distance measurements, fails to maintain adequate diversity among dominated solutions when tackling complex optimization landscapes like OneTrapZeroTrap.

The distinction matters because dominated solutions serve as stepping stones toward discovering the true Pareto front—the set of optimal trade-offs between competing objectives. By providing insufficient diversity signals for these intermediate solutions, SPEA2 becomes inefficient at exploring the solution space compared to algorithms like NSGA-II and SMS-EMOA under identical experimental conditions. The proposed SPEA2+ variant remedies this by evaluating all pairwise distances rather than relying on the k-th nearest-neighbor heuristic, effectively improving the algorithm's capacity to explore and maintain healthy population diversity throughout the evolutionary process.

For practitioners in optimization-heavy fields—operations research, engineering design, machine learning hyperparameter tuning—this work validates existing empirical suspicions while providing theoretical proof that algorithm design choices have measurable consequences. Organizations currently deploying SPEA2 may benefit from transitioning to SPEA2+ for complex problems, though the improved variant maintains backward compatibility on simpler optimization tasks. The research demonstrates how rigorous theoretical analysis can identify and systematically address algorithmic weaknesses without requiring complete algorithmic redesign.

• →SPEA2's k-th nearest-neighbor fitness assignment provides insufficient diversity signals for dominated solutions on complex optimization problems
• →SPEA2+ uses all-pairwise distance calculations to improve diversity maintenance and match performance of competing algorithms like NSGA-II
• →Original SPEA2 struggles with Pareto front coverage on benchmark problems where NSGA-II and SMS-EMOA succeed
• →Theoretical runtime analysis reveals previously unexamined algorithmic components responsible for handling dominated individuals
• →Improved variant maintains compatibility with original SPEA2 performance on simpler optimization landscapes