Convergence criteria for genetic algorithms

被引:86
作者
Greenhalgh, D
Marshall, S
机构
[1] Univ Strathclyde, Dept Stat & Modeling Sci, Glasgow G1 1XH, Lanark, Scotland
[2] Univ Strathclyde, Dept Elect & Elect Engn, Glasgow G1 1XW, Lanark, Scotland
关键词
genetic algorithms; convergence criteria; upper bounds; probability; optimal coding;
D O I
10.1137/S009753979732565X
中图分类号
TP301 [理论、方法];
学科分类号
081202 [计算机软件与理论];
摘要
In this paper we discuss convergence properties for genetic algorithms. By looking at the effect of mutation on convergence, we show that by running the genetic algorithm for a sufficiently long time we can guarantee convergence to a global optimum with any specified level of confidence. We obtain an upper bound for the number of iterations necessary to ensure this, which improves previous results. Our upper bound decreases as the population size increases. We produce examples to show that in some cases this upper bound is asymptotically optimal for large population sizes. The final section discusses implications of these results for optimal coding of genetic algorithms.
引用
收藏
页码:269 / 282
页数:14
相关论文
共 14 条
[1]
[Anonymous], 1989, GENETIC ALGORITHM SE
[2]
[Anonymous], 1991, Handbook of genetic algorithms
[3]
AYTUG H, 1999, UNPUB INFORMS J COMP
[4]
Aytug H., 1996, ORSA J COMPUTING, V8, P183
[5]
AYTUG S, 1996, EUROPEAN J OPER RES, V96, P195
[6]
DEJONG KA, 1975, THESIS U MICHIGAN AN
[7]
The use of genetic algorithms in morphological filter design [J].
Harvey, NR ;
Marshall, S .
SIGNAL PROCESSING-IMAGE COMMUNICATION, 1996, 8 (01) :55-71
[8]
General Cardinality Genetic Algorithms [J].
Koehler, Gary J. ;
Bhattacharyya, Siddhartha ;
Vose, Michael D. .
EVOLUTIONARY COMPUTATION, 1997, 5 (04) :439-459
[9]
Nix A. E., 1992, Annals of Mathematics and Artificial Intelligence, V5, P79, DOI 10.1007/BF01530781
[10]
Salomon R, 1997, SOFTWARE-CONC TOOL, V18, P175