Stochastic analysis and convergence velocity estimation of genetic algorithms

来源期刊：中南大学学报(英文版)2003年第1期

论文作者：郭观七 喻寿益

文章页码：58 - 63

Key words：genetic algorithm; operator formulization; Markov chain; convergence velocity

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.