A rigorous analysis of the compact genetic algorithm for linear functions

被引：69

作者：

Droste S. ^{[1
]}

机构：

[1] LS Informatik 2, Universität Dortmund

来源：

Natural Computing | 2006年 / 5卷 / 3期

关键词：

Compact genetic algorithm; Runtime; Theoretical analysis;

D O I：

10.1007/s11047-006-9001-0

中图分类号：

学科分类号：

摘要：

Estimation of distribution algorithms (EDAs) solve an optimization problem heuristically by finding a probability distribution focused around its optima. Starting with the uniform distribution, points are sampled with respect to this distribution and the distribution is changed according to the function values of the sampled points. Although there are many successful experiments suggesting the usefulness of EDAs, there are only few rigorous theoretical results apart from convergence results without time bounds. Here we present first rigorous runtime analyses of a simple EDA, the compact genetic algorithm (cGA), for linear pseudo-Boolean functions on n variables. We prove a general lower bound for all functions and a general upper bound for all linear functions. Simple test functions show that not all linear functions are optimized in the same runtime by the cGA. © Springer Science+Business Media, Inc. 2006.

引用

页码：257 / 283

页数：26

共 11 条

[1] Beyer H.-G., Schwefel H.-P., Wegener I., How to analyse evolutionary algorithms, Theoretical Computer Science, 287, pp. 101-130, (2002)
[2] Droste S., Not all linear functions are equally difficult for the compact genetic algorithms, Proceedings of the Genetic and Evolutionary Computation Conference, pp. 679-686, (2005)
[3] Droste S., Jansen T., Wegener I., On the analysis of the (1+1) EA, Theoretical Computer Science, 276, pp. 51-81, (2002)
[4] Harik G.R., Lobo F.G., Goldberg D.E., The compact genetic algorithm, Proceedings of the IEEE Conference on Evolutionary Computation, pp. 523-528, (1998)
[5] He J., Yao X., A study of drift analysis for estimating computation time of evolutionary algorithms, Natural Computing, 3, pp. 21-35, (2004)
[6] Larranaga P., Lozano J.A., Estimation of Distribution Algorithms, (2002)
[7] Motwani R., Raghavan P., Randomized Algorithms, (1995)
[8] Muhlenbein H., Mahnig T., Convergence theory and applications of the factorized distribution algorithm, Journal of Computing and Information Technology, 7, pp. 19-32, (1999)
[9] Rudolph G., Convergence Properties of Evolutionary Algorithms, (1997)
[10] Wegener I., Methods for the analysis of evolutionary algorithms on pseudo-boolean functions, Evolutionary Optimization, pp. 349-369, (2002)

← 1 2 →