论文部分内容阅读
[摘要]旅行商问题(Traveling Salesman Problem，简称TSP)是求一次遍访指定城市并返回出发城市的最短旅行路线的问题，它是图论中一个经典的NP完全问题，用电子计算机需要指数级的时间才能得到解决。尝试用粒子群算法来求解旅行商问题，结合遗传算法的思想，并且给出交叉和变异操作的设计。该算法符合组合优化问题的特点，在求解旅行商问题上有较高的搜索效率。
[关键词]旅行商问题 TSP 粒子群算法 交叉 变异
中图分类号：F590文献标识码：A文章编号：1671－7597 (2008) 0110019－01
从目前各种求解TSP的方法来看，小规模的TSP例子很适合于用全局优化技术求解，但是要考虑城市规模比较大的TSP实例则需要采用启发式方法。对于复杂优化问题，单一机制的优化算法很难实现全局优化，且效率较低。多种优化机制和邻域搜索结构相混合，是能较大程度提高全局优化度的有力途径，并可一定程度上放松对单一算法参数选择的苛刻性。所以混合优化策略会是一种趋势。
一、求解TSP的粒子群算法
（一）初始化
一般都是随机生成规模为N的初始路径 。初始路径中的城市是按访问的顺序排列的，例如:对于一个10个城市的TSP：3-2-5-4-7-1-6-9-8-10，表示从城市3出发依次经过城市2, 5, 4, 7, 1, 6, 9, 8，10然后返回城市3的一条路径。并且这种表达方式满足TSP问题的约束条件。保证了每个城市经过且只经过一次，并且保证任何一个城市子集中不形成回路。
（二）交叉操作
交叉的本质就是从种群中选择父代以生成新的母体群。交叉的方法很多，我在算法中采用了以下策略：
1．交叉策略A：在第2个串中随机选择一个交叉区域；将old2的交叉区域加到old1后面，删除old1中已在old2交叉区中出现过的城市。
2．交叉策略B：在第2个串中随机选择一个交叉区域；将old2的交叉区域加到old1对应的位置，删除old1中已在old2的交叉区中出现过的城市。
3．交叉策略C：在第2个串中随机选择一个交叉区域；将old2的交叉区域加到old1的随机位置，删除old1中在old2的交叉区中已出现的城市。
4．交叉策略D：在第2个串中随机选择一个交叉区域，如交叉区域为：6，5，4，3；将old2的交叉区域加到old1的城市6的位置，删除old1中已在old2的交叉区中出现过的城市。
（三）变异操作
变异的目的是防止种群中的解跑到局部极值去。变异是对子代的随机的改变。我在算法中采用了以下变异策略：
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次访问的城市，假设J1 5．变异策略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
For j＝1：n
3.第j个粒子的路径C（j）与个体极值作交叉操作，产生新的路径C’(j),若新的路径长度变短,则保存结果。C’(j)与全局极值作交叉操作,产生新的路径C”(j), 若新的路径长度变短,则保存结果。C”(j)变异得到新的位置C”’(j)，若新的路径长度变短,则保存结果。最后产生的路径为C1(j),若△E< 0，则C1(j)覆盖原始路径C(j)
End for
根据各个粒子的个体极值找出全局极值glbest和全局极值位置gcbest。
End While
4. 输出全局极值glbest和全局极值位置gcbest。
三、算法结论
本文在深入分析和研究了粒子群算法基本理论与方法的基础上，尝试用新的方法将粒子群概念应用到TSP这一离散领域优化的问题之中，取得了突破。同时针对PSO的弱点提出了交叉变异的方法，进一步提升了粒子群算法在寻找TSP最优解领域的能力，在求解旅行商问题上有较高的搜索效率，能在较短时间内获得较好解，而且简单有效。算法的分析和测试表明，该粒子群算法是有效的。虽然该算法没有专门针对TSP问题的经典算法那么高效，但是仍然是粒子群算法求解旅行商问题的崭新尝试。
粒子群算法求解TSP问题的研究处于初期，还有许多问题值得研究，如算法的收敛性、理论依据等。但从当前的应用效果看，这种模仿自然生物的寻优思想具有光明的前景，更多深入细致的工作还有待于进一步展开。
参考文献：
[1]AlbertoGomez, Ricardo, Gonzalez, JoseParreno, RaulPino: A Particle Swarm-based Met heuristic to solve the Traveling Salesman Problem [A].Proceedings of the 2006 International Conference on Artificial Intelligence, ICAI 2006[C], Las Vegas, Nevada, USA, June 26-29, 2006, Volume 2. CSREA Press/CSREA Press 2006, ISBN 1-932415-97-1, 698-702.
[2]高尚，杨静宇，背包问题的混合粒子群优化算法[J]，中国工程科学，2006，8(11)：94-98.
[3]高渤，粒子群优化算法的研究与展望[J]，重庆工学院学报，2006,20(11)：62－64.
[关键词]旅行商问题 TSP 粒子群算法 交叉 变异
中图分类号：F590文献标识码：A文章编号：1671－7597 (2008) 0110019－01
从目前各种求解TSP的方法来看，小规模的TSP例子很适合于用全局优化技术求解，但是要考虑城市规模比较大的TSP实例则需要采用启发式方法。对于复杂优化问题，单一机制的优化算法很难实现全局优化，且效率较低。多种优化机制和邻域搜索结构相混合，是能较大程度提高全局优化度的有力途径，并可一定程度上放松对单一算法参数选择的苛刻性。所以混合优化策略会是一种趋势。
一、求解TSP的粒子群算法
（一）初始化
一般都是随机生成规模为N的初始路径 。初始路径中的城市是按访问的顺序排列的，例如:对于一个10个城市的TSP：3-2-5-4-7-1-6-9-8-10，表示从城市3出发依次经过城市2, 5, 4, 7, 1, 6, 9, 8，10然后返回城市3的一条路径。并且这种表达方式满足TSP问题的约束条件。保证了每个城市经过且只经过一次，并且保证任何一个城市子集中不形成回路。
（二）交叉操作
交叉的本质就是从种群中选择父代以生成新的母体群。交叉的方法很多，我在算法中采用了以下策略：
1．交叉策略A：在第2个串中随机选择一个交叉区域；将old2的交叉区域加到old1后面，删除old1中已在old2交叉区中出现过的城市。
2．交叉策略B：在第2个串中随机选择一个交叉区域；将old2的交叉区域加到old1对应的位置，删除old1中已在old2的交叉区中出现过的城市。
3．交叉策略C：在第2个串中随机选择一个交叉区域；将old2的交叉区域加到old1的随机位置，删除old1中在old2的交叉区中已出现的城市。
4．交叉策略D：在第2个串中随机选择一个交叉区域，如交叉区域为：6，5，4，3；将old2的交叉区域加到old1的城市6的位置，删除old1中已在old2的交叉区中出现过的城市。
（三）变异操作
变异的目的是防止种群中的解跑到局部极值去。变异是对子代的随机的改变。我在算法中采用了以下变异策略：
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次访问的城市，假设J1
6．变异策略F：计算路径中相邻城市之间距离最大的两个城市J1和J2，然后选取选取离J1距离最近的城市J3，在路径中将城市J3安排到城市J1和J2之间，其余不变。
二、算法步骤
1.初始化，设定粒子数n，设定迭代次数m，随机排列城市顺序产生n条初始路径。
2.根据当前位置计算适应值ltsp0，设置当前适应值为个体极值plbest，当前位置为个体极值位置pcbest，根据各个粒子的个体极值找出全局极值glbest和全局极值位置gcbest。
while（迭代次数<规定迭代次数m）do
For j＝1：n
3.第j个粒子的路径C（j）与个体极值作交叉操作，产生新的路径C’(j),若新的路径长度变短,则保存结果。C’(j)与全局极值作交叉操作,产生新的路径C”(j), 若新的路径长度变短,则保存结果。C”(j)变异得到新的位置C”’(j)，若新的路径长度变短,则保存结果。最后产生的路径为C1(j),若△E< 0，则C1(j)覆盖原始路径C(j)
End for
根据各个粒子的个体极值找出全局极值glbest和全局极值位置gcbest。
End While
4. 输出全局极值glbest和全局极值位置gcbest。
三、算法结论
本文在深入分析和研究了粒子群算法基本理论与方法的基础上，尝试用新的方法将粒子群概念应用到TSP这一离散领域优化的问题之中，取得了突破。同时针对PSO的弱点提出了交叉变异的方法，进一步提升了粒子群算法在寻找TSP最优解领域的能力，在求解旅行商问题上有较高的搜索效率，能在较短时间内获得较好解，而且简单有效。算法的分析和测试表明，该粒子群算法是有效的。虽然该算法没有专门针对TSP问题的经典算法那么高效，但是仍然是粒子群算法求解旅行商问题的崭新尝试。
粒子群算法求解TSP问题的研究处于初期，还有许多问题值得研究，如算法的收敛性、理论依据等。但从当前的应用效果看，这种模仿自然生物的寻优思想具有光明的前景，更多深入细致的工作还有待于进一步展开。
参考文献：
[1]AlbertoGomez, Ricardo, Gonzalez, JoseParreno, RaulPino: A Particle Swarm-based Met heuristic to solve the Traveling Salesman Problem [A].Proceedings of the 2006 International Conference on Artificial Intelligence, ICAI 2006[C], Las Vegas, Nevada, USA, June 26-29, 2006, Volume 2. CSREA Press/CSREA Press 2006, ISBN 1-932415-97-1, 698-702.
[2]高尚，杨静宇，背包问题的混合粒子群优化算法[J]，中国工程科学，2006，8(11)：94-98.
[3]高渤，粒子群优化算法的研究与展望[J]，重庆工学院学报，2006,20(11)：62－64.