摘要： 经典遗传算法(Canonical Genetic Algorithms)利用单一种群对种群个体进行交叉、变异和选择操作,在进化过程中的超级个体易产生过早收敛现象,粗粒度并行遗传算法利用多个子种群进行进化计算,各子群体分别独立进行遗传操作,相互交换最优个体后继续进化。该文证明了该算法的搜索过程是一个有限时齐遍历马尔柯夫链,给出粗粒度并行遗传算法全局最优收敛性证明。对于旅行商问题TSP(Traveling Salesman Problem)利用粗粒度并行遗传算法进行了求解,以解决经典遗传算法的收敛到局部最优值问题。仿真结果表明,算法的收敛性能优于经典遗传算法。

关键词: 粗粒度并行遗传算法, 有限时齐遍历马尔柯夫链, 收敛, TSP

Abstract: Canonical genetic algorithm applies a single population to optimize the functions. The super-individual during the early stage of evolving process can cause pre-maturity phenomenon. Coarse-grained Genetic Algorithm (CGGA) applies multi-population to optimize the objective problem. Different population evolves independently. The migration factor is introduced to the CGGA. The elite individual replaces the neighboring populations worst individual. The search process of CGGA is an ergodic homogeneous Markov chain. The global convergence proof of CGGA is presented in this paper. The NP-hard Traveling Salesman Problem (TSP) is cited as the benchmark problem to test the efficacy of the CGGA. The simulation result shows that CGGA holds faster convergence speed than the Canonical Genetic Algorithm(CGA).The inherent pre-mature problem can be greatly levied by CGGA.

中图分类号: 

• TP18