A study of drift analysis for estimating computation time of evolutionary algorithms

Jun HE, Xin YAO

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

218 Citations (Scopus)

Abstract

This paper introduces drift analysis and its applications in estimating average computation time of evolutionary algorithms. Firstly, drift conditions for estimating upper and lower bounds of the mean first hitting times of evolutionary algorithms are presented. Then drift analysis is applied to two specific evolutionary algorithms and problems. Finally, a general classification of easy and hard problems for evolutionary algorithms is given based on the analysis. © 2004 Kluwer Academic Publishers.
Original languageEnglish
Pages (from-to)21-35
Number of pages15
JournalNatural Computing
Volume3
Issue number1
DOIs
Publication statusPublished - 2004
Externally publishedYes

Bibliographical note

Work partially supported by an EPSRC grant (GR/S63847/01) and the State Key Lab of Software Engineering, P.R. China.

Keywords

  • Algorithm analysis
  • Combinatorial optimisation
  • Evolutionary computation
  • Meta-heuristics

Fingerprint

Dive into the research topics of 'A study of drift analysis for estimating computation time of evolutionary algorithms'. Together they form a unique fingerprint.

Cite this