Publication: Research - peer-review › Article in proceedings – Annual report year: 2012
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.
|Title of host publication||Proceedings of the fourteenth international conference on Genetic and evolutionary computation|
|Publisher||Association for Computing Machinery|
|State||Published - 2012|
|Event||Genetic and Evolutionary Computation Conference (GECCO 2012) - Philadelphia, United States|
|Conference||Genetic and Evolutionary Computation Conference (GECCO 2012)|
|Period||07/07/2012 → 11/07/2012|
|Citations||Web of Science® Times Cited: 7|
Loading map data...