基于粒子群的TSP问题的研究

1基于粒子群的TSP问题的研究摘要：在传统求解TSP问题的算法中，都有其各自局限性，诸如陷入局部极小或收敛过慢，针对这一问题提出利用PSO一定程度上改善以上问题，传统的PSO算法只能求解连续性问题，因此引入交换序，使得PSO可以处理TSP这类离散问题，通过matlab软件仿真，实验证明改进后的PSO解决TSP问题是比较有效的。关键词：PSO；TSP；交换序；matlabResearchonTSPproblembasedonPSO(NanchangUniversityInformationEngineeringSchoolofcomputerscienceandtechnologyHuTao406130914127)Abstract:ThispaperstudiestheTSPproblemsolvingTSPprobleminthetraditionalalgorithm,hasitsownlimitations,suchasfallingintolocalminimumandslowconvergence,inordertosolvethisproblemisproposedtoimprovetheaboveproblemsusingPSOinacertainextent,PSOalgorithmcanonlysolvethetraditionalcontinuity,thereforeintroducingexchangeorder,sothatthePSOcantreatmentofTSPthiskindofdiscreteproblems,throughtheMATLABsoftwaresimulation,theexperimentprovesthattheimprovedPSOtosolveTSPproblemsiseffective.Keywords:PSO;TSP;switchingsequence;matlab0引言旅行商问题（TravellingSalesmanProblem）是一个经典的NP难组合优化问题，假如一个旅行商要经过n个城市，他要选择行走城市的顺序，使所有城市都走过一次，最后回到原点，求一条最短的线路。蚁群算法是由意大利学者在上世纪90年代提出的一种智能优化算法，随即被应用到解决TSP问题，通过信息素的不断更新最终收敛于最优解，但由于初级阶段的信息素缺乏，面对庞大数据时收敛速度过慢，而且人为的参数设定也会影响收敛的结果，其他诸如遗传算法、免疫算法都存在一定的局限性。粒子群算法（ParticleSwarmOptimization），简称PSO算法，是由美国心理学家JamesKennedy和电器工程师RussellEberhart于1995年提出的一种全局优化算法，本文利用改进后的粒子群算法来求解TSP问题,实验通过引进交换子和交换序使得PSO算法可以解决离散的TSP问题，展现其实现容易、精度高、收敛快的特点。1TSP问题有n个城市，一个旅行商从某个城市出发，遍历所有城市后回到出发点，求一条经历所有城市且仅一次的最短遍历路径。给定加权图),(EVG，其中},,2,1{nv表示结点（城市）的集合，给定},,|{RwVjiwEijij为赋权边（表示两个城市的距离）的集合；路径可以表示为},,,,{121iiiin其中121,,,,iiiin为},,2,1{n的一个n元轮换。记GGH为)(中所有路径的集合，即2111)(vvnivvnjiwwsw目标是寻找一条最短的路径*S使)(),(min)(*GHSSwSw其中2标准PSO算法粒子群算法（简称PSO）是源于对鸟群觅食过程中的迁徙和群居的模拟，在粒子群算法中，个体被看着是在D维搜索空间中没有重量和体积的粒子，并以一定的速度飞行。假设粒子的总数为m,粒子的初始位置和速度随机产生然后按照（1）、（2）、（3）和（4）进行迭代计算，直到满足条件。)f(p)f(xIf)f(p)f(xIfkiki1kiki1kikikixpp（1）)}(),(),(min{arg21kmkkkgpfpfpfp（2）)()(22111kikgkikikikixprcxprcwvv（3）11kikikivxx（4）其中ip为粒子i所经历的最好位置，ix为粒子i当前的位置，gp是整个粒子群中最好的位置，iv为粒子i当前的飞行速度，)(xf为粒子群的适应值函数，w为权重参数，1c表示对自身的学习因子，2c表示对群体的学习因子，1r和2r为1,0之间的随机数。标准粒子群的流程图可表示为：图1标准粒子群算法流程图33粒子群算法的改进对于TSP问题的求解，显然不能直接使用标准的粒子群模型，标准的粒子群算法只能解决连续性的问题，求解离散性问题必须将标准粒子群算法改进，引入交换子和交换序以后就可以用粒子群算法处理TSP问题了。定义1：设n个节点的TSP解序列niasi,,2,1),(，表示该问题的行走路径，定义交换子),(21iiss为交换解中的.21iiaa和定义2：一个或多个交换子的有序序列为一个交换序，记为),,(21nssss，其中nsss,,,21是交换序子，它们满足结合性。例如：nsssssss])[(2100'，而且可以得出0'sss定义3：不同的交换序作用在同一解上可能产生相同的新解，所有相同效果的交换序的集合称为交换序的等价集。根据定义，位置—位置表示一组交换序，也就是速度；实数速度表示去交换序中前k个整数的交换子，位置+速度是更新位置。改进后的粒子更新的公式如下：)()(211kidkgdkidkidkidkidxpcxpcvv（5）11kidkidkidvxx（6）其中]1,0[,的随机数，取8.021cc。求解TSP问题的粒子群算法步骤：1）初始化位置和交换序；2）检查循环条件，若不满足转5）；3）计算交换序；4）根据适应度更新idp、gdp和每一个粒子的状态，转步骤2）；5）显示结果。4实验仿真本实验选取15个城市来进行实验，表1坐标表示城市的位置，用欧氏距离来度量它们之间的距离，用matlab软件进行仿真，取粒子数目400m，最大迭代次数为300，如图1分别表示迭代次数为300的仿真图像，图3表示收敛过程的距离，最终TSP问题的最优解为)7,13,14,4,15,8,2,1,9,3,6,11,10,5,12(，它们之间的总距离为54.8319，即旅行商按412713144158219361110512顺序行走路程是最短的，最短距离是54.8317，由图3可知本实验收敛速度较快，性能较好。表115个城市的位置城市1234567x坐标70.0073.5275.3271.3579.5080.0076.32y坐标70.0075.3273.5278.9679.5070.0078.428910111213141571.2174.0177.7778.8380.4674.4672.5368.0075.0069.0175.6275.3281.0381.0378.6476.12图2迭代300次的图形图3显示收敛过程的距离5结论本文通过引入交换子和交换序，使粒子群算法可以用来解决离散性问题，由上述实验可知，改进后的粒子群算法不仅可以较快的求解TSP问题，而且可以用到更多关于离散型问题的求解，如背包问题，由此可见，这是一个有效且易实现的算法，但是它也存在容易陷入局部最优的弊端，产生停滞现象，解决这个问题比较有效的办法是利用贪心法或者k-means聚类算法预先求出一组接近最优解的解作为迭代的初始条件，这样可以大大降低陷入局部最优的概率，由于时间关系，本文不做详细讨论。5参考文献[1]高芳等.智能粒子群优化算法研究.计算机系统结构，2008；24-16[2]张江维等.粒子群优化算法在TSP中的研究及应用[J].计算机应用技术,2008:35-36[3]卞锋等.粒子群优化算法在TSP中的研究及应用[J].计算机应用技术,2008:35-36[4]刘一飞等.求解旅行商问题的一种改进的粒子群算法[J].运筹与管理,2010:23-25[5]孙辉等.基于不同行为的两分群交换粒子群优化算法[J].人工智能，2010:36-07[6]孙明雪等.一群算法的改进及其在TSP中的应用.计算机应用技术，2004:56-12[7]宋志飞等.基于蚁群算法的TSP问题的研究.计算机应用技术，2013；23-11[8]刘建华.粒子群算法的基本理论及其改进研究.控制科学与工程，2009；67-32[9]陈小全等.基于改进粒子群算法的聚类研究.计算机科学与技术，2012；35-12[11]张长春，苏昕等粒子群算法和蚁群算法的结合及其在组合优化中的应用.计算机应用技术，2007,02-01[12]谭浩等.一种基于子群杂交机制的粒子群算法求解旅行商问题[J].系统工程，2005：86[13]张旭梅等.基于k-中心点法的改进粒子群算法在旅行商问题中的应用.工商管理[14]徐玉杰,刘清.粒子群算法的改进及应用.计算机软件与理论,2013[15]熊伟等.求解TSP问题的增强型自探索粒子群算法[J].华北电力大学学报,2009:70-73