旅行商问题 Traveling Salesman Problem（TSP）

Presentation on theme: "旅行商问题 Traveling Salesman Problem（TSP）"— Presentation transcript:

1 旅行商问题 Traveling Salesman Problem（TSP）

2 旅行商问题的发展历史 旅行商问题，也称货郎担问题，是一个较古老的问题。其起源已经有些模糊了。最早大概可以追溯到 1759 年 Euler 提出的骑士旅行问题。 十九世纪初，爱尔兰数学家William R. Hamilton和英国数学家Thomas P. Kirkman研究过一些与旅行商问题相关的数学问题。

3 二十世纪初，人们开始研究通用形式的旅行商问题。
二十世纪二十年代，数学家和经济学家 Karl Menger 在维也纳向他的同事提出了这个问题。 二十世纪三十年代，旅行商问题出现在 Princeton 大学的数学圈子里，主要的推动者有 Hassler Whitney 与 Merrill Flood。 二十世纪四十年代，统计学家(Mahalanobis(1940), Jessen(1942), Gosh(1948), Marks(1948))把它和农业应用联系在一起研究。美国RAND 公司也推动了这个问题的发展。 最终，旅行商问题成为了组合优化问题中的一个困难问题原型的典型代表。求解这种问题令人望而生畏：当问题规模变大的时候，路径的数目将是个天文数字，逐一检查它们几乎是不可能的。在很长的一段时间内，没有任何解决这个问题的好想法出现.

4 1954 年，旅行商问题的求解终于获得了突破。George Dantizig, Ray Fulkerson 和 Selmer Johnson 提出了一个求解旅行商问题的算法并用它成功地解决了一个有49 个城市的实例。这个规模在当时相当引人注目; 1977 年，Groetschel 找到了有 120 个城市的旅行商问题的最优路径; 1987年，Padberg 与 Rinaldi 找到了规模为 532 和 2392 的旅行商问题的最优路径；Groetschel与Holland找到了规模为666的旅行商问题的最优路径。 Applegate, Bixby,Chavátal 和 Cook 于 1994 年,1998年和 2001年解决了规模为 7397, 13509和 15112的旅行商问题。 2004 年，一个具有 个城市的旅行商问题的最优路径由 Applegate, Bixby,Chavátal, Cook 和 Helsgaun 找到。这是到目前为止精确找到最优解的最大规模的旅行商问题.

5 旅行商问题吸引了越来越多的人对它进行研究。其中，有数学家，计算机科学家，运筹学家，还有一些其它领域的研究者。
然而，该问题是否存在一个有效的通用的求解方法仍然是一个开放性的问题。事实上，旅行商问题的解决将意味着 P=NP问题的解决。Clay Mathematics Institute 曾悬赏 100 万美元来寻求这个问题的解法，但没人拿到这个奖。

6 旅行商问题的描述 旅行商问题(TSP) 的文字描述可以表达如下：给定一组 N 个城市和它们两两之间的直达距离，找出一个闭合的回路，使得每个城市刚好经过一次且仅一次且总的旅行距离最短。即要寻求一条回路 T = (t 1 ,t2,...,tn)，使得下列目标函数最小： 上式中 t i为城市号，取值为 [1 ,n ]，从而 ( t1 , t2,...,tn)就可以看作是关于n的一个排列。d ( ti ,tj)表示城市 ti 与 t j之间的距离。对于对称型 TSP，有 d ( ti ,tj)= d(tj,ti)

7 旅行商问题的分类 从问题对应到图的类型，TSP 可以分为两类： 1、任意两个城市间的距离都是对称的，它对应的是图论中的无向图；
2、两个城市间的距离是非对称的，它对应的是图论中的有向图； 从问题本身的限制条件的强弱，主要有三类： 1、不做任何限制(但是一般都要求城市间的费用不为负数)，只给出距离矩阵，求最短回路； 2、要求距离间要满足三角不等式； 3、定义在欧氏平面上的 TSP，即 Euclidean TSP，它给出每个城市在欧氏平面上的坐标，而城市间的距离就是以它们的欧氏距离来定义。

