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

research-article

Improved runtime analysis of the simple genetic algorithm

Authors:

Pietro S. Oliveto,

Carsten WittAuthors Info & Claims

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

Pages 1621 - 1628

https://doi.org/10.1145/2463372.2463566

Published: 06 July 2013 Publication History

Abstract

A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of our previous one. Firstly, the new result holds for population sizes up to mu = n1/4-epsilon which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.

References

[1]

W. Feller. An Introduction to Probability Theory and Its Applications, volume 2. Wiley, 1971.

[2]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and machine learning. Addison-Wesley, 1989.

Digital Library

[3]

E. Happ, D. Johannsen, C. Klein, and F. Neumann. Rigorous analyses of fitness-proportional selection for optimizing linear functions. In Proc. of GECCO '08, pages 953--960, 2008.

Digital Library

[4]

T. Jansen and I. Wegener. Real royal road functions: where crossover provably is essential. Discrete Applied Mathematics, 149(1--3):111--125, 2005.

Digital Library

[5]

T. Kötzing, D. Sudholt, and M. Theile. How crossover helps in pseudo-boolean optimization. In Proc. of GECCO '11, pages 989--996, 2011.

Digital Library

[6]

P. K. Lehre. Negative drift in populations. In Proc. of PPSN '10, Part I, pages 244--253, 2010.

Digital Library

[7]

P. K. Lehre. Fitness-levels for non-elitist populations. In Proc. of GECCO '11, pages 2075--2082, 2011.

Digital Library

[8]

P. K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623--642, 2012.

Digital Library

[9]

F. Neumann, P. S. Oliveto, G. Rudolph, and D. Sudholt. On the effectiveness of crossover for migration in parallel evolutionary algorithms. In Proc. of GECCO '11, pages 1587--1594, 2011.

Digital Library

[10]

F. Neumann, P. S. Oliveto, and C. Witt. Theoretical analysis of fitness-proportional selection: Landscapes and efficiency. In Proc. of GECCO '09, pages 835--842, 2009.

Digital Library

[11]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[12]

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

[13]

P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3):369--386, 2011.

Digital Library

[14]

P. S. Oliveto and C. Witt. On the analysis of the simple genetic algorithm. In Proc. of GECCO '12, pages 1341--1348, 2012.

Digital Library

[15]

J. E. Rowe and D. Sudholt. The choice of the offspring population size in the (1,$łambda$) EA. In Proc. of GECCO '12, pages 1349--1356, 2012.

Digital Library

[16]

D. Sudholt. Crossover speeds up building-block assembly. In Proc.\ of GECCO '12, pages 689--702, 2012.

Digital Library

[17]

R. A. Watson and T. Jansen. A building-block royal road where crossover is provably essential. In Proc. of GECCO '07, pages 1452--1459, 2007.

Digital Library

Cited By

Sudholt D(2017)How crossover speeds up building block assembly in genetic algorithmsEvolutionary Computation10.1162/EVCO_a_0017125:2(237-274)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00171
Oliveto PWitt C(2015)Improved time complexity analysis of the Simple Genetic AlgorithmTheoretical Computer Science10.1016/j.tcs.2015.01.002605:C(21-41)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.01.002
Doerr BDoerr CEbel F(2015)From black-box complexity to designing new genetic algorithmsTheoretical Computer Science10.1016/j.tcs.2014.11.028567:C(87-104)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.028
Show More Cited By

Index Terms

Improved runtime analysis of the simple genetic algorithm
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the analysis of the simple genetic algorithm
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

For many years it has been a challenge to analyze the time complexity of Genetic Algorithms (GAs) using stochastic selection together with crossover and mutation. This paper presents a rigorous runtime analysis of the well-known Simple Genetic Algorithm ...
On the runtime analysis of the Simple Genetic Algorithm

For many years it has been a challenge to analyze the time complexity of Genetic Algorithms (GAs) using stochastic selection together with crossover and mutation. This paper presents a rigorous runtime analysis of the well-known Simple Genetic Algorithm ...
Improved time complexity analysis of the Simple Genetic Algorithm

A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size µ n 1 / 8 - ε requires exponential time with overwhelming probability. This paper presents an ...

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

4
Total Citations
View Citations
144
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sudholt D(2017)How crossover speeds up building block assembly in genetic algorithmsEvolutionary Computation10.1162/EVCO_a_0017125:2(237-274)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00171
Oliveto PWitt C(2015)Improved time complexity analysis of the Simple Genetic AlgorithmTheoretical Computer Science10.1016/j.tcs.2015.01.002605:C(21-41)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.01.002
Doerr BDoerr CEbel F(2015)From black-box complexity to designing new genetic algorithmsTheoretical Computer Science10.1016/j.tcs.2014.11.028567:C(87-104)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.028
Corus DDang DEremeev ALehre P(2014)Level-Based Analysis of Genetic Algorithms and Other Search ProcessesParallel Problem Solving from Nature – PPSN XIII10.1007/978-3-319-10762-2_90(912-921)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10762-2_90

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