Average drift analysis and population scalability

Jun HE, Xin YAO

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

12 Citations (Scopus)


This paper aims to study how the population size affects the computation time of evolutionary algorithms (EAs) in a rigorous way. The computation time of EAs can be measured by either the number of generations (hitting time) or the number of fitness evaluations (running time) to find an optimal solution. Population scalability is the ratio of the expected hitting time between a benchmark algorithm and an algorithm using a larger population size. Average drift analysis is introduced to compare the expected hitting time of two algorithms and to estimate lower and upper bounds on the population scalability. Several intuitive beliefs are rigorously analyzed. It is proven that: 1) using a population sometimes increases rather than decreases the expected hitting time; 2) using a population cannot shorten the expected running time of any elitist EA on any unimodal function on the time-fitness landscape, however, this statement is not true in terms of the distance-based fitness landscape; and 3) using a population cannot always reduce the expected running time on deceptive functions, which depends on whether the benchmark algorithm uses elitist selection or random selection.
Original languageEnglish
Article number7579655
Pages (from-to)426-439
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Issue number3
Publication statusPublished - 2016
Externally publishedYes


  • Computation time
  • Drift analysis
  • Evolutionary algorithm (EA)
  • Fitness landscape
  • Population size


Dive into the research topics of 'Average drift analysis and population scalability'. Together they form a unique fingerprint.

Cite this