The Gambler's Ruin Problem, Genetic Algorithms, and the Sizing of Populations

被引：180

作者：

Harik, George ^{[1
]}

Cantu-Paz, Erick ^{[1
]}

Goldberg, David E. ^{[1
]}

Miller, Brad L. ^{[2
]}

机构：

[1] Univ Illinois, Illinois Genet Algorithms Lab, Urbana, IL 61801 USA

[2] I2 Technol, Cambridge, MA 02139 USA

来源：

EVOLUTIONARY COMPUTATION | 1999年 / 7卷 / 03期

关键词：

Population size; noise; decision making; building block supply;

D O I：

10.1162/evco.1999.7.3.231

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents a model to predict the convergence quality of genetic algorithms based on the size of the population. The model is based on an analogy between selection in GAS and one-dimensional random walks. Using the solution to a classic random walk problem-the gambler's ruin-the model naturally incorporates previous knowledge about the initial supply of building blocks (BBs) and correct selection of the best BB over its competitors. The result is an equation that relates the size of the population with the desired quality of the solution, as well as the problem size and difficulty. The accuracy of the model is verified with experiments using additively decomposable functions of varying difficulty. The paper demonstrates how to adjust the model to account for noise present in the fitness evaluation and for different tournament sizes.

引用

页码：231 / 253

页数：23

共 24 条

[1] Abramowitz M., 1972, Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tables, V9
[2] Back T., 1994, Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence (Cat. No.94TH0650-2), P57, DOI 10.1109/ICEC.1994.350042
[3] Cantu-Paz E., 1997, Genetic Programming 1997 Proceedings of the Second Annual Conference, P353
[4] Cvetkovic D ., 1994, 9411 GMD AS GA
[5] Dc Jong K. A, 1975, 769381 U MICR DEP CO
[6] DEB K, 1993, FOUNDATIONS OF GENETIC ALGORITHMS 2, P93
[7] Feller W., 1966, INTRO PROBABILITY TH, VI
[8] Goldberg D. E., 1991, Complex Systems, V5, P265
[9] Goldberg D. E., 1992, Complex Systems, V6, P333
[10] Goldberg D. E., 1991, 4 INT C GEN ALG U CA

← 1 2 3 →