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

Jun He, Xin Yao

Research output: Contribution to journalArticlepeer-review

163 Citations (SciVal)

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.
Original languageEnglish
Pages (from-to)59-97
Number of pages39
JournalArtificial Intelligence
Volume145
Issue number1-2
Early online date21 Feb 2003
DOIs
Publication statusPublished - 01 Apr 2003

Keywords

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

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