A CUDA-based Self-adaptive Subpopulation Model in Genetic Programming: cuSASGP

A parallel model encourages genetic diversity and frequently shows a better search performance than do single population models. In the parallel model, individuals generally migrate to another subpopulation based on their fitness values, where both the number of individuals in each subpopulation and the topology are fixed. To enhance the parallel model in the framework of genetic programing (GP), it is important to consider a balance between local and genetic search. The incorporation of a local search method into the parallel GP model is a promising approach to enhancing it. In GP, individuals have various features because of their structures, and therefore, it is difficult to determine which feature is the most effective for local search. Therefore, we propose a novel adaptive subpopulation model based on various features of individuals in each generation, in which subpopulations are adaptively reconstructed based on a fitness value and the distance between individuals. The proposed method automatically generates a correlation network on the basis of the difference between individuals in terms of not only a fitness value but also node size and generates subpopulations by network clustering. By virtue of the reconstruction, individuals with similar features can evolve in the same subpopulation to enhance local search. Since, on the one hand, the generation of a correlation network of individuals requires considerable computational effort, and on the other, calculating correlation among individuals is very suitable for parallelization, we use CUDA to construct a correlation network. Using three benchmark problems widely adopted in studies in the literature, we demonstrate that performance improvement can be achieved through reconstructing subpopulations based on a correlation network of individuals, and that the proposed method significantly outperforms a typical method.