Emergence of diversity and its benefits for crossover in genetic algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

  • Duc Cuong Dang
  • Tobias Friedrich
  • Timo Kötzing
  • Martin S. Krejca
  • Pietro S. Oliveto
  • Dirk Sudholt
  • Andrew M. Sutton

Colleges, School and Institutes

External organisations

  • University of Nottingham
  • Hasso Plattner Institute
  • Sheffield University

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 a standard (μ+1) GA and the Jumpk 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 Ω(n/ log n) compared to mutationonly algorithms like the (1+1) EA.

Details

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings
Publication statusPublished - 31 Aug 2016
Event14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom
Duration: 17 Sep 201621 Sep 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9921 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
CountryUnited Kingdom
CityEdinburgh
Period17/09/1621/09/16

Keywords

  • Crossover, Diversity, Genetic algorithms, Runtime analysis, Theory