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
TitleProceedings 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: 3
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