旅行商問題TravelingSalesmanProblem(TSP)(共30張課件)

旅行(lǚxíng)商問題

TravelingSalesmanProblem（TSP）第一頁，共三十頁。旅行商問題的發(fā)展(fāzhǎn)歷史旅行商問題，也稱貨郎擔(dān)問題，是一個(gè)較古老的問題。其起源(qǐyuán)已經(jīng)有些模糊了。最早大概可以追溯到1759年Euler提出的騎士旅行問題。十九世紀(jì)初，愛爾蘭數(shù)學(xué)家WilliamR.Hamilton和英國數(shù)學(xué)家ThomasP.Kirkman研究過一些與旅行商問題相關(guān)的數(shù)學(xué)問題。第二頁，共三十頁。二十世紀(jì)初，人們開始研究通用形式的旅行商問題。二十世紀(jì)二十年代，數(shù)學(xué)家和經(jīng)濟(jì)學(xué)家KarlMenger在維也納向他的同事提出了這個(gè)問題。二十世紀(jì)三十年代，旅行商問題出現(xiàn)在Princeton大學(xué)的數(shù)學(xué)圈子里，主要的推動(dòng)者有HasslerWhitney與MerrillFlood。二十世紀(jì)四十年代，統(tǒng)計(jì)學(xué)家(Mahalanobis(1940),Jessen(1942),Gosh(1948),Marks(1948))把它和農(nóng)業(yè)應(yīng)用聯(lián)系在一起研究。美國RAND公司也推動(dòng)了這個(gè)問題的發(fā)展。最終，旅行商問題成為了組合優(yōu)化問題中的一個(gè)困難問題原型的典型代表。求解這種問題令人望而生畏：當(dāng)問題規(guī)模(guīmó)變大的時(shí)候，路徑的數(shù)目將是個(gè)天文數(shù)字，逐一檢查它們幾乎是不可能的。在很長的一段時(shí)間內(nèi)，沒有任何解決這個(gè)問題的好想法出現(xiàn).第三頁，共三十頁。1954年，旅行商問題的求解終于獲得了突破。GeorgeDantizig,RayFulkerson和SelmerJohnson提出了一個(gè)求解旅行商問題的算法并用它成功地解決(jiějué)了一個(gè)有49個(gè)城市的實(shí)例。這個(gè)規(guī)模在當(dāng)時(shí)相當(dāng)引人注目;1977年，Groetschel找到了有120個(gè)城市的旅行商問題的最優(yōu)路徑;1987年，Padberg與Rinaldi找到了規(guī)模為532和2392的旅行商問題的最優(yōu)路徑；Groetschel與Holland找到了規(guī)模為666的旅行商問題的最優(yōu)路徑。Applegate,Bixby,Chavátal和Cook于1994年,1998年和2001年解決了規(guī)模為7397,13509和15112的旅行商問題。2004年，一個(gè)具有24978個(gè)城市的旅行商問題的最優(yōu)路徑由Applegate,Bixby,Chavátal,Cook和Helsgaun找到。這是到目前為止精確找到最優(yōu)解的最大規(guī)模的旅行商問題.第四頁，共三十頁。旅行商問題吸引了越來越多的人對(duì)它進(jìn)行研究。其中，有數(shù)學(xué)家，計(jì)算機(jī)科學(xué)家，運(yùn)籌學(xué)家，還有一些其它領(lǐng)域的研究者。然而(ránér)，該問題是否存在一個(gè)有效的通用的求解方法仍然是一個(gè)開放性的問題。事實(shí)上，旅行商問題的解決將意味著P=NP問題的解決。ClayMathematicsInstitute曾懸賞100萬美元來尋求這個(gè)問題的解法，但沒人拿到這個(gè)獎(jiǎng)。第五頁，共三十頁。旅行商問題(wèntí)的描述旅行商問題(TSP)的文字描述可以表達(dá)如下：給定一組N個(gè)城市和它們兩兩之間的直達(dá)距離，找出一個(gè)閉合的回路(huílù)，使得每個(gè)城市剛好經(jīng)過一次且僅一次且總的旅行距離最短。即要尋求一條回路(huílù)T=(t1,t2,...,tn)，使得下列目標(biāo)函數(shù)最小：上式中ti為城市號(hào)，取值為[1,n]，從而(t1,t2,...,tn)就可以看作是關(guān)于n的一個(gè)排列。d(ti,tj)表示城市ti與tj之間的距離。對(duì)于對(duì)稱型TSP，有d(ti,tj)=d(tj,ti)第六頁，共三十頁。旅行商問題(wèntí)的分類從問題對(duì)應(yīng)到圖的類型，TSP可以分為兩類：1、任意兩個(gè)城市間的距離都是對(duì)稱的，它對(duì)應(yīng)的是圖論中的無向圖；2、兩個(gè)城市間的距離是非對(duì)稱的，它對(duì)應(yīng)的是圖論中的有向圖；從問題本身的限制條件的強(qiáng)弱，主要有三類：1、不做任何限制(但是一般都要求城市間的費(fèi)用不為負(fù)數(shù))，只給出距離矩陣，求最短回路；2、要求距離間要滿足三角不等式；3、定義在歐氏平面(píngmiàn)上的TSP，即EuclideanTSP，它給出每個(gè)城市在歐氏平面(píngmiàn)上的坐標(biāo)，而城市間的距離就是以它們的歐氏距離來定義。第七頁，共三十頁。從問題的多項(xiàng)式可解性上分，TSP可以分為兩類：1、目前己經(jīng)知道有多項(xiàng)式時(shí)間算法可解的，比如其距離矩陣滿足特定的條件(Demidenko條件、Kalmanson條件、Supnick條件)等；2、目前尚沒有發(fā)現(xiàn)多項(xiàng)式時(shí)間算法可解的，而研究熱點(diǎn)是如何尋找更多的多項(xiàng)式時(shí)間可解的情形。對(duì)旅行(lǚxíng)商問題的研究經(jīng)過幾十年的發(fā)展，已經(jīng)產(chǎn)生了許多其它擴(kuò)展形式,例如多旅行商問題(Multi-SalesmanProblem),多目標(biāo)旅行商問題(Multi-ObjectiveTSP)等等。第八頁，共三十頁。旅行商問題的應(yīng)用(yìngyòng)和價(jià)值旅行商問題是一個(gè)具有廣泛的實(shí)用背景與重要的理論價(jià)值的組合優(yōu)化難題。許多關(guān)于TSP的工作并不僅是由實(shí)際應(yīng)用直接推動(dòng)的，而是因?yàn)門SP為其它一般的各類算法提供了思想方法平臺(tái)(píngtái)，而這些算法廣泛地應(yīng)用于各種離散優(yōu)化問題。其次，TSP大量的直接應(yīng)用給研究領(lǐng)域帶來了生機(jī)，并引導(dǎo)了未來的工作第九頁，共三十頁。運(yùn)輸問題是TSP最自然的應(yīng)用。由于其模型的簡單性，TSP在其它一些領(lǐng)域有著有趣的應(yīng)用。一個(gè)經(jīng)典的例子是如何安排機(jī)器在一塊電路板或其他物體上鉆孔，其中需要鉆的孔可以看成是各個(gè)城市，而旅行的費(fèi)用就是鉆頭從一個(gè)孔移到下一個(gè)孔所花的時(shí)間。雖然鉆孔的技術(shù)不斷發(fā)展，但無論何時(shí)，只要鉆機(jī)設(shè)備的移動(dòng)時(shí)間在所有制造業(yè)的過程中占據(jù)顯著的地位，TSP在減少費(fèi)用上就扮演了一個(gè)非常重要的角色。許多實(shí)際中出現(xiàn)的問題都可以轉(zhuǎn)化成旅行商問題的模型而解決。例如還有結(jié)晶學(xué)中的結(jié)構(gòu)分析問題，車輛調(diào)度問題，計(jì)算機(jī)布線問題，單個(gè)機(jī)器上的工序(gōngxù)調(diào)度問題等等。第十頁，共三十頁。旅行(lǚxíng)商問題的計(jì)算復(fù)雜性時(shí)間復(fù)雜性，即隨著輸入問題規(guī)模的增長(zēngzhǎng)，算法所需計(jì)算步數(shù)的增長(zēngzhǎng)速度。計(jì)算機(jī)科學(xué)家們有一個(gè)共識(shí)：即當(dāng)輸入規(guī)模n表示的算法復(fù)雜性函數(shù)f(n)是以多項(xiàng)式為界的，算法才被認(rèn)為是有效的。從本質(zhì)上講，所有的計(jì)算問題又可以歸結(jié)為判定問題，如果說：一個(gè)算法解決了某一判定問題，則算法輸出“是”，否則輸出“非”。而從輸入到輸出，算法所需要運(yùn)行的步驟即為算法的時(shí)間復(fù)雜性。第十一頁，共三十頁。很多優(yōu)化問題，諸如旅行商問題、最小覆蓋問題、多處理器任務(wù)調(diào)度問題、背包問題等都被發(fā)現(xiàn)可以(kěyǐ)多項(xiàng)式約化為NP中最難的問題，即NP完全問題。普遍認(rèn)為多項(xiàng)式時(shí)間的算法是“好的算法”、“有效的算法”，而所有的NP完全問題目前都還沒有找到多項(xiàng)式時(shí)間的算法，它們需要耗費(fèi)時(shí)間復(fù)雜性函數(shù)的數(shù)量級(jí)往往是指數(shù)級(jí)的，所以單單依靠提高計(jì)算機(jī)的速度對(duì)問題的解決是非常有限的第十二頁，共三十頁。TSP的時(shí)間(shíjiān)復(fù)雜度TSP搜索空間隨著城市數(shù)n的增大而增大，所有的旅程路線組合數(shù)為(n-1)!/2。5個(gè)城市的情形對(duì)應(yīng)120/10=12條路線；10個(gè)城市的情景對(duì)應(yīng)3628800/20=181440條路線；100個(gè)城市的情景對(duì)應(yīng)有4.666×10155條路線。所以對(duì)于輸入規(guī)模為n個(gè)城市的TSP找到最優(yōu)解的時(shí)間復(fù)雜性函數(shù)的數(shù)量級(jí)是O(n!)，當(dāng)n比較大時(shí)，耗費(fèi)(hàofèi)的時(shí)間已經(jīng)是個(gè)天文數(shù)字。表2.1是在假定所用計(jì)算機(jī)每秒可以執(zhí)行10億次運(yùn)算的前提下，對(duì)不同的時(shí)間復(fù)雜性函數(shù)所耗費(fèi)時(shí)間的比較。第十三頁，共三十頁。第十四頁，共三十頁。求解(qiújiě)旅行商問題的已有算法多年來對(duì)TSP的研究，人們提出了許多求解方法，其中有精確(jīngquè)算法如線性規(guī)劃方法、動(dòng)態(tài)規(guī)劃方法、分支定界方法；近似算法如插入法、最近鄰算法、Clark&Wright算法、生成樹法、Christofides算法、r-opt算法、混合算法、概率算法等。近年來，還有很多嘗試解決該問題的較為有效的方法不斷被提出，例如禁忌搜索方法、遺傳算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)方法、蟻群算法等。第十五頁，共三十頁?；跒?zāi)變(zāibiàn)思想的GA實(shí)現(xiàn)TSP實(shí)例遺傳算法的局部搜索能力較強(qiáng)，但是很容易陷入局部極值。雖然增加變異概率可以搜索到遠(yuǎn)離當(dāng)前極值的點(diǎn)，但是新點(diǎn)的值往往不能和當(dāng)前保留下來的較優(yōu)值相提并論，因?yàn)檫@些較優(yōu)值都是經(jīng)過千百代的進(jìn)化而存留下來的，于是遠(yuǎn)離當(dāng)前極值的點(diǎn)往往在兩到三代以內(nèi)就被淘汰掉了。增加變異概率實(shí)際上是把遺傳算法退化成了一種純粹的隨機(jī)搜索，所謂(suǒwèi)的自適應(yīng)也無從談起！

