TSP的結構特征挖掘與啟發(fā)式算法設計_圖文

1、大連理工大學碩士學位論文TSP的結構特征挖掘與啟發(fā)式算法設計姓名：李強申請學位級別：碩士專業(yè)：軟件工程指導教師：江賀20071215大連理工大學碩士學位論文摘要旅行商問題（）是經(jīng)典的一難解組合優(yōu)化問題之一，在交通、網(wǎng)絡、電路設計等方面有著廣泛的應用背景。根據(jù)計算復雜性理論可知：對于一難解問題，除非，否則不存在多項式時間內得到最優(yōu)解的精確算法。因此對于大規(guī)模的實例，求解它的高效啟發(fā)式算法設計一直是計算機科學研究的熱點。骨架、脂肪等作為描述結構特征的工具，對啟發(fā)式算法設計有著重要的意義，已經(jīng)成為目前研究問題的主要研究領域。本文首先對問題的研究現(xiàn)狀進行了介紹和分析，指出在結構特征工具的研究上的不足之

2、處。通過構造偏移實例的技巧，分析了問題的脂肪計算復雜性，并首次給出了獲取的脂肪是一難解的理論證明，即在的假設下，不存在算法可以在多項式時間內獲得完整脂肪。在此基礎上，通過分析問題局部最優(yōu)解與脂肪的關系，給出了求解問題新的元啟發(fā)式算法一動態(tài)候選集搜索算法。利用該算法，本文改進了目前求解問題最好的算法之一的。然后，本文在分析局部最優(yōu)解與全局最優(yōu)解關系的基礎上，提出一種新的描述結構特征工具擾邊。通過假設可以構造多項式時間內的算法求得擾邊，進而引出可以在多項式時間內求的問題的最優(yōu)解，用反證法給出了求解擾邊是一難的理論證明。通過試驗分析，發(fā)現(xiàn)通過對局部最優(yōu)解之間的相互操作，可以求得有效模擬擾邊的“近似擾

3、邊”。并在此基礎上，提出了基于近似擾邊的元啟發(fā)式算法框架（）。最后同樣在上對算法框架進行了實現(xiàn)。關鍵詞：旅行商閘題；啟發(fā)式算法；脂肪；擾邊的結構特征挖掘與啟發(fā)式算法設計始（），髓伍，鵲，刪，陽。，（）小張，（、：；獨創(chuàng)性說明作者鄭重聲明：本碩士學位論文是我個人在導師指導下進行的研究工作及取得研究成果。盡我所知，除了文中特別加以標注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫的研究成果，也不包含為獲得大連理工大學或者其他單位的學位或證書所使用過的材料。與我一同工作的同志對本研究所做的貢獻均已在論文中做了明確的說明并表示了謝意。作者簽名：盜絲日期：哩：蘭：多大連理工大學碩士研究生學位論文大連理

4、工大學學位論文版權使用授權書本學位論文作者及指導教師完全了解“大連理工大學碩士、博士學位論文版權使用規(guī)定”，同意大連理工大學保留并向國家有關部門或機構送交學位論文的復印件和電子版，允許論文被查閱和借閱。本人授權大連理工大學可以將本學位論文的全部或部分內容編入有關數(shù)據(jù)庫進行檢索，也可采用影印、縮印或掃描等復制手段保存和匯編學位論文。作者躲導師簽名：翅墮丑業(yè)月塹目絲庫。堡月暨目大連理工大學碩士學位論文緒論（）問題”堤為人們所廣泛研究的典型組合優(yōu)化問題，問題形式化描述為：給定無向加權圖（礦，丘們，為頂點集，礦，為邊集，睜表示邊的數(shù)目，：呻為邊權函數(shù)。實例（記為（，計）的可行解為，玨矗，其中，且對，邊

5、，可行解的目標函數(shù)值定義為；：。“，。），的目標是尋求目標函數(shù)值最小解，即滿足帕）。，（川），其中（）為中所有環(huán)路的集合。問題與調度和劃分等問題相關，廣泛應用于芯片設計、電路版布局、機器人控制、車輛選路等領域，其廣闊的通用性使之成為組合優(yōu)化的重要代表。研究背景和課題意義組合優(yōu)化問題的目標是從組合問題的可行解中求出最優(yōu)解。在現(xiàn)實世界里存在大量的組合優(yōu)化問題，其中許多問題（如：旅行商問題、圖著色問題、分配問題、調度問題、布線問題及路由選擇問題等）至今沒有找到有效地多項式算法，這些問題已被證明是完全問題。優(yōu)化問題有三個基本要素：變量、約束和目標函數(shù)。在求解過程中，選定的基本參數(shù)稱為變量；對變量取值的

