research-article

Escaping large deceptive basins of attraction with heavy-tailed mutation operators

Authors:

Tobias Friedrich,

Francesco Quinzan,

Markus WagnerAuthors Info & Claims

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 293 - 300

https://doi.org/10.1145/3205455.3205515

Published: 02 July 2018 Publication History

Abstract

In many evolutionary algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one.

In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results in a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable.

In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut).

We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.

References

[1]

Carlos Ansótegui, Meinolf Sellmann, and Kevin Tierney. 2009. A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms. 142--157.

Digital Library

[2]

Mauro Birattari, Thomas Stützle, Luis Paquete, and Klaus Varrentrapp. 2002. A Racing Algorithm for Configuring Metaheuristics. In Proc. of GECCO. 11--18.

[3]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. 2010. Optimal Fixed and Adaptive Mutation Rates for the LeadingOnes Problem. In Proc. of PPSN. 1--10.

Digital Library

[4]

Benjamin Doerr, Thomas Jansen, Dirk Sudholt, Carola Winzen, and Christine Zarges. 2013. Mutation Rate Matters Even When Optimizing Monotonie Functions. Evolutionary Computation 21, 1 (2013), 1--27.

Digital Library

[5]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast genetic algorithms. In Proc. of GECCO. 777--784.

Digital Library

[6]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276,1--2 (2002), 51--81.

Digital Library

[7]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276,1--2 (2002), 51--81.

Digital Library

[8]

A. E. Eiben, R. Hinterding, and Z. Michalewicz. 1999. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation 3, 2 (1999), 124--141.

Digital Library

[9]

A. E. Eiben and J. E. Smith. 2003. Introduction to evolutionary computation. Springer.

Digital Library

[10]

Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. 2011. Maximizing Non-monotone Submodular Functions. SIAM Journal of Computing 40, 4 (2011), 1133--1153.

Digital Library

[11]

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, and Carsten Witt. 2010. Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models. Evolutionary Computation 18, 4 (2010), 617--633.

Digital Library

[12]

Tobias Friedrich and Frank Neumann. 2015. Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms. Evolutionary Computation 23, 4 (2015), 543--558.

Digital Library

[13]

Tobias Friedrich, Pietro S. Oliveto, Dirk Sudholt, and Carsten Witt. 2009. Analysis of Diversity-preserving Mechanisms for Global Exploration. Evolutionary Computation 17, 4 (2009), 455--476.

Digital Library

[14]

Christian Gießen and Carsten Witt. 2015. Population Size vs. Mutation Strength for the (1+λ)EA on OneMax. In Proc. of GECCO. 1439--1446.

Digital Library

[15]

Clarissa Van Hoyweghen, David E. Goldberg, and Bart Naudts. 2002. From Twomax To The Ising Model: Easy And Hard Symmetrical Problems. In Proc. of GECCO. 626--633.

[16]

Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. 2011. Sequential Model-Based Optimization for General Algorithm Configuration. In Proc. of LION. 507--523.

Digital Library

[17]

Thomas Jansen and Ingo Wegener. 2005. Real royal road functions-where crossover provably is essential. Discrete Applied Mathematics 149, 1--3 (2005), 111--125.

Digital Library

[18]

Heinz Mühlenbein. 1992. How Genetic Algorithms Really Work: Mutation and Hillclimbing. In Proc. of PPSN. 15--26.

[19]

Martin Pelikan and David E. Goldberg. 2000. Genetic Algorithms, Clustering, and the Breaking of Symmetry. In Proc. of PPSN. 385--394.

Digital Library

[20]

Ingo Wegener. 2001. Theoretical Aspects of Evolutionary Algorithms. In Proc. of ICALP. 64--78.

Digital Library

Cited By

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
Doerr BKrejca MVu NLi XHandl J(2024)Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy HeuristicsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654140(169-177)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654140
Krejca MWitt CLi XHandl J(2024)A Flexible Evolutionary Algorithm with Dynamic Mutation Rate ArchiveProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654076(1578-1586)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654076
Show More Cited By

Index Terms

Escaping large deceptive basins of attraction with heavy-tailed mutation operators
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial optimization
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Generalization of the Heavy-Tailed Mutation in the (1+(λ,λ)) Genetic Algorithm
GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion

The heavy-tailed mutation operator, proposed by Doerr, Le, Makhmara, and Nguyen (2017) for evolutionary algorithms, is based on the power-law assumption of mutation rate distribution. Here we generalize the power-law assumption on the distribution ...
Constrained differential evolution with multiobjective sorting mutation operators for constrained optimization

The proposed constrained differential evolution framework uses nondominated sorting mutation operator based on fitness and diversity information for constrained optimization. This study proposes a new constraint differential evolution framework.Parents ...
Evaluation of heavy-tailed mutation operator on maximum flow test generation problem
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference Companion

The general recommendation for the mutation rate in standard-bit mutation is 1/n, which gives asymptotically optimal expected optimization times for several simple test problems. Recently, Doerr et al. have shown that such mutation rate is not ideal, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

July 2018

1578 pages

ISBN:9781450356183

DOI:10.1145/3205455

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council
Hasso Plattner Institute

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
133
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Doerr BKrejca MVu NLi XHandl J(2024)Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy HeuristicsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654140(169-177)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654140
Krejca MWitt CLi XHandl J(2024)A Flexible Evolutionary Algorithm with Dynamic Mutation Rate ArchiveProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654076(1578-1586)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654076
Aboutaib BSutton ALi XHandl J(2024)Mixed Binomial Distributions for Binary Mutation OperatorsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654010(796-804)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654010
Doerr CJanett DLengler J(2024)Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear FunctionsAlgorithmica10.1007/s00453-024-01258-986:10(3115-3152)Online publication date: 22-Jul-2024
https://doi.org/10.1007/s00453-024-01258-9
Bossek JSudholt D(2024)Runtime Analysis of Quality Diversity AlgorithmsAlgorithmica10.1007/s00453-024-01254-z86:10(3252-3283)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00453-024-01254-z
Pérez Cáceres LLópez-Ibáñez MStützle TSilva SPaquete L(2023)Automated Algorithm Configuration and DesignProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595046(2438-2463)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595046
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
Doerr CJanett DLengler JSilva SPaquete L(2023)Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590482(1565-1574)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590482
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
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents