1、旅行商問題Traveling Salesman Problem（TSP）,旅行商問題的發(fā)展歷史,旅行商問題，也稱貨郎擔問題，是一個較古老的問題。其起源已經(jīng)有些模糊了。最早大概可以追溯到 1759 年 Euler 提出的騎士旅行問題。 十九世紀初，愛爾蘭數(shù)學家William R. Hamilton和英國數(shù)學家Thomas P. Kirkman研究過一些與旅行商問題相關的數(shù)學問題。,二十世紀初，人們開始研究通用形式的旅行商問題。 二十世紀二十年代，數(shù)學家和經(jīng)濟學家 Karl Menger 在維也納向他的同事提出了這個問題。 二十世紀三十年代，旅行商問題出現(xiàn)在 Princeton 大學的數(shù)學圈子里，

2、主要的推動者有 Hassler Whitney 與 Merrill Flood。 二十世紀四十年代，統(tǒng)計學家(Mahalanobis(1940), Jessen(1942), Gosh(1948), Marks(1948)把它和農(nóng)業(yè)應用聯(lián)系在一起研究。美國RAND 公司也推動了這個問題的發(fā)展。 最終，旅行商問題成為了組合優(yōu)化問題中的一個困難問題原型的典型代表。求解這種問題令人望而生畏：當問題規(guī)模變大的時候，路徑的數(shù)目將是個天文數(shù)字，逐一檢查它們幾乎是不可能的。在很長的一段時間內(nèi)，沒有任何解決這個問題的好想法出現(xiàn).,1954 年，旅行商問題的求解終于獲得了突破。George Dantizig,

3、Ray Fulkerson 和 Selmer Johnson 提出了一個求解旅行商問題的算法并用它成功地解決了一個有49 個城市的實例。這個規(guī)模在當時相當引人注目; 1977 年，Groetschel 找到了有 120 個城市的旅行商問題的最優(yōu)路徑; 1987年，Padberg 與 Rinaldi 找到了規(guī)模為 532 和 2392 的旅行商問題的最優(yōu)路徑；Groetschel與Holland找到了規(guī)模為666的旅行商問題的最優(yōu)路徑。 Applegate, Bixby,Chavtal 和 Cook 于 1994 年,1998年和 2001年解決了規(guī)模為 7397, 13509和 15112的旅

4、行商問題。 2004 年，一個具有 24978 個城市的旅行商問題的最優(yōu)路徑由 Applegate, Bixby,Chavtal, Cook 和 Helsgaun 找到。這是到目前為止精確找到最優(yōu)解的最大規(guī)模的旅行商問題.,旅行商問題吸引了越來越多的人對它進行研究。其中，有數(shù)學家，計算機科學家，運籌學家，還有一些其它領域的研究者。 然而，該問題是否存在一個有效的通用的求解方法仍然是一個開放性的問題。事實上，旅行商問題的解決將意味著 P=NP問題的解決。Clay Mathematics Institute 曾懸賞 100 萬美元來尋求這個問題的解法，但沒人拿到這個獎。,旅行商問題的描述,旅行商問

5、題(TSP) 的文字描述可以表達如下：給定一組 N 個城市和它們兩兩之間的直達距離，找出一個閉合的回路，使得每個城市剛好經(jīng)過一次且僅一次且總的旅行距離最短。即要尋求一條回路 T = (t 1 ,t2,.,tn)，使得下列目標函數(shù)最?。?上式中 t i為城市號，取值為 1 ,n ，從而 ( t1 , t2,.,tn)就可以看作是關于n的一個排列。d ( ti ,tj)表示城市 ti 與 t j之間的距離。對于對稱型 TSP，有 d ( ti ,tj)= d(tj,ti),旅行商問題的分類,從問題對應到圖的類型，TSP 可以分為兩類： 1、任意兩個城市間的距離都是對稱的，它對應的是圖論中的無向圖；

6、 2、兩個城市間的距離是非對稱的，它對應的是圖論中的有向圖； 從問題本身的限制條件的強弱，主要有三類： 1、不做任何限制(但是一般都要求城市間的費用不為負數(shù))，只給出距離矩陣，求最短回路； 2、要求距離間要滿足三角不等式； 3、定義在歐氏平面上的 TSP，即 Euclidean TSP，它給出每個城市在歐氏平面上的坐標，而城市間的距離就是以它們的歐氏距離來定義。,從問題的多項式可解性上分，TSP 可以分為兩類： 1、目前己經(jīng)知道有多項式時間算法可解的，比如其距離矩陣滿足特定的條件 (Demidenko 條件、Kalmanson 條件、Supnick 條件)等； 2、目前尚沒有發(fā)現(xiàn)多項式時間算法

7、可解的，而研究熱點是如何尋找更多的多項式時間可解的情形。 對旅行商問題的研究經(jīng)過幾十年的發(fā)展，已經(jīng)產(chǎn)生了許多其它擴展形式,例如多旅行商問題(Multi-Salesman Problem),多目標旅行商問題(Multi-Objective TSP)等等。,旅行商問題的應用和價值,旅行商問題是一個具有廣泛的實用背景與重要的理論價值的組合優(yōu)化難題。 許多關于 TSP 的工作并不僅是由實際應用直接推動的，而是因為 TSP 為其它一般的各類算法提供了思想方法平臺，而這些算法廣泛地應用于各種離散優(yōu)化問題。 其次，TSP 大量的直接應用給研究領域帶來了生機，并引導了未來的工作,運輸問題是 TSP 最自然的應

8、用。由于其模型的簡單性，TSP 在其它一些領域有著有趣的應用。一個經(jīng)典的例子是如何安排機器在一塊電路板或其他物體上鉆孔，其中需要鉆的孔可以看成是各個城市，而旅行的費用就是鉆頭從一個孔移到下一個孔所花的時間。雖然鉆孔的技術不斷發(fā)展，但無論何時，只要鉆機設備的移動時間在所有制造業(yè)的過程中占據(jù)顯著的地位，TSP 在減少費用上就扮演了一個非常重要的角色。 許多實際中出現(xiàn)的問題都可以轉化成旅行商問題的模型而解決。例如還有結晶學中的結構分析問題，車輛調(diào)度問題，計算機布線問題，單個機器上的工序調(diào)度問題等等。,旅行商問題的計算復雜性,時間復雜性，即隨著輸入問題規(guī)模的增長，算法所需計算步數(shù)的增長速度。 計算機科

9、學家們有一個共識：即當輸入規(guī)模n表示的算法復雜性函數(shù) f (n)是以多項式為界的，算法才被認為是有效的。 從本質(zhì)上講，所有的計算問題又可以歸結為判定問題，如果說：一個算法解決了某一判定問題，則算法輸出“是”，否則輸出“非”。而從輸入到輸出，算法所需要運行的步驟即為算法的時間復雜性。,很多優(yōu)化問題，諸如旅行商問題、最小覆蓋問題、多處理器任務調(diào)度問題、背包問題等都被發(fā)現(xiàn)可以多項式約化為 NP 中最難的問題，即 NP 完全問題。 普遍認為多項式時間的算法是“好的算法”、“有效的算法”，而所有的 NP 完全問題目前都還沒有找到多項式時間的算法，它們需要耗費時間復雜性函數(shù)的數(shù)量級往往是指數(shù)級的，所以單單

10、依靠提高計算機的速度對問題的解決是非常有限的,TSP的時間復雜度,TSP 搜索空間隨著城市數(shù) n 的增大而增大，所有的旅程路線組合數(shù)為( n -1)!/2。 5 個城市的情形對應 120/10=12 條路線； 10 個城市的情景對應3628800/20=181440 條路線； 100 個城市的情景對應有 4.66610155 條路線。 所以對于輸入規(guī)模為n個城市的 TSP 找到最優(yōu)解的時間復雜性函數(shù)的數(shù)量級是 O( n!)，當n 比較大時，耗費的時間已經(jīng)是個天文數(shù)字。 表 2.1 是在假定所用計算機每秒可以執(zhí)行 10 億次運算的前提下，對不同的時間復雜性函數(shù)所耗費時間的比較。,求解旅行商問題的

11、已有算法,多年來對 TSP 的研究，人們提出了許多求解方法，其中有精確算法如線性規(guī)劃方法、動態(tài)規(guī)劃方法、分支定界方法； 近似算法如插入法、最近鄰算法、Clark&Wright 算法、生成樹法、Christofides 算法、r-opt 算法、混合算法、概率算法等。 近年來，還有很多嘗試解決該問題的較為有效的方法不斷被提出，例如禁忌搜索方法、遺傳算法、模擬退火算法、神經(jīng)網(wǎng)絡方法、蟻群算法等。,基于災變思想的GA實現(xiàn)TSP實例,遺傳算法的局部搜索能力較強，但是很容易陷入局部極值。 雖然增加變異概率可以搜索到遠離當前極值的點，但是新點的值往往不能和當前保留下來的較優(yōu)值相提并論，因為這些較優(yōu)值都是經(jīng)過

12、千百代的進化而存留下來的，于是遠離當前極值的點往往在兩到三代以內(nèi)就被淘汰掉了。 增加變異概率實際上是把遺傳算法退化成了一種純粹的隨機搜索，所謂的自適應也無從談起！,災變思想,那么如何解決遺傳算法容易陷入局部極值的問題呢？ 讓我們來看看大自然提供的方案。六千五百萬年以前，恐龍和靈長類動物并存，恐龍在地球上占絕對統(tǒng)治地位，如果恐龍沒有滅絕靈長類動物是絕沒有可能統(tǒng)治地球的。正是恐龍的滅絕才使靈長類動物有了充分進化的余地。 事實上地球至少經(jīng)歷了5次物種大滅絕，每次物種滅絕都給更加高級的生物提供了充分進化的余地。 所以要跳出局部極值就必須殺死當前所有的優(yōu)秀個體，從而讓遠離當前極值的點有充分的進化余地。這

13、就是災變思想。,災變倒計數(shù)處理,下一個問題是什么時候進行災變，換句話說什么時候局部搜索已經(jīng)充分了呢？ 可用了一個災變倒計數(shù)的概念：從500開始遞減，每一代遞減一次，如果出現(xiàn)了新的最優(yōu)值，就從新開始計數(shù)，如果出現(xiàn)新最優(yōu)值的時候倒計數(shù)遞減次數(shù)的2.5倍已經(jīng)超過500則從新的初始值開始倒數(shù)。 例：初始倒數(shù)500，如果倒數(shù)到200時出現(xiàn)新最優(yōu)值，則從(500 - 200) * 2.5 = 750開始從新倒數(shù)，下一次如果倒數(shù)到100時出現(xiàn)新最優(yōu)值，則從(750 - 100) * 2.5 = 1625開始倒計數(shù)(這里的2.5是一個經(jīng)驗值，可以在全局參數(shù)設置里面調(diào)整)。也就是說倒計數(shù)的長度取決于進化的速度，

14、進化速度越慢倒計數(shù)長度越長。如果倒計數(shù)完畢還沒有新的最優(yōu)值，就認為局部搜索已經(jīng)充分，就發(fā)生災變。,程序輸入是一個文本文件，記錄所有城市的坐標，以及最優(yōu)個體的序列。以一張只有10個城市的地圖為例，文本中可能記錄了以下內(nèi)容：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

15、.364700, 0.060100, 9 表示第一個城市的坐標為0.308500, 0.109000(程序客戶區(qū)的寬和高為單位1，所有城市的坐標值均在0.0,0.0到1.0,1.0之內(nèi))，第二個城市坐標為0.153200, 0.983900.依次類推。 后面所跟的整數(shù)為最優(yōu)個體的序列，上述數(shù)據(jù)表示旅行商應該從第8號城市(0.604600, 0.592500)出發(fā)，經(jīng)過3，7，2，0，4，6，5，1，9號城市，最后又回到第8號城市。,程序的最終目標是求取一個序列，使得旅行商按照這個序列旅行時行程最短。 程序的變異方法是自繁殖變異，有兩種：1、隨機取兩點，逆序這兩點間的序列。2、隨機把一個城市轉移

16、到另一個序列位置。 對于一個500個城市的地圖，大概在5萬代左右發(fā)生第一次災變，用時約6-8分鐘，災變前夕的災變倒計數(shù)初始值已經(jīng)從800達到2000-20000?？梢钥吹綇囊淮螢淖兘Y束到下一次災變開始，最優(yōu)值的變化趨勢近似呈一條拖拽線，越接近局部極值進化速度越慢，這也說明災變倒計數(shù)的策略是正確的。,以下是一次試驗的數(shù)據(jù)統(tǒng)計： 程序運行2個小時，進化到100萬代，發(fā)生了16次災變，最優(yōu)個體產(chǎn)生于第606722代，屬于第11個進化周期，總行程長度為17.164006，第一次災變發(fā)生在第49773代，第一次災變前最優(yōu)個體產(chǎn)生于第45523代，總行程長度為18.029128。,最佳路線圖,第一次災變前

17、的最佳路線,第一次災變前的最優(yōu)分趨勢圖,最后一次災變前的最優(yōu)分趨勢圖,在每個進化周期內(nèi)最優(yōu)分圖形基本呈拖拽線形狀，可以看到多數(shù)進化周期已經(jīng)沒有進化速度，說明局部搜索已經(jīng)充分，少數(shù)進化周期在發(fā)生災變時還有明顯進化速度，這是因為這些周期恰好進入一個比較長的停滯期時被程序認為局部搜索充分了，停滯期的出現(xiàn)根隨機數(shù)有關，個人認為應該可以通過調(diào)節(jié)災變初始值和災變倍增值解決。,第一次災變前的平均分趨勢圖,最后一次災變前的平均分趨勢圖,分析平均分趨勢圖,可以看到每次發(fā)生災變后群體平均分會達到一個較大的值，然后迅速下降，再慢慢上升。這說明旅行商問題的局部極值非常多，極值附近解的分數(shù)要遠遠低于整個解空間的平均分，這主要是因為一個較優(yōu)解進行一次變異后生成的子女絕大部分都是畸形的分數(shù)很低的個體，由于遺傳算法并不放棄這些進化方向，從而影響了群體的平均分。