6、限制成為約束；表示可行方案衡量標準的函數(shù)成為目標函數(shù)。是作為最典型的難問題之一具有古老的歷史。最早的記錄來自于年歐拉研究的騎士周游問題，即對于象棋棋盤中的個方格，走訪每個方格一次且僅一次。公司于年首次引入問題，公司的聲譽使得成為一個知名且流行的問題。問題在當時引起注意的另一個原因，是由于線性規(guī)劃這一新方法的出現(xiàn)以及人們試圖用它求解組合優(yōu)化問題。根據(jù)計算復雜性理論【】可知：對于難解問題，除非，否則不存在多項式時問內得到最優(yōu)解的完全算法。由確定型圖靈機在多項式時間內可識別的一切語言的集合被稱為類語言。由確定型圖靈機在多項式時間內可解的一切判定問題的集合稱為類問題。由非確定型圖靈機在多項式時間內可識

7、別的一切語言稱為類語言。由非確定型圖靈機在多項式時間內可計算的判定問題類稱做問題類。如果對類問題的解進行驗證，可在多項式時間內完成。習慣上，簡稱和問題。雖然現(xiàn)在還不能證明或者，但是還有一系列的特殊問題，這類問題的特殊性質使得很多人相信。這類特殊的問題就是完全問題（問的結構特征挖掘與啟發(fā)式算法設計題，代表）。問題存在著一個共同的性質，即如果一個問題存在多項式時間的算法，則所有的問題都可以在多項式時間內求解，即成立。這是因為，每一個問題都可以在多項式時間內轉化成任何一個問題。比如前面說的哈密爾頓回路問題就是一個問題。問題的歷史并不久，在年找到了第一個問題，此后人們又陸續(xù)發(fā)現(xiàn)很多問題，現(xiàn)在可能已經(jīng)有

8、多個了。所以，一般認為問題是難解的問題，因為它不太可能存在一個多項式時間的算法。問題有著廣泛的應用背景，在文獻】提到的電路板鉆孔應用相當于，個城市的；在文獻】中提及的射線檢晶器例子相當于，個城市的：而在文獻報道的構造有萬個“城市”之多。因此，研究問題對解決現(xiàn)實中的一些問題有著重要的意義，而且作為組合優(yōu)化問題的典型代表，對問題的研究對其他相關的難解問題有著重要的借鑒和指導作用。國內外研究現(xiàn)狀等人早在年就求解過的旅行商問題最優(yōu)解。年代中期對于多面體理論的研究，產生了一些比較有效的不等式約束，如：子回路消去不等式（）、梳子不等式（）、團樹不等式（等等。）在過去的幾十年里，人們又相繼研究了一些可產生的

9、近似解的算法，包括近鄰法（）、貪婪法（）、最近插入法（）、最遠插入法（）、雙最小生成樹法（）、剝離法（）、空間填充曲線法（）以及其他由，等人提供的算法。這些算法大多假定城市與某種標準距離度量下的平面上的點相對應。還有一類算法（例如、和算法）旨在進行局部優(yōu)化：通過施加局部擾動改進一條路徑。問題同時也成為世紀年代和年代演化算法領域的一個研究目標，并且，幾乎演化算法的每個會議都會有一些關于的論文。比較這些方法，尤其是它們所采用的表示方式和變化算子對研究問題有著重要的意義?！繄蟮懒嗽诠ぷ髡镜膯蝹€處理機上用小時解決了個城市的：】僅在到個小時之內解決了同樣的問題，但采用的是包含個結點機的并行實現(xiàn)；】貝在一

10、臺工作站用了大約分鐘大連理工大學碩士學位論文來求解個城市的。這些描述大都缺乏最終解質量的比較，但都表明演化算法在求解大型（例如，個以上城市）時速度太慢。它們所提供的性能結果很大程度上依賴于一些具體細節(jié)，包括種群規(guī)模、演化代數(shù)、城市數(shù)等等。并且，許多結果只適用于相對較小的（如最多個城市）。文獻【】中觀察所見：看起來少于個城市的例子很適合于全局優(yōu)化技術求解。但是，要考慮城市規(guī)模比這大得多的實例則需要采用啟發(fā)式算法。國外的研究現(xiàn)狀對于旅行商問題的一些特殊情況，國外研究出一系列較為成熟的結果，如：機器排序問題（等，）、二分圖情形（，）、平面旅行商問題中的一些特例（，）等等。由于可解情形的結果都是成熟的

