提出基于年龄的非精英选择策略，显著提升多目标优化算法速度。
Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy
- 引入个体年龄机制，年轻个体免于淘汰
- 速度提升因子达 Θ(k)^{k-1}，与目标数无关
- 适用于常数 k 时仍有效，适合高维优化场景
与单目标进化算法中非精英策略已成常态不同，多目标进化算法几乎总是采用贪婪方式选择下一代。唯一例外是 Bian 等人（IJCAI 2023）提出的 SMS-EMOA 随机选择机制，证明其可在双目标跳跃基准上将运行时间缩短至原时间的 $\max\{1,2^{k/4}/n\}$ 倍。然而，该加速仅在 $k \ge 4\log_2(n)$ 时成立，且为超多项式时间；此外，后续研究显示其优势随目标数增加而减弱。本文提出一种基于年龄的非精英选择机制：个体若年龄小于阈值，则免于被移除。该方法克服了上述两个缺陷，证明可实现 $\max\{1,Θ(k)^{k-1}\}$ 的速度提升，且不受目标数影响。尤其在常数 $k$ 下即可获得正向加速，此时运行时间为多项式。结果表明，基于年龄的非精英机制比随机选择更强大，支持其在多目标优化中的应用。
原文摘要 · Abstract (English)
Different from single-objective evolutionary algorithms, where non-elitism is an established concept, multi-objective evolutionary algorithms almost always select the next population in a greedy fashion. In the only notable exception, Bian, Zhou, Li, and Qian (IJCAI 2023) proposed a stochastic selection mechanism for the SMS-EMOA and proved that it can speed up computing the Pareto front of the bi-objective jump benchmark with problem size $n$ and gap parameter $k$ by a factor of $\max\{1,2^{k/4}/n\}$. While this constitutes the first proven speed-up from non-elitist selection, suggesting a very interesting research direction, it has to be noted that a true speed-up only occurs for $k \ge 4\log_2(n)$, where the runtime is super-polynomial, and that the advantage reduces for larger numbers of objectives as shown in a later work. In this work, we propose a different non-elitist selection mechanism based on aging, which exempts individuals younger than a certain age from a possible removal. This remedies the two shortcomings of stochastic selection: We prove a speed-up by a factor of $\max\{1,Θ(k)^{k-1}\}$, regardless of the number of objectives. In particular, a positive speed-up can already be observed for constant $k$, the only setting for which polynomial runtimes can be witnessed. Overall, this result supports the use of non-elitist selection schemes, but suggests that aging-based mechanisms can be considerably more powerful than stochastic selection mechanisms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。