Evolutionary Algorithms (EAs) have become the most popular tool for solving widely-existed multi-objective optimization problems. In Multi-Objective EAs (MOEAs), there is increasing interest in using an archive to store non-dominated solutions generated during the search. This approach can 1) mitigate the effects of population oscillation, a common issue in many MOEAs, and 2) allow for the use of smaller, more practical population sizes. In this paper, we analytically show that the archive can even further help MOEAs through reusing its solutions during the process of new solution generation. We first prove that using a small population size alongside an archive (without incorporating archived solutions in the generation process) may fail on certain problems, as the population may remove previously discovered but promising solutions. We then prove that reusing archive solutions can overcome this limitation, resulting in at least a polynomial speedup on the expected running time. Our analysis focuses on the well-established SMS-EMOA algorithm applied to the commonly studied OneJumpZeroJump problem as well as one of its variants. We also show that reusing archive solutions can be better than using a large population size directly. Finally, we show that our theoretical findings can generally hold in practice by experiments on well-known practical optimization problems -- multi-objective 0-1 Knapsack, TSP, QAP and NK-landscape problems -- with realistic settings.

翻译：进化算法已成为解决广泛存在的多目标优化问题最流行的工具。在多目标进化算法中，利用存档存储搜索过程中产生的非支配解日益受到关注。该方法能够：1）缓解许多MOEA中常见的种群振荡效应；2）允许使用更小、更实用的种群规模。本文通过理论分析证明，在新解生成过程中重用存档解能进一步帮助MOEA。我们首先证明，仅使用小规模种群配合存档（未在生成过程中利用存档解）可能在某些问题上失效，因为种群可能丢弃先前发现但具有潜力的解。随后证明重用存档解可突破此限制，在期望运行时间上至少实现多项式级加速。我们的分析聚焦于经典SMS-EMOA算法在广泛研究的OneJumpZeroJump问题及其变体上的表现。同时证明，重用存档解可能优于直接使用大规模种群。最后，通过对多目标0-1背包、TSP、QAP和NK-landscape等经典实际优化问题在现实参数设置下的实验，验证了理论结论的普适性。