11、定理，因此嚴格來說，已不屬于算法研究的范疇。而對于規(guī)模比較大的一般實例而言，目前國外還沒有提出最常用有效的算法求的問題的最優(yōu)解。目前，學者認同最簡單有效的是基于算法的算法，算法是在經(jīng)典算法的基礎上提出的最高效局部搜索算法，是目前已知的求解問題最好算法。如目前最大的已成功求解的例子（城市數(shù)為），其中就用到了算法。它的求解過程如下：（）用算法求的近似解，；（）用線性規(guī)劃的方法求得解的下限為，；（）證明在，和，之間不存在解。整個線性規(guī)劃求解（不包括用近似解算法求解）的過程是在工作站上完成的，折算成個人計算機（）所消耗的時間為年。國內的研究現(xiàn)狀國內對的研究一般多為對某種算法策略的改進，比如對遺傳算法【

12、”、模擬退火【、禁忌搜索【等算法的局部改進。其中比較好的是多級歸約算法【、求解問題的并集搜索的新宏啟發(fā)算法等。多級歸約算法是一種通過對問題的局部最優(yōu)解與全局最優(yōu)解之間關系的分析，發(fā)現(xiàn)對局部最優(yōu)解的簡單的相交操作能以很高的概率得到全局最優(yōu)解的部分解。利用這些部分解可以大大縮減原問題的搜索空間，同時也不會降低搜索的性能。再通過多次歸約使問題的規(guī)模降到足夠小，然后對這個較小規(guī)模的實例直接用已有的算法求解，最后通過相反的次序拼接部分解，最終得到一個合法解。論文最后的試驗表明，采用多級歸約算法求得的解的質量甚至好于目前求解問題最好的算法。的結構特征挖掘與啟發(fā)式算法設計求解問題并集搜索的新宏啟發(fā)式算法是利

13、用問題解的概率統(tǒng)計模型，分析了問題的局部最優(yōu)解并集的性質，發(fā)現(xiàn)局部最優(yōu)解的并集規(guī)模較小且包含了絕大多數(shù)全局最優(yōu)解的邊。利用該性質，將局部最優(yōu)解并集作為啟發(fā)集，并調用局部搜索算子在其上求解問題，由此得到一種稱為并集搜索的新宏啟發(fā)算法。利用該算法改進的問題算法的、在（附錄）中典型實例上的試驗結果表明新算法在求解的質量上有了較顯著的提高。本文的主要工作本文針對目前的描述結構特征的工具研究現(xiàn)狀和不足，主要做了以下的三個方面的工作：（）介紹了的一些概念，并針對目前的研究熱點描述結構特征工具的研究現(xiàn)狀進行了介紹和分析，指出不足之處。（）分析了問題的脂肪計算復雜性，通過構造偏移實例的技巧，首次給出了獲取的脂

14、肪是一難解的理論證明，即在尸的假設下，不存在算法可以在多項式時間內獲得完整脂肪。在此基礎上，通過分析問題局部最優(yōu)解與脂肪的關系，給出了求解問題新的元啟發(fā)式算法一動態(tài)候選集搜索算法。利用該算法，本文改進了目前求解問題最好的算法之一的。（）首次提出一種新的描述結構特征工具擾邊。本文首先在分析了全局和局部最優(yōu)解關系的基礎上，給出了求解擾邊是一難得理論證明。然后，通過試驗分析，通過對局部最優(yōu)解之間的相互操作，求得可以有效模擬擾邊的“近似擾邊”。并在此基礎上，提出了基于近似擾邊的元啟發(fā)式算法框架（）。最后在上對算法框架進行了實現(xiàn)。本文最后，對工作做了總結并對描述結構特征工具以后的研究做了展望。本文的結構

15、本文第章為緒論，介紹了研究領域的背景、國內外的研究現(xiàn)狀和本文的主要內容：第章為問題的現(xiàn)狀研究，包括啟發(fā)式算法的介紹和目前的研究熱點結構特征工具的研究現(xiàn)狀；第章為脂肪的理論分析與啟發(fā)式算法設計；第章為擾邊的理論分析與啟發(fā)式算法設計；最后在結論里對本文進行了總結并對以后的研究作了展望。一一大連理工大學碩士學位論文問題的研究現(xiàn)狀問題是一個典型的組合優(yōu)化問題，解的空間很大，窮舉所有的解根本不可能也不現(xiàn)實，其可能的路徑數(shù)目與城市數(shù)目是成指數(shù)型增長的。傳統(tǒng)方法求解問題，采用窮舉法。但因為搜索空間太大，因此到達一定規(guī)模，用窮舉法不現(xiàn)實。的搜索空間是給定的個城市的排列的集合，因此有一不同的排列組合。但考慮到，

