Using Markov Chains to Analyze a Bounding Case of Parallel Genetic Algorithms

This paper uses Markov chains to analyze the search quality of a bounding case of parallel genetic algorithms with multiple populations. In the bounding case considered here, each population exchanges individuals with all the others. First, the migration rate is set to the maximum value possible, and later the analysis is refined to consider lower migration rates. In the algorithm examined by this paper, migration occurs only after each population converges. Then, incoming individuals are incorporated into the populations and the algorithm restarts. The analysis shows how to calculate the probability that each population will eventually converge to the correct solution, and the expected number of migration-restart events until all the populations converge to the same solution