TY - JOUR

T1 - Drift analysis and average time complexity of evolutionary algorithms

AU - He, Jun

AU - Yao, Xin

N1 - He, J., Yao, X. (2001). Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127 (1) 57-85
RAE2008

PY - 2001/3/15

Y1 - 2001/3/15

N2 - The computational time complexity is an important topic in the theory of evolutionary algorithms (EAs). This paper reports some new results on the average time complexity of EAs. Based on drift analysis, some useful drift conditions for deriving the time complexity of EAs are studied, including conditions under which an EA will take no more than polynomial time (in problem size) to solve a problem and conditions under which an EA will take at least exponential time (in problem size) to solve a problem. The paper first presents the general results, and then uses several problems as examples to illustrate how these general results can be applied to concrete problems in analyzing the average time complexity of EAs. While previous work only considered (1+1) EAs without any crossover, the EAs considered in this paper are fairly general, which use a finite population, crossover, mutation, and selection.

AB - The computational time complexity is an important topic in the theory of evolutionary algorithms (EAs). This paper reports some new results on the average time complexity of EAs. Based on drift analysis, some useful drift conditions for deriving the time complexity of EAs are studied, including conditions under which an EA will take no more than polynomial time (in problem size) to solve a problem and conditions under which an EA will take at least exponential time (in problem size) to solve a problem. The paper first presents the general results, and then uses several problems as examples to illustrate how these general results can be applied to concrete problems in analyzing the average time complexity of EAs. While previous work only considered (1+1) EAs without any crossover, the EAs considered in this paper are fairly general, which use a finite population, crossover, mutation, and selection.

KW - evolutionary algorithms

KW - time complexity

KW - random sequences

KW - drift analysis

KW - stochastic inequalities

U2 - 10.1016/S0004-3702(01)00058-3

DO - 10.1016/S0004-3702(01)00058-3

M3 - Article

SN - 0004-3702

VL - 127

SP - 57

EP - 85

JO - Artificial Intelligence

JF - Artificial Intelligence

IS - 1

ER -