On the Analysis of the Simple Genetic Algorithm

Pietro S. Oliveto; Carsten Witt

doi:10.1145/2330163.2330349

On the Analysis of the Simple Genetic Algorithm

Pietro S. Oliveto
, Carsten Witt

University of Birmingham

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

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.

Original language	English
Title of host publication	Proceedings of the fourteenth international conference on Genetic and evolutionary computation
Publisher	Association for Computing Machinery
Publication date	2012
Pages	1341-1348
ISBN (Print)	978-1-4503-1177-9
DOIs	https://doi.org/10.1145/2330163.2330349
Publication status	Published - 2012
Event	2012 Genetic and Evolutionary Computation Conference - Philadelphia, United States Duration: 7 Jul 2012 → 11 Jul 2012 http://www.sigevo.org/gecco-2012/

Conference

Conference	2012 Genetic and Evolutionary Computation Conference
Country/Territory	United States
City	Philadelphia
Period	07/07/2012 → 11/07/2012
Internet address	http://www.sigevo.org/gecco-2012/

Access to Document

10.1145/2330163.2330349

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{bdf5ec44ece44549bf5d050b3965b3f4,

title = "On the Analysis of the Simple Genetic Algorithm",

abstract = "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.",

author = "Oliveto, \{Pietro S.\} and Carsten Witt",

year = "2012",

doi = "10.1145/2330163.2330349",

language = "English",

isbn = "978-1-4503-1177-9",

pages = "1341--1348",

booktitle = "Proceedings of the fourteenth international conference on Genetic and evolutionary computation",

publisher = "Association for Computing Machinery",

address = "United States",

note = "2012 Genetic and Evolutionary Computation Conference, GECCO 2012 ; Conference date: 07-07-2012 Through 11-07-2012",

url = "http://www.sigevo.org/gecco-2012/",

}

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, 2012 Genetic and Evolutionary Computation Conference, Philadelphia, Pennsylvania, United States, 07/07/2012. https://doi.org/10.1145/2330163.2330349

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

PB - Association for Computing Machinery

T2 - 2012 Genetic and Evolutionary Computation Conference

Y2 - 7 July 2012 through 11 July 2012

ER -

On the Analysis of the Simple Genetic Algorithm

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this