Escaping Local Optima Using Crossover With Emergent Diversity
Escaping Local Optima Using Crossover With Emergent Diversity
复制标题
DOI：
10.1109/tevc.2017.2724201
复制
发表时间：
2018-08-01
影响因子：
14.3
通讯作者：
Sutton, Andrew M.
中科院分区：
文献类型：
--
作者：
Dang, Duc-Cuong;Friedrich, Tobias;Sutton, Andrew M.
种群多样性是遗传算法避免过早收敛和有效利用交叉的关键。然而，多样性如何在种群中出现的动态还没有得到很好的理解。我们使用严格的运行时分析来深入了解（mu + 1）遗传算法和Jump测试函数的种群动态和遗传性能。我们表明，交叉之后的突变的相互作用可能是导致多样性突然爆发的催化剂。与（1 + 1）进化算法等仅突变的算法相比，这可以显著改善预期优化时间。此外，将突变率增加一个任意小的常数因子可以促进多样性的产生，从而导致更大的加速。通过实验来补充我们的理论发现，并进一步强调跨界对功能类的好处。
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 the (mu + 1) GA and the Jump test function. 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 significant improvements of the expected optimization time compared to mutation-only algorithms like the (1 + 1) evolutionary algorithm. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to even larger speedups. Experiments were conducted to complement our theoretical findings and further highlight the benefits of crossover on the function class.