From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms

Jun HE, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

137 Citations (Scopus)

Abstract

Almost all analyses of time complexity of evolutionary algorithms (EAs) have been conducted for (1 + 1) EAs only. Theoretical results on the average computation time of population-based EAs are few. However, the vast majority of applications of EAs use a population size that is greater than one. The use of population has been regarded as one of the key features of EAs. It is important to understand in depth what the real utility of population is in terms of the time complexity of EAs, when EAs are applied to combinatorial optimization problems. This paper compares (1 + 1) EAs and (N + N) EAs theoretically by deriving their first hitting time on the same problems. It is shown that a population can have a drastic impact on an EA's average computation time, changing an exponential time to a polynomial time (in the input size) in some cases. It is also shown that the first hitting probability can be improved by introducing a population. However, the results presented in this paper do not imply that population-based EAs will always be better than (1 + 1) EAs for all possible problems.
Original languageEnglish
Pages (from-to)495-511
Number of pages17
JournalIEEE Transactions on Evolutionary Computation
Volume6
Issue number5
DOIs
Publication statusPublished - Oct 2002
Externally publishedYes

Bibliographical note

This work was supported in part by an EPSRC Grant (GR/R52541/01) and by the State Key Lab of Software Engineering, Wuhan University.

Keywords

  • Evolutionary algorithms
  • First hitting time
  • Population
  • Time complexity

Fingerprint

Dive into the research topics of 'From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms'. Together they form a unique fingerprint.

Cite this