On the runtime analysis of the Simple Genetic Algorithm

Pietro S. Oliveto, Carsten Witt

    Research output: Contribution to journalJournal articleResearchpeer-review

    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 μ⩽n1/8−εμ⩽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
    JournalTheoretical Computer Science
    Volume545
    Pages (from-to)2-19
    ISSN0304-3975
    DOIs
    Publication statusPublished - 2014

    Keywords

    • COMPUTER
    • EVOLUTIONARY ALGORITHMS
    • DRIFT ANALYSIS
    • MUTATION
    • BOUNDS
    • Simple Genetic Algorithm
    • Crossover
    • Runtime analysis

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

    Cite this