An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms

在多目标进化算法（MOEAs）领域，使用档案存储搜索过程中生成的非支配解的趋势正在增加。原因是：1）MOEAs很容易最终得到包含被其他被丢弃的解支配的劣解的种群；2）具有问题帕累托前沿大小的种群通常不切实际。在本文中，我们首次从理论上证明使用档案可以保证MOEAs的加速。具体而言，我们证明了对于两种广泛研究的问题（OneMinMax和LeadingOnesTrailingZeroes）上的两种成熟MOEAs（NSGA-II和SMS-EMOA），使用档案可以带来期望运行时间的多项式加速。原因是使用档案后，种群的大小可以减小到一个小常数；不需要保留所有找到的帕累托最优解。这与现有MOEAs的理论研究形成对比，现有研究需要具有问题帕累托前沿大小的种群。本文的研究结果不仅为MOEAs设计中越来越流行的实践提供了理论证明，而且对理论界研究更实际的MOEAs也有益处。

论文验证使用存档可以加速多目标进化算法（MOEAs）的运行时间，解决MOEAs在寻找Pareto最优解时可能遗漏优秀解的问题。

论文证明使用存档可以将MOEAs的期望运行时间加速为多项式级别，因为存档可以将种群大小降至一个小常数，而不需要保留所有Pareto最优解。

论文使用两个常见问题和两个流行算法进行实验，证明了使用存档可以加速MOEAs的运行时间。此外，论文提供了实用的MOEAs设计建议，也为理论研究提供了新的思路。

近期相关研究包括“An Efficient Multi-Objective Evolutionary Algorithm Based on Decomposition for Large-Scale Optimization”和“Multi-Objective Evolutionary Algorithms: A Survey of the State of the Art”。