PSO是什么意思？用法、例句，基于 PSO 算法解决 TSP 项目

各位老铁们好，相信很多人对PSO是什么意思？用法、例句都不是特别的了解，因此呢，今天就来为大家分享下关于PSO是什么意思？用法、例句以及基于 PSO 算法解决 TSP 项目的问题知识，还望可以帮助大家，解决大家的一些困惑，下面一起来看看吧！

PSO(ParticleSwarmOptimization)算法即粒子群优化算法，源于对鸟群捕食行为的学习。基本思想是：个体获取的局部信息提供给群体，群体根据所有局部信息获得一个动态的全局最优解，每个个体再根据这个全局最优解调整自身的局部最优解，这个过程进行迭代，直到达到终止条件。

TSP(TravelingSalesmanProblem)即旅行商问题，简单来说就是：给定n个城市的位置，求一条访问各个城市一次的最短路径，TSP也是一个组合优化问题。

这里，Vj代表每个粒子的速度；w是惯性权重系数，有利于算法的收敛；c1和c2分别为局部加速权重系数和全局加速权重系数，决定了下一代的局部速度取决于局部最优解多一些，还是全局最优解多一些；r1和r2是两个0~1中间的随机数，也是为了算法收敛。

下面是我在report里做的PSO算法运行流程图：

但很明显，PSO算法更适合用来解决连续优化问题，而旅行商问题是一个组合优化问题。经过大量的论文学习和讨论后，使用了一种改进的PSO算法，引入了交换子和交换序的概念。

假设在一个旅行商问题中，有n个城市节点，那么这个问题的解序列可记为S=(ai),i=1,2,…,n.那么SO(i1,i2)就是一个交换子，i1和i2表示城市节点a1和a2.若对解序列进行S’=S+SO(i1,i2)的运算，就是将解序列S中a1和a2的位置进行调换。多个交换子的序列SS=(SO1,SO2,…,SOn)就是一个交换序，其中交换子的顺序是有意义的，不同的顺序可能产生不同的解序列。

放在这个具体路线规划问题中，就是先将所有城市节点随机排列，得到一个解序列，然后对城市节点进行逐个调换，将调换前后的路径长度进行对比，如果变好则更新全局最优解，否则继续寻找更佳的交换子和交换序，在这一过程中，w系数就起到了收敛的作用，它会使我们进行调换的局部解序列越来越短。

privatevoidparticle(inti){\nArrayList<SO>Vi;\nintlen;\nintj;\nfloatra;\nfloatrb;\nArrayList<SO>Vii=newArrayList<SO>();\n//refreshvelocity\n//Vii=wVi+ra(Pid-Xid)+rb(Pgd-Xid)\nVi=listV.get(i);\n//wVi+表示获取Vi中size*w取整个交换序列\nlen=(int)(Vi.size()*w);\nfor(j=0;j<len;j++){\nVii.add(Vi.get(j));\n}\n//Pid-Xid\nArrayList<SO>a=minus(Pd[i],oPopulation[i]);\nra=random.nextFloat();\n//ra(Pid-Xid)\nlen=(int)(a.size()*ra);\nfor(j=0;j<len;j++){\nVii.add(a.get(j));\n}\n//Pgd-Xid\nArrayList<SO>b=minus(Pgd,oPopulation[i]);\nrb=random.nextFloat();\n//rb(Pgd-Xid)\nlen=(int)(b.size()*rb);\nfor(j=0;j<len;j++){\nSOtt=b.get(j);\nVii.add(tt);\n}\n//savenewVii\nlistV.set(i,Vii);\n//refreshposition\n//Xid’=Xid+Vid\nadd(oPopulation[i],Vii);\n}\n

改变swarm的数目和迭代次数，得到的路径长度如下：

随着两个参数的无限增长，得到的最佳路径也会越来越短，但同时所耗的内存和时间也会有所增加。

P.S.在IntelliJ里面做界面真的太方便了。

代码已上传到Github：https://github.com/cyansoul/TSP-Solver-Bases-on-PSO-algorithm

文章到此结束，如果本次分享的PSO是什么意思？用法、例句和基于 PSO 算法解决 TSP 项目的问题解决了您的问题，那么我们由衷的感到高兴！