Emergence of diversity and its benefits for crossover in genetic algorithms

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

doi:10.1007/978-3-319-45823-6_83

Emergence of diversity and its benefits for crossover in genetic algorithms

Duc Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto^*, Dirk Sudholt, Andrew M. Sutton

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

13 Citations (Scopus)

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 Jump_k 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
Title of host publication	Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings
Publisher	Springer Verlag
Pages	890-900
Number of pages	11
Volume	9921 LNCS
ISBN (Print)	9783319458229
DOIs	https://doi.org/10.1007/978-3-319-45823-6_83
Publication status	Published - 31 Aug 2016
Event	14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom Duration: 17 Sept 2016 → 21 Sept 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)	03029743
ISSN (Electronic)	16113349

Conference

Conference	14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
Country/Territory	United Kingdom
City	Edinburgh
Period	17/09/16 → 21/09/16

Keywords

Crossover
Diversity
Genetic algorithms
Runtime analysis
Theory

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-45823-6_83

http://eprints.whiterose.ac.uk/101311/

Cite this

Dang, D. C., Friedrich, T., Kötzing, T., Krejca, M. S., Lehre, P. K., Oliveto, P. S., Sudholt, D., & Sutton, A. M. (2016). Emergence of diversity and its benefits for crossover in genetic algorithms. In Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings (Vol. 9921 LNCS, pp. 890-900). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9921 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-45823-6_83

Dang, Duc Cuong ; Friedrich, Tobias ; Kötzing, Timo et al. / Emergence of diversity and its benefits for crossover in genetic algorithms. Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. Vol. 9921 LNCS Springer Verlag, 2016. pp. 890-900 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e41fe782b28b4180872170487a48e68c,

title = "Emergence of diversity and its benefits for crossover in genetic algorithms",

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

keywords = "Crossover, Diversity, Genetic algorithms, Runtime analysis, Theory",

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

year = "2016",

month = aug,

day = "31",

doi = "10.1007/978-3-319-45823-6_83",

language = "English",

isbn = "9783319458229",

volume = "9921 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "890--900",

booktitle = "Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings",

note = "14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 ; Conference date: 17-09-2016 Through 21-09-2016",

}

Dang, DC, Friedrich, T, Kötzing, T, Krejca, MS, Lehre, PK, Oliveto, PS, Sudholt, D & Sutton, AM 2016, Emergence of diversity and its benefits for crossover in genetic algorithms. in Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. vol. 9921 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9921 LNCS, Springer Verlag, pp. 890-900, 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016, Edinburgh, United Kingdom, 17/09/16. https://doi.org/10.1007/978-3-319-45823-6_83

Emergence of diversity and its benefits for crossover in genetic algorithms. / Dang, Duc Cuong; Friedrich, Tobias; Kötzing, Timo et al.
Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. Vol. 9921 LNCS Springer Verlag, 2016. p. 890-900 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9921 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Emergence of diversity and its benefits for crossover in genetic algorithms

AU - Dang, Duc Cuong

AU - Friedrich, Tobias

AU - Kötzing, Timo

AU - Krejca, Martin S.

AU - Lehre, Per Kristian

AU - Oliveto, Pietro S.

AU - Sudholt, Dirk

AU - Sutton, Andrew M.

PY - 2016/8/31

Y1 - 2016/8/31

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

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

KW - Crossover

KW - Diversity

KW - Genetic algorithms

KW - Runtime analysis

KW - Theory

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

U2 - 10.1007/978-3-319-45823-6_83

DO - 10.1007/978-3-319-45823-6_83

M3 - Conference contribution

AN - SCOPUS:84988514114

SN - 9783319458229

VL - 9921 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 890

EP - 900

BT - Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings

PB - Springer Verlag

T2 - 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016

Y2 - 17 September 2016 through 21 September 2016

ER -

Dang DC, Friedrich T, Kötzing T, Krejca MS, Lehre PK, Oliveto PS et al. Emergence of diversity and its benefits for crossover in genetic algorithms. In Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. Vol. 9921 LNCS. Springer Verlag. 2016. p. 890-900. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-45823-6_83

Emergence of diversity and its benefits for crossover in genetic algorithms

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this