Improved Runtime Analysis of the Simple Genetic Algorithm

Pietro S. Oliveto, Carsten Witt

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


A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of our previous one. Firstly, the new result holds for population sizes up to mu = n1/4-epsilon 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
Title of host publicationProceeding of the fifteenth annual conference on Genetic and evolutionary computation
PublisherAssociation for Computing Machinery
Publication date2013
ISBN (Print)978-1-4503-1963-8
Publication statusPublished - 2013
Event2013 Genetic and Evolutionary Computation Conference - Amsterdam, Netherlands
Duration: 6 Jul 201310 Jul 2013


Conference2013 Genetic and Evolutionary Computation Conference
Internet address


  • Simple Genetic Algorithm
  • Crossover
  • Runtime Analysis

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

Cite this