Improved time complexity analysis of the Simple Genetic Algorithm

Pietro S. Oliveto, Carsten Witt

Research output: Contribution to journalJournal articleResearchpeer-review

625 Downloads (Pure)

Abstract

A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μ≤n1/8−ε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μ≤n1/4−ε which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.
Original languageEnglish
JournalTheoretical Computer Science
Volume605
Pages (from-to)21-41
ISSN0304-3975
DOIs
Publication statusPublished - 2015

Keywords

  • Simple Genetic Algorithm
  • Crossover
  • Runtime analysis

Cite this

@article{7fbf215c195b47739f855c4b6794bdf7,
title = "Improved time complexity analysis of the Simple Genetic Algorithm",
abstract = "A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μ≤n1/8−ε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μ≤n1/4−ε which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.",
keywords = "Simple Genetic Algorithm, Crossover, Runtime analysis",
author = "Oliveto, {Pietro S.} and Carsten Witt",
year = "2015",
doi = "10.1016/j.tcs.2015.01.002",
language = "English",
volume = "605",
pages = "21--41",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Improved time complexity analysis of the Simple Genetic Algorithm. / Oliveto, Pietro S.; Witt, Carsten.

In: Theoretical Computer Science, Vol. 605, 2015, p. 21-41.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Improved time complexity analysis of the Simple Genetic Algorithm

AU - Oliveto, Pietro S.

AU - Witt, Carsten

PY - 2015

Y1 - 2015

N2 - A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μ≤n1/8−ε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μ≤n1/4−ε which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.

AB - A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μ≤n1/8−ε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μ≤n1/4−ε which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.

KW - Simple Genetic Algorithm

KW - Crossover

KW - Runtime analysis

U2 - 10.1016/j.tcs.2015.01.002

DO - 10.1016/j.tcs.2015.01.002

M3 - Journal article

VL - 605

SP - 21

EP - 41

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -