research-article

Open access

Escaping Local Optima with Diversity Mechanisms and Crossover

Authors:

Duc-Cuong Dang,

Tobias Friedrich,

Martin S. Krejca,

Per Kristian Lehre,

Pietro S. Oliveto,

Andrew M. SuttonAuthors Info & Claims

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Pages 645 - 652

https://doi.org/10.1145/2908812.2908956

Published: 20 July 2016 Publication History

Abstract

Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jump_k. All previous results in this context only hold for unrealistically low crossover probability p_c=O(k/n), while we give analyses for the setting of constant p_c < 1 in all but one case. Our bounds show a dependence on the problem size~$n$, the jump length k, the population size μ, and the crossover probability p_c. For the typical case of constant k > 2 and constant p_c, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ:

O}(n^k-1) for duplicate elimination/minimisation,

O}(n² log n) for maximising the convex hull,

O(n log n) for det. crowding (assuming p_c = k/n),

O(n log n) for maximising the Hamming distance,

O(n log n) for fitness sharing,

O(n log n) for the single-receiver island model.

This proves a sizeable advantage of all variants of the (μ+1) GA compared to the (1+1) EA, which requires θ(n^k). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.

References

[1]

E. Alfaro-Cid, J. J. M. Guervós, F. F. de Vega, A. I. Esparcia-Alcázar, and K. Sharman. Bloat control operators and diversity in genetic programming: A comparative study. Evol. Comput. Journal, 18: 305--332, 2010.

Digital Library

[2]

J. Arabas. Approximating the genetic diversity of populations in the quasi-equilibrium state. IEEE Trans. Evol. Comput., 16: 632--644, 2012.

Digital Library

[3]

G. Bell. The masterpiece of nature the evolution and genetics of sexuality. 1982.

[4]

E. K. Burke, S. M. Gustafson, and G. Kendall. Diversity in genetic programming: an analysis of measures and correlation with fitness. IEEE Trans. Evol. Comput., 8: 47--62, 2004.

Digital Library

[5]

N. Chaiyaratana, T. Piroonratana, and N. Sangkawelert. Effects of diversity control in single-objective and multi-objective genetic algorithms. J. Heuristics, 13: 1--34, 2007.

Digital Library

[6]

B. Doerr and L. A. Goldberg. Adaptive drift analysis. Algorithmica, 65: 224--250, 2013.

Digital Library

[7]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. Algorithmica, 64: 673--697, 2012.

Digital Library

[8]

T. Friedrich, P. S. Oliveto, D. Sudholt, and C. Witt. Analysis of diversity-preserving mechanisms for global exploration. Evol. Comput. Journal, 17: 455--476, 2009.

Digital Library

[9]

W. Gao and F. Neumann. Runtime analysis for maximizing population diversity in single-objective optimization. In Proc. of GECCO '14, pp. 777--784, 2014.

Digital Library

[10]

J. He and X. Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3: 21--35, 2004.

Digital Library

[11]

T. Jansen and I. Wegener. The Analysis of Evolutionary Algorithms - a Proof That Crossover really can help. Algorithmica, 34: 47--66, 2002.

Digital Library

[12]

T. Kötzing, D. Sudholt, and M. Theile. How crossover helps in pseudo-boolean optimization. In Proc. of GECCO '11, pp. 989--996, 2011.

Digital Library

[13]

A. Moraglio and D. Sudholt. Runtime analysis of convex evolutionary search. In Proc. of GECCO '12, pp. 649--656, 2012.

Digital Library

[14]

F. Neumann, P. S. Oliveto, G. Rudolph, and D. Sudholt. On the effectiveness of crossover for migration in parallel evolutionary algorithms. In Proc. of GECCO '11, pp. 1587--1594, 2011.

Digital Library

[15]

R. K. Ursem. Diversity-guided evolutionary algorithms. In Proc. of PPSN VII, pp. 462--474, 2002.

Digital Library

[16]

R. A. Watson and T. Jansen. A building-block royal road where crossover is provably essential. In Proc. of GECCO '07, pp. 1452--1459, 2007.

Digital Library

[17]

C. Witt. Runtime Analysis of the (μ + 1) EA on Simple Pseudo-Boolean Functions. Evol. Comput. Journal, 14: 65--86, 2006.

Digital Library

Cited By

Sudholt DSquillero GLi XHandl J(2024)Theory and Practice of Population Diversity in Evolutionary ComputationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648430(1391-1409)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648430
Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Bajpai PBansal J(2024)Voronoi Tessellations based Simple OptimizerInformation Sciences10.1016/j.ins.2024.120795(120795)Online publication date: May-2024
https://doi.org/10.1016/j.ins.2024.120795
Show More Cited By

Index Terms

Escaping Local Optima with Diversity Mechanisms and Crossover

Recommendations

Fast mutation in crossover-based algorithms
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was successfully used only in purely mutation-based algorithms. There, it can relieve the algorithm ...
How crossover helps in pseudo-boolean optimization
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions ...
How crossover speeds up building block assembly in genetic algorithms

We reinvestigate a fundamental question: How effective is crossover in genetic algorithms in combining building blocks of good solutions? Although this has been discussed controversially for decades, we are still lacking a rigorous and intuitive answer. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

July 2016

1196 pages

ISBN:9781450342063

DOI:10.1145/2908812

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Union Seventh Framework Programme
EPSRC

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
601
Total Downloads

Downloads (Last 12 months)135
Downloads (Last 6 weeks)21

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sudholt DSquillero GLi XHandl J(2024)Theory and Practice of Population Diversity in Evolutionary ComputationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648430(1391-1409)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648430
Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Bajpai PBansal J(2024)Voronoi Tessellations based Simple OptimizerInformation Sciences10.1016/j.ins.2024.120795(120795)Online publication date: May-2024
https://doi.org/10.1016/j.ins.2024.120795
Lengler JOpris ASudholt D(2024)Analysing Equilibrium States for Population DiversityAlgorithmica10.1007/s00453-024-01226-386:7(2317-2351)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-024-01226-3
Friedrich TKötzing TRadhakrishnan ASchiller LSchirneck MTennigkeit GWietheger S(2023)Crossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/36036293:2(1-32)Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1145/3603629
Sudholt DSquillero GSilva SPaquete L(2023)Theory and Practice of Population Diversity in Evolutionary ComputationProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595053(1361-1378)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595053
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Lengler JOpris ASudholt DSilva SPaquete L(2023)Analysing Equilibrium States for Population DiversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590465(1628-1636)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590465
Hevia Fajardo MSudholt D(2023)Theoretical and Empirical Analysis of Parameter Control Mechanisms in the (1 + (λ, λ)) Genetic AlgorithmACM Transactions on Evolutionary Learning and Optimization10.1145/35647552:4(1-39)Online publication date: 14-Jan-2023
https://dl.acm.org/doi/10.1145/3564755
Doerr BQu Z(2023)A First Runtime Analysis of the NSGA-II on a Multimodal ProblemIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325055227:5(1288-1297)Online publication date: Oct-2023
https://doi.org/10.1109/TEVC.2023.3250552
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents