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

《求解旅行商问题的几种解法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2010年第5期边疆经济与文化No．5．2010(总第77期)THEBORDERECONOMYANDCUIJ1IjREGenera1．No．77【旅游经济】高春涛(哈尔滨商业大学基础科学学院，哈尔滨150028)摘要：旅行商问题(TSP)是一个典型的NP完全问题，现在还没有找到有效的解法。目前比较热门的求解TSP问题的方法主要有四种：神经网络算法；模拟退火算法；遗传算法；蚁群算法。关键词：旅行商问题；组合优化；解法中图分类号：F592文献标志码：A文章编号：1672-5409(2010)05-0010-

2、02的极小解相对应，从而将求解能量函数极小解的过一、引言程转化为网络向平衡态的演化过程。尤其是通过对旅行商问题(TravelingSalesmanProblem)，是TSP问题的成功求解，开辟了神经网络模型在计算指给定n个城市，任何两城市之问皆有路连通，其机科学应用中的新天地，动态反馈网络从而受到广距离为已知，某旅行商从其中某城市出发，要经过泛的研究和关注，被广泛应用于优化问题中，且已每城市一次，且只能一次，最后又必须返回出发城设计出了专用的硬件电路。l市，要求找出最短的巡回路径。由于在很多实际问Hop

3、field网络是一种非线性动力学模型，通过题中，如印刷电路板的铅孔路线方案、连锁店的货引入类似Lyapunov函数的能量函数概念，把神经物配送路线等问题经过简化处理，均可建模为旅行网络的拓扑结构(用连接矩阵表示)与所求问题商问题，因而对旅行商问题求解方法的研究具有重(用目标函数描述)对应起来，转换成神经网络动要的应用价值。旅行商问题是运筹学中有代表性的力学系统的演化问题。因此，在用Hopfield网络求组合优化问题，也是典型的NP完全问题。虽然它解优化问题之前，必须将问题映射为相应的神经网陈述起来很简单

4、，但求解却很困难，对于具有n个络。对TSP问题的求解，首先将问题的合法解映城市的TSP问题，其可能的路径数目为(n一射为一个置换矩阵，并给出相应的能量函数，然后1)!／2，至今尚未找到有效的求解方法，在理论将满足置换矩阵要求的能量函数的最小值与问题的上枚举法可以解决这一问题，但是当n较大时，解最优解相对应。题的时间消耗会使枚举法显得没有任何实际价值。2．模拟退火算法因此寻求一种求解时间短，能满足实际问题精度要模拟退火算法最初的思想由Metropolis在1953求的解，成为解决该问题的主要途径。年提出，

5、Kirkpatrick在1983年成功地将其应用在组合最优化问题中。模拟退火算法的出发点是基于二、TSP求解方法物理中固体物质的退火过程与一般组合优化问题之求解旅行商问题的方法可以分为两大类，一类间的相似性。模拟退火算法在某一初温下，伴随温是精确算法，目的是要找到理论最优解；另一类是度参数的不断下降，结合概率突跳特征在解空间中近似算法，其算法简单，计算量小，大多数情况下随机寻找目标函数的全局最优解，即在局部优解能求得的满意解能满足要求。概率性地跳出并最终趋于全局最优。⋯用固体退火1．Hopfield神经

6、网络算法模拟组合优化问题，将内能E模拟为目标函数f，1982年，Hopfield开创性地在物理学、神经生温度T演化成控制参数t，即得到解组合优化问题物学和计算机科学等领域架起了桥梁，提出了的模拟退火算法：有初始解i和控制参数初值t开Hopfield反馈神经网络模型(HNN)。Hopfield网络始，对当前解重复“产生新解一计算目标函数差是典型的全连接网络，通过在网络中引人能量函数一接受或舍弃”的迭代，并逐步衰减t值，算法终以构造动力学系统，并使网络的平衡态与能量函数止时的当前解即为所得近似最优解。收稿日

7、期：2010-01．22作者简介：高春涛(1973一)，女，黑龙江拜泉人，讲师，硕士，主要从事混沌神经网络研究。圆B⋯G⋯w⋯UA高春涛：求解旅行商问题的几种解法解决TSP问题的模拟退火算法的框架为：给step6按某种规则，用该后代解替代原解组中的某定起、止“温度”T，T0和退火速度a，初始的一个解；Step7若当前解组符合停机条件，则算法终条路径C。；While(T>To)do；在C0的邻域内产生止，否则，转Step4。另一条路径C；计算两条路径所引起的目标函数遗传算法的优点是算法进行全空间并行搜索，

8、(能量)值的变化△E；若AE≤O，接受新值，若并将搜索重点集中于性能高的部分，从而能够提高exp(一AE／T)>rand(0，1)(rand(0，1)效率且不易陷入局部极小；算法具有固有的并行表示0～1之间的随机数，也接受新值，否则就拒性，提高对种群的遗传处理可处理大量的模式，并绝；确定新的参数值，若扰动被接受，则C0一c1，且容易并行实现。其主要缺点是对于结构复杂的组否则不变化；若接受新值，降温T+一一aT，否则不降合优化问题，搜索空间大