第十六頁，共三十頁。災(zāi)變(zāibiàn)思想那么如何解決遺傳算法容易陷入局部極值的問題呢？讓我們來看看大自然提供的方案。六千五百萬年以前，恐龍和靈長類動(dòng)物并存，恐龍?jiān)诘厍蛏险冀^對(duì)統(tǒng)治地位，如果恐龍沒有滅絕靈長類動(dòng)物是絕沒有可能統(tǒng)治地球的。正是恐龍的滅絕才使靈長類動(dòng)物有了充分進(jìn)化的余地。事實(shí)上地球至少經(jīng)歷了5次物種大滅絕，每次物種滅絕都給更加高級(jí)的生物(shēngwù)提供了充分進(jìn)化的余地。所以要跳出局部極值就必須殺死當(dāng)前所有的優(yōu)秀個(gè)體，從而讓遠(yuǎn)離當(dāng)前極值的點(diǎn)有充分的進(jìn)化余地。這就是災(zāi)變思想。

第十七頁，共三十頁。災(zāi)變倒計(jì)數(shù)(jìshù)處理下一個(gè)(yīɡè)問題是什么時(shí)候進(jìn)行災(zāi)變，換句話說什么時(shí)候局部搜索已經(jīng)充分了呢？可用了一個(gè)災(zāi)變倒計(jì)數(shù)的概念：從500開始遞減，每一代遞減一次，如果出現(xiàn)了新的最優(yōu)值，就從新開始計(jì)數(shù)，如果出現(xiàn)新最優(yōu)值的時(shí)候倒計(jì)數(shù)遞減次數(shù)的2.5倍已經(jīng)超過500則從新的初始值開始倒數(shù)。例：初始倒數(shù)500，如果倒數(shù)到200時(shí)出現(xiàn)新最優(yōu)值，則從(500-200)*2.5=750開始從新倒數(shù)，下一次如果倒數(shù)到100時(shí)出現(xiàn)新最優(yōu)值，則從(750-100)*2.5=1625開始倒計(jì)數(shù)(這里的2.5是一個(gè)經(jīng)驗(yàn)值，可以在全局參數(shù)設(shè)置里面調(diào)整)。也就是說倒計(jì)數(shù)的長度取決于進(jìn)化的速度，進(jìn)化速度越慢倒計(jì)數(shù)長度越長。如果倒計(jì)數(shù)完畢還沒有新的最優(yōu)值，就認(rèn)為局部搜索已經(jīng)充分，就發(fā)生災(zāi)變。第十八頁，共三十頁。程序輸入是一個(gè)文本文件，記錄所有城市的坐標(biāo)，以及最優(yōu)個(gè)體的序列。以一張只有10個(gè)城市的地圖為例，文本中可能記錄了以下內(nèi)容：