16、如果不考慮起始城市的話，每條路徑都能用種不同的方法表示（對于一個對稱）。如路徑，同時可以包括序列、一等種序列。因此的搜索空間是悻（呻（）！。已經(jīng)被證明了是屬于難的問題，而根據(jù)計算復雜性理論可知：對于一難解問題，除非尸，否則不存在多項式時間內得到最優(yōu)解的完全算法。因而對大規(guī)模問題，人們尋求往往是在可接受的計算時間內能得到（在解的性能上）可接受的近似解的啟發(fā)式算法（）。問題的啟發(fā)式算法問題的啟發(fā)式算法可以分為兩類：環(huán)路構造算法和環(huán)路改進算法。前者從某個非法解開始，通過某種增廣策略逐步改變該解，直到得到一個合法解為止。環(huán)路構造算法包括最近鄰、貪心算法、等。環(huán)路改進算法則在給定初始的合法解之后，使用某

17、種策略來改進初始解。這些策略包括局部搜索、禁忌搜索、模擬退火、遺傳算法等。、是最常見也是最常用的環(huán)路改進算法，它們不僅可以單獨用來求解問題，也可以作為局部優(yōu)化算子而廣泛應用于其他環(huán)路改迸算法。禁忌搜索中的算法在相當長的一段時間內是求解問題最好的算法，改進的算法依然目前是求解問題最好的局部搜索算法。的啟發(fā)式算法均可以通過兩個要素來衡量：運行時間和解的質量（即環(huán)路的長度）。在算法設計中，每種啟發(fā)式算法都是在運行時間和解的質量之間進行平衡。在后面的敘述中，本文集中于那些具有代表性的應用廣泛的啟發(fā)式算法，較少介紹那些使用范圍狹窄僅僅針對某種類型實例的特定算法。環(huán)路構造算法本節(jié)詳細討論的環(huán)路構造算法包括

18、最近鄰算法、貪心算法、算法和算法等。不同的算法在局部搜索中具有不同的作用。前三種環(huán)路構造算法為環(huán)路改進算法提供了在運行時間上可行的較好初始回路。通過衡量他們在環(huán)路改進算法的結構特征挖掘與啟發(fā)式算法設計中的不同效果，可以為算法設計提供許多好的思路。第四種環(huán)路構造算法在一定程度上代表了目前環(huán)路構造算法所能取得的最好結果，因此其可以作為其他算法的一個參照算法。最近鄰問題的啟發(fā)式算法中最著名也是最自然的是最近鄰算法（，）。在這個算法中，每次選擇一個距離當前頂點最近的沒有被訪問過的頂點。利用這一方法構造了一個頂點序列（】），（），以（。），其中初始頂點攻（。）的選擇完全隨機。對應的環(huán)路按照這一序列依次訪

19、問各個頂點，在訪問后回到（）。以上所述的最近鄰算法的時間復雜度為（）。對于滿足三角不等式的那些問題而言，算法的解滿足（）丁（）（以）。雖然如此，實際上對于大量的實例而言，算法的系數(shù)為（，）。：、】等人分別實現(xiàn)了標準的最近鄰算法?！康热诉€提出了最近鄰算法的不同變體（包括、等）。、表給出了的最近鄰算法實驗結果。為了與隨機歐氏空間上的實例相比較，的實例依照表的規(guī)則給出。從表中，我們可以看到：最近鄰算法在不同種類的實例上的運行時間都很短，而解的質量通常超過下界左右。表最近鄰算法的試驗性能問題規(guī)模大連理工大學碩士學位論文表中實例的參照標準解空間實例名稱，貪心算法有些學者將最近鄰算法稱為貪心算法，但是一般

20、而言，問題的貪心算法特指以下矩陣胚理論（）的貪心算法。在此啟發(fā)式算法，將實例看成一個完全圖。一條環(huán)路就是該完全圖上的一條環(huán)路，也就是說一組邊的集合，其中每個頂點的度為。算法在構造環(huán)路時，每次加入一條新的邊。算法從最短的邊開始，依次加入剩余可用邊中最短的邊。這里，一條邊是可用的，當且僅當它不在環(huán)路中并且加入后不會產生個度為的頂點或者邊數(shù)小于的環(huán)路。在運行過程中，算法將生成一系列的環(huán)路片斷。因此該算法也被稱為多片斷（）啟發(fā)式算法。問題的貪心算法的運行時間復雜度為（），因此相對而言，比最近鄰算法慢一些。然而，另一方面，在最壞情況下，它所生成的環(huán)路比最近鄰方法要好。因此，從這里可以看出算法設計的一個基

21、本規(guī)律：算法設計總是在尋求運行時間和求解質量之間的平衡，對于一個好的成熟的算法而言，其運行時間與求解質量永遠是一對矛盾。如何在這一對矛盾中間取舍，是算法設計人員所要面臨重要課題。一個好的算法，總是需要在某方面做出犧牲，因此獲得另一方面性能的改進。這種取舍通常依賴于具體問題的特性和求解問題的客觀條件。例如，在類似交通調度這樣的在線問題，其要求算法的時效性較強，在這個時候就應該選擇運行速度快的算法，即使在解的質量方面略有下降也可以接受。而在類似電路板印刷這樣的離線問題，通常的時效性要求較低，而對算法的求解質量要求較高，這個時候就應該選擇運行時間略長而解的質量更高的算法。因此，判斷一個算法的優(yōu)劣，需

