On the Analysis of the Simple Genetic Algorithm

Pietro S. Oliveto, Carsten Witt

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    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
    ISBN (Print)978-1-4503-1177-9
    Publication statusPublished - 2012
    Event2012 Genetic and Evolutionary Computation Conference - Philadelphia, United States
    Duration: 7 Jul 201211 Jul 2012


    Conference2012 Genetic and Evolutionary Computation Conference
    CountryUnited States
    Internet address

    Fingerprint Dive into the research topics of 'On the Analysis of the Simple Genetic Algorithm'. Together they form a unique fingerprint.

    Cite this