资源描述：
《旅行商问题研究及混合粒子群算法求解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、旅行商问题研究及混合粒子群算法求解382009,45(25)ComputerEngineeringandApplications计算机工程与应用旅行商问题研究及混合粒子群算法求解孙聪,赵新超SUNCong,ZHAOXin-chao北京邮电大学理学院数学系,北京100876DepartmentofMathematics,SchoolofScience,BeijingUniversityofPostsandTelecommunications,Bering100876,ChinaE-mail:suncong@lsec.ac.cnSUNCong,ZHAOXin-c
2、hao.Researchontravelingsalesmanproblemanditssolvmgthhybridparticleswarm0一mizationalgorithm,ComputerEngineeringandApplications,2009,45(25):38-40.Abstract:ThispaperquMitativelyanalyzesthebasicParticleSwarmOptimization(PSO)algorithm.Integratingtheideasofgeneticalgorithm.3kindsofcrosso
3、verand4mutationoperatorsareconstructedand12hybridPSOalgorithmsareobtained.A14-cityproblemisfirstlyusedtoexamineandanalyzetheproposedalgorithms.Tofurtherverifytheproposedalgorithms'performance,severalgoodhybridalgorithmsareselectedbasedontheanalyticresultstosolvetheChinese34一citypro
4、blem(CTSP)andthekroClO0problem.TheoptimalsolutionisquicklyobtainedforCTSPinstanceandanevenbettersolutioncomparedwiththerecentalgorithmsisobtainedforkroC100instance.Keywords:travelingsalesmanproblem;ParticleSwarmOptimization(PSO);2-opt;3-opt;geneticalgorithm摘要:定性地分析了基本粒子群算法,结合遗传算法思想
5、,构造了3种杂交和4种变异运算法则,从而得到了12种混合粒子群算法,并采用14城市算例对其检验和分析.为进一步验证混合算法的性能,根据分析结果挑选了几种较优的混合算法用以解决中国34城市(CTSP)问题和kroC100问题,其中CTSP问题很快达到最优解,对kroC100问题该文提供的算法获得了一个比现有已知结果更好的结果.关键词:旅行商问题;粒子群算法;2一opt;3-opt;遗传算法DOI:10.3778/j.issn.1002—8331.2009.25.012文章编号:1002—8331(20o9)25—0038—03文献标识码:A中图分类号:TP30
6、2.7l引言旅行商问题(P)的具体描述如下:给定//,个城市及两两城市之间的距离,求一条经过各城市一次且仅一次的最短环线.旅行商问题的求解算法主要包括确定性算法和非确定算法,由于TSP问题是典型的NP问题f",所以现代启发式算法就显示出其优越性,比如遗传算法,蚁群算法,模拟退火算法和禁忌表算法等.粒子群算法(PS0)最早由Kennedy和Eberhart提出圆,基本原理源于对鸟群捕食行为的仿真.基本粒子群算法多用于连续空间.Clere曾针对TSP问题的求解重新定义粒子的位置,速度和相关的运算,构造了离散粒子群算法.由于缺少对离散量与连续量运算规律不同的考虑,
7、仿真结果与其他算法相比仍有较大的差距【3】.高尚等H】在粒子群算法中加入遗传算法思想构造了混合算法,徐俊杰等[sl提出了一种基于两阶段策略的粒子群优化,蔡荣英等啕提出了一种带有自学习算子的粒子群算法.2混合粒予群算法2.1构造思想PSO初始化为一群随机粒子(随机解),通过迭代找到问题的最优或满意的解.在每次迭代中,粒子通过跟踪粒子本身所找到的最优解(个体最优解)和整个种群目前找到的最优解(全局最优解)更新自己.每个粒子根据如下公式更新自己的速度和新的位置印:l(t+1)=f(t)+c1?rl?(p广{(￡))4-C2?r2?(pg-f())'(t+1)=;f
8、(t)+f(+1)(t)为第i个粒子t时刻的速度,(
