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

Jun HE; Xin YAO

doi:10.1023/B:NACO.0000023417.31393.c7

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

Jun HE, Xin YAO

Research output: Journal Publications › Journal Article (refereed) › peer-review

219 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 language	English
Pages (from-to)	21-35
Number of pages	15
Journal	Natural Computing
Volume	3
Issue number	1
DOIs	https://doi.org/10.1023/B:NACO.0000023417.31393.c7
Publication status	Published - 2004
Externally published	Yes

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

Access to Document

10.1023/B:NACO.0000023417.31393.c7

Cite this

@article{0d370f8684e74cfda88301b0d97c3de2,

title = "A study of drift analysis for estimating computation time of evolutionary algorithms",

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. {\textcopyright} 2004 Kluwer Academic Publishers.",

keywords = "Algorithm analysis, Combinatorial optimisation, Evolutionary computation, Meta-heuristics",

author = "Jun HE and Xin YAO",

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

year = "2004",

doi = "10.1023/B:NACO.0000023417.31393.c7",

language = "English",

volume = "3",

pages = "21--35",

journal = "Natural Computing",

issn = "1567-7818",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

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

AU - HE, Jun

AU - YAO, Xin

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

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - Algorithm analysis

KW - Combinatorial optimisation

KW - Evolutionary computation

KW - Meta-heuristics

UR - http://www.scopus.com/inward/record.url?scp=4344644853&partnerID=8YFLogxK

U2 - 10.1023/B:NACO.0000023417.31393.c7

DO - 10.1023/B:NACO.0000023417.31393.c7

M3 - Journal Article (refereed)

SN - 1567-7818

VL - 3

SP - 21

EP - 35

JO - Natural Computing

JF - Natural Computing

IS - 1

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this