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

doi:10.1109/TEVC.2017.2724201

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

Computer Science (Duluth)

Research output: Contribution to journal › Article › peer-review

108 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 language	English (US)
Pages (from-to)	484-497
Number of pages	14
Journal	IEEE Transactions on Evolutionary Computation
Volume	22
Issue number	3
DOIs	https://doi.org/10.1109/TEVC.2017.2724201
State	Published - 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.

Keywords

Diversity
genetic algorithms (GAs)
recombination
runtime analysis
theory

Publisher link

10.1109/TEVC.2017.2724201

http://eprints.whiterose.ac.uk/118392/7/08019856.pdf

Find It

Find It at U of M Libraries

Cite this

@article{a81a8b4f157f44e38d720fe10a4e4f66,

title = "Escaping Local Optima Using Crossover with Emergent Diversity",

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.",

keywords = "Diversity, genetic algorithms (GAs), recombination, runtime analysis, theory",

author = "Dang, {Duc Cuong} and Tobias Friedrich and Timo Kotzing and Krejca, {Martin S.} and Lehre, {Per Kristian} and Oliveto, {Pietro S.} and Dirk Sudholt and Sutton, {Andrew M.}",

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: {\textcopyright} 2018 IEEE.",

year = "2018",

month = jun,

doi = "10.1109/TEVC.2017.2724201",

language = "English (US)",

volume = "22",

pages = "484--497",

journal = "IEEE Transactions on Evolutionary Computation",

issn = "1089-778X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Escaping Local Optima Using Crossover with Emergent Diversity

AU - Dang, Duc Cuong

AU - Friedrich, Tobias

AU - Kotzing, Timo

AU - Krejca, Martin S.

AU - Lehre, Per Kristian

AU - Oliveto, Pietro S.

AU - Sudholt, Dirk

AU - Sutton, Andrew M.

N1 - 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.

PY - 2018/6

Y1 - 2018/6

N2 - 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.

AB - 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.

KW - Diversity

KW - genetic algorithms (GAs)

KW - recombination

KW - runtime analysis

KW - theory

UR - http://www.scopus.com/inward/record.url?scp=85028699580&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028699580&partnerID=8YFLogxK

U2 - 10.1109/TEVC.2017.2724201

DO - 10.1109/TEVC.2017.2724201

M3 - Article

AN - SCOPUS:85028699580

SN - 1089-778X

VL - 22

SP - 484

EP - 497

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

IS - 3

ER -

Escaping Local Optima Using Crossover with Emergent Diversity

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this