More Web Proxy on the site http://driver.im/

research-article

Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets

Authors:

Benjamin Doerr,

Daniel Johannsen,

Martin SchmidtAuthors Info & Claims

FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

Pages 119 - 126

https://doi.org/10.1145/1967654.1967665

Published: 05 January 2011 Publication History

Abstract

In this work, we investigate a (1+1) Evolutionary Algorithm for optimizing functions over the space {0,...,r} ⁿ, where r is a positive integer. We show that for linear functions over {0,1,2}ⁿ, the expected runtime time of this algorithm is O(n log n). This result generalizes an existing result on pseudo-Boolean functions and is derived using drift analysis. We also show that for large values of r, no upper bound for the runtime of the (1+1) Evolutionary Algorithm for linear function on {0,...,r}ⁿ can be obtained with this approach nor with any other approach based on drift analysis with weight-independent linear potential functions.

References

[1]

A. Auger and B. Doerr, editors. Theory of Randomized Seach Heuristics. 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, pages 59--66. ACM, 2009.

Digital Library

[3]

B. Doerr, E. Happ, and C. Klein. A tight analysis of the (1 + 1)-EA for the single source shortest path problem. In CEC'07, pages 1890--1895. IEEE, 2007.

[4]

B. Doerr and D. Johannsen. Edge-based representation beats vertex-based representation in shortest path problems. In GECCO'10, pages 759--766. ACM, 2010.

Digital Library

[5]

B. Doerr, D. Johannsen, and C. Winzen. Drift analysis and linear functions revisited. In CEC'10, pages 1--8. ACM, 2010.

[6]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. In GECCO'10, pages 1449--1456. ACM, 2010.

Digital Library

[7]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. In GECCO'10, 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, pages 571--578. ACM, 2005.

Digital Library

[10]

B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14(3):502--525, 1982.

[11]

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

Digital Library

[12]

J. He and X. Yao. Erratum to: drift analysis and average time complexity of evolutionary algorithms {Artificial Intelligence 127 (2001) 57--85}. Artificial Intelligence, 140(1-2):245--248, 2002.

Digital Library

[13]

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

[14]

J. Jägersküpper. A blend of Markov-chain and drift analysis. In PPSN'08, pages 41--51. Springer, 2008.

Digital Library

[15]

F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 378(1):32--40, 2007.

Digital Library

[16]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization. Springer, 2010.

Digital Library

[17]

J. Reichel and M. Skutella. Evolutionary algorithms and matroid optimization problems. In GECCO'07, pages 947--954. ACM, 2007.

Digital Library

[18]

J. Reichel and M. Skutella. On the size of weights in randomized search heuristics. In FOGA'09, pages 21--28. ACM, 2009.

Digital Library

[19]

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

Cited By

Lv ZQian CSun Y(2024)Benchmarking Analysis of Evolutionary Neural Architecture SearchIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.332485228:6(1659-1673)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3324852
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
Kazakovtsev LRozhnov IShkaberina G(2021)Self-Configuring (1 + 1)-Evolutionary Algorithm for the Continuous p-Median Problem with Agglomerative MutationAlgorithms10.3390/a1405013014:5(130)Online publication date: 22-Apr-2021
https://doi.org/10.3390/a14050130
Show More Cited By

Index Terms

Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets
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 ...
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 ...
Fixed-target runtime analysis of the (1 + 1) EA with resampling
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

We conduct a fixed-target runtime analysis of (1 + 1) EA with resampling on the OneMax and BinVal problems. For OneMax, our fixed-target upper bound refines the previously known bound. Our fixed-target lower bound for OneMax is the first of this kind. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

January 2011

262 pages

ISBN:9781450306331

DOI:10.1145/1967654

Program Chairs:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
W. B. Langdon
University College London, UK

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: 05 January 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '11

Sponsor:

SIGEVO

FOGA '11: Foundations of Genetic Algorithms XI

January 5 - 9, 2011

Schwarzenberg, Austria

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
156
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lv ZQian CSun Y(2024)Benchmarking Analysis of Evolutionary Neural Architecture SearchIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.332485228:6(1659-1673)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3324852
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
Kazakovtsev LRozhnov IShkaberina G(2021)Self-Configuring (1 + 1)-Evolutionary Algorithm for the Continuous p-Median Problem with Agglomerative MutationAlgorithms10.3390/a1405013014:5(130)Online publication date: 22-Apr-2021
https://doi.org/10.3390/a14050130
Doerr BNeumann F(2021)A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/34723041:4(1-43)Online publication date: 31-Dec-2021
https://doi.org/10.1145/3472304
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
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
Doerr BPohl SMoore J(2012)Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabetProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330346(1317-1324)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330346

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