22、要在運行時間和求解質量兩個方面進行綜合考慮，在不同的情況下，算法的適用性不同。對于滿足三角不等式的那些問題實例而言，貪心算法所獲得解滿足（）（）（）療）。對于己知最壞的例子，貪心算法的系數(shù)也僅在（）。的結構特征挖掘與啟發(fā)式算法設計表給出了的貪心算法實驗結果。對于隨機歐氏空間上的實例而言，算法的性能隨著實例規(guī)模的增加而逐漸上升，運行時間迅速上升。對于隨機歐氏空間上的實例而言，算法的性能隨著實例規(guī)模的增加而逐漸下降。算法在實例上的結果與隨機歐氏空間上的實例類似。而在隨機距離矩陣實例上，算法的性能隨著實例規(guī)模的增加而迅速下降（環(huán)路超出下界的百分比從迅速上升到）。表貪心算法的試驗性能！生：?。海栴}規(guī)

23、模蘭翌塑里型堡墮！嬰竺堡！受塑（）啟發(fā)式算法源自于提出一個求解車輛調度的通用算法】。在問題中，算法從一個偽環(huán)路（）開始。該偽環(huán)路以一個隨機選定的頂點作為軸心（），訪問一個頂點后，在訪問下一個頂點前，商人都回到軸心。（換句話說，算法從一個開始，在這個圖上，每一個非軸心頂點都與軸心頂點之間有兩條邊相連）。對于每對非軸心頂點，結余（）表示商人直接從其中一個到另外一個非軸心頂點而不經(jīng)過軸心時總的環(huán)路可以縮短的距離。接下來，類似于貪心算法的處理方法，算法處理按照結余非增的順序依次處理非軸心頂點，只要它不會生成一個非軸心頂點的環(huán)路或者導致某個非軸心頂點和多個（多于）的非軸心頂點相鄰。該構造算法在僅有兩個非

24、軸心頂點和軸心相鄰時結一一大連理工大學碩士學位論文束，此時算法得到一個完整的環(huán)路。與貪心算法類似，問題的算法的運行時間復雜度為（）。對于滿足三角不等式的問題實例，算法的理論界是（）（），常數(shù)因子是貪心算法倍。然而，對于已知的最壞的情況，算法的系數(shù)與貪心算法相同，也是（）。表給出了等人在國際競賽【】中提供的算法的實驗性能。從表中可以看出，對于隨機歐氏空間上的實例麗言，算法的性能隨著實例規(guī)模的增加基本穩(wěn)定（環(huán)路長度超出下界左右），運行時間迅速上升。對于隨機歐氏空間上的實例而言，算法的性能隨著實例規(guī)模的增加而逐漸下降。算法在實例上的結果隨著實例規(guī)模增加而逐漸上升（環(huán)路超出下界的百分比從下降到）。表算

25、法的試驗性能！墊：！：！曼翌！墮翌！墮堡！墮翌塑堡笪！竺！塑墊！問題規(guī)模算法前面的三個算法在滿足三角不等式的情況下，最壞情況下算法的理論界的系數(shù)都是的函數(shù)。沒有排除有更好性能算法存在的可能性，實際上，許多算法都可以取得好的多的性能。例如，等提出雙重最小生成樹（），最近鄰插入（），和最近鄰擴展（）等，在滿足三角不等式的情況下，算法在最壞情況下的理論界系數(shù)為。并且，他們通過構造大的實例，指的結構特征挖掘與啟發(fā)式算法設計出該理論界系數(shù)不能被進一步提高。由于這些算法都可以歸類于最近鄰算法、貪心算法、，因此本文中不再詳細討論，盡管他們在最壞情況下的性能更好。下面要介紹的算法在最壞的情況下理論界的系數(shù)為（

26、對于滿足三角不等式的實例而言）。即便是對于歐氏平面上的問題而言，這個理論界也是非常好的。的基本算法框架如下：首先，為所有的頂點構造一棵最小生成樹，注意這樣的一棵最小生成樹的長度比最優(yōu)環(huán)路短，因為刪除最優(yōu)環(huán)路上的任意一邊即可得到一個生成樹；其次，對于最小生成樹上的度為奇數(shù)的頂點，計算一個最小長度的匹配，容易證明：對于滿足三角不等式的實例，該匹配的長度不超過（，）。匹配和最小生成樹構成了一個連通圖，在該圖上，任意一個頂點的度均為偶數(shù)。這樣，這個圖上必定包含了一個歐拉回路（），也就是說一個回路經(jīng)過每條邊一次且剛好一次，并且這樣的回路易于獲得。這樣一條環(huán)路可以通過遍歷該歐氏回路并利用捷徑（）避免多次訪

