Emergence of diversity and its benefits for crossover in genetic algorithms

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

Standard

Emergence of diversity and its benefits for crossover in genetic algorithms. / Dang, Duc Cuong; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M.

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 proceedingConference contribution

Harvard

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

APA

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

Vancouver

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)). https://doi.org/10.1007/978-3-319-45823-6_83

Author

Dang, Duc Cuong ; Friedrich, Tobias ; Kötzing, Timo ; Krejca, Martin S. ; Lehre, Per Kristian ; Oliveto, Pietro S. ; Sudholt, Dirk ; Sutton, Andrew M. / 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)).

Bibtex

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

}

RIS

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 -