## On the Analysis of the Simple Genetic Algorithm

Publication: Research - peer-review › Article in proceedings – Annual report year: 2012

### Standard

**On the Analysis of the Simple Genetic Algorithm.** / Oliveto, Pietro S.; Witt, Carsten.

Publication: Research - peer-review › Article in proceedings – Annual report year: 2012

### Harvard

*Proceedings of the fourteenth international conference on Genetic and evolutionary computation.*Association for Computing Machinery, pp. 1341-1348., 10.1145/2330163.2330349

### APA

*Proceedings of the fourteenth international conference on Genetic and evolutionary computation.*(pp. 1341-1348). Association for Computing Machinery. 10.1145/2330163.2330349

### CBE

### MLA

*Proceedings of the fourteenth international conference on Genetic and evolutionary computation.*Association for Computing Machinery. 2012. 1341-1348. Available: 10.1145/2330163.2330349

### Vancouver

### Author

### Bibtex

}

### RIS

TY - GEN

T1 - On the Analysis of the Simple Genetic Algorithm

AU - Oliveto,Pietro S.

AU - Witt,Carsten

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

M3 - Article in proceedings

SN - 978-1-4503-1177-9

SP - 1341

EP - 1348

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

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

PB - Association for Computing Machinery

ER -