0.604600,0.592500,8

0.610500,0.261400,3

0.572800,0.494300,7

0.153200,0.983900,2

0.955700,0.772000,0

0.914400,0.276500,4

0.998500,0.484800,6

0.449800,0.605300,5

0.308500,0.109000,1

0.364700,0.060100,9

表示第一個(gè)城市的坐標(biāo)為0.308500,0.109000(程序客戶區(qū)的寬和高為單位1，所有城市的坐標(biāo)值均在[0.0,0.0]到[1.0,1.0]之內(nèi))，第二個(gè)城市坐標(biāo)為0.153200,0.983900...依次類推。后面所跟的整數(shù)為最優(yōu)個(gè)體的序列，上述數(shù)據(jù)表示旅行(lǚxíng)商應(yīng)該從第8號(hào)城市(0.604600,0.592500)出發(fā)，經(jīng)過3，7，2，0，4，6，5，1，9號(hào)城市，最后又回到第8號(hào)城市。

第十九頁，共三十頁。程序的最終目標(biāo)是求取一個(gè)序列，使得旅行(lǚxíng)商按照這個(gè)序列旅行(lǚxíng)時(shí)行程最短。程序的變異方法是自繁殖變異，有兩種：1、隨機(jī)取兩點(diǎn)，逆序這兩點(diǎn)間的序列。2、隨機(jī)把一個(gè)城市轉(zhuǎn)移到另一個(gè)序列位置。對(duì)于一個(gè)500個(gè)城市的地圖，大概在5萬代左右發(fā)生第一次災(zāi)變，用時(shí)約6-8分鐘，災(zāi)變前夕的災(zāi)變倒計(jì)數(shù)初始值已經(jīng)從800達(dá)到2000-20000?？梢钥吹綇囊淮螢?zāi)變結(jié)束到下一次災(zāi)變開始，最優(yōu)值的變化趨勢(shì)近似呈一條拖拽線，越接近局部極值進(jìn)化速度越慢，這也說明災(zāi)變倒計(jì)數(shù)的策略是正確的。第二十頁，共三十頁。以下是一次試驗(yàn)(shìyàn)的數(shù)據(jù)統(tǒng)計(jì)：

