Standard Steady State Genetic Algorithms Can Hillclimb Faster Than Mutation-Only Evolutionary Algorithms
Standard Steady State Genetic Algorithms Can Hillclimb Faster Than Mutation-Only Evolutionary Algorithms
复制标题
DOI：
10.1109/tevc.2017.2745715
复制
发表时间：
2018-10-01
影响因子：
14.3
通讯作者：
Oliveto, Pietro S.
中科院分区：
文献类型：
--
作者：
Corus, Dogan;Oliveto, Pietro S.
解释遗传算法的真实的能力在多大程度上取决于交叉将个体重组成更高质量解的能力是进化计算中的一个重要问题。在本文中，我们将展示如何变异和交叉之间的相互作用，可以使气体爬山速度比他们的突变只有同行。我们设计了一个马尔可夫链框架，允许严格证明上界的运行时间的标准稳态气体爬山的ONEMAX功能。的界限建立，稳态气体是25%的速度比所有标准的位变异的进化算法与静态突变率为低阶项的适度人口规模。分析还表明，较大的种群可能比大小为2的种群更快。我们提出了一个贪婪的（2 + 1）GA匹配的上限大于2的人口的下限，严格证明了两个人不能超过更大的人口规模下贪婪的选择和贪婪的交叉低阶条款。在互补实验中，最佳的人口规模大于2和贪婪的GA比标准的更快，进一步表明导出的下限也适用于标准的稳态（2 + 1）GA。
Explaining to what extent the real power of genetic algorithms (GAs) lies in the ability of crossover to recombine individuals into higher quality solutions is an important problem in evolutionary computation. In this paper we show how the interplay between mutation and crossover can make GAs hillclimb faster than their mutation-only counterparts. We devise a Markov chain framework that allows to rigorously prove an upper bound on the runtime of standard steady state GAs to hillclimb the ONEMAX function. The bound establishes that the steady-state GAs are 25% faster than all standard bit mutation-only evolutionary algorithms with static mutation rate up to lower order terms for moderate population sizes. The analysis also suggests that larger populations may be faster than populations of size 2. We present a lower bound for a greedy (2 + 1) GA that matches the upper bound for populations larger than 2, rigorously proving that two individuals cannot outperform larger population sizes under greedy selection and greedy crossover up to lower order terms. In complementary experiments the best population size is greater than 2 and the greedy GAs are faster than standard ones, further suggesting that the derived lower bound also holds for the standard steady state (2 + 1) GA.