旅行商问题TSP的几种求解方法

离散数学相关

　　第23卷　第08期

文章编号:1006-9348(2006)08-0153-05

计　算　机　仿　真

2006年08月　　

旅行商问题(TSP)的几种求解方法

田贵超,黎明,韦雪洁

(南昌航空工业学院测试技术与控制工程系,江西南昌330034)

摘要:旅行商问题(TSP)是组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难。而快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。该文首先介绍了什么是TSP,接着论述了六种目前针对TSP比较有效的解决方法(模拟退火算法、禁忌搜索算法、Hopfield神经网络优化算法、蚁群算法、遗传算法和混合优化策略)的基本思想,并且简单阐述了它们的求解过程,最后分别指出了各自的优缺点并对解决TSP的前景提出了展望。关键词:旅行商问题;组合优化;路径;展望中图分类号:TP301.6　　文献标识码:A

SeveralMethodsforSolvingTravelingSalesmanTIANGui-chao,LIM(DepartmentofTest&ControlEngineering,Technology,

ABSTRACT:The(isoneofthetypicalNP-Completehardproblemsinmistobedescribedbuthardtobesolved.

Itspossibleamountsofpath

increasewamountsofcity,soitisverydifficulttosolve.ButtosolveTSPquicklyandeffectivelytheoreticalvaluesandhighpracticalapplicationvalues.TSPisfirstintroducedinthispaper.Thenthebasicthoughtsofsixeffectivemethods(simulatedannealingalgorithm,taboosearchalgorithm,Hopfieldneuralnetworksoptimizationalgorithm,antcolonyalgorithm,geneticalgorithmsandhybridoptimizationstrategy)forsolvingTSPandtheirprocessesarediscussed.Atlast,theadvantagesanddisadvantagesofthesixmainsolvingmethodsarerespectivelyindicated,andtheprospectforthefutureofsolvingTSPisprovided.

KEYWORDS:Travelingsalesmanproblem(TSP);Combinatorialoptimization;Path;Prospect

2)非对称旅行商问题(dij≠dji, i,j=1,2,3,…,n)。

1　引言

旅行商问题(TravelingSalesmanProblem,简称TSP)即给定n个城市和两两城市之间的距离,要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G=(V,A),其中V为顶点集,A为各顶点相互连接组成的边集,设D=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵,要求确定一条长度最短的Hamilton回路,即遍历所有顶点当且仅当一次的最短距离。

旅行商问题可分为如下两类:

1)对称旅行商问题(dij=dji,Πi,j=1,2,3,…,n);

基金项目:国家自然基金(60475002)收稿日期:2005-06-30

非对称旅行商问题较难求解,我们一般是探讨对称旅行商问题的求解。

若对于城市V={v1,v2,v3,…,vn}的一个访问顺序为T={t1,t2,t3,…,ti,…,tn},其中ti∈V(i=1,2,3,…,n),且记tn+1=t1,则旅行商问题的数学模型为[1]:minL=

n

∑d

i=1

ti,ti+1

。

TSP是一个典型的组合优化问题,并且是一个NP完全

难题,是诸多领域内出现的多种复杂问题的集中概括和简化形式,

并且已成为各种启发式的搜索、优化算法的间接比较标准。因此,快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值[2]。

—153—

离散数学相关

2　主要求解方法

基于TSP的问题特性,构造型算法成为最先开发的求解算法,如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但是,由于构造型算法优化质量较差,迄今为止已开发了许多性能较好的改进型搜索算法[3],主要有:

1)模拟退火算法2)禁忌搜索算法

3)Hopfield神经网络优化算法4)蚁群算法5)遗传算法6)混合优化策略2.1　模拟退火算法方法2.1.1　基本思想

模拟退火算法(simulatedannealing,SA)是基于MonteCarlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。SA算法由某一较高初温开始,结合具有概率突跳特性的Metropolis抽样策略在解空间中随机寻找目标函数的全局最优解,伴随温度参数的不断下降重复抽样过程,最终得到问题的全局最优解。

从算法结构知,新状态产生函数、、函数、)[3]2.1.2　求解TSP

1)编码选择:TSP解的最常用的一种策略———路径编码。

2)SA状态产生函数的设计:对于基于路径编码的SA状态产生函数操作,可将其设计为:①互换操作(SWAP);②逆序操作(INV);③插入操作(INS)。

3)SA状态接受函数的设计:min{1,exp(-△/t)}>random[0,1]准则是作为接受新状态的条件最常用的方案,其中△为新旧状态的目标值差,t为“温度”。

4)初温和初始状态:最常用且可理解的初温确定方案是,首先随机产生一组状态,确定两两状态间的最大目标值差:|Δmax|,然后由式t0=-Δmax/lnpr,其中pr为初始接受概率(理论上应接近1,实际设计时也可以取0.1)。初始状态可采用启发式算法(如2opt方法)快速得到一个解,并以此为SA的初始状态。

5)退温函数的设计:指数退温函数是最常用的退温策略(tk=λtk-1,λ为退温速率)。

6)温度修改准则和算法终止准则的设计:可采用阈值法设计的“温度修改”和“算法终止”两准则。2.2　禁忌搜索算法2.2.1　基本思想

禁忌搜索(TabuSearch或TabooSearch,简称TS)是一种亚启发式搜索技术[4],由Glover在1986年首次提出,进而

形成一套完整算法[5,6]。它是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法通过引入一种灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态 …… 此处隐藏：8534字，全部文档内容请下载后查看。喜欢就下载吧 ……