一种求解TSP问题的粒子群算法设计-科技论文

变异的目的是防止种群中的解跑到局部极值去。变异是对子代的随机的改变。我在算法中采用了以下变异策略：
1．变异策略A：在第1－n个访问的城市中随机地选取第J1次和第J2次访问的城市，在路径C0中交换第J1次和第J2次访问的城市，其余不变，此时的路径为C1。
2．变异策略B：在第1－n个访问的城市中随机地选取第J1次访问的城市，在路径C0中交换第J1次和第J1＋1次访问的城市，其余不变，此时的路径为C1。
3．变异策略C：也称逆转策略，在第1－n个访问的城市中随机地选取第J1次和第J2次访问的城市，在路径C0中第J1次和第J2次访问的城市之间的子路径以反方向插入，其余不变，此时的路径为C1。
4．变异策略D：在第1－n个访问的城市中随机地选取第J1次和第J2次访问的城市，假设J15．变异策略E：在第1－n个访问的城市中随机地选取第J1次访问的城市，选取离J1距离最近的城市J2，在路径中将城市J2安排到城市J1之后，其余不变。
6．变异策略F：计算路径中相邻城市之间距离最大的两个城市J1和J2，然后选取选取离J1距离最近的城市J3，在路径中将城市J3安排到城市J1和J2之间，其余不变。
二、算法步骤
1.初始化，设定粒子数n，设定迭代次数m，随机排列城市顺序产生n条初始路径。
2.根据当前位置计算适应值ltsp0，设置当前适应值为个体极值plbest，当前位置为个体极值位置pcbest，根据各个粒子的个体极值找出全局极值glbest和全局极值位置gcbest。
while（迭代次数<规定迭代次数m）do
Forj＝1：n
3.第j个粒子的路径C（j）与个体极值作交叉操作，产生新的路径C’(j),若新的路径长度变短,则保存结果。C’(j)与全局极值作交叉操作,产生新的路径C”(j),若新的路径长度变短,则保存结果。C”(j)变异得到新的位置C”’(j)，若新的路径长度变短,则保存结果。最后产生的路径为C1(j),若△E<0，则C1(j)覆盖原始路径C(j)
Endfor
根据各个粒子的个体极值找出全局极值glbest和全局极值位置gcbest。
EndWhile
4.输出全局极值glbest和全局极值位置gcbest。
三、算法结论
本文在深入分析和研究了粒子群算法基本理论与方法的基础上，尝试用新的方法将粒子群概念应用到TSP这一离散领域优化的问题之中，取得了突破。同时针对PSO的弱点提出了交叉变异的方法，进一步提升了粒子群算法在寻找TSP最优解领域的能力，在求解旅行商问题上有较高的搜索效率，能在较短时间内获得较好解，而且简单有效。算法的分析和测试表明，该粒子群算法是有效的。虽然该算法没有专门针对TSP问题的经典算法那么高效，但是仍然是粒子群算法求解旅行商问题的崭新尝试。
粒子群算法求解TSP问题的研究处于初期，还有许多问题值得研究，如算法的收敛性、理论依据等。但从当前的应用效果看，这种模仿自然生物的寻优思想具有光明的前景，更多深入细致的工作还有待于进一步展开。