HPSO求解TSP问题

1基于混合粒子群算法的TSP问题**（**大学**学院，**）摘要：旅行商问题（TSP）是一种经典的组合优化问题，属于NP难题，已有不少学者运用各种方法对其进行求解，包括线性规划（LP），动态规划（DP）以及诸如遗传算法（GA），蚁群优化算法（ACO）和粒子群优化算法（PSO）等的智能优化算法。本文是用一种混合粒子群算法（HPSO）来求解TSP问题，该算法摒弃了标准粒子群算法（PSO）中通过跟踪极值来更新粒子位置的方法，而是引入了GA中的交叉和变异操作，通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。最后，仿真结果表明，该算法可以解决较小规模的TSP问题，以较快速度找到最优路径，且对于大规模TSP问题，可以找到较优路径。关键词：混合粒子群算法;旅行商问题;交叉;变异TheTravelingSalesmanProblemBasedonHybridParticleSwarmOptimization**(***)Abstract:Travelingsalesmanproblem(TSP)isaclassiccombinatorialoptimizationproblem,whichbelongstoNP-hardproblems.AndmanyscholarshaveusedvariousmethodstosolveTSP,includinglinearprogramming(LP),dynamicprogramming(DP),andintelligentoptimizationalgorithmssuchasgeneticalgorithm(GA),antcolonyoptimizationalgorithm(ACO)aswellasparticleswarmoptimizationalgorithm(PSO).Thispaperemploysahybridparticleswarmoptimizationalgorithm(HPSO)tosolveTSP.ThealgorithmabandonsthewayofupdatingthelocationofparticlesbytrackingextremuminstandardPSOalgorithm,andintroducesthecrossoveroperatorandthemutationoperatorinGAalgorithm,searchingtheoptimalsolutionbythewayofswappingwithindividualextremumaswellasGlobalextremumandmutatingtheparticleitself.ThesimulationresultsindicatethatthealgorithmcansolvetherelativelysmallscaleTSPatarelativelyfastspeedtoachievetheoptimalroute,andforthelargescaleTSP,itcanachievethenearoptimalroute.Keywords:HPSO;TSP;crossover;mutation1.引言旅行商问题（TSP）是一个典型的NP难题[1]，即其最坏情况下的计算复杂度随问题规模指数增长，而其也常用于测试新提出算法的效率。TSP问题可描述为：已知n个城市相互之间的距离，假定有一个旅行商要走访这n个城市，而每个城市只能访问一次，最后回到出发地，需要选择一条最优路径使得所走路线最短。事实上，很多NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺母问题等。对于TSP问题，众多学者已用了各种各样的方法来求解。文献[2]使用的是混合蛙跳算法（SFLA），结果2表明其适用于小规模的TSP问题。文献[3]将装有传感器的无人驾驶侦察机的最短飞行路线问题转化为TSP问题，并用蚁群优化算法（ACO）来求解。文献[4]用自适应聚类算法求解大规模TSP问题，将大规模数据分解成几个小规模数据集，并用一种新型的遗传算法（GA）求解小规模数据集代表的小规模TSP问题。文献[5]用多主体优化系统（MAOS）求解TSP问题，实验表明各主体的协同搜索可实现整体的高性能。文献[6]分析了一种简单的ACO算法求解TSP问题的运行时间，以及参数对运行时间的影响。文献[7]基于GA提出一种可以从庞大的搜索空间中快速求得TSP问题的最优解的算法。文献[8]提出两种粒子群算法指导下的蚂蚁优化算法（AS-PSO）的变型，并用于求解TSP问题。文献[9]将模糊逻辑与ACO和PSO结合来求解TSP问题，结果表明模糊逻辑可以节省时间和最优长度。文献[10]具体研究了使用并行和现场可编程阵列（FPGAs）的GA算法，并用TSP问题作为个案研究，结果表明并行技术可得到更好的结果。文献[11]提出一种新型的追求最少信息丢失的染色体编码机制以及一种最少约束的针对2-D的欧几里得TSP问题的交叉机制。文献[12]给出一种带有搜索空间平滑技术的局部搜索法，任何传统的启发式搜索算法可与该平滑算法协力。多个随机生成的TSP实例用来测试该算法。粒子群算法（PSO）[13,14]是一种群体智能优化算法，由Kennedy和Eberhart于1995年提出。标准的PSO是通过追随个体极值和群体极值来完成极值寻优的，虽然操作简单，收敛速度也比较快，但随着迭代次数的不断增加，在种群收敛集中的同时，各粒子也越来越相似，可能无法跳出局部最优解。针对这一点，很多文献对PSO做出改进或与其他方法结合使用。文献[15]使用混沌序列结合传统的线性递减的惯性权重，并采用交叉算子来提高PSO的探索和求精能力。本文的混合粒子群算法（HPSO）摒弃了标准PSO中的通过跟踪极值来更新粒子位置的方法，而是引入了遗传算法（GA）中的交叉和变异操作，通过与个体极值和群体极值的交叉以及变异的方式来搜寻最优解。2.TSP问题TSP问题是一个比较经典的组合优化问题，涉及多个城市（节点），每个城市都有一个二维或三维坐标，或任意两个城市间有一条连接着两者的路，路的长度则为两城市间的距离。故TSP问题就是找到一条最短路径，满足每个城市经过且仅经过一次。设历经的城市数为n，城市iv与城市jv之间的路径长度为(,)ijpathvv，本文只考虑对称TSP问题，即(,)(,)ijjipathvvpathvv，则TSP问题就是找到一条闭合路径12(,,),,nijLvvvvvifij，目标函数为：1111min(,),njjnjpathvvwherevv（1）其中，n为城市数量，1(,)jjpathvv为城市jv与城市1jv之间的路径长度，1v为出发城市。3.粒子群算法3.1标准粒子群算法在PSO算法中，假如粒子群包含n个粒子，每个粒子的维数为d，则粒子群中单个粒子的位置为,1,2,(,,,)iiiidxxxx，单个粒子速度为,1,2,(,,,)iiiidvvvv，粒子根据如下公式更新速度和位置：3i,,11,,22,,v(1)()[()][()]jijijijgjijtwvtcrpxtcrpxt（2）,,,(1)()(1),1,2,,,1,2,,ijijijxtxtvtinjd（3）其中，,ijp为个体极值，,gjp为全局极值，,()ijvt和,(1)ijvt分别为第t代和第t+1代粒子的速度，,()ijxt和,(1)ijxt分别为第t代和第t+1代粒子的位置，w为惯性权重，1c和2c为正的学习因子，1r和2r为0到1之间均匀分布的随机数。该算法的终止条件是适应度函数值小于某个数值或迭代一定的次数。3.2混合粒子群算法本文的HPSO算法摒弃了PSO算法中通过跟踪极值来更新粒子位置的方法，而是引入了GA算法中的交叉和变异操作，通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。基于HPSO算法的TSP问题的求解流程如图1所示：种群初始化适应度值计算更新粒子个体最优交叉群体最优交叉粒子变异算法是否结束结束NY图1混合粒子群算法流程图Fig.1FlowchartforHPSO其中，种群初始化模块初始化粒子群种群；适应度值计算模块计算粒子群个体的适应度值；更新粒子模块根据粒子适应度值更新个体最优粒子和群体最优粒子；个体最优交叉把个体和个体最优粒子进行交叉得到新粒子；群体最优交叉把个体和群体最优粒子进行交叉得到新粒子；粒子变异是指粒子自身变异得到新粒子。4.算法实现4.1个体编码粒子个体编码采用整数编码的方式，每个粒子表示历经的所有城市顺序，比如当历经的城市数为410，个体编码为47158102936，表示从城市4出发，经过7,1,5,8,10,2,9,3,6最终回到城市4，从而完成城市遍历。4.2适应度值粒子适应度值表示路径长度，第i个粒子的适应度值计算公式为：11(,)nijjjfpathvv（4）4.3交叉操作个体通过和个体极值和群体极值交叉来更新，交叉方法采用整数交叉法。首先选择两个交叉位置，然后把个体和个体极值或个体和群体极值进行交叉。以上述10个城市为例，假定随机选取的交叉位置为3和5，个体和极值的编码分别为47158102936和46173102985，则交叉操作方法如下：471581029364717310293646173102985（5）其中，47173102936为新个体的编码。产生的新个体若存在重复位置则进行调整，调整方法为用个体中未包括的城市代替重复包括的城市，如下所示：4717310293647185102936（6）其中，47185102936为调整后的新个体编码。对得到的新个体采用保留优秀个体策略，只有当新粒子适应度值好于旧粒子时才更新粒子。4.3变异操作变异采用个体内部两位互换方法，首先随机选取变异位置pos1和pos2，然后把两个变异位置互换，假设变异位置为6和8，变异操作如下所示：4718510293647185921036（7）其中，47185921036为经变异操作后产生的新个子。对得到的新个体依然采用保留优秀个体策略，只有当新粒子适应度值好于旧粒子时才更新粒子。5.仿真分析根据HPSO算法的原理和流程，在matlab中编程分别实现对涉及15和51个城市的TSP问题路径寻优。1)对于涉及15个城市的TSP问题，各城市的位置分布如图2所示。算法进化次数为100，种群规模即个体数目为100.程序运行了2次，算法进化过程中最优粒子适应度值变化分别如图3和图5所示，规划出的最优路径分别如图4和图6所示。551015202530354045505510203040506070kmkm城市分布图城市位置图2城市分布图Fig.2Thedistributionofcities0102030405060708090100200220240260280300320340算法训练过程迭代次数适应度值5101520253035404550551020304050607080kmkm规划路径规划路径图3适应度值变化（a）图4规划出的最优路径（a）Fig.3Thevariationoffitnessfunction(a)Fig.4Theoptimalroutecalculated(a)0102030405060708090100200220240260280300320340算法训练过程迭代次数适应度值5101520253035404550551020304050607080kmkm规划路径规划路径图5适应度值变化（b）图6规划出的最优路径（b）Fig.5Thevariationoffitnessfunction(b)Fig.6Theoptimalroutecalculated(b)62)对于涉及51个城市的TSP问题，各城市的位置分布如图7所示。01020304050607010203040506070kmkm城市分布