粗粒度并行遗传算法收敛性分析及优化运算  

Convergence Analysis of Coarse-Grained Parallel Genetic Algorithm and Its Application to Optimization

作　　者：戴晓明[1] 陈昌领[1] 邵惠鹤[1] Kay Das 程铁鹏 茅雪飞[1] 

机构地区：[1]上海交通大学自动化研究所,上海200030 [2]意法半导体亚太研究发展中心,新加坡117674

出　　处：《上海交通大学学报》2003年第4期499-502,共4页Journal of Shanghai Jiaotong University

基　　金：国家重点基础研究发展(973 )项目 ( G19980 3 0 415 )

摘　　要：提出了一种新型的粗粒度并行遗传算法 ( CGGA) ,该算法利用多个子种群基于不同的编码方式进行进化计算 .首先各子群体独立进行交叉、变异和选择遗传操作 ,每代进化后迁移算子被引入用来进行种群间的信息交流 ,迁移算子将各个子种群的最优个体替换相邻种群最差个体后继续进化 .基于时齐遍历马尔可夫链理论 ,给出了 CGGA各个子种群的概率转移矩阵与其进化概率转移矩阵 ,证明了以概率 1全局收敛 .对典型的测试函数 CGGA进行了求解 .仿真结果表明 ,本算法的收敛性能优于经典遗传算法 ( CGA) ,可以有效解决Coarse-grained parallel genetic algorithm(CGGA) applies multi-population to optimize the objective problem. Different population is based on different coding schemes. The migration factor is introduced to the CGGA. The respective population's elite individual replaces the neighboring population's worst individual. The search process of CGGA is an ergodic homogeneous Markov chain. The global convergence proof of CGGA was presented. The simulation on the benchmark problems shows that the CGGA achieves better convergence performance than canonical genetic algorithm(CGA). The inherent premature convergence problem can be greatly levied by the CGA.

关 键 词：粗粒度并行遗传算法 时齐遍历马尔可夫链 全局收敛 经典遗传算法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]