资源描述：
《基于改进的粒子群优化算法求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、基于改进的粒子群优化算法求解TSP问题//.paper.edu-1-中国科技论文在线基于改进的粒子群优化算法求解TSP问题沐爱勤1,2，张瑞平1*作者简介：沐爱勤(1978-),女,讲师，硕士，主要研究方向：计算数学，智能优化算法（1.中国矿业大学理学院，江苏徐州221000；2.徐州空军学院基础部，江苏徐州221000）摘要：粒子群优化算法是一种新型的优化算法，主要应用于连续优化问题，本文通过引入移动算子和移动序的概念，使粒子群优化算法能够处理离散问题。将改进算法与邻域相结合应用于旅行商问题的实验表明该算法在求解组合优
2、化问题上的有效性。关键词：移动算子；粒子群；旅行商问题中图分类号：TP301SolvingTravelingSalesmanProblemBasedonImprovedParticleSwarmOptimizationAlgorithmMuAiqin1,2,ZhangRuiping1(1.CollegeofScience,ChinaUniversityofMining&Technology,XuZhou,221000;2.FoundationDepartments,XuzhouAirForceAcademy,Xu
3、Zhou,221000)Abstract:PSOisanewoptimizationalgorithmwhichisappliedincontinuousoptimizations.ThispaperdiscussesthediscreteproblembyusingPSOwiththenotionofmobileoperatorsandmobilesequence.CombingtheimprovedPSOandneighborhoods,theexperimentsoftravelingsalesmanproblem
4、showthealgorithm’seffectivenessinsolvingthecombinatorialoptimizationproblem.Keywords:mobileoperators;ParticleSwarmOptimization(PSO);TravelingSalesmanProblem(TSP)0．引言粒子群算法（PSO）[1]是由心理学家Kennedy和Eberhart博士在1995年共同提出的一种新的模仿鸟群行为的智能优化算法。与其它优化算法相比，粒子群算法思想直观、实现简单而且具有很高的执
5、行效率，目前已经广泛应用于函数优化，神经网络训练，模糊系统控制以及其它应用邻域。旅行商问题（TSP）就是一个典型的组合优化问题。其问题可以描述如下：给定n个城市及两两城市之间的距离，求经过各城市一次且仅一次的最短路径。传统的PSO算法定义于连续的函数空间，要应用到组合优化问题上，必须对基本PSO算法进行改造成为离散的PSO，才能应用到问题的求解。在应用求解TSP的问题中，由于算法有时搜索的解与最优解之间只相差一个城市的位置，所以本文考虑引入移动算子及移动序的概念，对基本PSO算法进行改造，并将其应用于TSP问题上。1移动
6、算子和移动序定义1设N个节点的TSP问题的解序列为),,(21Nnnns;=，Eni∈，定义移动算子),(kisv为解s中的in点移动k位（k为整数），如果0>k表示向后移动k位，反之0<k表示向前移动k??位，0=k则表示in点不移动。),('kiss+=表示解s经过移动算子),(kisv操作后的新解。这里加号被赋予了新的含义。由于TSP问题求解的是一个H圈，解//.paper.edu-2-中国科技论文在线),,(21Nnnn;与解),,,,(1132nnnnnNN??;实际上是同一个解，所以对于
7、移动算子),(kisv可用下面图来表示。图1移动算子的定义如果0>k，in点逆时针移动k位，如果0<k，in点则顺时针移动
8、k
9、位。例1设一个五个节点的TSP问题，)5,4,3,2,1(=s，移动算子sv)2,1(，则)5,4,1,3,2()2,1()5,4,3,2,1()2,1('=+=+=svss如果移动算子为)3,3(sv，则)5,4,2,3,1()3,3()5,4,3,2,1()3,3('=+=+=svss定义2一个或多个移动算子的有序序列就是移动序，记作v.),,,(21lsvs
10、vsvv;=其中lsvsvsv,,,21;是移动算子，它们之间的顺序是有意义的。移动序作用于一个TSP解上意味着这个移动序中的所有移动算子依次作用于该解上。定义3不同的移动序作用于同一解上可能产生相同的新解，所有具有相同效果的移动序的集合称为移动序的等价集。定义4若干个移动序可以合并成一个新的移动序，定义⊕为两个移动
