Stochastic analysis and convergence velocity estimation of genetic algorithms

Abstract

Formulizations of mutation and crossover operators independent of representation of solutions are proposed. A kind of precisely quantitative Markov chain of populations of standard genetic algorithms is modeled. It is proved that inadequate parameters of mutation and crossover probabilities degenerate standard genetic algorithm to a class of random search algorithms without selection bias toward any solution based on fitness. After introducing elitist reservation, the stochastic matrix of Markov chain of the best-so-far individual with the highest fitness is derived. The average convergence velocity of genetic algorithms is defined as the mathematical expectation of the mean absorbing time steps that the best-so-far individual transfers from any initial solution to the global optimum. Using the stochastic matrix of the best-so-far individual, a theoretic method and the computing process of estimating the average convergence velocity are proposed.

Keywords

genetic algorithm / operator formulization / Markov chain / convergence velocity

References

[1] HollandJ HAdaptation in nature and artificial systems[M], 1992, Cambridge, The MIT Press

[2] BäckTWhitleyD, VoseM. Order statistics for convergence velocity analysis in simplified evolutionary algorithms [A]. Foundations of Genetic Algorithms[C], 1995, San Mateo CA, Morgen Kaufmann: 91-102

[3] BäckTMännerR, ManderickB. The interaction of mutation rate, selection and self-adaptation within a genetic algorithm [A]. Parallel Problem Solving from Nature [C], 1992, Amsterdam, Elsevier: 85-94

[4] RudolphG. Convergence analysis of canonical genetic algorithms [J]. IEEE Transactions on Neural Network, 1994, 5(1): 96-101

[5] SuzukiJ. Markov chain analysis on simple genetic algorithms [J]. IEEE Transactions on System, Man and Cybernetics, 1995, 25(4): 655-659

[6] ReynoldsD, GomatamJ. Stochastic modelling of genetic algorithms [J]. Artificial Intelligence, 1996, 82: 303-330

[7] GoldbergD E, DebKRawlinsG J E. A comparative analysis of selection schemes used in genetic algorithms [A]. Foundations of Genetic Algorithms [C], 1991, San Mateo CA, Morgen Kaufmann: 69-91

[8] ZhangB T. Comparison of selection methods for evolutionary optimization [J]. Evolutionary Optimization, 2000, 2(1): 55-70

[9] SenDing-xuanStochastic process (in Chinese) [M], 1990, Wuhan, Press of Huazhong University of Science and Technology