Parallelization of Genetic Algorithms and Application to Multi-objective Optimization Problem


Abstract

In this paper, I investigated about the island parallel GA, one of the parallelization methods of GAs. The island parallel GA divides its population into plural subpopulations and assigns them to processing elements on a parallel computer. Each subpopulation searches for the optimal solution independently, and maintains its diversity of genes by exchanging individuals periodically with certain conditions. This operation is called migration. The setting of migration operation is the most important for island parallel GA. To implement this migration operation, there are two possibilities, synchronously exchange individuals, synchronously migration model, and asynchronously exchange individuals, asynchronously migration model. Synchronous migration operation is started among subpopulations simultaneously according to fixed interval called migration interval. If individuals called migrants are introduced before the search converged, it is difficult to generate superior schemata because good schemata will be destructed. Thus it is effective to introduce individuals after the search converged. However, the progress of the search situation differs both the objective problems and every subpopulation, and it makes difficult to set optimal migration interval. So I expected that asynchronous migration was more effective than synchronous migration. In this paper, I proposed a new migration method that operates asynchronously migration according as the search situation in each subpopulation. I investigated about asynchronous migration suitable for single and multi-objective function optimization, and for binary and real-coded GAs. I confirmed the effectiveness of the island parallel GA for multi-modal function optimization by applying to multi-modal function optimization problem. The proposed migration method worked effective at strong multi-modality problem, so I revealed that proposed migration method promotes the special feature of the island parallel GA. Usual optimization method such as the hill-climbing method is bad at multimodal function optimization. So this result shows that my method is effective at the problems, which need for GA. Moreover 1 evaluated my method by applying for a test problem based on the building block hypothesis, which explains the mechanism of optimization by GA. I revealed that each subpopulation searches different schema and generates higher ordered schema by combining the lower ordered schema in the subpopulation and the other schema, which introduced from the other subpopulations. The super linear speedup of the calculation time was obtained at multi-objective optimization problem by reducing the ranking operation's calculation time.