【源码】PSO算法解决经典TSP问题

qq_1537237806

旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

$ T4 k! h- Q, L
PSO是粒子群优化算法（——Particle Swarm Optimization）的英文缩写，是一种基于种群的随机优化技术，由Eberhart和Kennedy于1995年提出。粒子群算法模仿昆虫、兽群、鸟群和鱼群等的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断改变其搜索模式。
0 x% {9 m. _: b6 h0 G
( {+ Z/ d" q% L" _2 x4 B5 @1 A3 Y* |
一般而言，如果不考虑对TSP问题的额外的处理方式，直接用PSO算法，对于一些规模较小的问题（节点数量一般不超过20），PSO算法的效果还行，但是，当问题的规模变得比较大时（50及以上），PSO算法就无能为力。一个重要的原因在于当节点数量增加时，问题的复杂度会变得很大，PSO算法会陷入局部最优，而且这个局部最优往往离最优解很远。这个时候，有两种选择，一是改进PSO算法本身，这个基本很难，我尝试过，效果并不太好，PSO算法的模式基本都是固定的，如果只改变速度中的权重或是简单的调参，收效甚微；二是改变对TSP问题的编码以及粒子速度与位置的定义，使问题本身相对更加容易处理。