Implementation of Elitism in Cellular Genetic Algorithms
Hisao Ishibuchi, Ken Ohara, Yusuke Nojima · 2007
Elitism often has a large effect on the search ability of evolutionary algorithms. Many studies, however, did not discuss its implementation in cellular algorithms where a population of individuals is spatially distributed over a two-dimensional grid-world. In this paper, we examine two implementation schemes of elitism in cellular algorithms. One is global elitism where a number of the best individuals in the entire population are viewed as elite. The other is local elitism where an individual is viewed as elite when it is the best individual among its neighbors. Effects of elitism on the behavior of cellular algorithms are examined through performance evaluation, takeover time analysis, and diversity analysis. We use a cellular genetic algorithm with two neighborhood structures. One is for local competition among neighbors (e.g., fight for water and sunlight in the case of biological evolution of plants). The definition of local elitism is based on this competition neighborhood. The other is for local selection of parents from neighboring individuals. Since we have these two different neighborhood structures, we can specify the size of local competition for elitism independently of the size of local selection. Experimental results show that the choice of an implementation scheme of elitism has a dominant effect on the performance of our cellular genetic algorithm while it has only a slight effect on the takeover time. Good results are obtained under local elitism when the selection neighborhood is larger than the competition neighborhood. This relation in the size of the neighborhood structures coincides with many cases in biological evolution in nature such as plants and territorial animals.