程序運(yùn)行2個(gè)小時(shí)，進(jìn)化到100萬代，發(fā)生了16次災(zāi)變，最優(yōu)個(gè)體產(chǎn)生于第606722代，屬于第11個(gè)進(jìn)化周期，總行程長度為17.164006，第一次災(zāi)變發(fā)生在第49773代，第一次災(zāi)變前最優(yōu)個(gè)體產(chǎn)生于第45523代，總行程長度為18.029128。

第二十一頁，共三十頁。最佳(zuìjiā)路線圖

第二十二頁，共三十頁。第一次災(zāi)變前的最佳(zuìjiā)路線

第二十三頁，共三十頁。第一次災(zāi)變(zāibiàn)前的最優(yōu)分趨勢(shì)圖

第二十四頁，共三十頁。最后(zuìhòu)一次災(zāi)變前的最優(yōu)分趨勢(shì)圖

在每個(gè)進(jìn)化(jìnhuà)周期內(nèi)最優(yōu)分圖形基本呈拖拽線形狀，可以看到多數(shù)進(jìn)化(jìnhuà)周期已經(jīng)沒有進(jìn)化(jìnhuà)速度，說明局部搜索已經(jīng)充分，少數(shù)進(jìn)化(jìnhuà)周期在發(fā)生災(zāi)變時(shí)還有明顯進(jìn)化(jìnhuà)速度，這是因?yàn)檫@些周期恰好進(jìn)入一個(gè)比較長的停滯期時(shí)被程序認(rèn)為局部搜索充分了，停滯期的出現(xiàn)根隨機(jī)數(shù)有關(guān)，個(gè)人認(rèn)為應(yīng)該可以通過調(diào)節(jié)災(zāi)變初始值和災(zāi)變倍增值解決。

第二十五頁，共三十頁。第一次災(zāi)變(zāibiàn)前的平均分趨勢(shì)圖

第二十六頁，共三十頁。最后一次災(zāi)變(zāibiàn)前的平均分趨勢(shì)圖

第二十七頁，共三十頁。分析(fēnxī)平均分趨勢(shì)圖

可以看到每次發(fā)生災(zāi)變后群體平均分會(huì)達(dá)到一個(gè)較大的