GEOMETRIC CONVERGENCE OF GENETIC ALGORITHMS UNDER TEMPERED RANDOM RESTART

被引：1

作者：

Mendivil, F. ^{[1
]}

Shonkwiler, R. ^{[2
]}

Spruill, C. ^{[2
]}

机构：

[1] Acadia Univ, Dept Math, Wolfville, NS B0P 1X0, Canada

[2] Georgia Inst Technol, Atlanta, GA 30332 USA

来源：

JOURNAL OF APPLIED PROBABILITY | 2009年 / 46卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Nonstationary Markov chain; hitting time; Perron-Frobenius; decreasing mutation rate;

D O I：

暂无

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

Geometric convergence to 0 of the probability that the goal has not been encountered by the nth generation is established for a class of genetic algorithms. These algorithms employ a quickly decreasing mutation rate and a crossover which restarts the algorithm in a controlled way depending on the current population and restricts execution of this crossover to occasions when progress of the algorithm is too slow. It is shown that without the crossover studied here, which amounts to a tempered restart of the algorithm, the asserted geometric convergence need not hold.

引用

页码：960 / 974

页数：15

共 7 条

[1]

Cerf R, 1996, ANN I H POINCARE-PR, V32, P455

[2]

Cerf R., 1996, ANN APPL PROBAB, V6, P778

[3]

DAVIS ET, 1993, EVOLUT COMPUT, V1, P269

[4]

HU A, 2002, INT J COMPUT NUMER A, V1, P353

[5]

Lowe M., 1996, EXPOS MATH, V14, P289

[6] Restarting search algorithms with applications to simulated annealing [J].

Mendivil, F ;

Shonkwiler, R ;

Spruill, MC .

ADVANCES IN APPLIED PROBABILITY, 2001, 33 (01) :242-259

[7]

Shonkwiler R., 1994, Journal of Complexity, V10, P64, DOI 10.1006/jcom.1994.1003

← 1 →