research-article

Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet

Authors:

Benjamin Doerr,

Sebastian PohlAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Pages 1317 - 1324

https://doi.org/10.1145/2330163.2330346

Published: 07 July 2012 Publication History

Abstract

We analyze the run-time of the (1 + 1) Evolutionary Algorithm optimizing an arbitrary linear function f : {0,1,...,r}ⁿ -> R. If the mutation probability of the algorithm is p = c/n, then (1 + o(1))(e^c/c))rn log n + O(r³n log log n) is an upper bound for the expected time needed to find the optimum. We also give a lower bound of (1 + o(1))(1/c)rn log n. Hence for constant c and all r slightly smaller than (log n)^1/3, our bounds deviate by only a constant factor, which is e(1 + o(1)) for the standard mutation probability of 1/n. The proof of the upper bound uses multiplicative adaptive drift analysis as developed in a series of recent papers. We cannot close the gap for larger values of r, but find indications that multiplicative drift is not the optimal analysis tool for this case.

References

[1]

A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics, volume 1 of Series on Theoretical Computer Science. World Scientific, 2011.

Digital Library

[2]

S. Baswana, S. Biswas, B. Doerr, T. Friedrich, P. P. Kurur, and F. Neumann. Computing single source shortest paths using single-objective fitness. In FOGA'09: Proceedings of the 10th ACM Workshop on Foundations of Genetic Algorithms, pages 59--66. ACM, 2009.

Digital Library

[3]

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics, 23(4):493--507, 1952.

[4]

B. Doerr and L. A. Goldberg. Adaptive drift analysis. In PPSN'10: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature, pages 32--41, 2010.

Digital Library

[5]

B. Doerr, D. Johannsen, and M. Schmidt. Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets. In Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms, FOGA '11, pages 119--126. ACM, 2011.

Digital Library

[6]

B. Doerr, D. Johannsen, and C. Winzen. Drift analysis and linear functions revisited. In CEC'10: Proceedings of the 2010 IEEE Congress on Evolutionary Computation, pages 1967--1974. IEEE, 2010.

[7]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. In GECCO'10: Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference, pages 1449--1456. ACM, 2010.

Digital Library

[8]

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

[9]

C. Gunia. On the analysis of the approximation capability of simple evolutionary algorithms for scheduling problems. In GECCO'05: Proceedings of the 7th Annual Genetic and Evolutionary Computation Conference, pages 571--578. Jahn, 2005.

Digital Library

[10]

J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):51--81, 2001.

Digital Library

[11]

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

[12]

J. Jagersküpper. A blend of Markov-chain and drift analysis. In PPSN'08: Proceedings of the 10th International Conference on Parallel Problem Solving from Nature, pages 41--51. Springer, 2008.

Digital Library

[13]

D. Johannsen. Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universitat des Saarlandes, 2010. Available online at http://scidok.sulb.uni-saarland.de/volltexte/2011/3529/pdf/Dissertation_3166_Joha_Dani_2010.pdf.

[14]

J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest path problems. Journal of Mathematical Modelling and Algorithms, 3(4):349--366, 2004.

[15]

C. Witt. Optimizing linear functions with randomized search heuristics - the robustness of mutation. In STACS'12: Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science, pages 420--431, 2012.

Cited By

Jedidia FDoerr BKrejca M(2024)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science10.1016/j.tcs.2024.114622(114622)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114622
Fischer PLarsen EWitt C(2023)First Steps Towards a Runtime Analysis of NeuroevolutionProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607125(61-72)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607125
Ben Jedidia FDoerr BKrejca MSilva SPaquete L(2023)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590523(230-238)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590523
Show More Cited By

Index Terms

Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

The choice of the offspring population size in the (1,λ) evolutionary algorithm

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...
A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably ...
An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

July 2012

1396 pages

ISBN:9781450311779

DOI:10.1145/2330163

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 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: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, 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
119
Total Downloads

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

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jedidia FDoerr BKrejca M(2024)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science10.1016/j.tcs.2024.114622(114622)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114622
Fischer PLarsen EWitt C(2023)First Steps Towards a Runtime Analysis of NeuroevolutionProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607125(61-72)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607125
Ben Jedidia FDoerr BKrejca MSilva SPaquete L(2023)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590523(230-238)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590523
Neumann FPourhassan MWitt C(2020)Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform ConstraintAlgorithmica10.1007/s00453-020-00779-3Online publication date: 4-Nov-2020
https://doi.org/10.1007/s00453-020-00779-3
Neumann FPourhassan MWitt CAuger AStützle T(2019)Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraintProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321722(1506-1514)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321722
Doerr BDoerr CKötzing T(2018)Static and Self-Adjusting Mutation Strengths for Multi-valued Decision VariablesAlgorithmica10.1007/s00453-017-0341-180:5(1732-1768)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0341-1
Doerr BDoerr CKoetzing TNeumann FSutton A(2016)The Right Mutation Strength for Multi-Valued Decision VariablesProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908891(1115-1122)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908891
Lissovoi AWitt C(2016)MMAS Versus Population-Based EA on a Family of Dynamic Fitness FunctionsAlgorithmica10.1007/s00453-015-9975-z75:3(554-576)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00453-015-9975-z
Kötzing TLissovoi AWitt CHe JJansen TOchoa GZarges C(2015)(1+1) EA on Generalized Dynamic OneMaxProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725502(40-51)Online publication date: 17-Jan-2015
https://dl.acm.org/doi/10.1145/2725494.2725502
Yu YQian CZhou Z(2015)Switch Analysis for Running Time Analysis of Evolutionary AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2014.237889119:6(777-792)Online publication date: Dec-2015
https://doi.org/10.1109/TEVC.2014.2378891
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.

Figures

Tables

Media

View Table of Conten