CONVERGENCE RATES FOR A CLASS OF EVOLUTIONARY ALGORITHMS WITH ELITIST STRATEGY

Abstract

Abstract:

This paper discusses the convergence rates about a class of evolutionary algorithms in general search spaces by means of the ergodic theory in Markov chain and some techniques in Banach algebra. Under certain conditions that transition probability functions of Markov chains corresponding to evolutionary algorithms satisfy, the authors obtain the convergence rates of the exponential order. Furthermore, they also analyze the characteristics of the conditions which can be met by genetic operators and selection strategies.

Key words: Convergence rate, Markov chain, Banach algebra, genetic operator, elitist selection, evolutionary algorithms

CLC Number:

DING Li-Xin, KANG Li-Shan. CONVERGENCE RATES FOR A CLASS OF EVOLUTIONARY ALGORITHMS WITH ELITIST STRATEGY[J].Acta mathematica scientia,Series B, 2001, 21(4): 531-540.

Trendmd

References

[1]Fogel D B. An introduction to simulated evolutionary optimization. IEEE Trans on Neural Networks,1994,(1): 3-14

[2]Xu Z B, Gao Y. Analysis of premature about genetic algorithms and prevention (in Chinese). Science in China (Series E), 1996,(4): 363-375

[3]Zhang J S, Xu Z B, Leung Y. Genetic algorithms of entirety annealing and their sufficient and necessary convergence conditions (in Chinese). Science in China (Series E), 1997,(2): 154-164

[4]He J, Kang L S. On the convergence rates of evolutionary algorithms. Theoretical Computer Science,1999, (1): 23-29

[5]Peng H, Wang X H. Estimate for the convergence rates of genetic algorithms with elitist strategy (in Chinese). Chinese Science Bulletin, 1997,(2): 144-147

[6]Suzuki J. A Markov chain analysis on simple genetic algorithms. IEEE Trans on Systems, Man, and Cybernetics, 1995,(4): 655-659

[7]Rudolph G. Convergence rate of evolutionary algorithms for a class of convex objective functions. Control and Cybernetics, 1997,(3): 375-390

[8]Rudolph G. Convergence rates of simple evolutionary algorithms under factorization mutation distributions. Proc 3th European Conference on Artificial Evolution, Berlin:Springer, 1998. 275-285

[9]Rudolph G. Local convergence rates of simple evolutionary algorithms with Cauchy mutations. IEEE Trans on Evolutionary Computation, 1998,(4): 249-258

[10]Xu Z B, Li G. Algorithms from imitating life for solving global optimization problems (I): simulating evolutionary algorithms (in Chinese). Journal of Operational Research, 1995,(2):1-13

[11]Rudolph G. Convergence analysis of canonical genetic algorithms. IEEE Trans on Neural Networks,1994,(1): 96-101

[12]Hu D H. Strong ergodic properties of Markov process in general space and its convergence rates (in Chinese). Acta Math Sinica, 1984,(3): 293-304

[13]Hu D H. Ergodic properties of Markov field and its couple (in Chinese). Acta Math Sinica, 1992,(4):505-515

[14]Rosenthal J S. Minorization conditions and convergence rates for Markov chain Monte Carlo. J Amer Statist Assoc, 1995, (4): 558-566

[15]Eiben A E, Aarts E H L, Van Hee K M. Global convergence of genetic algorithms: a Markov chain analysis.Lecture Note in Computer Science, No 496, Springer-Verlag, 1991. 4-12

[16]Rudolph G. Convergence Properties of Evolutionary Algorithms. Hamburg: Kov¨ac, 1997