大事然来与用
TSP问题的几种常用求解算法比较
黄永斌
(宁波大学机械工程与力学学院浙江宁波315211)
算法分析
摘要：本文介绍了TSP间题及其常见的解法，给出了计算实例，并结合计算实例对各求解算法进行了比较。本文对于各种算法的比较对于TSP问题的求解具有一定的参考价值。
关键调TSP问题0-1规划智能算法
中图分类号：0158
文献标识码：A
文章编号：1007-9416(2014)05-0139-02
旅行商间题(TravelingSalesmanProblem，TSP)是典型的组合优化问题，很多优化间题都可以直接或间接的转为为TSP间题，而且TSP间题已被证明具有NPC计算复杂性，有很大的求解难度，因此研究TSP间题的求解方法有着很大的实际意义。本文旨在介绍求解TSP的几种常用解法，并结合实例比较这些算法的性能，为TSP的
求解提供一些参考。 1TSP向题描述
TSP间题的数学表述为：一个有穷的城市集合C=C,,C,，" C_),对于每一对城市CC,EC有距离d(C,C)ER*。间：经过C中所有城市的旅行路线，记为序列，是否存在最
小的正数B,对所有可能的序列都有 Za(.C)+d(C.m)B 2TSP间题几种常用求解方法
TSP问题有着很多求解算法，主要有。 2.1贪要算法
贪婪算法(2(Greedyalgorithm)是求解大规模TSP间题的常用算法之一，是一种求解优化间题的简单，迅速的求解办法。贪婪法有
限考虑当前情况下量最优的优化测度，自项向下，逐步选代，具有算法简单，耗时短的特点，但贪婺算法的求解结果往往不是最优的，基至可能与全局最优解间有不小的差距。
2.2模拟退火算法
模拟退火(SimulatedAnnealing，SA)算法是求解TSP间题的有效方法之一，容易编程实现，求解速度快。模拟退火是一种全局优化算法，加人了随机状态模型，使算法以概率选择的方式通近最优状态，其收敏性可以得到严格的理论证明。模拟退火算法具有一整套完整的退火搜索计划，包括足够高的初始温度、缓慢的退火速度、大量的选代次数及足够的概率扰动。
2.3遗传算法
遗传算法(GeneticAlgorithm，GA)是一种常用的智能算法，具有全局搜索能力，对TSP问题有良好的效果。遗传算法是由Michi-gan大学的J.Holland教授于1975年提出，算法通常由编码、个体适应度评估和遗传运算三部分构成，其中遗传运算包括染色体复制、交叉、变异和倒位等困。
2.4粒子群算法
粒子群算法(ParticleSwarmOptimization，PSO)是依据鸟类觅食的群体性模型而发明的新型智能算法，是由美国电气工程师 Eberhart和社会心理学家Kennedy于1995年提出，具有通用性强，参
表1各算法的求解结果
算法
贪婪算法模拟退火
遗传算法粒子群算法蚁群算法
算法名称贪婪算法模拟退火遗传算法粒子群算法教群算法
优点
参数设置
初始位置为2号城市初始路径设：
123456789101，初始温度为1.5，终止温度为1；衰减因子为0.93
最大代数：100，次替代的样本数量： 10，交叉概率：0.1变异的概率0.8；种群数目：100
耗时
0.000071s
0.854s 0.349s
粒子群规模：10，最大选代次数为200
0.128s
蚂蚊个数：20；最大选代次数；200；启发式因子：5；信息蒸发系数：0.1，信息索增强系数：100；信息素重要性因子为1
1.408292s
表2各算法性能比较缺点
求解速度快，算法容易实现求解速度快，全局优化
全局优化算法，求解速度快
通用性强，参数少，收敛速度快鲁棒性强，并行计算能力强
最优解 13771 12062
12055 12055 12055
无法保证结果接近全局最优解概率型算法，无法
局部寻优能力弱，容易早熟
局部搜索能力差，搜索精度不高容易陷人局部最优秀解
作者简介：黄永斌(1992一),男,汉,江苏铜山，宁波大学机械工程与力学学院,本科，工程力学。
万方数据
最优路径
215103846792 1086945321710
218963541072 218963541072 218963541072
适用范围
求解精度要求不高的场合广泛应用于全局优化问题
多种优化间题实数优化问题离散型优化问题
139