多目标优化研究者终于有了 SPEA2 的理论短板分析——原版在支配解处理上存在盲区，SPEA2$^+$ 的改进思路（全距离密度估计）简单有效，做进化算法理论或应用的团队值得关注。
本文首次对 SPEA2 算法中处理支配解的部分进行了运行时分析，发现其在 OneTrapZeroTrap 基准上无法像 NSGA-II 等算法一样高效覆盖帕累托前沿。问题根源在于使用 k 近邻距离进行适应度分配，导致对支配个体的多样性维持不足。为此，作者提出改进版本 SPEA2$^+$，采用所有成对距离进行密度估计，在复杂问题上达到与其他主流算法相同的性能保证，同时在简单问题上保持原算法表现。实验验证了理论分析的正确性。
SPEA2$^+$: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees
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.