王　东,归伟夏

(广西大学计算机与电子信息学院, 广西南宁530004)



基于交叉亲和度评价的多种群遗传算法

王东,归伟夏

(广西大学计算机与电子信息学院, 广西南宁530004)

摘要：为进一步解决传统多种群遗传算法进化过程中迅速丧失种群多样性，导致的易早熟、收敛到局部最优解等问题，提出一种基于交叉亲和度评价的多种群遗传算法，采用多种群并行搜索的思想，结合模拟退火算法提高算法的搜索能力，种群之间通过交叉推优选出的交流个体,进行亲和度评价替换目标种群个体来完成交流。通过对TSP问题的求解表明，算法得到的解都接近最优解，性能优于传统多种群遗传算法。

关键词:遗传算法；交叉亲和度评价；模拟退火；多种群

0引言

遗传算法(genetic algorithm，GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的一种随机方法，由美国学者Holland教授[1-2]于1975年首次提出。由于GA在解决连续变量的函数优化问题中表现出来很好的鲁棒性、自适应性和隐含并行性，因此应用十分广泛[3-4]。然而遗传算法也存在很多问题，如计算代价太高，收敛速度缓慢，种群不能很好的覆盖搜索区域以及易陷入局部最优解等问题。

多种群并行遗传[5]是近年来所提出的改进遗传算法中性能较好的一种方法。其基本思想是用多个子种群代替原单一种群，使种群很好地覆盖搜索区域并使算法的搜索效率得到质的提高，每个子种群按不同的进化策略、遗传算子并行进化，并通过子种群间交换信息(一般为最优个体)来增加基因模式数，这样处理可以选取和保留每个子种群的优秀个体，在保持优秀个体进化稳定性的同时，加快进化速度，避免未成熟收敛。……