Analyses of Simple Genetic Algorithms and Island Model Parallel Genetic Algorithms

H. Asoh and H. Mühlenbein investigated empirically the relation among the mean convergence time, the population size, and the chromosome length of genetic algorithms (GAs). In this paper, from the mathematical point of view, the relation they revealed is convincing. Our analyses of GAs make use of the Markov chain formalism based on the Wright-Fisher model, which is a typical and well-known model in population genetics. We also give the mean convergence time under genetic drift. Genetic drift can be described by the Wright-Fisher model. We determine the stationary states of the corresponding Markov chain model and the mean convergence time to reach one of these stationary states. Furthermore, we derive the most effective mutation rate for the standard GAs and also the most effective migration rate for the island model parallel GAs with some restrictions. These rates are coincide with known empirical results.