在广泛使用的进化多目标算法优于简单算法的情况下，对函数运行时间的分析

《ACM Transactions on Evolutionary Learning and Optimization》：Runtime Analysis of Functions Where Widely-Used Evolutionary Multi-Objective Algorithms Beat Simple Ones

多目标优化算法的运行时间分析表明，(G)SEMO在Pareto-sparse问题上效率低下，而NSGA-II/III/SMS-EMOA通过多样性机制实现O(n log n)的期望计算量。实验验证了理论结论，揭示了算法关键组件的重要性。

　　

摘要

在进化多目标优化中，运行时间分析用于研究进化多目标算法（EMOAs）覆盖帕累托前沿的（预期）时间。最近，这种分析方法已被应用于NSGA-II、NSGA-III和SMS-EMOA算法。然而，大多数分析表明，这些广泛使用的算法的运行时间保证与最简单的EMOA算法（G）SEMO相同。据我们所知，没有运行时间分析能够证明某种流行的EMOA算法在确定性问题上优于（G）SEMO。

我们提出了一些问题来说明流行EMOA算法相对于（G）SEMO的优越性。我们引入了一种多目标问题的分类方法，并识别出所谓的$a$和$b$-帕累托稀疏问题，这类问题对于（G）SEMO来说较为困难，因为帕累托最优解之间的距离较大。我们已经证明了一个关于（G）SEMO解决任何$a$、$b$-帕累托稀疏问题的期望适应度评估次数的通用下界。在许多示例问题上，这个下界为$n^{\Omega \left(n\right)}$：OneTrapZeroTrap（Trap函数在两个目标情况下的推广）、具有较大间隙参数的OneJumpZeroJump类，以及一类称为OneZeroCountSat的双目标MaxSat实例。因此，（G）SEMO在所有这些问题上的表现都较差。

相反，我们证明了三种流行的EMO算法——NSGA-II、NSGA-III和SMS-EMOA——在加入了避免基因型重复的简单多样性机制后，其效率大大提高，它们在期望中仅需$O(nlog?n)$次适应度评估即可完成优化。在OneTrapZeroTrap和OneZeroCountSat上的实验结果证实了我们的理论预测：（G）SEMO总是失败，而其他算法总是成功。我们的分析揭示了这些复杂算法中关键组件的重要性，并有助于更好地理解它们的能力。