An Evaluation of the Asynchronous Island Parallel GA
Hirosuke Horii, Susumu Kunifuji, Teruo Matsuzawa · Transactions of the Society of Instrument and Control Engineers · 1999
There are two typical problems in Genetic Algorithms (GAs). First, GAs require huge calculation time for the genetic operations, such as selection, crossover, mutation, and individuals' fitness evaluations. Secondly, maintenance of the diversity of the population is necessary to avoid the premature convergence which spreads local optimum solution and stagnates the evolution. Island Parallel GAs divide a population into subpopulations and assign them to processing elements on a parallel computer in order to improve the processing speed. Each subpopulation searches for the optimal solution independently, and exchanges individuals periodically in order to maintain the diversity of each subpopulation. This exchange operation is called migration. In this research, we propose a new migration scheme. Individuals are exchanged among subpopulations asynchronously according to each subpopulation's search situation. The effect of the new migration scheme on the combinational optimization problems was verified by applying our algorithm to Knapsack Problems and Royal Road Functions using a parallel computer CRAY-T3E. Through these experiments, the following results were obtained. The migration scheme proposed in this research is effective for the combinational optimization problems. Especially, when our algorithm is applyed to the problem which has strong tendency of building block hypothesis, our algorithm performs effectively by the parallel search of the building blocks.