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

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

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.

Details

Original languageEnglish
Pages (from-to)59-97
Number of pages39
JournalArtificial Intelligence
Volume145
Publication statusPublished - 1 Apr 2003

Keywords

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