摘要： 在扩展分布式遗传算法(EDGA)的基础上提出了一种新的基于最优解收集的扩展式并行遗传算法(EPGA)。在该算法中，群体被划分为子群分配给各子处理单元(PE)计算，根处理器则在采用全局搜索策略进行搜索的同时，不断地从各子处理单元上收集局部最优解替换当前群体以获取较好的最优解。该算法采用子群的概念去获得较好的加速比，采用全局搜索策略的概念去获得较好的最优解，同时具有EDGA不具有的许多优点。给出了该算法针对经典的TSP问题的非阻塞MPI实现。实验表明该算法可以有效地提高遗传算法的加速比及增加获得最优解的概率。

关键词: 扩展式, 并行, 遗传算法, 最优解收集

Abstract: On the basis of extended distributed genetic algorithm(EDGA), this paper presents a new algorithm, extended parallel genetic algorithm (EPGA) based on optimum result collecting. In this algorithm, a group is partitioned into some subgroups, and the subgroups are allocated to each processor element (PE) to compute. Root processor runs genetic algorithm using a global searching strategy. In the mean time it replaces current groups by the optimum results collected from each PE. Compared with EDGA, this algorithm has more advantages. It implementes EPGA using non-blocking MPI and evaluates its performance by solving traveling salesman problem (TSP). The experiments prove this algorithm can improve the speed up and probability of finding the optimum result in genetic algorithm.

Key words: Extended, Parallel, Genetic algorithm, Optimum result collecting

中图分类号: 

• TP312