8 从问题的多项式可解性上分，TSP 可以分为两类：
1、目前己经知道有多项式时间算法可解的，比如其距离矩阵满足特定的条件 (Demidenko 条件、Kalmanson 条件、Supnick 条件)等； 2、目前尚没有发现多项式时间算法可解的，而研究热点是如何寻找更多的多项式时间可解的情形。 对旅行商问题的研究经过几十年的发展，已经产生了许多其它扩展形式,例如多旅行商问题(Multi-Salesman Problem),多目标旅行商问题(Multi-Objective TSP)等等。

9 旅行商问题的应用和价值 旅行商问题是一个具有广泛的实用背景与重要的理论价值的组合优化难题。
许多关于 TSP 的工作并不仅是由实际应用直接推动的，而是因为 TSP 为其它一般的各类算法提供了思想方法平台，而这些算法广泛地应用于各种离散优化问题。 其次，TSP 大量的直接应用给研究领域带来了生机，并引导了未来的工作

10 运输问题是 TSP 最自然的应用。由于其模型的简单性，TSP 在其它一些领域有着有趣的应用。一个经典的例子是如何安排机器在一块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从一个孔移到下一个孔所花的时间。虽然钻孔的技术不断发展，但无论何时，只要钻机设备的移动时间在所有制造业的过程中占据显著的地位，TSP 在减少费用上就扮演了一个非常重要的角色。 许多实际中出现的问题都可以转化成旅行商问题的模型而解决。例如还有结晶学中的结构分析问题，车辆调度问题，计算机布线问题，单个机器上的工序调度问题等等。

11 旅行商问题的计算复杂性 时间复杂性，即随着输入问题规模的增长，算法所需计算步数的增长速度。
计算机科学家们有一个共识：即当输入规模n表示的算法复杂性函数 f (n)是以多项式为界的，算法才被认为是有效的。 从本质上讲，所有的计算问题又可以归结为判定问题，如果说：一个算法解决了某一判定问题，则算法输出“是”，否则输出“非”。而从输入到输出，算法所需要运行的步骤即为算法的时间复杂性。

12 很多优化问题，诸如旅行商问题、最小覆盖问题、多处理器任务调度问题、背包问题等都被发现可以多项式约化为 NP 中最难的问题，即 NP 完全问题。

13 TSP的时间复杂度 TSP 搜索空间随着城市数 n 的增大而增大，所有的旅程路线组合数为( n -1)!/2。
5 个城市的情形对应 120/10=12 条路线； 10 个城市的情景对应 /20= 条路线； 100 个城市的情景对应有 4.666×10155 条路线。 所以对于输入规模为n个城市的 TSP 找到最优解的时间复杂性函数的数量级是 O( n!)，当n 比较大时，耗费的时间已经是个天文数字。 表 2.1 是在假定所用计算机每秒可以执行 10 亿次运算的前提下，对不同的时间复杂性函数所耗费时间的比较。

14

15 求解旅行商问题的已有算法 多年来对 TSP 的研究，人们提出了许多求解方法，其中有精确算法如线性规划方法、动态规划方法、分支定界方法；
近似算法如插入法、最近邻算法、Clark&Wright 算法、生成树法、Christofides 算法、r-opt 算法、混合算法、概率算法等。 近年来，还有很多尝试解决该问题的较为有效的方法不断被提出，例如禁忌搜索方法、遗传算法、模拟退火算法、神经网络方法、蚁群算法等。

16 基于灾变思想的GA实现TSP实例 遗传算法的局部搜索能力较强，但是很容易陷入局部极值。
虽然增加变异概率可以搜索到远离当前极值的点，但是新点的值往往不能和当前保留下来的较优值相提并论，因为这些较优值都是经过千百代的进化而存留下来的，于是远离当前极值的点往往在两到三代以内就被淘汰掉了。 增加变异概率实际上是把遗传算法退化成了一种纯粹的随机搜索，所谓的自适应也无从谈起！

17 灾变思想 那么如何解决遗传算法容易陷入局部极值的问题呢？
让我们来看看大自然提供的方案。六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地。 事实上地球至少经历了5次物种大灭绝，每次物种灭绝都给更加高级的生物提供了充分进化的余地。 所以要跳出局部极值就必须杀死当前所有的优秀个体，从而让远离当前极值的点有充分的进化余地。这就是灾变思想。

