Escaping Local Optima Using Crossover with Emergent Diversity

Duc Cuong Dang, Tobias Friedrich, Timo Kotzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, Andrew M. Sutton

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

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 (μ + 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.

Original languageEnglish (US)
Pages (from-to)484-497
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume22
Issue number3
DOIs
StatePublished - Jun 2018

Bibliographical note

Funding Information:
Manuscript received August 26, 2016; revised January 16, 2017 and May 4, 2017; accepted June 20, 2017. Date of publication August 29, 2017; date of current version May 25, 2018. This work was supported in part by the European Union Seventh Framework Programme (FP7/2007–2013) under Grant 618091 (SAGE), in part by the EPSRC under Grant EP/M004252/1, and in part by the COST Action through the European Cooperation in Science and Technology under Grant CA15140 [Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice (ImAppNIO)]. (Corresponding author: Per Kristian Lehre.) D.-C. Dang is with the ASAP Research Group, School of Computer Science, University of Nottingham, Nottingham NG81BB, U.K.

Funding Information:
Ideas leading to this work were discussed at Dagstuhl seminar 16011 "Evolution and Computing." This work was supported in part by the European Union Seventh Framework Programme (FP7/2007-2013) under Grant 618091 (SAGE), in part by the EPSRC under Grant EP/M004252/1, and in part by the COST Action through the European Cooperation in Science and Technology under Grant CA15140 [Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice (ImAppNIO)].

Publisher Copyright:
© 2018 IEEE.

Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

Keywords

  • Diversity
  • genetic algorithms (GAs)
  • recombination
  • runtime analysis
  • theory

Fingerprint Dive into the research topics of 'Escaping Local Optima Using Crossover with Emergent Diversity'. Together they form a unique fingerprint.

Cite this