Hierarchical Fair Competition Model for Parallel Evolutionary Algorithms.pdf

The Hierarchical Fair Competition (HFC) Model for Parallel Evolutionary Algorithms Jian Jun. Hu hujianju@cse.msu.edu Department of Computer Science and Engineering Michigan State University East Lansing, MI 48824 Erik D. Goodman goodman@egr.msu.edu Genetic Algorithms Research and Applications Group Michigan State University 2857 W. Jolly Rd., Okemos, MI 48864 Abstract -The HFC model for evolutionary computation is inspired by the stratified competition often seen in society and biology. Subpopulations are stratified by fitness. Individuals move from low-fitness subpopulations to higher-fitness subpopulations if and only if they exceed the fitness-based admission threshold of the receiving subpopulation, but not of a higher one. HFC’s balanced exploration and exploitation, while avoiding premature convergence, is shown on a genetic programming example. I. INTRODUCTION One of the central problems in evolutionary computation is to combat premature convergence and to achieve balanced exploration and exploitation. In a traditional GA, selection pressure must not overwhelm the diversity-increasing operators (mutation and, to some extent, crossover) or premature convergence is likely to occur. As the evolutionary process goes on, the average fitness of the population gets higher and higher, and then only those new individuals with similarly high fitness tend to survive. New “explorer” individuals in fairly different regions of the search space usually have low fitness, until some local exploration and exploitation of their beneficial characteristics has occurred. So a standard EA tends to concentrate more and more of its search effort near several discovered peaks, and to get “stuck” in these local optima (we use here the language of continuous, real-valued function optimization, but more generally, the concept of “attractors” can instead be used). Many variations [1,2,3,4,5,6] on traditional GA’s and especially many