research-article

Comparing global and local mutations on bit strings

Authors:

Benjamin Doerr,

Thomas Jansen,

Christian KleinAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 929 - 936

https://doi.org/10.1145/1389095.1389274

Published: 12 July 2008 Publication History

Get Access

Abstract

Evolutionary algorithms operating on bit strings usually employ a global mutation where each bit is flipped independently with some mutation probability. Most often the mutation probability is set fixed in a way that on average exactly one bit is flipped in a mutation. A seemingly very similar concept is a local one realized by an operator that flips exactly one bit chosen uniformly at random.

Most known results indicate that the global approach leads to run-times at least as good as the local approach. The draw-back is that the global approach is much harder to analyze. It would therefore be highly useful to derive general principles of when and how results for the local operator extend to the global ones.

In this paper, we show that there is little hope for such general principles, even under very favorable conditions. We show that there is a fitness function such that the local operator from each initial search point finds the optimum in small polynomial time, whereas the global operator for almost all initial search points needs a weakly exponential time.

References

[1]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2. edition, 2001.]]

Digital Library

Google Scholar

[2]

B. Doerr, E. Happ, and C. Klein. A tight bound for the (1+1)-EA on the single source shortest path problem. In D. Srinivasan and L. Wang, editors, Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC), pages 1890--1895. IEEE Press, 2007.]]

Crossref

Google Scholar

[3]

S. Droste, T. Jansen, and I. Wegener. On the optimization of unimodal functions with the (1+1) evolutionary algorithm. In A. E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of the 5th International Conference on Parallel Problem Solving From Nature (PPSN), volume 1498 of Lecture Notes in Computer Science, pages 13--22. Springer, 1998.]]

Digital Library

Google Scholar

[4]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1-2):51--81, 2002.]]

Digital Library

Google Scholar

[5]

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

Digital Library

Google Scholar

[6]

J. Horn, D. E. Goldberg, and K. Deb. Long path problems. In Y. Davidor, H.-P. Schwefel, and R. Männer, editors, Proceedings of the Third Conference on Parallel Problem Solving from Nature (PPSN III), volume 866 of Lecture Notes in Computer Science, pages 149--158. Springer, 1994.]]

Digital Library

Google Scholar

[7]

T. Jansen and I. Wegener. On the choice of the mutation probability for the (1+1) ea. In M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J. J. M. Guervós, and H.-P. Schwefel, editors, Proceedings of the 6th International Conference on Parallel Problem Solving From Nature (PPSN), volume 1917 of Lecture Notes in Computer Science, pages 89--98. Springer, 2000.]]

Digital Library

Google Scholar

[8]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.]]

Digital Library

Google Scholar

[9]

G. Rudolph. How mutation and selection solve long path problems in polynomial expected time. Evolutionary Computation, 4(2):195--205, 1996.]]

Digital Library

Google Scholar

[10]

G. Rudolph. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovač, Hamburg, 1997.]]

Google Scholar

Cited By

View all

Zheng WDoerr B(2023)Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives*Evolutionary Computation10.1162/evco_a_0032831:4(337-373)Online publication date: 1-Dec-2023
https://doi.org/10.1162/evco_a_00328
Rajabi AWitt C(2023)Stagnation Detection with Randomized Local Search*Evolutionary Computation10.1162/evco_a_0031331:1(1-29)Online publication date: 1-Mar-2023
https://doi.org/10.1162/evco_a_00313
Meyerson EQiu XMiikkulainen RWagner M(2022)Simple genetic operators are universal approximators of probability distributions (and other advantages of expressive encodings)Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528746(739-748)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528746
Show More Cited By

Index Terms

Comparing global and local mutations on bit strings
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

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 ...
An extended mutation concept for the local selection based differential evolution algorithm
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

A new mutation concept is proposed to generalize local selection based Differential Evolution algorithm to work in general multi-modal problems. Three variations of the proposed method are compared with classic Differential Evolution algorithm using a ...
Global versus local search: the impact of population sizes on evolutionary algorithm performance

In the field of Evolutionary Computation, a common myth that "An Evolutionary Algorithm (EA) will outperform a local search algorithm, given enough runtime and a large-enough population" exists. We believe that this is not necessarily true and challenge ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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
152
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zheng WDoerr B(2023)Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives*Evolutionary Computation10.1162/evco_a_0032831:4(337-373)Online publication date: 1-Dec-2023
https://doi.org/10.1162/evco_a_00328
Rajabi AWitt C(2023)Stagnation Detection with Randomized Local Search*Evolutionary Computation10.1162/evco_a_0031331:1(1-29)Online publication date: 1-Mar-2023
https://doi.org/10.1162/evco_a_00313
Meyerson EQiu XMiikkulainen RWagner M(2022)Simple genetic operators are universal approximators of probability distributions (and other advantages of expressive encodings)Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528746(739-748)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528746
Rajabi AWitt C(2021)Stagnation Detection with Randomized Local SearchEvolutionary Computation in Combinatorial Optimization10.1007/978-3-030-72904-2_10(152-168)Online publication date: 27-Mar-2021
https://doi.org/10.1007/978-3-030-72904-2_10
Sudholt D(2020)Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is BeneficialAlgorithmica10.1007/s00453-020-00671-0Online publication date: 25-Jan-2020
https://doi.org/10.1007/s00453-020-00671-0
Meyerson EMiikkulainen RWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Modular universal reparameterizationProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454997(7903-7914)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454997
Jansen TZarges C(2018)Theoretical Analysis of Lexicase Selection in Multi-objective OptimizationParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99259-4_13(153-164)Online publication date: 21-Aug-2018
https://doi.org/10.1007/978-3-319-99259-4_13
Antipov DDoerr B(2018)Precise Runtime Analysis for PlateausParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99259-4_10(117-128)Online publication date: 21-Aug-2018
https://doi.org/10.1007/978-3-319-99259-4_10
Jansen TZarges C(2014)Performance analysis of randomised search heuristics operating with a fixed budgetTheoretical Computer Science10.1016/j.tcs.2013.06.007545(39-58)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1016/j.tcs.2013.06.007
Doerr BJansen TSudholt DWinzen CZarges C(2013)Mutation rate matters even when optimizing monotonic functionsEvolutionary Computation10.1162/EVCO_a_0005521:1(1-27)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1162/EVCO_a_00055
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.

Cited By

Index Terms

Recommendations

The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation Rate

An extended mutation concept for the local selection based differential evolution algorithm

Global versus local search: the impact of population sizes on evolutionary algorithm performance