求解旅行商问题的几种解法
2010年第5期(总第77期)
边疆经济与文化
THE BORDER ECONOMY AND CULT URE
No 1512010General 1No 177
10
B I A N J I A N G J I N G J I Y U W EN HUA
【旅游经济】
求解旅行商问题的几种解法
高春涛
(哈尔滨商业大学基础科学学院,哈尔滨150028)
摘 要:旅行商问题(TSP )是一个典型的NP 完全问题,现在还没有找到有效的解法。目前比较热门的求解TSP 问题的方法主要有四种:神经网络算法;模拟退火算法;遗传算法;蚁群算法。
关键词:旅行商问题;组合优化;解法
中图分类号:F 592 文献标志码:A 文章编号:167225409(2010)0520010202
收稿日期:2010201222作者简介:高春涛(1973
),女,黑龙江拜泉人,讲师,硕士,主要从事混沌神经网络研究。
一、引言
旅行商问题(Traveling Sales man Pr oble m ),是指给定n 个城市,任何两城市之间皆有路连通,其距离为已知,某旅行商从其中某城市出发,要经过每城市一次,且只能一次,最后又必须返回出发城市,要求找出最短的巡回路径。由于在很多实际问题中,如印刷电路板的铅孔路线方案、连锁店的货物配送路线等问题经过简化处理,均可建模为旅行商问题,因而对旅行商问题求解方法的研究具有重要的应用价值。旅行商问题是运筹学中有代表性的组合优化问题,也是典型的NP 完全问题。虽然它陈述起来很简单,但求解却很困难,对于具有n 个城市的TSP 问题,其可能的路径数目为(n -1)!/2,至今尚未找到有效的求解方法,在理论上枚举法可以解决这一问题,但是当n 较大时,解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短,能满足实际问题精度要求的解,成为解决该问题的主要途径。 二、TSP 求解方法
求解旅行商问题的方法可以分为两大类,一类是精确算法,目的是要找到理论最优解;另一类是近似算法,其算法简单,计算量小,大多数情况下求得的满意解能满足要求。
1.Hopfield 神经网络算法
1982年,Hopfield 开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁,提出了Hopfield 反馈神经网络模型(HNN )。Hopfield 网络是典型的全连接网络,通过在网络中引入能量函数以构造动力学系统,并使网络的平衡态与能量函数
的极小解相对应,从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。尤其是通过对TSP 问题的成功求解,开辟了神经网络模型在计算机科学应用中的新天地,动态反馈网络从而受到广泛的研究和关注,被广泛应用于优化问题中,且已
设计出了专用的硬件电路。
[1]
Hopfield 网络是一种非线性动力学模型,通过引入类似Lyapunov 函数的能量函数概念,把神经网络的拓扑结构(用连接矩阵表示)与所求问题(用目标函数描述)对应起来,转换成神经网络动力学系统的演化问题。因此,在用Hopfield 网络求解优化问题之前,必须将问题映射为相应的神经网络。对TSP 问题的求解,首先将问题的合法解映射为一个置换矩阵,并给出相应的能量函数,然后将满足置换矩阵要求的能量函数的最小值与问题的最优解相对应。
2.模拟退火算法
模拟退火算法最初的思想由Metr opolis 在1953
年提出,[2]
Kirkpatrick 在1983年成功地将其应用在组合最优化问题中。模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特征在解空间中随机寻找目标函数的全局最优解,即在局部优解能
概率性地跳出并最终趋于全局最优。[1]
用固体退火模拟组合优化问题,将内能E 模拟为目标函数f,温度T 演化成控制参数t,即得到解组合优化问题的模拟退火算法:有初始解i 和控制参数初值t 开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t 值,算法终止时的当前解即为所得近似最优解。
高春涛:求解旅行商问题的几种解法
B I A N J I A N G J I N G J I Y U W EN HUA
11
解决TSP 问题的模拟退火算法的框架为:[3]
给定起、止“温度”T,T 0和退火速度a,初始的一条路径C 0;W hile (T >T 0)do;在C 0的邻域内产生另一条路径C 1;计算两条路径所引起的目标函数(能量)值的变化△E;若△E ≤0,接受新值,若exp (-△E /T )>rand (0,1)(rand (0,1)表示0～1之间的随机数,也接受新值,否则就拒绝;确定新的参数值,若扰动被接受,则C0←C1,否则不变化;若接受新值,降温T ←aT,否则不降温;End 。
模拟退火算法的实验性能具有质量高、初值鲁棒性强、通用易实现的优点。但是,为寻到最优解,算法通常要求较高的初温、较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样,因而模拟退火算法往往优化过程较长,这也是模拟退火算法最大的缺点。
3.遗传算法
遗传算法(Genetic A lgorith m s 简称G A )是基于生物进化原理的普适性全局优化算法,是美国M ichigan 大学的Holland 教授于1975年受进化论的启发而首次提出的。它引进生物学中基因遗传和“自然选择,适者生存”的进化思想,将优化问题的求解看成可行解的进化过程。一般地,遗传算法以一群随机产生的可行解开始,每个解用一串编码表示为个体,由优化目标函数确定个体的适应度对个体进行评价。通过交叉、变异等遗传算子的操作对种群进行组合产生下一代个体,逐步向优化的种群进化。
与传统的优化方法相比,遗传算法的主要特点是:遗传算法使用参数的编码集,而不是参数本身进行操作;遗传算法不在单点上寻优,而是从整个种群中选择生命力强的个体产生新的种群;遗传算法仅使用问题的目标函数进行工作,不需要其他的先决条件或辅助信息;遗传算法使用随机转换原理而不是确定性规则来工作。
遗传算法在具体实施中有多种变形和修正,其
主要操作思想可描述成:[4]
Step 1问题的染色体表示;Step2初始解组(种群)的生成;Step3计算解组中各个解的适值函数(代价函数);Step4从解组中随机抽取两个解作为父母代;Step5对父母代实施遗传操作(交叉、变异等)以产生一个后代解;
Step6按某种规则,用该后代解替代原解组中的某个解;Step7若当前解组符合停机条件,则算法终止,否则,转Step4。
遗传算法的优点是算法进行全空间并行搜索,并将搜索重点集中于性能高的部分,从而能够提高效率且不易陷入局部极小;算法具有固有的并行性,提高对种群的遗传处理可处理大量的模式,并
且容易并行实现。其主要缺点是对于结构复杂的组合优化问题,搜索空间大,搜索时间比较长,往往会出现早熟收敛的情况;对初始种群很敏感,初始种群的选择常常直接影响解的质量和算法效率。
4.蚁群算法
蚁群算法(Ant Col ony A lgorithm ,简称ACA )是由意大利学者Dorigo M 等人首先提出来的一种新型的模拟进化算法。它是从对蚁群行为的研究中产生的。仿生学家经过大量细致观察与研究发现,原来蚂蚁在寻食的过程中,通过一种称之为信息素的物质相互传递信息。更具体地说,蚂蚁在运动过程中能够在它所经过的路径上留下信息素,而且在运动过程中感知这种信息素的存在及其强度,并以此指导自己的运动方向。蚂蚁倾向于朝着信息素强度高的方向前进,因此,由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁群就是通过个体之间这种信息交换机制来彼此协作达到搜索食物的目的。为了避免蚂蚁两次走上同一条路径,为每个蚂蚁设置一个禁忌表以记录它走过的路径。
蚁群算法的优点在于:它是一种自适应、自组织、本质上并行的方法,而且是一种正向反馈的方法,可以促使整个系统向最优解进化,具有较强的鲁棒性,对蚁群算法模型稍加修改,就可以应用于其他问题,同时它可以与多种启发式算法结合,以改善算法的性能。但是该算法也具有收敛速度慢、易陷入局部最优等缺点。此外,算法中的参数设定目前尚无理论的依据,要靠实验来调整和确定。
TSP 问题是组合优化领域中的一个典型问题,解决此问题有较大的现实意义,并且此问题也可作为测试新的算法的标准问题,因此此问题一直是研究的热点。
参考文献:[1] 王 凌.智能优化算法及其应用[M ].北京:清华大学出版社,2001.
[2] M ETROP LO I S N,ROSE NBLUT B A W ,ROSE NBLUT B M N,ET AL.Equati on of State Calculati ons Fast Computing Machines
[J ].J of che m ical physica,1953,21(6):1087-1092.[3] 高 尚.求解旅行商问题的模拟退火算法[J ].华东船舶工业学院学报:自然科学版,2003,17(3):13-16.[4] 马 良.旅行推销员问题的算法综述[J ].数学的实践与认识,2000,30(2):156-165.
〔责任编辑:乙 侻〕
2.旅行商TSP问题(1.1)
旅行商问题 旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。 目录 目录 旅行商问题 (1) 目录 (1) 1.简介 (1) 2．研究历史 (2) 3.问题解法 (2) 4.解法思路 (2) 途程建构法 (2) 途程改善法 (2) 合成启发法 (3) 5.研究进展 (3) 6.问题分析 (3) 1.简介 “旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法。TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
2．研究历史 旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。 3.问题解法 旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP-Complete 的问题，从距离矩阵中产生一个近似最佳解的途径，有以下几种解法： 1、途程建构法（Tour Construction Procedures） 2、途程改善法（Tour Improvement Procedure） 先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。 3、合成启发法（Composite Procedure） 有以下几种解法:起始解求解+2-Opt：起始解求解+3-Opt： 4.解法思路 旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP完全问题（NP-Complete），所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种： 途程建构法 从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：如 1、近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点直到最后。（像贪婪算法） 2、节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。（像Dijstra算法） 3、插入法（Insertion procedures）：如插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。 途程改善法 先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：
TSP问题求解实验报告
TSP问题求解 （一）实验目的 熟悉和掌握遗传算法的原理，流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。 （二）实验原理 巡回旅行商问题 给定一组n个城市和俩俩之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。TSP问题也称为货郎担问题，是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的典型难题。TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法，模拟退火方法以及遗传算法方法等。 TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然的想法。
基本遗传算法可定义为一个8元组： （SGA）=（C，E，P0，M，Φ，Г，Ψ，Τ） C ——个体的编码方法，SGA使用固定长度二进制符号串编码方法； E ——个体的适应度评价函数； P0——初始群体； M ——群体大小，一般取20—100； Ф——选择算子，SGA使用比例算子； Г——交叉算子，SGA使用单点交叉算子； Ψ——变异算子，SGA使用基本位变异算子； Т——算法终止条件，一般终止进化代数为100—500； 问题的表示 对于一个实际的待优化问题，首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决TSP，一个旅程很自然的表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用。 路径表示是表示旅程对应的基因编码的最自然，最简单的表示方法。它在编码，解码，存储过程中相对容易理解和实现。例如：旅程（5-1-7-8-9-4-6-2-3）可以直接表示为（5 1 7 8 9 4 6 2 3） （三）实验内容 N>=8。
旅行商问题概述_郭靖扬
旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，简称ＴＳＰ）是一个著名的组合优化问题：给定ｎ个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。如果用图论来描述，那就是已知带权图Ｇ＝ （Ｃ，Ｌ），寻出总权值最小的Ｈａｍｉｌｔｏｎ圈。其中Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝表示ｎ个城市的集合，Ｌ＝｛ｌｉｊ｜ｃｉ，ｃｊ∈Ｃ｝是集合Ｃ中元素（城市）两两连接的集合，每一条边ｌｉｊ，都存在与之对应的权值ｄｉｊ，实际应用中ｄｉｊ可以表示距离、费用、时间、油量等。 ＴＳＰ的描述虽然简单， 解决起来却很困难。最简单思路是用穷举法把所有可能的巡回路径全部列出来，最短的一个就是最优解，但这样只能处理很小规模的问题。旅行商问题属于 ＮＰ－ｃｏｍｐｌｅｔｅ问题， 是ＮＰ（ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃｐｏｌｙ－ｎｏｍｉｎａｌ）问题中最难的一类，不能在多项式时间内求解。如果有ｎ座城市，那么巡游路径共有（ｎ－１）！／２条，计算的时间和（ｎ－１）！成正比。当 城市数ｎ＝２０，巡回路径有１．２×１０１８种，ｎ＝１００， 巡回路径就有多达４．６×１０１５５种，而据估计宇宙中基本粒子数“仅仅只有”１０８７个。 尽管如此，随着算法研究的逐步深入和计算机技术飞速提高，对ＴＳＰ问题的研究不断取得进展。７０年来，被征服的ＴＳＰ规模从几十个城市增加到上万个城市。目前的最高记录是在２００４年５月，找到的巡游瑞典２４９７８个城镇的最优路径 （ｓｗ２４９７８）， 花费了８４．８个ＣＰＵ年。图１展示了ＴＳＰ的研究进展，最近的二三十年时间里，被攻克的ＴＳＰ规模高速增长，差不多是每十年增加一个数量级。照这样发展下去的话，再过２０年就能解决上百万个城市的ＴＳＰ，有专家甚至已经为此准备好了数据：全球１９０，４７１１个城市的坐标。当然，能不能达到这 个目标，有赖于未来计算技术的发展。 图１ＴＳＰ的发展 字母后面的数字表示城市数，“ｓｗ２４９７８”就是瑞典的 ２４９７８个城镇。 一、应用 旅行商问题具有重要的实际意义和工程背景。它一开始 是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域，下面举几个实例。 印制电路板转孔是ＴＳＰ应用的经典例子，在一块电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为ＴＳＰ，孔相当于城市，孔到孔之间的移动时间就是距离。 为了避免大气干扰，使光学系统达到其衍射极限分辨率，欧美发达国家提出发展空间光干涉仪和综合孔径望远镜的计划。美国航空航天局有一个卫星群组成空间天文台（Ｓｐａｃｅ－ｂａｓｅｄＯｂｓｅｒｖａｔｏｒｉｅｓ）的计划， 用来探测宇宙起源和外星智慧生命。欧洲空间局也有类似的Ｄａｒｗｉｎ计划。对天体成像的时候，需要对两颗卫星的位置进行调整，如何控制卫星，使消耗的燃料最少，可以用ＴＳＰ来求解。这里把天体看作城市，距离就是卫星移动消耗的燃料。 美国国家卫生协会在人类基因排序工作中用ＴＳＰ方法绘制放射性杂交图。把ＤＮＡ片断作为城市，它们之间的相似程度作为城市间的距离。法国科学家已经用这种办法作出了老鼠的放射性杂交图。 此外，旅行商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是，它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题，和ＴＳＰ同属ＮＰ－ｃｏｍｐｌｅｔｅ类，它们都是同等难度的，如果其中一个能用多项式确定性算法解决，那么其他所有的ＮＰ－ｃｏｍｐｌｅｔｅ类问题也能用多项式确定性算法解决。很多方法本来是从ＴＳＰ发展起来的，后来推广到其他ＮＰ－ｃｏｍｐｌｅｔｅ类问题上去。 二、ＴＳＰ求解方法 求解旅行商问题的方法可以分为两大类，一类是精确算法，目的是要找到理论最优解；另一类是近似算法，不强求最优解，只要找到“足够好”的满意解就可以了。 （一）精确算法 如前面所述，穷举法和全局搜索算法属于精确算法，但 旅行商问题概述 郭靖扬 （电子科技大学光电信息学院， 四川成都６１００５４） 【摘要】旅行商问题是组合优化的经典问题，应用广泛，而且长期以来被作为ＮＰ－ｃｏｍｐｌｅｔｅ问题的理想研究平台。文章介绍 了旅行商问题的基础知识、应用，以及常用的求解方法。 【关键词】旅行商问题；组合优化；ＮＰ－ｃｏｍｐｌｅｔｅ；ｋ－ｏｐｔ；智能算法【中图分类号】ＴＰ１８２【文献标识码】Ａ【文章编号】１００８－１１５１（２００６）０８－０２２９－０２大众科技 ＤＡＺＨＯＮＧＫＥＪＩ２００６年第８期（总第９４期） Ｎｏ．８，２００６ （ＣｕｍｕｌａｔｉｖｅｌｙＮｏ．９４） 【收稿日期】２００６－０３－１８【作者简介】郭靖扬（１９８０－），四川宜宾人，电子科技大学光电信息学院硕士研究生。 ２２９－－
旅行商问题数学建模
黄石理工学院 数学建模大型作业2011—2012 学年第1学期
目录 一．摘要 二．旅行问题 1.问题描述 2.符号说明 3.模型设计 4.建模求解 5.模型分析 6. 三．建模过程及心得体会 四．参考文件
一．摘要 本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。 关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型 二．旅行问题 问题描述 某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F 旅游购物。他计划走遍这些城市各一次且仅一次，最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线？ 在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。
模型设计 首先给出一个定义：设v1,v2,......,vn 是图G 中的n 个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON 回路。 问题1. 分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立： 对于6个城市的旅行问题设A,B,C,D,E,F 六个城市分别对应v1,v2,v3,v4,v5,v6。假设ij d 表示从城市i 到城市j 的费用。定义0-1整数型变量ij x =1表示从城市i 旅行到城市j ，否则 ij x =0。则旅行问题的数学模型可表示为一个整数规划问题。 min z=66 1 ij ij i j d x =∑∑ (i ≠j) s.t. 6 1ij i x =∑=1 （i ≠j ；j=1,2, (6) 6 1 ij j x =∑=1 (i ≠j ；i=1,2, (6) 1i j ij u u nx n -+≤- (i ≠j;i=2,3,……,6;j=2,3,……6) 其中辅助变量i u （i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，i u =访问城市的顺序数。 模型求解 运用LINGO ，输入程序： MODEL : !Traveling Sales Problem for the cities of six city; SETS :
TSP问题的解决方案
《算法设计与分析》实验报告一 学号：姓名： 日期：20161230 得分： 一、实验内容： TSP问题 二、所用算法的基本思想及复杂度分析： 1、蛮力法 1）基本思想 借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点到自身节点的距离为无穷大。在第一行找到最小项a[1][j]，从而跳转到第j行，再找到最小值a[j][k]，再到第k行进行查找。。。然后构造各行允许数组row[n]={1,1…1}，各列允许数组colable[n]={0,1,1….1}，其中1表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已经被访问。如果改行或该列不允许访问，跳过该点访问下一节点。程序再发问最后一个节点前，所访问的行中至少有1个允许访问的节点，依次访问这些节点找到最小的即可；在访问最后一个节点后，再次访问，会返回k=0，即实现访问源节点，得出一条简单回路。 2）复杂度分析 基本语句是访问下一个行列中最小的点，主要操作是求平方，假设有n个点，则计算的次 页脚内容1
数为n^2-n。T(n)=n*(n-1)=O(n^2)。 2、动态规划法 1）基本思想 假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。 推导：(分情况来讨论) ①当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的城市3->城市0(0 为起点城市)。此时d(i, V’)=Cis(就是城市i 到城市s 的距离)、 ②如果V’不为空，那么就是对子问题的最优求解。你必须在V’这个城市集合中，尝试每一个， 并求出最优解。 d(i, V’)=min{Cik +d(k, V’-{k})} 注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。 综上所述，TSP问题的动态规划方程就出来了： 2）复杂度分析 和蛮力法相比，动态规划求解tsp问题，把原来时间复杂性O（n！）的排列转化为组合问题，从而降低了时间复杂度，但仍需要指数时间。 3、回溯法 1）基本思想 页脚内容2
模拟退火算法的旅行商问题
人工智能原理 实验报告 模拟退火算法解决TSP问题
目录 1 旅行商问题和模拟退火算法........................................... 错误!未定义书签。 旅行商问题................................................................... 错误!未定义书签。 旅行商问题的描述................................................. 错误!未定义书签。 模拟退火算法............................................................... 错误!未定义书签。 基本思想................................................................. 错误!未定义书签。 2 TSP模拟退火算法的实现................................................ 错误!未定义书签。 TSP算法实现............................................................... 错误!未定义书签。 TSP算法描述......................................................... 错误!未定义书签。 TSP算法流程......................................................... 错误!未定义书签。 TSP的C实现 .............................................................. 错误!未定义书签。 加载数据文件......................................................... 错误!未定义书签。 计算总距离的函数................................................. 错误!未定义书签。 交换城市的函数..................................................... 错误!未定义书签。 执行模拟退火的函数............................................. 错误!未定义书签。 实验结果......................................................................... 错误!未定义书签。 小结................................................................................. 错误!未定义书签。3源代码................................................................................ 错误!未定义书签。
多旅行商问题模型
以点0表示旅行商的出发城市，称为源点，点1,2, ,l 表示m 个旅行商需访 问的城市。MTSP 问题的数学模型可以表示为： 令10ij x ?=??弧(i,j)在线路上 弧(i,j)不在线路上 模型表示如下： 0000min 10,1,,10,1,,()01,0,1,,R R ij ij i j R ij i R ij j ij ij z d x x j R x i R X x S x i j R ====?=?? ?==????==??=∈??==?∑∑∑∑或 式中：1;ij R m l d =+-为增广费用。若用(,1,,)ij c i j l =表示旅行商经过对应弧度(,)i j 所花的费用，如时间、距离、花费等，那么给ij c 增加(1)m -行和(1)m -列，每一新的行或列是ij c 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用ij d 。 一般MTSP 中，旅行商访问l 个城市必须满足以下2个条件。 条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m 条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP ，可通过附加虚拟城市的方法把MTSP 转化为TSP 。将另外(1)m -个旅行商理解为(1)m -个虚拟城市，这(1)m -个虚拟城市标号分别为1,2,,1,l l l m +++-，它们与城市0具有相同的坐标(即相同位置)。在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP 中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(1)m -个虚拟城市到原点的距离为 00(,0,1,,1),ij c M i j l l m M ==++-为一无穷大的正数（即永远不能达到），到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。将源点0复制(1)m -个，m 个源点编号为0,1,1,l l m ++-每一个同源点0一样与其他
货郎担问题或旅行商问题动态规划算法
#include { /*if(mincost <= cost[cur][i]+cost[i][start]) { continue; //其作用为结束本次循环。即跳出循环体中下面尚未执行的语句。区别于break } */ visit[i] = 1; //递归调用时，防止重复调用 int value = cost[cur][i] + imin(num-1, i); if(mincost > value) { mincost = value; } visit[i] = 0;//本次递归调用完毕，让下次递归调用 } } return mincost; } int main() { int i,j; // int k,e,w; n=4; int cc[4][4]={{0,10,15,20}, {5,0,9,10}, {6,13,0,12}, {8,8,9,0}}; for(i=0; i 实验报告：用遗传算法解决旅行商问题的简单实现 实验目的：编写程序实现用遗传算法解决旅行商问题，研究遗传算法的工作原理和收敛性质。 实验者： 问题描述：TSP是一个具有广泛应用背景和重要理论价值的组合优化难题，TSP问题可以简单的描述为：已知N个城市之间的相互距离．现有一个旅行商必须遍历这N个城市，并且每个城市只能访一次，最后必须返回出发城市。如何安排他对这些城市的访问次序，可使旅行路线的总长度最短？ 本次实验的目标问题中国大陆31个大城市的公路旅行商问题，数据来源是《中国大城市公路里程表》（后附）。 需求分析：TSP已经被证明是一个NP—Hard问题，即找不到一种算法能在多项式时间内求得问题的最优解。利用遗传算法，在一定时间内求得近似最优解的可能性比较大。实验目标是： 1）设计用遗传算法解决TSP问题的程序； 2）求出该TSP问题的（近似）最短路程； 3）求得相应的城市遍历序列； 4）检查算法收敛性，求解决该问题的（近似）最优遗传参数。 算法分析： 1．算法基本流程 2．编码策略与初始群体设定 TSP的一般编码策略主要有二进制表示、次序表示、路径表示、矩阵表示和边表示等。而路径编码是最直观的方式，以城市序号作为遗传基因。在本实验中，我们用一个N维向量来表示一个个体，N是城市总数，元素表示城市遍历顺序，以最后一个到达的城市为结束。则群体用一个N * POP的矩阵表示，POP为群体中的人口（个体数）。初始群体在空间中自动生成。 3．适应度函数及结束条件 适应度函数采用题目的目标函数——路径的总路程（包括回到出发点）。适应度越低，个体越优秀。由于暂时无法先验估计收敛性和目标结果，所以以一个参数，最大遗传代数MAXGEN作为程序结束控制。 4．遗传算子设计 遗传算子的设计方法主要有两大类：自然算法和贪心算法。自然算法是以大自然的进化规律为依据，大体采用“优胜劣汰”的机制来进行遗传；贪心算法则是以迅速收敛为目标，对个体进行更严格的选择和遗传处理。 算法设计与分析实验报告实验三旅行商问题 院系： 班级：计算机科学与技术 学号： 姓名： 任课教师： 成绩： 湘潭大学 2016年5月 实验三旅行商问题 一. 实验内容 分别编程实现回溯法和分支限界法求TSP问题的最优解，分析比较两种算法的时间复杂度并验证分析结果。 二．实验目的 1、掌握回溯法和分支限界法解决问题的一般步骤，学会使用回溯法和分支限界法解决实际问题； 2、理解回溯法和分支限界法的异同及各自的适用范围。 三. 算法描述 旅行商问题的回溯法算法可描述如下： Template if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&& (cc+a[x[n-1]][x[n]]+a[x[n]][1] +a[x[n]][1] 旅行商问题： 问题描述：已知一个由n个城市（顶点）组成的有向网G , n个城市为v1, v2,…, v n , G的邻接矩阵为D=(d ij)nxn , d ij为边< v i, v j>上的权（表示城市v i到v j的耗费）。一个旅行商从v1开始，巡回访问每个城市一次且仅一次，最后返回v1, 这个旅行商该如何选择旅行线路，使得整个行程耗费最小？ ● 分析： 可利用求一般问题的所有解的回溯算法得到解最优化问题的回溯算法。 (1) 该问题是求最短的哈密顿回路。 (2) 用min表示当前最优值，s[1..n]表示当前最优解。 (3) 除了解的约束条件，用如下剪枝条件进一步剪枝： 当前路径长度>=min (4) 设置一个标记数组tag[1..n]： tag[i]=1, 顶点i在当前路径上 tag[i]=0, 顶点i不在当前路径上 当一个顶点退出当前路径时，该顶点的标记应复原为0。 ● 回溯算法： 算法 TRAVELING_SALESMAN 输入：正整数n和含n个顶点的有向网G的邻接矩阵D。 输出：关于G的旅行商问题的一条最短旅行线路和最小耗费, 若问题无解，则输出no solution。 min=∞ x[1]=1 //用x[1..n]表示当前搜索路径, 从顶点1开始。 len=0 //len表示当前路径的长度 tag[1]=1; tag[2..n]=0 //设顶点标记初值。 salesman( 2 ) if min<∞ then output (min, s[1..n]) //输出最优值和最优解。 else output (“no solution”)//输出无解 end if end TRAVELING_SALESMAN 过程 salesman(k) //在已得到当前路径x[1..k-1]的情况下，求G的长度 2012 年第一学期研究生课程考核 （实验报告、研究报告） 考核科目：算法分析与复杂性理论 学生所在学院：计算机科学与技术学院 学生所在学科：计算机应用技术 姓名： 学号： 学生类别：研究生 一、实验目的 1.通过TSP算法的具体实现，加深对算法复杂分析的理解。 2.通过TSP算法的具体实现，提高对NP完全问题的认识。 3.通过TSP算法的具体实现，理解不确定性算法。 4.通过TSP算法的具体实现，理解不确定性算法。 二、实验环境 实验平台：Visual C++ 6.0 编程语言：C++ 编程电脑配置： 三、实验内容描述 TSP（Travelling Salesman Problem）又称货郎担或巡回售货员问题，在运筹学、管理科学及工程实际中具有广泛的用途。及工程实际中具有广泛的用途。TSP问题是组合优化中的著名难题，一直受到人们的极大关注。由于其NP难题性质，至今尚未完全解决。此问题可以抽象描述为： 给出一个n个顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。其中，任何一个包含所有n个顶点的环路被称作一个旅行。 对于旅行商问题，顶点表示旅行商所要旅行的城市（包括起点）。边上权值给出了在两个城市旅行所需的路程。旅行表示当旅行商游览了所有城市后再回到出发点时所走的路线。 四、实验原理 许多研究表明，应用蚁群优化算法求解TSP问题优于模拟退火法、遗传算法、神经网络算法、禁忌算法等多种优化方法。 为说明该算法，引人如下的标记: m表示蚁群中蚂蚁的数量； 表示城市i和城市j之间的距离；表示t时刻位于城 市i的蚂蚁数，显然应满足，表示t时刻在ij连线上的信息数 量。在算法的初始时刻，将m只蚂蚁随机地放到n座城市上，此时各路径上的信息量相等，设。每只蚂蚁根据路径上保留的信息量独立地选择下一个城市。在时刻t，蚂蚁k从城市i转移到城市j 的概率为 其中，表示蚂蚁走下一步允许选择的所有城市，列表纪录了当前蚂蚁k所走过的城市，当所有n个城市都加入到中时，蚂 蚁k便完成了一次循环，此时蚂蚁走所走过的路径便是问题的一个解。是一个启发式因子，表示蚂蚁从城市i转移到城市j的期望程度，在蚂蚁算法中，通 常取 城市ij之间距离的倒数。α和β分别表示路径上信息量和启发示因子的重要程度。 当所有蚂蚁完成一次循环后，各路径上的信息量要根据下面的公式进行调整： 令x ij 弧(i,j)在线路上 弧(i,j) 不在线路上 以点0表示旅行商的出发城市，称为源点，点1,2丄，1表示m个旅行商需访 问的城市。MTSP问题的数学模型可以表示为: 模型表示如下: RR min z d ij x ij i0j0 R x ij 1 j 0,1,L ,R i0 R x ij 1 i 0,1,L ,R j0 X (x ij ) S x ij 0或1 i, j 0,1,L ,R 式中：R m l 1;d ij为增广费用。若用C ij (i,j 1,L ,1)表示旅行商经过对应弧度(i, j)所花的费用，如时间、距离、花费等，那么给q增加(m 1)行和(m 1)列，每一新的行或列是c ij 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用d ij 。 一般MTSP中，旅行商访问I个城市必须满足以下2个条件。 条件 1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP，可通过附加虚拟城市的方法把 MTSP转化为TSP。 将另外(m 1)个旅行商理解为(m 1)个虚拟城市，这(m 1)个虚拟城市标号分 别为l 1,l 2,L ,l m 1,，它们与城市0具有相同的坐标(即相同位置)。在旅 行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(m 1)个虚拟城市到原点的距离为 c ij M0(i, j 0,l 1,L ,l m 1 ) , M 0为一无穷大的正数(即永远不能达到) ，到其他各点距离与原点一致，这样遗传算法就不会出现 0-0-0 的途径。将源点 0 复制(m 1)个，m个源点编号为0,1 1,L l m 1,每一个同源点0 —样与其他 T S P问题算法分析集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289- 算法第二次大作业 TSP问题算法分析 021251班 王昱（02125029） 一．问题描述 “TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。 TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。 二．算法描述 2.1分支界限法 2.1.1算法思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 2.1.2算法设计说明 设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。 对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即： bound(x1)≥bound(x1,x2)≥…≥bound(x1,…,xn) 若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。 再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。 直到一个叶子结点时的可行解X=(x1,…,xn)，及目标函数值 bound(x1,…,xn)。 2.2A*算法 算法思想 对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有 f*(n)=g*(n)+h*(n)。 （实验报告、研究报告） 考核科目：算法分析与复杂性理论 学生所在学院：计算机科学与技术学院 学生所在学科：计算机应用技术 姓名： 学号： 学生类别：研究生 一、实验目的 1.通过TSP算法的具体实现，加深对算法复杂分析的理解。 2.通过TSP算法的具体实现，提高对NP完全问题的认识。 3.通过TSP算法的具体实现，理解不确定性算法。 4.通过TSP算法的具体实现，理解不确定性算法。 二、实验环境 实验平台：Visual C++ 编程语言：C++ 编程电脑配置： 三、实验内容描述 TSP（Travelling Salesman Problem）又称货郎担或巡回售货员问题，在运筹学、管理科学及工程实际中具有广泛的用途。及工程实际中具有广泛的用途。TSP问题是组合优化中的著名难题，一直受到人们的极大关注。由于其NP难题性质，至今尚未完全解决。此问题可以抽象描述为： 给出一个n个顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。其中，任何一个包含所有n个顶点的环路被称作一个旅行。 对于旅行商问题，顶点表示旅行商所要旅行的城市（包括起点）。边上权值给出了在两个城市旅行所需的路程。旅行表示当旅行商游览了所有城市后再回到出发点时所走的路线。 四、实验原理 许多研究表明，应用蚁群优化算法求解TSP问题优于模拟退火法、遗传算法、神经网络算法、禁忌算法等多种优化方法。 为说明该算法，引人如下的标记: m表示蚁群中蚂蚁的数量； 表示城市i和城市j之间的距离；表示t时刻位于城市i的蚂蚁数，显然应满足，表示t时刻在ij连线上的信息数量。在算法的初始时刻，将m只蚂蚁随机地放到n座城市上，此时各路径上的信息量相等，设。每只蚂蚁根据路径上保留的信息量独立地选择下一个城市。在时刻t，蚂蚁k从城市i转移到城市j 的概率为 其中，表示蚂蚁走下一步允许选择的所有城市，列表纪录了当前蚂蚁k所走过的城市，当所有n个城市都加入到中时，蚂蚁k便完成了一次循环，此时蚂蚁走所走过的路径便是问题的一个解。是一个启发式因子，表示蚂蚁从城市i转移到城市j的期望程度，在蚂蚁算法中， 通常取 城市ij之间距离的倒数。α和β分别表示路径上信息量和启发示因子的重要程度。 当所有蚂蚁完成一次循环后，各路径上的信息量要根据下面的公式进行调整： 其中表示路径上信息的蒸发系数；表示信息的保留系数；表示本次循环路径ij上信息的增量。表示第k只蚂蚁在本次循环中留在路 2010年第5期(总第77期) 边疆经济与文化 THE BORDER ECONOMY AND CULT URE No 1512010General 1No 177 10 B I A N J I A N G J I N G J I Y U W EN HUA 【旅游经济】 求解旅行商问题的几种解法 高春涛 (哈尔滨商业大学基础科学学院,哈尔滨150028) 摘 要:旅行商问题(TSP )是一个典型的NP 完全问题,现在还没有找到有效的解法。目前比较热门的求解TSP 问题的方法主要有四种:神经网络算法;模拟退火算法;遗传算法;蚁群算法。 关键词:旅行商问题;组合优化;解法 中图分类号:F 592 文献标志码:A 文章编号:167225409(2010)0520010202 收稿日期:2010201222作者简介:高春涛(1973 ),女,黑龙江拜泉人,讲师,硕士,主要从事混沌神经网络研究。 一、引言 旅行商问题(Traveling Sales man Pr oble m ),是指给定n 个城市,任何两城市之间皆有路连通,其距离为已知,某旅行商从其中某城市出发,要经过每城市一次,且只能一次,最后又必须返回出发城市,要求找出最短的巡回路径。由于在很多实际问题中,如印刷电路板的铅孔路线方案、连锁店的货物配送路线等问题经过简化处理,均可建模为旅行商问题,因而对旅行商问题求解方法的研究具有重要的应用价值。旅行商问题是运筹学中有代表性的组合优化问题,也是典型的NP 完全问题。虽然它陈述起来很简单,但求解却很困难,对于具有n 个城市的TSP 问题,其可能的路径数目为(n -1)!/2,至今尚未找到有效的求解方法,在理论上枚举法可以解决这一问题,但是当n 较大时,解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短,能满足实际问题精度要求的解,成为解决该问题的主要途径。 二、TSP 求解方法 求解旅行商问题的方法可以分为两大类,一类是精确算法,目的是要找到理论最优解;另一类是近似算法,其算法简单,计算量小,大多数情况下求得的满意解能满足要求。 1.Hopfield 神经网络算法 1982年,Hopfield 开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁,提出了Hopfield 反馈神经网络模型(HNN )。Hopfield 网络是典型的全连接网络,通过在网络中引入能量函数以构造动力学系统,并使网络的平衡态与能量函数 的极小解相对应,从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。尤其是通过对TSP 问题的成功求解,开辟了神经网络模型在计算机科学应用中的新天地,动态反馈网络从而受到广泛的研究和关注,被广泛应用于优化问题中,且已 设计出了专用的硬件电路。 [1] Hopfield 网络是一种非线性动力学模型,通过引入类似Lyapunov 函数的能量函数概念,把神经网络的拓扑结构(用连接矩阵表示)与所求问题(用目标函数描述)对应起来,转换成神经网络动力学系统的演化问题。因此,在用Hopfield 网络求解优化问题之前,必须将问题映射为相应的神经网络。对TSP 问题的求解,首先将问题的合法解映射为一个置换矩阵,并给出相应的能量函数,然后将满足置换矩阵要求的能量函数的最小值与问题的最优解相对应。 2.模拟退火算法 模拟退火算法最初的思想由Metr opolis 在1953 年提出,[2] Kirkpatrick 在1983年成功地将其应用在组合最优化问题中。模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特征在解空间中随机寻找目标函数的全局最优解,即在局部优解能 概率性地跳出并最终趋于全局最优。[1] 用固体退火模拟组合优化问题,将内能E 模拟为目标函数f,温度T 演化成控制参数t,即得到解组合优化问题的模拟退火算法:有初始解i 和控制参数初值t 开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t 值,算法终止时的当前解即为所得近似最优解。实验报告：遗传算法在解决旅行商问题的应用
[精品文档]旅行商问题
旅行商问题
TSP实验报告
多旅行商问题模型
TSP问题算法分析
TSP实验报告
求解旅行商问题的几种解法