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

research-article

On the analysis of the simple genetic algorithm

Authors:

Pietro S. Oliveto,

Carsten WittAuthors Info & Claims

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

Pages 1341 - 1348

https://doi.org/10.1145/2330163.2330349

Published: 07 July 2012 Publication History

Abstract

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 (SGA) for OneMax. It is proved that the SGA has exponential runtime with overwhelming probability for population sizes up to μ≤ n^1/8-ε for some arbitrarily small constant ε and problem size n. To the best of our knowledge, this is the first time non-trivial lower bounds are obtained on the runtime of a standard crossover-based GA for a standard benchmark function. The presented techniques might serve as a first basis towards systematic runtime analyses of GAs.

References

[1]

A. Auger and B. Doerr eds. Theory of Randomized Seach Heuristics - Foundations and Recent Developments. World Scientific, 2010.

Digital Library

[2]

B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. In Proc. of GECCO '08, pages 539--546, 2008.

Digital Library

[3]

B. Doerr, M. Fouz, and C. Witt. Sharp bounds by probability-generating functions and variable drift. In Proc. of GECCO '11, pages 2083--2090, 2011.

Digital Library

[4]

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

Digital Library

[5]

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

[6]

J. Jägersküpper and C. Witt. Rigorous runtime analysis of a (μ +1) ES for the Sphere function. In Proc. of GECCO '05, pages 849--856, 2005.

Digital Library

[7]

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

[8]

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

[9]

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

Digital Library

[10]

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

Digital Library

[11]

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

[12]

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

[13]

F. Neumann, D. Sudholt, and C. Witt. Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intelligence, 3(1):35--68, 2009.

[14]

F. Neumann, D. Sudholt, and C. Witt. A few ants are enough: ACO with iteration-best update. In Proc. of GECCO '10, pages 63--70, 2010.

Digital Library

[15]

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

Digital Library

[16]

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.

[17]

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

Digital Library

[18]

G. Rudolph. Convergence properties of canonical genetic algorithms. IEEE Transactions on Neural Networks, 5(1):96--101, 1994.

Digital Library

[19]

M. D. Vose. The Simple Genetic Algorithm: Foundations and Theory. MIT Press, 1998.

Digital Library

[20]

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

[21]

C. Zarges. On the utility of the population size for inversely fitness proportional mutation rates. In Proc. of FOGA '09, pages 39--46, 2009.

Digital Library

Cited By

Doerr B(2020)Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative DriftEvolutionary Computation10.1162/evco_a_00283(1-25)Online publication date: 16-Nov-2020
https://doi.org/10.1162/evco_a_00283
Doerr B(2020)Exponential upper bounds for the runtime of randomized search heuristicsTheoretical Computer Science10.1016/j.tcs.2020.09.032Online publication date: Sep-2020
https://doi.org/10.1016/j.tcs.2020.09.032
Gupta R(2018)Spatial Facility Management: A Step to Design Smart CityGeospatial Infrastructure, Applications and Technologies: India Case Studies10.1007/978-981-13-2330-0_13(155-166)Online publication date: 5-Nov-2018
https://doi.org/10.1007/978-981-13-2330-0_13
Show More Cited By

Index Terms

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

Recommendations

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 ...
Improved runtime analysis of the simple genetic algorithm
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

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 ...

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

10
Total Citations
View Citations
188
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr B(2020)Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative DriftEvolutionary Computation10.1162/evco_a_00283(1-25)Online publication date: 16-Nov-2020
https://doi.org/10.1162/evco_a_00283
Doerr B(2020)Exponential upper bounds for the runtime of randomized search heuristicsTheoretical Computer Science10.1016/j.tcs.2020.09.032Online publication date: Sep-2020
https://doi.org/10.1016/j.tcs.2020.09.032
Gupta R(2018)Spatial Facility Management: A Step to Design Smart CityGeospatial Infrastructure, Applications and Technologies: India Case Studies10.1007/978-981-13-2330-0_13(155-166)Online publication date: 5-Nov-2018
https://doi.org/10.1007/978-981-13-2330-0_13
Reali FPriami CMarchetti L(2017)Optimization Algorithms for Computational Systems BiologyFrontiers in Applied Mathematics and Statistics10.3389/fams.2017.000063Online publication date: 11-Apr-2017
https://doi.org/10.3389/fams.2017.00006
(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
Wang Y(2014)The hybrid genetic algorithm with two local optimization strategies for traveling salesman problemComputers and Industrial Engineering10.1016/j.cie.2014.01.01570(124-133)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1016/j.cie.2014.01.015
Doerr BKünnemann MAlba E(2013)How the (1+λ) evolutionary algorithm optimizes linear functionsProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463569(1589-1596)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463569
Oliveto PWitt CAlba E(2013)Improved runtime analysis of the simple genetic algorithmProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463566(1621-1628)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463566
Doerr BDoerr CEbel FAlba E(2013)Lessons from the black-boxProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463480(781-788)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463480
Chalupa DAlba E(2013)An analytical investigation of block-based mutation operators for order-based stochastic clique covering algorithmsProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463436(495-502)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463436

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