27、問同一個頂點而得到，顯然該環(huán)路長度不超過該歐拉回路。（一條捷徑用兩個頂點之間的直接連邊代替他們之間的一條路徑，由三角不等式可知，該直接邊的長度小于它所替代的路徑）相對其它的環(huán)路構造算法而言，算法不僅在最壞情況下的理論界更好，而且在實際運用中，通過精心選擇捷徑，所能獲得的環(huán)路質量也確實更好。算法的運行時間相對于最近鄰、貪心算法、而言更長。這主要歸結于算法中匹配一步所需的時間為。（行），而其他的三種算法的總的運行時間不超過（玎）。理論上說這種運行時間上的差距可以被縮?。阂环N具有相同理論界的算法的變種，通過使用基于可擴展匹配算法并且匹配在長度小于（珂）最優(yōu)匹配時立即中止，該變種的時間復雜度為（）。然

28、而，該種方法始終未被實際編碼實現(xiàn)過，基于局部搜索的環(huán)路改進算法的卓越性能使得這樣編碼實現(xiàn)的意義不大。表給出了算法的實驗性能。從表中，我們看到，算法在各種實例上的環(huán)路長度超過下界均不到。而相對于其他的三種環(huán)路構造算法，算法的運行時間要多得多。下面，我們對四種環(huán)路構造算法的性能進行對比。對于隨機歐氏平面上的實例的情況，四種環(huán)路構造算法所求得的解的長度均逼近超出，下界，其中算法的解超出下界不到。對于其余的三個環(huán)路構造算法而言，隨著實例的規(guī)模的增加，算法的解的質量的變化比較大。算法在實例的規(guī)模為時的解的質量與實例的規(guī)模很大時候的解的質量之間沒有明顯關聯(lián)。特別是，對于貪心算法，它的解的平均距離從（實例規(guī)

29、模為時）下降至（實例規(guī)模為，）。大連理工大學碩士學位論文就運行時間而言，算法的增長速度如預期的超過挖。其他的環(huán)路構造算法的運行時間增長速度低于，從實驗的角度來看，運行時間應該在（功，盡管當時，由于內存的容量的限制，算法的運行時間迅猛上升。即使在這種情況下，最近鄰，貪心算法和中最慢的一個也只需要大約秒鐘時間來求解，個頂點的實例。因此，算法在解的性能上可以作為其他環(huán)路構造算法的一個參照，面其他的三種環(huán)路構造算法由于運行時間短，可以用于環(huán)路改進算法以生成初始環(huán)路。表算法的試驗性能三生：！：！問題規(guī)模里型堊型堡生嬰塑堡墮曼塑塑里塑平均運行時間（秒）環(huán)路改進算法環(huán)路改進算法包括局部搜索及其變體、禁忌搜索

30、、模擬退火、遺傳算法等。、是最常見也是最常用的環(huán)路改進算法，它們不僅可以單獨用來求解問題，也可以作為局部優(yōu)化算子而廣泛應用于其他環(huán)路改進算法。禁忌搜索中的算法在相當長的一段時間內是求解問題最好的算法，改進的算法（）依然目前是求解問題最好的局部搜索算法。模擬退火和遺傳算法也被應用于問題的求解，并取得了相當好的實驗性能。特別是遺傳算法在年間一直是求解問題最好的算法，直到算法的出現(xiàn)。的結構特征挖掘與啟發(fā)式算法設計局部搜索在本節(jié)中，我們考慮問題的基于環(huán)路改進的啟發(fā)式算法。這類算法通過對環(huán)路的一系列操作（交換或移動），將一個環(huán)路轉換成另外一個環(huán)路。給定一個可行環(huán)路，算法對其進行一系列的操作（每次操作可以

31、減少當前環(huán)路的長度），直到不能進一步減少為止。此時的環(huán)路稱為一個局部最優(yōu)環(huán)路。換句話說，我們可以將這一過程看作是鄰域搜索的過程，每個環(huán)路擁有一個鄰域（由一系列的相鄰的環(huán)路組成，也就是說這些環(huán)路可以通過一個簡單移動或者交換得到）。算法持續(xù)地進行這樣的移動或交換，直到?jīng)]有更好的相鄰環(huán)路存在。在這些簡單的環(huán)路改進算法中，最著名的是和。算法最早由提出叨，盡管此前已經(jīng)提出了基本的交換操作【勰】。該交換刪除兩條邊，這樣將環(huán)路打破為條路徑，然后以別的方式連接這兩條路徑。如圖所示。值得一提的是，該圖是示意性的。在實際運用中，如果邊的長度如圖所示，則由于此將導致環(huán)路長度的增加，故該將不會付諸實施。對于（見圖）而

