arXiv:2505.01647v1 宣布类型: cross 摘要: 与单目标进化算法不同，在单目标进化算法中，非精英主义是一个已确立的概念，多目标进化算法几乎总是以贪婪的方式选择下一代种群。唯一的例外是Bian, Zhou, Li, and Qian (IJCAI 2023)提出了SMS-EMOA的一种随机选择机制，并证明它可以将具有问题规模$n$和间隔参数$k$的双目标跳跃基准 Pareto 前沿的计算速度提升一个因子$\max\{1, 2^{k/4}/n\}$。虽然这是非精英选择首次被证明可以提升计算速度，这表明了一种非常有趣的研究方向，但需要注意的是，真正的加速只发生在$k \ge 4\log_2(n)$时，此时运行时间是超多项式的，并且随着时间目标数量的增加，优势会减弱，如后来的工作所示。在本文中，我们提出了一种基于年龄的不同非精英选择机制，该机制免除了年轻于某一定年龄的个体被移除的可能性。这纠正了随机选择的两个不足之处：我们证明了运行速度可以获得一个因子$\max\{1,\Theta(k)^{k-1}\}$的提升，而与目标数量无关。特别是，当$k$为常数时，这是唯一可以观察到多项式运行时间的设置，这种情况下的积极加速已经可以观察到。总体而言，这项结果支持非精英选择方案的使用，但表明基于年龄的机制比随机选择机制可能更为强大。