论文标题
对多模式目标的多目标进化算法的理论分析
Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives
论文作者
论文摘要
对MOEAS的理论理解远远落后于他们在实践中的成功。特别是，以前的理论工作认为大多数由单峰目标组成的简单问题。 为了深入了解进化算法如何解决多模式的多座问题，我们提出了OJZJ问题，这是一个双向目标问题，这是经典跳跃功能基准的两个目标。我们证明，无论运行时如何，SEMO的概率都不会计算完整的帕累托阵线。相比之下，对于所有问题尺寸$ n $和所有跳跃尺寸$ {k \ in [4 .. \ frac n2-1]} $，全局semo（gsemo）覆盖了帕累托阵线，预期的$θ（（n -2k）n^{k}）$迭代。对于$ k = o（n）$，我们还显示了更紧密的绑定$ \ frac 32 e n^{k+1} \ pm o（n^{k+1}）$，这可能是第一个绑定的MOEA的运行时，该运行时间与低阶项分开。我们还将GSEMO与两种显示单目标多模式问题的优势相结合。当将GSEMO与重尾突变操作员一起使用时，预期的运行时至少提高了至少$ k^{ω（k）} $。当将Rajabi和Witt（2022）的最近停滞检测策略改编成Gsemo时，预期的运行时也提高了至少$ k^{ω（k）} $的倍数，并超过了$ k $中的小型多项元素的重尾GSEMO。通过实验分析，我们表明，这些渐近差异已经可以看到小问题的大小可见：一个因子 - $ 5 $ $ 5 $从重尾突变中加速，并且可以观察到$ 4 $ $ 4 $的停滞检测的$ 10 $加速，并且问题尺寸在$ 4 $之间，并且在$ 10 $ $ 10 $之间。总体而言，我们的结果表明，最近开发的思想是为了帮助应对本地Optima的单目标进化算法，也可以有效地用于多目标优化。
The theoretical understanding of MOEAs is lagging far behind their success in practice. In particular, previous theory work considers mostly easy problems that are composed of unimodal objectives. As a first step towards a deeper understanding of how evolutionary algorithms solve multimodal multiobjective problems, we propose the OJZJ problem, a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark. We prove that SEMO with probability one does not compute the full Pareto front, regardless of the runtime. In contrast, for all problem sizes $n$ and all jump sizes ${k \in [4..\frac n2 - 1]}$, the global SEMO (GSEMO) covers the Pareto front in an expected number of $Θ((n-2k)n^{k})$ iterations. For $k = o(n)$, we also show the tighter bound $\frac 32 e n^{k+1} \pm o(n^{k+1})$, which might be the first runtime bound for an MOEA that is tight apart from lower-order terms. We also combine the GSEMO with two approaches that showed advantages in single-objective multimodal problems. When using the GSEMO with a heavy-tailed mutation operator, the expected runtime improves by a factor of at least $k^{Ω(k)}$. When adapting the recent stagnation-detection strategy of Rajabi and Witt (2022) to the GSEMO, the expected runtime also improves by a factor of at least $k^{Ω(k)}$ and surpasses the heavy-tailed GSEMO by a small polynomial factor in $k$. Via an experimental analysis, we show that these asymptotic differences are visible already for small problem sizes: A factor-$5$ speed-up from heavy-tailed mutation and a factor-$10$ speed-up from stagnation detection can be observed already for jump size~$4$ and problem sizes between $10$ and $50$. Overall, our results show that the ideas recently developed to aid single-objective evolutionary algorithms to cope with local optima can be effectively employed also in multiobjective optimization.
