research-article

Mutation rates of the (1+1)-EA on pseudo-boolean functions of bounded epistasis

Authors:

Andrew M. Sutton,

Darrell Whitley,

Adele E. HoweAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 973 - 980

https://doi.org/10.1145/2001576.2001709

Published: 12 July 2011 Publication History

Abstract

When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)-EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of 1/n is provably optimal. On functions where epistasis is bounded by a constant k, we show that for sufficiently high fitness, the commonly used mutation rate of 1/n is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degree-k polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum k-satisfiability problems and NK-landscapes show that this expectation-maximized mutation rate can cause significant gains early in search.

References

[1]

Thomas Bäck. The interaction of mutation rate, selection, and self-adaptation within a genetic algorithm. In Reinhard Männer and Bernard Manderick, editors, Parallel Problem Solving from Nature 2, pages 85--94, Amsterdam, 1992. Elsevier.

[2]

Thomas Bäck. Self-adaptation in genetic algorithms. In Francisco J. Varela and Paul Bourgnine, editors, Proceedings of the First European Conference on Artificial Life, pages 263--271, Cambridge, MA, 1992. The MIT Press.

[3]

Thomas Bäck. Optimal mutation rates in genetic search. In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 2--8, San Mateo, CA, 1993. Morgan Kaufmann.

Digital Library

[4]

Thomas Bäck and Martin Schütz. Intelligent mutation rate control in canonical genetic algorithms. In Zbigniew Ras and Maciek Michalewicz, editors, Foundations of Intelligent Systems, volume 1079 of Lecture Notes in Computer Science, pages 158--167. Springer Berlin / Heidelberg, 1996.

Digital Library

[5]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In Robert Schaefer, Carlos Cotta, Joanna Kolodziej, and Günter Rudolph, editors, Parallel Problem Solving from Nature -- PPSN XI, volume 6238 of Lecture Notes in Computer Science, pages 1--10. Springer Berlin / Heidelberg, 2010.

Digital Library

[6]

Sung-Soon Choi, Kyomin Jung, and Jeong Han Kim. Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions. In Rocco A. Servedio and Tong Zhang, editors, Proceedings of the Twenty-first Conference on Learning Theory (COLT 2008), pages 123--134, Helsinki, Finland, July 2008. Omnipress.

[7]

Kenneth A. De Jong. An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, 1975.

Digital Library

[8]

Benjamin Doerr, Thomas Jansen, Dirk Sudholt, Carola Winzen, and Christine Zarges. Optimizing monotone functions can be difficult. In Robert Schaefer, Carlos Cotta, Joanna Kolodziej, and Günter Rudolph, editors, Parallel Problem Solving from Nature -- PPSN XI, volume 6238 of Lecture Notes in Computer Science, pages 42--51. Springer Berlin / Heidelberg, 2010.

Digital Library

[9]

Stefan Droste, Thomas Jansen, and Ingo Wegener. A rigorous complexity analysis of the (1+1) evolutionary algorithm for separable functions with Boolean inputs. Evolutionary Computation, 6(2):185--196, 1998.

Digital Library

[10]

Josselin Garnier, Leila Kallel, and Marc Schoenauer. Rigorous hitting times for binary mutations. Evolutionary Computation, 7(2):167--203, 1999.

Digital Library

[11]

John J. Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 16(1):122--128, 1986.

Digital Library

[12]

Robert B. Heckendorn. Walsh Analysis, Epistasis, and Optimization Problem Difficulty for Evolutionary Algorithms. PhD thesis, Colorado State University, Fort Collins, CO,July 1999.

Digital Library

[13]

Robert B. Heckendorn, Soraya B. Rana, and L. Darrell Whitley. Test function generators as embedded landscapes. In Wolfgang Banzhaf and Colin R. Reeves, editors, Foundations of Genetic Algorithms V, pages 183--198. Morgan Kaufmann, 1998.

[14]

Robert B. Heckendorn and Alden H. Wright. Efficient linkage discovery by limited probing. Evolutionary Computation, 12:517--545, 2004.

Digital Library

[15]

Jürgen Hesser and Reinhard Männer. Towards an optimal mutation probability for genetic algorithms. In Hans-Paul Schwefel and Reinhard Männer, editors, Parallel Problem Solving from Nature, volume 496 of Lecture Notes in Computer Science, pages 23--32. Springer Berlin / Heidelberg, 1991.

Digital Library

[16]

John H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975.

Digital Library

[17]

Thomas Jansen and Ingo Wegener. On the choice of the mutation probability for the (1+1) EA. In Marc Schoenauer, Kalyanmoy Deb, Günther Rudolph, Xin Yao, Evelyne Lutton, Juan Merelo, and Hans-Paul Schwefel, editors, Parallel Problem Solving from Nature VI, volume 1917 of Lecture Notes in Computer Science, pages 89--98. Springer Berlin / Heidelberg, 2000.

Digital Library

[18]

