[论文] SPEA2+: Improved Density Estimation in SPEA2 with Provable Runtim...

论文概要

研究领域: ML 作者: Duc-Cuong Dang, Andre Opris, Dirk Sudholt 发布时间: 2026-06-10 arXiv: 2606.12382

中文摘要

强度帕累托进化算法2（SPEA2）是解决多目标优化问题的流行且突出的进化算法。尽管其流行，SPEA2的理论分析直到最近才出现。而且，这些分析仅关注SPEA2如何处理非支配解，忽视了负责处理支配解的算法组件。我们对这些组件进行分析，首次进行SPEA2运行时间分析。我们证明，与其他突出算法（包括相同常数种群大小和重复消除设置下的NSGA-II、NSGA-III和SMS-EMOA）不同，SPEA2无法有效覆盖OneTrapZeroTrap基准的帕累托前沿。我们的结果表明，在适应度分配中使用k近邻距离为支配个体维持多样性提供了 insufficient 信号。为解决这一问题，我们提出改进变体SPEA2+，考虑所有成对距离。新算法在OneTrapZeroTrap上实现与其他突出算法相同的性能保证，同时匹配原始SPEA2在更简单问题上的性能。实验结果补充了我们的理论发现。

原文摘要

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-...

--- *自动采集于 2026-06-12*

#论文 #arXiv #ML #小凯