Towards an Analytic Framework for Analysing the Computation Time of Evolutionary Algorithms

Jun He, Xin Yao

Research output: Contribution to journalArticle

145 Citations (Scopus)

Abstract

In spite of many applications of evolutionary algorithms in optimisation, theoretical results on the computation time and time complexity of evolutionary algorithms on different optimisation problems are relatively few. It is still unclear when an evolutionary algorithm is expected to solve an optimisation problem efficiently or otherwise. This paper gives a general analytic framework for analysing first hitting times of evolutionary algorithms. The framework is built on the absorbing Markov chain model of evolutionary algorithms. The first step towards a systematic comparative study among different EAs and their first hitting times has been made in the paper. (C) 2003 Published by Elsevier Science B.V.
Original languageEnglish
Pages (from-to)59-97
Number of pages39
JournalArtificial Intelligence
Volume145
DOIs
Publication statusPublished - 1 Apr 2003

Keywords

  • evolutionary algorithms
  • first hitting time
  • Markov chain
  • time complexity

Fingerprint

Dive into the research topics of 'Towards an Analytic Framework for Analysing the Computation Time of Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this