Hillol Kargupta and Byung-hoon Park. Gene expression and fast construction of distributed evolutionary representation. Evolutionary Computation, 9(1):43--69, 2001.

Digital Library

[19]

Stuart Kauffman and Simon Levin. Towards a general theory of adaptive walks on rugged landscapes. Journal of Theoretical Biology, 128:11--45, 1987.

[20]

Mikhail Kravchuk. Sur une généralisation des polynomes d'Hermite. Comptes rendus de l'Académie des sciences, 189(17):620--622, 1929.

[21]

Heinz Mühlenbein. How genetic algorithms really work: I. mutation and hillclimbing. In Reinhard Männer and Bernard Manderick, editors, Parallel Problem Solving from Nature 2, pages 15--25. Elsevier, Amsterdam, 1992.

[22]

Günter Rudolph. Convergence Properties of Evolutionary Algorithms. Verlag Dr Kova\v c, 1997.

[23]

J. David Schaffer, Richard A. Caruana, Larry J. Eshelman, and Rajarshi Das. A study of control parameters affecting online performance of genetic algorithms for function optimization. In Proceedings of the Third International Conference on Genetic Algorithms, pages 51--60, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc.

Digital Library

[24]

Andrew M. Sutton, L. Darrell Whitley, and Adele E. Howe. Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time. Theoretical Computer Science, 2011. (In press).

Digital Library

[25]

Alden H. Wright, Richard K. Thompson, and Jian Zhang. The computational complexity of N-K fitness functions. Evolutionary Computation, 4(4):373--379, 2000.

Digital Library

Cited By

Henaux VGoeffon ASaubion F(2020)Evolution of Deterministic Hill-climbers2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI50040.2020.00093(564-571)Online publication date: Nov-2020
https://doi.org/10.1109/ICTAI50040.2020.00093
Belavkin RChannon AAston EAston JKrašovec RKnight C(2016)Monotonicity of fitness landscapes and mutation rate controlJournal of Mathematical Biology10.1007/s00285-016-0995-373:6-7(1491-1524)Online publication date: 12-Apr-2016
https://doi.org/10.1007/s00285-016-0995-3
Chicano FSutton AWhitley LAlba E(2015)Fitness probability distribution of bit-flip mutationEvolutionary Computation10.1162/EVCO_a_0013023:2(217-248)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1162/EVCO_a_00130
Show More Cited By

Index Terms

Mutation rates of the (1+1)-EA on pseudo-boolean functions of bounded epistasis
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

The choice of the offspring population size in the (1,λ) EA
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log₁₀ n between exponential and polynomial running times on ...
Runtime Analysis of the (μ+1) EA on Simple Pseudo-Boolean Functions

Although Evolutionary Algorithms (EAs) have been successfully applied to optimization in discrete search spaces, theoretical developments remain weak, in particular for population-based EAs. This paper presents a first rigorous analysis of the (μ+1) EA ...
Use of the q-Gaussian mutation in evolutionary algorithms
Special issue on advances in computational intelligence and bioinformatics

This paper proposes the use of the q-Gaussian mutation with self-adaptation of the shape of the mutation distribution in evolutionary algorithms. The shape of the q-Gaussian mutation distribution is controlled by a real parameter q. In the proposed ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 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 ACM 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: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
90
Total Downloads

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

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Henaux VGoeffon ASaubion F(2020)Evolution of Deterministic Hill-climbers2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI50040.2020.00093(564-571)Online publication date: Nov-2020
https://doi.org/10.1109/ICTAI50040.2020.00093
Belavkin RChannon AAston EAston JKrašovec RKnight C(2016)Monotonicity of fitness landscapes and mutation rate controlJournal of Mathematical Biology10.1007/s00285-016-0995-373:6-7(1491-1524)Online publication date: 12-Apr-2016
https://doi.org/10.1007/s00285-016-0995-3
Chicano FSutton AWhitley LAlba E(2015)Fitness probability distribution of bit-flip mutationEvolutionary Computation10.1162/EVCO_a_0013023:2(217-248)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1162/EVCO_a_00130
Whitley DChicano F(2014)Elementary Landscape Decomposition of the Hamiltonian Path Optimization Problem,Evolutionary Computation in Combinatorial Optimisation10.1007/978-3-662-44320-0_11(121-132)Online publication date: 2014
https://doi.org/10.1007/978-3-662-44320-0_11
Chalupa DAlba E(2013)Adaptation of a multiagent evolutionary algorithm to NK landscapesProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482719(1391-1398)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482719
Chicano FLuque GAlba EAlba E(2013)Problem understanding through landscape theoryProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482683(1055-1062)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482683
Chicano FWhitley DAlba EMoore J(2012)Exact computation of the expectation curves for uniform crossoverProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330344(1301-1308)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330344
Chicano FAlba E(2012)Exact computation of the fitness-distance correlation for pseudoboolean functions with one global optimumProceedings of the 12th European conference on Evolutionary Computation in Combinatorial Optimization10.1007/978-3-642-29124-1_10(111-123)Online publication date: 11-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29124-1_10

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