18 灾变倒计数处理 下一个问题是什么时候进行灾变，换句话说什么时候局部搜索已经充分了呢？
可用了一个灾变倒计数的概念：从500开始递减，每一代递减一次，如果出现了新的最优值，就从新开始计数，如果出现新最优值的时候倒计数递减次数的2.5倍已经超过500则从新的初始值开始倒数。 例：初始倒数500，如果倒数到200时出现新最优值，则从( ) * 2.5 = 750开始从新倒数，下一次如果倒数到100时出现新最优值，则从( ) * 2.5 = 1625开始倒计数(这里的2.5是一个经验值，可以在全局参数设置里面调整)。也就是说倒计数的长度取决于进化的速度，进化速度越慢倒计数长度越长。如果倒计数完毕还没有新的最优值，就认为局部搜索已经充分，就发生灾变。

19 程序输入是一个文本文件，记录所有城市的坐标，以及最优个体的序列。以一张只有10个城市的地图为例，文本中可能记录了以下内容： 0
程序输入是一个文本文件，记录所有城市的坐标，以及最优个体的序列。以一张只有10个城市的地图为例，文本中可能记录了以下内容： 　　 , , 8 　　 , , 3 　　 , , 7 　　 , , 2 　　 , , 0 　　 , , 4 　　 , , 6 　　 , , 5 　　 , , 1 　　 , , 9 表示第一个城市的坐标为 , (程序客户区的宽和高为单位1，所有城市的坐标值均在[0.0,0.0]到[1.0,1.0]之内)，第二个城市坐标为 , 依次类推。 后面所跟的整数为最优个体的序列，上述数据表示旅行商应该从第8号城市( , )出发，经过3，7，2，0，4，6，5，1，9号城市，最后又回到第8号城市。 　　

20 程序的最终目标是求取一个序列，使得旅行商按照这个序列旅行时行程最短。
程序的变异方法是自繁殖变异，有两种：1、随机取两点，逆序这两点间的序列。2、随机把一个城市转移到另一个序列位置。 对于一个500个城市的地图，大概在5万代左右发生第一次灾变，用时约6-8分钟，灾变前夕的灾变倒计数初始值已经从800达到 。可以看到从一次灾变结束到下一次灾变开始，最优值的变化趋势近似呈一条拖拽线，越接近局部极值进化速度越慢，这也说明灾变倒计数的策略是正确的。

21 以下是一次试验的数据统计： 程序运行2个小时，进化到100万代，发生了16次灾变，最优个体产生于第606722代，属于第11个进化周期，总行程长度为 ，第一次灾变发生在第49773代，第一次灾变前最优个体产生于第45523代，总行程长度为 。

22 最佳路线图

23 第一次灾变前的最佳路线

24 第一次灾变前的最优分趋势图

25 最后一次灾变前的最优分趋势图 在每个进化周期内最优分图形基本呈拖拽线形状，可以看到多数进化周期已经没有进化速度，说明局部搜索已经充分，少数进化周期在发生灾变时还有明显进化速度，这是因为这些周期恰好进入一个比较长的停滞期时被程序认为局部搜索充分了，停滞期的出现根随机数有关，个人认为应该可以通过调节灾变初始值和灾变倍增值解决。

26 第一次灾变前的平均分趋势图

27 最后一次灾变前的平均分趋势图

28 分析平均分趋势图 可以看到每次发生灾变后群体平均分会达到一个较大的值，然后迅速下降，再慢慢上升。这说明旅行商问题的局部极值非常多，极值附近解的分数要远远低于整个解空间的平均分，这主要是因为一个较优解进行一次变异后生成的子女绝大部分都是畸形的分数很低的个体，由于遗传算法并不放弃这些进化方向，从而影响了群体的平均分。 灾变时对整个解空间进行随机搜索，这时的群体平均分可以作为整个解空间平均分的体现，进化一定时间以后，群体迅速陷入到一个特定的局部极值附近，这个时候较优解还没有进化出来，群体中充斥着畸形个体，只有少量比较优秀的个体，所以平均分也随之迅速下降，随后由于优秀个体存活率比较高，群体渐渐被优秀个体统治，群体平均分也开始上升。 仔细分析每一个进化周期的平均分趋势图可以发现，在进化的后期群体平均分有一个稳固上升的阶段（这应该是最优个体慢慢排挤其他个体的结果），在此之前都会有一个标志性的少量下挫曲线（如图），还不知道产生这个曲线的原因。

29 程序下载地址：