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

research-article

How the (1+λ) evolutionary algorithm optimizes linear functions

Authors:

Benjamin Doerr,

Marvin KünnemannAuthors Info & Claims

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

Pages 1589 - 1596

https://doi.org/10.1145/2463372.2463569

Published: 06 July 2013 Publication History

Abstract

We analyze how the (1+λ) evolutionary algorithm (EA) optimizes linear pseudo-Boolean functions. We prove that it finds the optimum of any linear function within an expected number of O(1/λn log n+n) iterations. We also show that this bound is sharp for some functions, e.g., the binary value function. Hence unlike for the(1+1) EA, for the (1+λ) EA different linear functions may have run-times of different asymptotic order. The proof of our upper bound heavily relies on a number of classic and recent drift analysis methods. In particular, we show how to analyze a process displaying different types of drifts in different phases. Our work corrects a wrongfully claimed better asymptotic runtime in an earlier work~\cite{He10}.

References

[1]

B. Doerr, M. Fouz, and C. Witt. Quasirandom evolutionary algorithms. In GECCO'10: Proc. of the 12th Ann. Genetic and Evolutionary Computation Conf., pages 1457--1464. ACM, 2010.

Digital Library

[2]

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

Digital Library

[3]

B. Doerr and L. A. Goldberg. Drift analysis with tail bounds. In PPSN'10: Proc. of the 11th Int. Conf. on Parallel Problem Solving from Nature, pages 174--183. Springer, 2010.

Digital Library

[4]

B. Doerr and L. A. Goldberg. Adaptive drift analysis. Algorithmica, 65:224--250, 2013.

Digital Library

[5]

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

[6]

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

Digital Library

[7]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. Algorithmica, 64:673--697, 2012.

Digital Library

[8]

S. Droste. A rigorous analysis of the compact genetic algorithm for linear functions. Natural Computing, 5(3):257--283, 2006.

Digital Library

[9]

S. Droste, T. Jansen, and I. Wegener. A rigorous complexity analysis of the (1+1) evolutionary algorithm for linear functions with Boolean inputs. In CEC'98: Proc. of the 1998 IEEE Cong. on Evolutionary Computation, pages 499--504. IEEE, 1998.

[10]

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

Digital Library

[11]

G. H. Gonnet. Expected length of the longest probe sequence in hash code searching. J. ACM, 28:289--304, 1981.

Digital Library

[12]

J. He. A note on the first hitting time of (1+λ) evolutionary algorithm for linear functions with Boolean inputs. In CEC'10: Proc. of the 2010 IEEE Cong. on Evolutionary Computation, pages 1--6. IEEE, 2010.

[13]

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

Digital Library

[14]

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:245--248, 2002.

Digital Library

[15]

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

Digital Library

[16]

J. Jägersküpper. Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theoretical Computer Science, 379(3):329--347, 2007.

Digital Library

[17]

J. Jägersküpper. A blend of Markov-chain and drift analysis. In PPSN'08: Proc. of the 10th Int. Conf. on Parallel Problem Solving from Nature, pages 41--51. Springer, 2008.

Digital Library

[18]

J. J\"agersküpper. Combining Markov-chain analysis and drift analysis--the (1+1) evolutionary algorithm on linear functions reloaded. Algorithmica, 59:409--424, 2011.

Digital Library

[19]

J. J\"agersküpper and T. Storch. When the plus strategy outperforms the comma strategy and when not. In FOCI'07: Proc. of the IEEE Symp. on Foundations of Computational Intelligence, pages 25--32. IEEE, 2007.

[20]

T. Jansen, K. A. D. Jong, and I. Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13:413--440, 2005.

Digital Library

[21]

T. Jansen, P. S. Oliveto, and C. Zarges. On the analysis of the immune-inspired B-cell algorithm for the vertex cover problem. In ICARIS'11: Proc. of the 10th International Conference on Artificial Immune Systems, pages 117--131. Springer, 2011.

Digital Library

[22]

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

Digital Library

[23]

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

Digital Library

[24]

P. S. Oliveto, J. He, and X. Yao. Analysis of population-based evolutionary algorithms for the vertex cover problem. In CEC'08: Proc. of the 2008 IEEE Cong. on Evolutionary Computation, pages 1563--1570, 2008.

[25]

P. S. Oliveto and C. Witt. On the analysis of the simple genetic algorithm. In GECCO'12: Proc. of the 14th Ann. Genetic and Evolutionary Computation Conf., pages 1341--1348, 2012.

Digital Library

[26]

J. E. Rowe and D. Sudholt. The choice of the offspring population size in the (1,λ) EA. In GECCO'12: Proc. of the 14th Ann. Genetic and Evolutionary Computation Conf., pages 1349--1356. ACM, 2012.

Digital Library

[27]

T. Storch. On the choice of the parent population size. Evolutionary Computation, 16:557--578, 2008.

Digital Library

[28]

A. Wald. On cumulative sums of random variables. Annals of Mathematical Statistics, 15:283--296, 1944.

[29]

C. Witt. Runtime analysis of the (μ+1) EA on simple pseudo-Boolean functions. Evolutionary Computation, 14:65--86, 2006.

Digital Library

[30]

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

[31]

C. Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing, in press, available online: Preprint available at http://arxiv.org/abs/1108.4386.

Cited By

Jorritsma JLengler JSudholt DSilva SPaquete L(2023)Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted OptimaProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590488(1602-1610)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590488
Aboutaib BSutton A(2022)Runtime Analysis of Unbalanced Block-Parallel Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_39(555-568)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-14721-0_39
Lissovoi AOliveto PWarwicker JBosman P(2017)On the runtime analysis of generalised selection hyper-heuristics for pseudo-boolean optimisationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071288(849-856)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071288
Show More Cited By

Index Terms

How the (1+λ) evolutionary algorithm optimizes linear functions
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Copyright © 2013 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: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
149
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jorritsma JLengler JSudholt DSilva SPaquete L(2023)Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted OptimaProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590488(1602-1610)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590488
Aboutaib BSutton A(2022)Runtime Analysis of Unbalanced Block-Parallel Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_39(555-568)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-14721-0_39
Lissovoi AOliveto PWarwicker JBosman P(2017)On the runtime analysis of generalised selection hyper-heuristics for pseudo-boolean optimisationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071288(849-856)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071288
Kötzing T(2016)Concentration of First Hitting Times Under Additive DriftAlgorithmica10.1007/s00453-015-0048-075:3(490-506)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00453-015-0048-0
Doerr BDoerr C(2016)The Impact of Random Initialization on the Runtime of Randomized Search HeuristicsAlgorithmica10.1007/s00453-015-0019-575:3(529-553)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00453-015-0019-5
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
(2015)Optimizing linear functions with the ( 1 + λ ) evolutionary algorithm-Different asymptotic runtimes for different instancesTheoretical Computer Science10.1016/j.tcs.2014.03.015561:PA(3-23)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.03.015
Kötzing TArnold D(2014)Concentration of first hitting times under additive driftProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598364(1391-1398)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598364
Doerr BDoerr CArnold D(2014)The impact of random initialization on the runtime of randomized search heuristicsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598359(1375-1382)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598359
Wei KDinneen M(2014)Hybridizing the dynamic mutation approach with local searches to overcome local optima2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900360(74-81)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900360
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