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.
Original language | English (US) |
---|---|
Title of host publication | Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings |
Editors | Emma Hart, Ben Paechter, Julia Handl, Manuel López-Ibáñez, Peter R. Lewis, Gabriela Ochoa |
Publisher | Springer Verlag |
Pages | 890-900 |
Number of pages | 11 |
ISBN (Print) | 9783319458229 |
DOIs | |
State | Published - 2016 |
Externally published | Yes |
Event | 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom Duration: Sep 17 2016 → Sep 21 2016 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 9921 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Other
Other | 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 |
---|---|
Country/Territory | United Kingdom |
City | Edinburgh |
Period | 9/17/16 → 9/21/16 |
Bibliographical note
Publisher Copyright:© Springer International Publishing AG 2016.
Keywords
- Crossover
- Diversity
- Genetic algorithms
- Runtime analysis
- Theory