基于寄生行为的混合粒子群算法及其在TSP中的应用

作     者：潘唯 

作者单位：安徽工业大学 

学位级别：硕士

导师姓名：汤亚玲;秦锋

授予年度：2015年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：旅行商问题 寄生行为 遗传算法 粒子群算法 

摘      要：旅行商问题(Traveling salesman problem,TSP)是著名的NP难题,同时也是组合优化中的一个典型问题。随着城市数目的增多,TSP的复杂度变大,求解难度也在不断提高,普通的算法已经难以适用于大规模TSP实例,因此,我们迫切需要一种高效率、智能化的优化方法。粒子群优化算法是仿真鸟群在觅食过程中活动规律和运动轨迹的一种智能算法,从随机产生的一组候选解开始搜索,通过粒子间的交互和协调进行迭代,直到找到或逼近最佳位置,完成寻优目标。为更好地解决旅行商问题,本文对粒子群优化算法的基本理论与相关应用进行研究与分析,提出一种基于寄生行为的混合粒子群算法(Hybrid particle swarm optimization based on parasitic behavior,HPSOPB)。该算法主要思想是将粒子群划分为寄生群和宿主群,通过种群间定期交换粒子的寄生行为实现协同进化进行全局寻优,并在两个子种群中分别使用不同的进化策略,以促进彼此的搜索进度。在宿主群中,为优化迭代效果,粒子可根据进化情况自主学习寄生群最优粒子的经验;在寄生群中,结合了遗传思想,为提高算法搜索能力保证种群多样性设计了适用于TSP的基于最短邻居集交叉算子和基于适应度方差的变异算子。理论研究证明,HPSOPB算法对应的随机过程是吸收态马尔科夫过程,且算法具有全局收敛性。最后,将HPSOPB算法应用到TSP中,通过3个TSP测试实例仿真比较HPSOPB算法与其他进化算法的寻优效果,结果表明,该算法搜索到的路径更优,且收敛到最终解所需迭代次数较少。