Improved time complexity analysis of the Simple Genetic Algorithm

Pietro S. Oliveto, Carsten Witt

Research output: Contribution to journalJournal articleResearchpeer-review

1078 Downloads (Pure)


A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μ≤n1/8−ε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μ≤n1/4−ε which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.
Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)21-41
Publication statusPublished - 2015


  • Simple Genetic Algorithm
  • Crossover
  • Runtime analysis

Fingerprint Dive into the research topics of 'Improved time complexity analysis of the Simple Genetic Algorithm'. Together they form a unique fingerprint.

Cite this