Conference paper
On the Analysis of the Simple Genetic Algorithm
In
Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation
—
2012, pp. 1341-1348
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-ε 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.
| Language: | English |
|---|---|
| Publisher: | Association for Computing Machinery |
| Year: | 2012 |
| Pages: | 1341-1348 |
| Proceedings: | 2012 Genetic and Evolutionary Computation ConferenceGenetic and Evolutionary Computation Conference |
| ISBN: | 1450311776 and 9781450311779 |
| Types: | Conference paper |
| DOI: | 10.1145/2330163.2330349 |
| ORCIDs: | Witt, Carsten |
