research-article

Population Size vs. Mutation Strength for the (1+λ) EA on OneMax

Authors:

Christian Gießen,

Carsten WittAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1439 - 1446

https://doi.org/10.1145/2739480.2754738

Published: 11 July 2015 Publication History

Abstract

The (1+1) EA with mutation probability c/n, where c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and λ. It turns out that 1/n is the only optimal mutation probability if λ=o(ln n ln ln n/ln ln ln n), which is the cut-off point for linear mnspeed-up. However, if λ is above this cut-off point then the standard mutation probability 1/n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater.

The results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds.

References

[1]

Anne Auger and Benjamin Doerr, editors. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing, 2011.

[2]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. Optimal fixed and adaptive mutation rates for the leadingones problem. In Proc. of Parallel Problem Solving from Nature (PPSN 2010), volume 6238, pages 1--10. Springer, 2010.

Digital Library

[3]

Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. Quasirandom evolutionary algorithms. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2010), page 1457--1464. ACM Press, 2010.

Digital Library

[4]

Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. Sharp bounds by probability-generating functions and variable drift. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2011), pages 2083--2090. ACM Press, 2011.

Digital Library

[5]

Benjamin Doerr and Leslie Ann Goldberg. Adaptive drift analysis. Algorithmica, 65(1):224--250, 2013.

Digital Library

[6]

Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorithmica, 64(4):673--697, 2012.

Digital Library

[7]

Benjamin Doerr and Marvin Künnemann. Royal road functions and the (1+ λ) evolutionary algorithm: Almost no speed-up from larger offspring populations. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2013), pages 424--431. IEEE Press, 2013.

[8]

Benjamin Doerr and Marvin Künnemann. Optimizing linear functions with the (1+λ) evolutionary algorithm -- different asymptotic runtimes for different instances. Theoretical Computer Science, 561:3--23, 2015.

Digital Library

[9]

Jens Jägersküpper. Combining markov-chain analysis and drift analysis -- the (1+1) evolutionary algorithm on linear functions reloaded. Algorithmica, 59(3):409--424, 2011. Preliminary version in Proc. of PPSN '08.

Digital Library

[10]

Thomas Jansen. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, 2013.

[11]

Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13(4):413--440, 2005.

Digital Library

[12]

Daniel Johannsen. Random combinatorial structures and randomized search heuristics. PhD thesis, Universität des Saarlandes, Germany, 2010.

[13]

Per Kristian Lehre and Carsten Witt. Concentrated hitting times of randomized search heuristics with variable drift. In Proc. of ISAAC '14, volume 8889 of Lecture Notes in Computer Science, pages 686--697. Springer, 2014. Full technical report at http://arxiv.org/abs/1307.2559.

[14]

Boris Mitavskiy, Jonathan E. Rowe, and Chris Cannings. Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. International Journal of Intelligent Computing and Cybernetics, 2(2):243--284, 2009.

[15]

Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Natural Computing Series. Springer, 2010.

Digital Library

[16]

Jonathan E. Rowe and Dirk Sudholt. The choice of the offspring population size in the (1,λ) evolutionary algorithm. Theoretical Computer Science, 545:20--38, 2014. Preliminary version in Proc. of GECCO 2012.

Digital Library

[17]

Dirk Sudholt. Crossover speeds up building-block assembly. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2010), pages 689--702. ACM Press, 2012.

Digital Library

[18]

Dirk Sudholt. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 17(3):418--435, 2013. Preliminary version in Proc. of PPSN '10.

Digital Library

[19]

Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing, 22(2):294--318, 2013. Preliminary version in Proc. of STACS '12.

Cited By

Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Friedrich TQuinzan FWagner MTakadama K(2018)Escaping large deceptive basins of attraction with heavy-tailed mutation operatorsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205515(293-300)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205515
Gieβen CWitt C(2018)Optimal Mutation Rates for the (1+$$\lambda $$ź) EA on OneMax Through Asymptotically Tight Drift AnalysisAlgorithmica10.1007/s00453-017-0360-y80:5(1710-1731)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0360-y
Show More Cited By

Index Terms

Population Size vs. Mutation Strength for the (1+λ) EA on OneMax
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

The Interplay of Population Size and Mutation Probability in the ($$1+\lambda $$1+ź) EA on OneMax

The ($$1+\lambda $$1+ź) EA with mutation probability c / n, where $$c>0$$c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and $$\...
The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation Rate

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and ...
Optimal Mutation Rates for the (1+$$\lambda $$ź) EA on OneMax Through Asymptotically Tight Drift Analysis

We study the (1+$$\lambda $$ź) EA, a classical population-based evolutionary algorithm, with mutation probability c / n, where $$c>0$$c>0 and $$\lambda $$ź are constant, on the benchmark function OneMax, which counts the number of 1-bits in a bitstring. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 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: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Natur og Univers, Det Frie Forskningsråd

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
131
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Friedrich TQuinzan FWagner MTakadama K(2018)Escaping large deceptive basins of attraction with heavy-tailed mutation operatorsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205515(293-300)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205515
Gieβen CWitt C(2018)Optimal Mutation Rates for the (1+$$\lambda $$ź) EA on OneMax Through Asymptotically Tight Drift AnalysisAlgorithmica10.1007/s00453-017-0360-y80:5(1710-1731)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0360-y
Doerr BDoerr C(2018)Optimal Static and Self-Adjusting Parameter Choices for the $$(1+(\lambda ,\lambda ))$$(1+(ź,ź)) Genetic AlgorithmAlgorithmica10.1007/s00453-017-0354-980:5(1658-1709)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0354-9
Doerr BLe HMakhmara RNguyen TBosman P(2017)Fast genetic algorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071301(777-784)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071301
Doerr B(2017)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067713(389-412)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3067713
Doerr C(2017)Non-static parameter choices in evolutionary computationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067707(736-761)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3067707
Gieβen CWitt C(2017)The Interplay of Population Size and Mutation Probability in the ($$1+\lambda $$1+ź) EA on OneMaxAlgorithmica10.1007/s00453-016-0214-z78:2(587-609)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s00453-016-0214-z
Doerr BDoerr CNeumann FSutton A(2016)Theory for Non-TheoreticiansProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2926982(463-482)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2926982
Doerr BDoerr CYang JNeumann FSutton A(2016)Optimal Parameter Choices via Precise Black-Box AnalysisProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908950(1123-1130)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908950
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