On the Benefits of Populations for the Exploitation Speed of Standard Steady-State Genetic Algorithms
On the Benefits of Populations for the Exploitation Speed of Standard Steady-State Genetic Algorithms
复制标题
论种群对标准稳态遗传算法开发速度的好处
DOI：
10.1007/s00453-020-00743-1
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Corus D
中科院分区：
文献类型：
--
作者：
Corus D
人们普遍认为，人口是有用的多模态优化问题的全球探索。事实上，有几个理论结果表明，这种优势比单轨迹搜索算法。在本文中，我们提供的证据表明，不断发展的人口通过交叉和变异也可能有利于优化时间爬山单峰函数。特别是，我们证明了OneMax的标准（µ+1）GA的预期运行时间的界限低于其一元黑盒复杂度，并且随着人口规模的增加，前导常数减少[MATH HERE]。我们的分析表明，最佳突变策略是在大多数情况下翻转两位。为了实现这一结果，我们提供了两个有趣的贡献随机搜索算法的理论：1）漂移分析的一个新的应用，比较吸收时间的不同马尔可夫链，而不定义一个明确的潜在功能。2)利用基本矩阵的求逆来计算马尔可夫链的吸收时间。后一种策略是以前提出的文献，但据我们所知，这是第一次被用来显示非平凡的预期运行时的界限。
It is generally accepted that populations are useful for the global exploration of multi-modal optimisation problems. Indeed, several theoretical results are available showing such advantages over single-trajectory search heuristics. In this paper we provide evidence that evolving populations via crossover and mutation may also benefit the optimisation time for hillclimbing unimodal functions. In particular, we prove bounds on the expected runtime of the standard (µ+1) GA for OneMax that are lower than its unary black box complexity and decrease in the leading constant with the population size up to [MATH HERE]. Our analysis suggests that the optimal mutation strategy is to flip two bits most of the time. To achieve the results we provide two interesting contributions to the theory of randomised search heuristics: 1) A novel application of drift analysis which compares absorption times of different Markov chains without defining an explicit potential function. 2) The inversion of fundamental matrices to calculate the absorption times of the Markov chains. The latter strategy was previously proposed in the literature but to the best of our knowledge this is the first time is has been used to show non-trivial bounds on expected runtimes.