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

摘要

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