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|
|Publication status||Published - 2012|
|Event||2012 Genetic and Evolutionary Computation Conference - Philadelphia, United States|
Duration: 7 Jul 2012 → 11 Jul 2012
|Conference||2012 Genetic and Evolutionary Computation Conference|
|Period||07/07/2012 → 11/07/2012|