The Unified Method Analyzing Convergence of Genetic Algorithms

This paper models the homogeneous finite Markov chain of the best individuals in the populations. Based on the limit distribution of transition probability that any state on the chain transfers into the state subset containing all global optima, a precise definition of the global convergence of genetic algorithms is presented regardless of the topologic structures of search landscapes. Two unified criterion theorems judging the global convergence are proposed and proved strictly, which are independent of encoding schemes and selection mechanisms. The results of analyzing the convergence of different genetic algorithms illustrate that the unified criterion theorems are generally practical and convenient.