标题： 随机种群更新在进化多目标优化中确实需要一个存档 显示英文标题

标题： Stochastic Population Update Provably Needs An Archive in Evolutionary Multi-objective Optimization

摘要： 进化算法（EAs）由于其基于种群的搜索特性，已被广泛应用于多目标优化。 种群更新是多目标进化算法（MOEAs）中的一个关键组件，通常以贪婪和确定性的方式进行。 然而，最近的研究对这种做法提出了质疑，并表明允许劣解有机会被保留的随机种群更新（SPU）可以帮助MOEAs更容易地跳出局部最优。 虽然在种群更新过程中引入随机性可以增强MOEAs的探索能力，但存在一个缺点，即种群可能无法始终保留找到的最佳解，从而需要较大的种群。 直觉上，解决这个问题的一个可能方法是引入一个存档，用于存储迄今为止找到的最佳解。 在本文中，我们从理论上证明，使用存档可以使小种群并显著加速基于SPU的MOEAs的搜索。 具体来说，我们分析了两种广为认可的MOEAs，SMS-EMOA和NSGA-II，在解决一个常被研究的双目标问题OneJumpZeroJump时的期望运行时间，并证明使用存档可以带来（甚至指数级）的加速。 SMS-EMOA和NSGA-II之间的比较还表明，$(\mu+\mu)$更新模式可能比$(\mu+1)$更新模式更适合SPU。 此外，我们推导的仅使用SPU的运行时间界限明显比之前已知的更紧。 我们的理论发现也在一个著名的实际问题——多目标旅行商问题上得到了实证验证。 我们希望这项工作能为探索进化多目标优化中设计算法的不同思路提供理论支持。 显示英文摘要

摘要： Evolutionary algorithms (EAs) have been widely applied to multi-objective optimization, due to their nature of population-based search. Population update, a key component in multi-objective EAs (MOEAs), is usually performed in a greedy, deterministic manner. However, recent studies have questioned this practice and shown that stochastic population update (SPU), which allows inferior solutions have a chance to be preserved, can help MOEAs jump out of local optima more easily. While introducing randomness in the population update process boosts the exploration of MOEAs, there is a drawback that the population may not always preserve the very best solutions found, thus entailing a large population. Intuitively, a possible solution to this issue is to introduce an archive that stores the best solutions ever found. In this paper, we theoretically show that using an archive can allow a small population and accelerate the search of SPU-based MOEAs substantially. Specifically, we analyze the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II, with SPU for solving a commonly studied bi-objective problem OneJumpZeroJump, and prove that using an archive can bring (even exponential) speedups. The comparison between SMS-EMOA and NSGA-II also suggests that the $(\mu+\mu)$ update mode may be more suitable for SPU than the $(\mu+1)$ update mode. Furthermore, our derived running time bounds for using SPU alone are significantly tighter than previously known ones. Our theoretical findings are also empirically validated on a well-known practical problem, the multi-objective traveling salesperson problem. We hope this work may provide theoretical support to explore different ideas of designing algorithms in evolutionary multi-objective optimization.