旅行商问题-Traveling-Salesman-Problem

旅行商问题TravelingSalesmanProblem（TSP）旅行商问题的发展历史•旅行商问题，也称货郎担问题，是一个较古老的问题。其起源已经有些模糊了。最早大概可以追溯到1759年Euler提出的骑士旅行问题。•十九世纪初，爱尔兰数学家WilliamR.Hamilton和英国数学家ThomasP.Kirkman研究过一些与旅行商问题相关的数学问题。•二十世纪初，人们开始研究通用形式的旅行商问题。•二十世纪二十年代，数学家和经济学家KarlMenger在维也纳向他的同事提出了这个问题。•二十世纪三十年代，旅行商问题出现在Princeton大学的数学圈子里，主要的推动者有HasslerWhitney与MerrillFlood。•二十世纪四十年代，统计学家(Mahalanobis(1940),Jessen(1942),Gosh(1948),Marks(1948))把它和农业应用联系在一起研究。美国RAND公司也推动了这个问题的发展。•最终，旅行商问题成为了组合优化问题中的一个困难问题原型的典型代表。求解这种问题令人望而生畏：当问题规模变大的时候，路径的数目将是个天文数字，逐一检查它们几乎是不可能的。在很长的一段时间内，没有任何解决这个问题的好想法出现.•1954年，旅行商问题的求解终于获得了突破。GeorgeDantizig,RayFulkerson和SelmerJohnson提出了一个求解旅行商问题的算法并用它成功地解决了一个有49个城市的实例。这个规模在当时相当引人注目;•1977年，Groetschel找到了有120个城市的旅行商问题的最优路径;•1987年，Padberg与Rinaldi找到了规模为532和2392的旅行商问题的最优路径；Groetschel与Holland找到了规模为666的旅行商问题的最优路径。•Applegate,Bixby,Chavátal和Cook于1994年,1998年和2001年解决了规模为7397,13509和15112的旅行商问题。•2004年，一个具有24978个城市的旅行商问题的最优路径由Applegate,Bixby,Chavátal,Cook和Helsgaun找到。这是到目前为止精确找到最优解的最大规模的旅行商问题.•旅行商问题吸引了越来越多的人对它进行研究。其中，有数学家，计算机科学家，运筹学家，还有一些其它领域的研究者。•然而，该问题是否存在一个有效的通用的求解方法仍然是一个开放性的问题。事实上，旅行商问题的解决将意味着P=NP问题的解决。ClayMathematicsInstitute曾悬赏100万美元来寻求这个问题的解法，但没人拿到这个奖。旅行商问题的描述•旅行商问题(TSP)的文字描述可以表达如下：给定一组N个城市和它们两两之间的直达距离，找出一个闭合的回路，使得每个城市刚好经过一次且仅一次且总的旅行距离最短。即要寻求一条回路T=(t1,t2,...,tn)，使得下列目标函数最小：•上式中ti为城市号，取值为[1,n]，从而(t1,t2,...,tn)就可以看作是关于n的一个排列。d(ti,tj)表示城市ti与tj之间的距离。对于对称型TSP，有d(ti,tj)=d(tj,ti)旅行商问题的分类•从问题对应到图的类型，TSP可以分为两类：1、任意两个城市间的距离都是对称的，它对应的是图论中的无向图；2、两个城市间的距离是非对称的，它对应的是图论中的有向图；•从问题本身的限制条件的强弱，主要有三类：1、不做任何限制(但是一般都要求城市间的费用不为负数)，只给出距离矩阵，求最短回路；2、要求距离间要满足三角不等式；3、定义在欧氏平面上的TSP，即EuclideanTSP，它给出每个城市在欧氏平面上的坐标，而城市间的距离就是以它们的欧氏距离来定义。•从问题的多项式可解性上分，TSP可以分为两类：1、目前己经知道有多项式时间算法可解的，比如其距离矩阵满足特定的条件(Demidenko条件、Kalmanson条件、Supnick条件)等；2、目前尚没有发现多项式时间算法可解的，而研究热点是如何寻找更多的多项式时间可解的情形。•对旅行商问题的研究经过几十年的发展，已经产生了许多其它扩展形式,例如多旅行商问题(Multi-SalesmanProblem),多目标旅行商问题(Multi-ObjectiveTSP)等等。旅行商问题的应用和价值•旅行商问题是一个具有广泛的实用背景与重要的理论价值的组合优化难题。•许多关于TSP的工作并不仅是由实际应用直接推动的，而是因为TSP为其它一般的各类算法提供了思想方法平台，而这些算法广泛地应用于各种离散优化问题。•其次，TSP大量的直接应用给研究领域带来了生机，并引导了未来的工作•运输问题是TSP最自然的应用。由于其模型的简单性，TSP在其它一些领域有着有趣的应用。一个经典的例子是如何安排机器在一块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从一个孔移到下一个孔所花的时间。虽然钻孔的技术不断发展，但无论何时，只要钻机设备的移动时间在所有制造业的过程中占据显著的地位，TSP在减少费用上就扮演了一个非常重要的角色。•许多实际中出现的问题都可以转化成旅行商问题的模型而解决。例如还有结晶学中的结构分析问题，车辆调度问题，计算机布线问题，单个机器上的工序调度问题等等。旅行商问题的计算复杂性•时间复杂性，即随着输入问题规模的增长，算法所需计算步数的增长速度。•计算机科学家们有一个共识：即当输入规模n表示的算法复杂性函数f(n)是以多项式为界的，算法才被认为是有效的。•从本质上讲，所有的计算问题又可以归结为判定问题，如果说：一个算法解决了某一判定问题，则算法输出“是”，否则输出“非”。而从输入到输出，算法所需要运行的步骤即为算法的时间复杂性。•很多优化问题，诸如旅行商问题、最小覆盖问题、多处理器任务调度问题、背包问题等都被发现可以多项式约化为NP中最难的问题，即NP完全问题。•普遍认为多项式时间的算法是“好的算法”、“有效的算法”，而所有的NP完全问题目前都还没有找到多项式时间的算法，它们需要耗费时间复杂性函数的数量级往往是指数级的，所以单单依靠提高计算机的速度对问题的解决是非常有限的TSP的时间复杂度•TSP搜索空间随着城市数n的增大而增大，所有的旅程路线组合数为(n-1)!/2。•5个城市的情形对应120/10=12条路线；•10个城市的情景对应3628800/20=181440条路线；•100个城市的情景对应有4.666×10155条路线。•所以对于输入规模为n个城市的TSP找到最优解的时间复杂性函数的数量级是O(n!)，当n比较大时，耗费的时间已经是个天文数字。•表2.1是在假定所用计算机每秒可以执行10亿次运算的前提下，对不同的时间复杂性函数所耗费时间的比较。求解旅行商问题的已有算法•多年来对TSP的研究，人们提出了许多求解方法，其中有精确算法如线性规划方法、动态规划方法、分支定界方法；•近似算法如插入法、最近邻算法、Clark&Wright算法、生成树法、Christofides算法、r-opt算法、混合算法、概率算法等。•近年来，还有很多尝试解决该问题的较为有效的方法不断被提出，例如禁忌搜索方法、遗传算法、模拟退火算法、神经网络方法、蚁群算法等。基于灾变思想的GA实现TSP实例•遗传算法的局部搜索能力较强，但是很容易陷入局部极值。•虽然增加变异概率可以搜索到远离当前极值的点，但是新点的值往往不能和当前保留下来的较优值相提并论，因为这些较优值都是经过千百代的进化而存留下来的，于是远离当前极值的点往往在两到三代以内就被淘汰掉了。•增加变异概率实际上是把遗传算法退化成了一种纯粹的随机搜索，所谓的自适应也无从谈起！灾变思想•那么如何解决遗传算法容易陷入局部极值的问题呢？•让我们来看看大自然提供的方案。六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地。•事实上地球至少经历了5次物种大灭绝，每次物种灭绝都给更加高级的生物提供了充分进化的余地。•所以要跳出局部极值就必须杀死当前所有的优秀个体，从而让远离当前极值的点有充分的进化余地。这就是灾变思想。灾变倒计数处理•下一个问题是什么时候进行灾变，换句话说什么时候局部搜索已经充分了呢？•可用了一个灾变倒计数的概念：从500开始递减，每一代递减一次，如果出现了新的最优值，就从新开始计数，如果出现新最优值的时候倒计数递减次数的2.5倍已经超过500则从新的初始值开始倒数。•例：初始倒数500，如果倒数到200时出现新最优值，则从(500-200)*2.5=750开始从新倒数，下一次如果倒数到100时出现新最优值，则从(750-100)*2.5=1625开始倒计数(这里的2.5是一个经验值，可以在全局参数设置里面调整)。也就是说倒计数的长度取决于进化的速度，进化速度越慢倒计数长度越长。如果倒计数完毕还没有新的最优值，就认为局部搜索已经充分，就发生灾变。•程序输入是一个文本文件，记录所有城市的坐标，以及最优个体的序列。以一张只有10个城市的地图为例，文本中可能记录了以下内容：0.604600,0.592500,80.610500,0.261400,30.572800,0.494300,70.153200,0.983900,20.955700,0.772000,00.914400,0.276500,40.998500,0.484800,60.449800,0.605300,50.308500,0.109000,10.364700,0.060100,9•表示第一个城市的坐标为0.308500,0.109000(程序客户区的宽和高为单位1，所有城市的坐标值均在[0.0,0.0]到[1.0,1.0]之内)，第二个城市坐标为0.153200,0.983900...依次类推。•后面所跟的整数为最优个体的序列，上述数据表示旅行商应该从第8号城市(0.604600,0.592500)出发，经过3，7，2，0，4，6，5，1，9号城市，最后又回到第8号城市。•程序的最终目标是求取一个序列，使得旅行商按照这个序列旅行时行程最短。•程序的变异方法是自繁殖变异，有两种：1、随机取两点，逆序这两点间的序列。2、随机把一个城市转移到另一个序列位置。•对于一个500个城市的地图，大概在5万代左右发生第一次灾变，用时约6-8分钟，灾变前夕的灾变倒计数初始值已经从800达到2000-20000。可以看到从一次灾变结束到下一次灾变开始，最优值的变化趋势近似呈一条拖拽线，越接近局部极值进化速度越慢，这也说明灾变倒计数的策略是正确的。•以下是一次试验的数据统计：程序运行2个小时，进化到100万代，发生了16次灾变，最优个体产生于第606722代，属于第11个进化周期，总行程长度为17.164006，第一次灾变发生在第49773代，第一次灾变前最优个体产生于第45523代，总行程长度为18.029128。最佳路线图第一次灾变前的最佳路线第一次灾变前的最优分趋势图最后一次灾变前的最优分趋势图在每个进化周期内最优分图形基本呈拖拽线形状，可以看到多数进化周期已经没有进化速度，说明局部搜索已经充分，少数进化周期在发生灾变时还有明显进化速度，这是因为这些周期恰好进入一个比较长的停滞期时被程序认为局部搜索充分了，停滞期的出现根随机数有关，个人认为应该可以通过调节灾变初始值和灾变倍增值解决。第一次灾变前的平均分趋势图最后一次灾变前的平均分趋势图分析平均分趋势图•可以看到每次发生灾变后群体平均分会达到一个较大的值，然后迅速下降，再慢慢上升。这说明旅行商问题的局部极值非常多，极值附近解的分数要远远低于整个解空间的平均分，这主要是因为一个较优解进行一次变异后生成的子女绝大部分都是畸形的分数很低的个体，由于遗传算法并不放弃这些进化方向，从而影响了群体的平均分。•灾变时对整个解空间进行随机搜索，这时的群体平均分可以作为整