Noahs Ark Strategy for Avoidance of Excess Convergence by a Parallel Genetic Algorithm with an Object-shared Space
In a genetic algorithm (GA), the undesirable phenomenon of excess convergence can often occur.Excess convergence is the phenomenon where the diversity of a group is lost. This phenomenon occurs because homogeneous individuals are increased rapidly in the group while evolving or searching. Therefore,crossover loses its function. Once the excess convergence occurs, the search by the GA becomes meaningless.Therefore, it is important to avoid excess convergence and maintain diversity. First, we show an implementation of a parallel GA based on a multiple-group-type island model,that uses object-shared space. Next, as a simple, effective method for avoiding excess convergence, we propose a diversity maintenance technique based on selection of the homogeneous individuals called the Noahs ark strategy for parallel GAs, and demonstrate its effectiveness on a knapsack problem. Our proposed method is to replace individuals in sub-groups that have excessively converged with the new individuals coming from the search space.That is, we avoid excess convergence by expelling homogeneous individuals, with the exception of one elite individual (that we call for Noah). Thus, we limit a decrease in diversity of an entire group.
genetic algorithm (GA) parallel GA excess convergence object-shared space replicated-worker pattern distributed parallel processing and knapsack problem
Ichiro Iimura Shinya Ikehata Shigeru Nakayama
Department of Information and Computer Science, Faculty of Engineering,Kagoshima University, 1-21-40, Korimoto, Kagoshima 890-0065, Japan
国际会议
成都
英文
527-531
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）