On the Analysis of the Simple Genetic Algorithm

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

View graph of relations

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 μ≤ n1/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.
Original languageEnglish
Title of host publicationProceedings of the fourteenth international conference on Genetic and evolutionary computation
PublisherAssociation for Computing Machinery
Publication date2012
Pages1341-1348
ISBN (print)978-1-4503-1177-9
DOIs
StatePublished

Conference

ConferenceGenetic and Evolutionary Computation Conference (GECCO 2012)
CountryUnited States
CityPhiladelphia
Period07/07/1211/07/12
Internet addresshttp://www.sigevo.org/gecco-2012/
CitationsWeb of Science® Times Cited: 6
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 33440588