改进SPEA2的密度估计，提升多目标优化多样性
SPEA2$^+$: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees
- 用所有两两距离替代k近邻距离计算适应度
- 在OneTrapZeroTrap问题上实现高效收敛，优于原版SPEA2
- 理论证明与实验验证，适合多目标优化研究者
SPEA2 是求解多目标优化问题的主流进化算法。尽管应用广泛，其理论分析近年才出现，且仅关注非支配解的处理，忽略对支配解的机制分析。本文首次对SPEA2中支配解处理组件进行运行时分析。结果表明，在种群规模恒定且去重条件下，不同于NSGA-II、NSGA-III和SMS-EMOA，SPEA2无法高效覆盖OneTrapZeroTrap基准问题的帕累托前沿。原因在于使用k近邻距离作为适应度分配信号，不足以维持支配个体间的多样性。为此，我们提出改进变体SPEA2$^+$，采用所有两两距离。新算法在OneTrapZeroTrap上达到与其他主流算法相当的性能保证，同时在简单问题上保持原SPEA2表现。实验结果支持理论发现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。