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

被引：190

作者：

He J. ^{[1
]}

Yao X. ^{[1
]}

机构：

[1] CERCIA, School of Computer Science, University of Birmingham, Birmingham B15 2TT, Edgbaston

来源：

Natural Computing | 2004年 / 3卷 / 1期

基金：

英国工程与自然科学研究理事会;

关键词：

Algorithm analysis; Combinatorial optimisation; Evolutionary computation; Meta-heuristics;

D O I：

10.1023/B:NACO.0000023417.31393.c7

中图分类号：

学科分类号：

摘要：

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.

引用

页码：21 / 35

页数：14

共 15 条

[1]

Beyer H.-G., The Theory of Evolutionary Strategies, (2001)

[2]

Beyer H.-G., Schwefel H.-P., Wegener I., How to analyse evolutionary algorithms, Theoretical Computer Science, 287, 1, pp. 101-130, (2002)

[3]

Chow Y.S., Teicher H., Probability Theory: Independence, Interchangeability and Martingales, (1988)

[4]

Droste S., Jansen T., Wegener I., A rigorous complexity analysis of the (1 + 1)-evolutionary algorithm for linear functions with Boolean inputs, Evolutionary Computation, 6, 2, pp. 185-196, (1998)

[5]

Droste S., Jansen T., Wegener I., On the analysis of the (1 + 1)-evolutionary algorithms, Theoretical Computer Science, 276, 1-2, pp. 51-81, (2002)

[6]

Eiben A.E., Rudolph G., Theory of evolutionary algorithms: A bird's eye view, Theoretical Computer Science, 229, 1-2, pp. 3-9, (1999)

[7]

Hajek B., Hitting time and occupation time bounds implied by drift analysis with applications, Advances in Applied Probability, 14, 3, pp. 502-525, (1982)

[8]

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

[9]

He J., Yao X., From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 6, 5, pp. 495-511, (2002)

[10]

He J., Yao X., Towards an analytic framework for analysing the computation time of evolutionary algorithms, Artificial Intelligence, 145, 1-2, pp. 59-97, (2003)

← 1 2 →