基于空间交配遗传算法的收敛性分析  

Convergence Analysis of Genetic Algorithm Based on Space Mating

作　　者：郑金华[1] 吕卉[1] 伍军[1] 周聪[1] 李珂[1] 李密青[1] 

机构地区：[1]湘潭大学信息工程学院,湘潭411105

出　　处：《模式识别与人工智能》2010年第5期639-645,共7页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.60773047);湖南省教育厅重点科研项目(No.06A074);湖南省教育厅一般项目(No.07C752)资助

摘　　要：基于空间交配遗传算法(GASM)采用空间交配遗传算子,有效克服早熟收敛问题,但缺少相关理论分析.文中采用马尔可夫链分析基于空间交配遗传算法的收敛性.证明采用最优个体保留机制的GASM,可收敛到全局最优解.同时证明在没有变异算子的情况下,GASM以概率1收敛到全局最优解.通过4个测试问题(其中3个为多峰值复杂问题)的对比实验,结果表明,GASM在求解多峰值复杂问题时,比采用最优个体保留机制的经典遗传算法,具有更好的收敛性.同时也与快速蜂群优化算法进行比较实验.The genetic algorithm based on space mating （GASM） with space mating operator overcomes the premature convergence effectively, but it lacks theoretical analysis. In this paper, the convergent properties of the genetic algorithm based on space mating are analyzed by homogeneous finite Markov chain. It is proved that the GASM with the elitist mechanism can converge to the global optimum, and the GASM can converge to it with probability one on the condition of no mutation operator. By comparing the experimental results of four test problems, in which three of them are multi-peak complex issues, it is shown that the convergence of GASM is better than that of the genetic algorithm with the elitist mechanism, namely elitist genetic algorithm （EGA） in solving the multi-peak complex problems. The algorithm is compared with the algorithm of fast marriage in honey bees optimization as well.

关 键 词：空间交配 遗传算法 快速蜂群优化算法 马尔可夫链 收敛性 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]