Escaping local optima using crossover with emergent diversity

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

Research output: Contribution to journalArticlepeer-review

45 Citations (Scopus)
132 Downloads (Pure)

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 run time analysis to gain insight into population dynamics and GA performance for the (μ+1) GA and the Jumpk 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 improvements of the expected optimisation time of order Ω (n/log n) compared to mutation-only algorithms like the (1+1) EA. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to speedups of order Ω(n). Experiments complement our theoretical ndings and further highlight the benets of crossover on Jumpk.
Original languageEnglish
Pages (from-to)484 - 497
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume22
Issue number3
Early online date29 Aug 2017
DOIs
Publication statusPublished - Jun 2018

Keywords

  • genetic algorithms
  • recombination
  • diversity
  • run time 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