32、言，算法利用條新的邊取代當前環(huán)路上的條邊，得到新的環(huán)路。圖交換大連理工大學碩士學位論文圖，交換在討論等算法的解的質量時，本文首先考慮問題的任意局部優(yōu)化算法的解質量。對于任意的問題而言，還有以下結論的成立：除非，否則不存在多項式時間的局部優(yōu)化算法能夠保證（）（）成立，對于任何常數(shù)。即使是的情況下，依然不存在多項式時間的局部優(yōu)化算法可以在不依賴于頂點距離的多項式規(guī)模的鄰域上確保獲得全局最優(yōu)解。在滿足三角不等式的情況下，等算法的理論界好得多。，和等指出在任意選擇初始環(huán)路的情況下，算法的解的目標函數(shù)值至少是全局最優(yōu)解的¨，對于算法這個系數(shù)：是帕，更一般的情況下，對于算法這個系數(shù)為。當實例限制

33、在歐氏空間且頂點之間距離通過空間上的某種范式（）計算，算法的理論界將更好。在這種情形下，沒有哪個算法的最壞情況下性能會差于（），盡管這個系數(shù)在二維歐氏空間上增長速度是（力。所有的這些理論下界都是在任意選擇初始環(huán)路（此時選擇的初始環(huán)路有可能是已經(jīng)是一個比較差的局部最優(yōu)解環(huán)路）的情況下獲得的。在實際應用中，通過使用一個好的啟發(fā)式算法以獲得一個好的初始環(huán)路，可以得到更好的理論界冽。當使用算法生成初始環(huán)路時，在滿足三角不等式的情況下，等算法的理論界在最壞情況下不超過，這個結果優(yōu)于上面二維歐氏空間上的結論。對于環(huán)路改造算法，另一個有趣而又重要的問題是：這些啟發(fā)式算法在達到一個局部最優(yōu)解前可以進行多少次交

34、換？對于和，這個數(shù)目可能非常的大（甚至在實例滿足三角不等式的情況下）。已經(jīng)證明存在這樣的實例和初始環(huán)路使得在停止局部搜索前進行（們）次的交換。，和等證明了對于同樣存在這樣的結論，并且可以推廣到，對于任意固定的。這些結論都是在任意選擇實倒和初始環(huán)路的情況下得到的。對于值較大的情況，即使使用好的初始環(huán)路對的結構特征挖掘與啟發(fā)式算法設計結論的影響也不大。證明對于足夠大的值，在的鄰域結構上尋找局部最優(yōu)解是完全的。這意味著無法在多項式時間內求得局部最優(yōu)環(huán)路，除非所有的問題均可以在多項式時間內求解。等使用鄰接表實現(xiàn)了和算法。為了減少算法的運行時間，等對算法的實現(xiàn)作了一些折衷，放棄了算法的理論界。然而，至少

35、對于歐氏空間上的實例而言，這樣的修改既沒有明顯影響到環(huán)路的質量也沒有明顯影響算法的交換次數(shù)。表，給出了和算法在隨機歐氏空間上的實例和隨機距離矩陣的實例的實驗結果。對于和算法的結果，文中采用了貪心算法的一種變體來生成初始環(huán)路。在選擇加入環(huán)路的邊時，貪心算法一般選擇最短的一條可行邊，而在本貪心算法的變體中，使用最短的兩條邊，其中選擇最短的一條邊的概率為，另一條邊的概率為。從平均性能上說，這種貪心算法的變體所得環(huán)路長度與原貪心算法基本相同。對于隨機歐氏空間上的實例而言，比最好的環(huán)路構造算法平均好，盡管算法的初始環(huán)路比差到。而算法比解的性能還要好左右，僅僅比下界多左右，這個結果對于一般的實際應用已經(jīng)足

36、夠了。對于隨機距離矩陣的實例而言，等算法的改進程度相對就沒有前面那么明顯了。盡管在這些實例上，和都明顯優(yōu)于最好的環(huán)路構造算法，隨著實例規(guī)模的增加，及的解的質量逐步下降，其超出，下界的百分比增長速度似乎是。正如我們在最近鄰算法和貪心算法中觀察到的一樣。算法在上的實驗結果與此類似，只是解的質量略有下降。算法的解平均超出下界，而算法平均超出。初始環(huán)路的選擇對算法的性能的影響比較大。等研究了不同的初始環(huán)路對、解的影響（見表、）。對于隨機歐氏空間和隨機距離矩陣上的規(guī)模為的實例，等比較了不同的初始環(huán)路生成算法對于和算法的影響。對于隨機歐氏空間上的實例，最差的初始環(huán)路并不對應著最差的環(huán)路，而恰恰相反，最好的

