TY - GEN

T1 - On the Analysis of the Simple Genetic Algorithm

A1 - Oliveto,Pietro S.

A1 - Witt,Carsten

AU - Oliveto,Pietro S.

AU - Witt,Carsten

PB - ACM

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1145/2330163.2330349

DO - 10.1145/2330163.2330349

SN - 978-1-4503-1177-9

BT - Proceedings of the fourteenth international conference on Genetic and evolutionary computation

T2 - Proceedings of the fourteenth international conference on Genetic and evolutionary computation

SP - 1341

EP - 1348

ER -