Emergence of Diversity and Its Benefits for Crossover in Genetic Algorithms
Emergence of Diversity and Its Benefits for Crossover in Genetic Algorithms
复制标题
遗传算法中多样性的出现及其对交叉的好处
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Andrew M. Sutton
中科院分区：
文献类型：
--
作者：
D. Dang;T. Friedrich;Timo Kötzing;Martin S. Krejca;P. Lehre;P. S. Oliveto;Dirk Sudholt;Andrew M. Sutton
种群多样性是避免遗传算法早熟收敛和有效利用交叉算子的关键。然而，种群中多样性如何出现的动力学还没有得到很好的理解。我们使用严格的运行时分析来深入了解标准（\（\mu \）+1）GA和\（\mathrm {Jump}_k\）测试函数的种群动态和GA性能。通过研究的随机过程的大小的最大集合相同的基因型，我们表明，交叉的相互作用，然后突变可能作为催化剂，导致突然爆发的多样性。这导致了阶数\（\varOmega（n/\log n）\）的预期优化时间的改进，而不是像（1+1）EA这样的仅变异算法。
Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for a standard (\(\mu \)+1) GA and the \(\mathrm {Jump}_k\) test function. By studying the stochastic process underlying the size of the largest collection of identical genotypes we show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order \(\varOmega (n/\log n)\) compared to mutation-only algorithms like the (1+1) EA.