On the Analysis of the Simple Genetic Algorithm

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Standard

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

Proceedings of the fourteenth international conference on Genetic and evolutionary computation. Association for Computing Machinery, 2012. p. 1341-1348.

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Harvard

Oliveto, PS & Witt, C 2012, 'On the Analysis of the Simple Genetic Algorithm'. in Proceedings of the fourteenth international conference on Genetic and evolutionary computation. Association for Computing Machinery, pp. 1341-1348., 10.1145/2330163.2330349

APA

Oliveto, P. S., & Witt, C. (2012). On the Analysis of the Simple Genetic Algorithm. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation. (pp. 1341-1348). Association for Computing Machinery. 10.1145/2330163.2330349

CBE

Oliveto PS, Witt C. 2012. On the Analysis of the Simple Genetic Algorithm. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation. Association for Computing Machinery. pp. 1341-1348. Available from: 10.1145/2330163.2330349

MLA

Oliveto, Pietro S. and Carsten Witt "On the Analysis of the Simple Genetic Algorithm". Proceedings of the fourteenth international conference on Genetic and evolutionary computation. Association for Computing Machinery. 2012. 1341-1348. Available: 10.1145/2330163.2330349

Vancouver

Oliveto PS, Witt C. On the Analysis of the Simple Genetic Algorithm. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation. Association for Computing Machinery. 2012. p. 1341-1348. Available from: 10.1145/2330163.2330349

Author

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

Proceedings of the fourteenth international conference on Genetic and evolutionary computation. Association for Computing Machinery, 2012. p. 1341-1348.

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Bibtex

@inbook{bdf5ec44ece44549bf5d050b3965b3f4,
title = "On the Analysis of the Simple Genetic Algorithm",
publisher = "Association for Computing Machinery",
author = "Oliveto, {Pietro S.} and Carsten Witt",
year = "2012",
doi = "10.1145/2330163.2330349",
isbn = "978-1-4503-1177-9",
pages = "1341-1348",
booktitle = "Proceedings of the fourteenth international conference on Genetic and evolutionary computation",

}

RIS

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 - Association for Computing Machinery

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 -