Performance Comparison between Parallel GA Based on Linkage Identification and Parallel Bayesian Optimization Algorithm

摘要

Genetic Algorithms (OAs) are considered robust optimization algorithms which can solve wide-spectrum of difficult problems such as combinatorial optimization problems. Still, there are some GA-difficult problems which cannot ensure tight linkage in encoding strings. In such problems, crossovers cannot perform effectively on loosely encoded strings due to building block disruptions. Recently, a series of advanced techniques in evolutionary computations have been proposed to solve such GA-difficult problems. As one of these techniques, linkage identification checks nonlinearity caused by bit-wise perturbations for pairs of loci. Another advanced technique is Estimation of Distribution Algorithms (EDAs) which estimates probabilistic distribution for populations, and the Bayesian Optimization Algorithm (BOA) is the most sophisticated method in the EDAs. These methods can solve GA-difficult problems, paying additional computational cost. Therefore, parallel versions of these techniques, parallel GA based on linkage identification and parallel BOA, are studied to reduce computation time. In this paper, we compare performance of the parallel GA based on linkage identification with that of parallel BOA in actual parallel computing environment From the results, we consider relations between performance of the algorithms and the characteristics of the problems to be solved. Finally, we make discussions on the problem domains which algorithm performs more efficiently.