37、初始環(huán)路所生成的最終環(huán)路最差！盡管算法產生一個顯著優(yōu)于其它啟發(fā)算法的初始環(huán)路，在應用和進行進一步優(yōu)化后，其最終得到的環(huán)路比其他的更差，甚至對于隨機生成的初始環(huán)路也是如此。這并不是算法的所特有的性質。等指出，與其他的著名的環(huán)路構造算法（包括最遠插入法、算法的快速近似算法等）相比，利用貪心算法生成的初始環(huán)路進行或優(yōu)化，得到的最終環(huán)路的質量更好。其中的原因在于：為了讓局部搜索可以持續(xù)快速地對環(huán)路進行優(yōu)化，初始環(huán)大連理工大學碩士學位論文路應該包含一定數(shù)目的可用缺陷（），而一個初始環(huán)路太好的情況下，通常很少有這樣的可用缺陷。注意，對于剩余的三個算法而言，初始環(huán)路算法越好最后得到的環(huán)路就越好。不考慮算法的

38、情況下，隨機距離矩陣上的實例同樣具有這樣的性質：好的初始環(huán)路生成好的最終環(huán)路。在隨機距離矩陣上的實例上，算法依然是一個例外：經(jīng)過算法生成的初始環(huán)路遠遠優(yōu)于隨機算法，但是最后得到的解卻比隨機算法要差。對于其他規(guī)模的實例，情況與此類似。表算法的實驗性能沖渤一，；盯一一們心平均運行時間（秒）的結構特征挖掘與啟發(fā)式算法設計表不同初始環(huán)路對環(huán)路改進算法的影響解超過下界的百分比（平均），問題規(guī)模為表算法及的平均交換次數(shù)一除了、之外，問題常見的局部搜索算法還包括、剝、和等。因為篇幅所限，在此不再累述。一大連理工大學碩士學位論文禁忌搜索和模擬退火和其他的算法一樣，蔡忌搜索也是基于以下觀察：局部最優(yōu)解并非一定是

39、質量好的解。因此，有必要對純粹的局部搜索算法進行改進，利用某種機制以幫助我們跳出局部最優(yōu)解的陷阱繼續(xù)搜索。一種可能的選擇是簡單地隨機重啟，每當局部搜索落入局部最優(yōu)解陷阱，按照某種隨機重啟策略重新選擇一個起始點開始局部搜索，由此得到一個新的解。隨機重啟策略的性能非常有限，并且隨著問題規(guī)模的增加而下降。例如：盡管對于隨機歐氏空間上的頂點個數(shù)為的城市而言，次運行結果中的最好者的性能通常優(yōu)于的平均解，但是對于個城市的實例而言，次運行結果中的最好者的性能也遠遠差于次運行結果中的最差者。隨機重啟策略的作用有限的一個原因在于：隨機重啟策略不考慮局部最優(yōu)解之間的相關性（局部最優(yōu)解的聚集性），也就是說對于任意的

40、局部最優(yōu)解，一個更好的解可能就在附近。如果這種聚集性確實存在的話，從一個當前解的附近重新開始搜索的性能，通常要優(yōu)于從任意選擇的點重新開始搜索。這也就是禁忌搜索的精髓之所在。禁忌搜索的基本策略如下：每一次都選擇最好的操作，即使該操作使得當前解的目標函數(shù)值變差。這樣，假設在每一步當前解的所有的鄰域均被檢查，若鄰域中存在解優(yōu)于當前解，則選擇鄰域中最好的解作為新的當前解，否則禁忌搜索陷入了局部最優(yōu)解，此時仍然選擇鄰域中最好的解作為下一個當前解。這樣做的一個風險是：從這個“鄰域中最好的解”開始的操作恰好選擇剛才離開的局部最優(yōu)解或者某個以前已經(jīng)訪問過的解。因此，有必要引入所謂的禁忌列表（）。最近所執(zhí)行的一系列操作的信息被保存在一個或多個禁忌列表中。使用禁忌列表可以避免重復訪問那些以前訪問過的頂點。目前存在多種問題的禁忌搜索算法，包括，擴】，刪。等。在本小節(jié)的討論中，我們僅僅限于那些有實驗結果的算法。問題的第一個禁忌搜索算法的實現(xiàn)是提供的。，等報告了關于該實現(xiàn)及變體的實驗結果，和等也研究了類似的方法。所有的這些算法使用作為基本交換操作，他們在禁忌列表及級別的實現(xiàn)上有所不