禁忌搜索演算法tsp

㈠ 禁忌搜索演算法與傳統優化演算法的區別

背景：禁忌搜索演算法（Tabu Search）是由美國科羅拉多州大學的Fred Glover教授在1986年左右提出來的，是一個用來跳出局部最優的搜尋方法。在解決最優問題上，一般區分為兩種方式：一種是傳統的方法，另一種方法則是一些啟發式搜索演算法。
使用傳統的方法，我們必須對每一個問題都去設計一套演算法，相當不方便，缺乏廣泛性，優點在於我們可以證明演算法的正確性，我們可以保證找到的答案是最優的；而對於啟發式演算法，針對不同的問題，我們可以套用同一個架構來尋找答案，在這個過程中，我們只需要設計評價函數以及如何找到下一個可能解的函數等，所以啟發式演算法的廣泛性比較高，但相對在准確度上就不一定能夠達到最優，但是在實際問題中啟發式演算法那有著更廣泛的應用

㈡ TS演算法是什麼

就是禁忌搜索演算法，又名「tabu搜索演算法」，是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。
禁忌（Tabu Search）演算法是一種亞啟發式(meta-heuristic)隨機搜索演算法，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。

㈢ LKH（Lin-Kernighan heuristic ）一種求TSP的鄰域搜索策略

PART I 引入

題主應該指的是1973年的針對TSP的LKH演算法。LKH演算法類似於k-opt方法，常見的2-opt作為一種local search的思想題主應該是知道的，（2-opt的基本變換2-interchange如下圖）。

那麼k-opt的過程，也可以element by element，也就可以通過不計順序的δ-path之間的uv-switch來實現，每個合適的k-opt裡面的exchange都是總和為正的增益值，那麼其每一個合適的exchange的一部分都可以被uv-switch達到，所以可以令每次的G*都大於0，作為stoppingcriteria，從邏輯上來說是合理的，符合作者的element by element，在啟發式所謂的exploitation上也有好的表現力。END

P.S element by element這種思想在其他的演算法也有體現，比如遺傳演算法的改進上也有比如單位點交叉防止收斂解震動。

其他演算法效能上的提升考慮，請依次閱讀文獻[2][1]及其他相關的資料。

綜上，LKH是可以認為基於k-opt成功的改進，無論是運行的速度上，還是搜索的精度上。它在解決TSP問題上，速度和精度上仍舊有較好的表現。

水平有限，隨緣回答，若有錯誤，請指出評論，謝謝！

參考文獻：

理解演算法框架內容，文獻[1]是較好的參考資料，理解演算法細節、討論，可以參考文獻[2]，其指出了backtracking的要求（從數值實驗/作者思考的philosophy上指出：應該從最多幾層開始backtracking，每層y_1, y_2contenders的數量如何，如何進一步refinements，每一次δ-path 變換中y_i怎麼高效選取等問題）

[1] Cook W.J., Cunningham W.H., Pulleyblank W.R., Schrijver A.Combinatorial Optimization

[2] S. Lin, B. W. Kernighan,An effective heuristic algorithm for the traveling salesman problem

㈣ 有關禁忌搜索

禁忌搜索（Tabu Search或Taboo Search，簡稱TS）的思想最早由Glover(1986)提出，它是對局部領域搜索的一種擴展，是一種全局逐步尋優演算法，是對人類智力過程的一種模擬。TS演算法通過引入一個靈活的存儲結構和相應的禁忌准則來避免迂迴搜索，並通過藐視准則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。相對於模擬退火和遺傳演算法，TS是又一種搜索特點不同的 meta-heuristic演算法。迄今為止，TS演算法在組合優化、生產調度、機器學習、電路設計和神經網路等領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究，並大有發展的趨勢。本章將主要介紹禁忌搜索的優化流程、原理、演算法收斂理論與實現技術等內容。

1. 引言

局部領域搜索是基於貪婪思想持續地在當前解的領域中進行搜索，雖然演算法通用易實現，且容易理解，但其搜索性能完全依賴於領域結構和初解，尤其窺陷入局部極小而無法保證全局優化性。針對局部領域搜索，為了實現全局優化，可嘗試的途徑有：以可控性概率接受劣解來逃逸局部極小，如模擬退火演算法；擴大領域搜索結構，如TSP的2opt擴展到k-opt；多點並行搜索，如進化計算；變結構領域搜索（ Mladenovic et al,1997）；另外，就是採用TS的禁忌策略盡量避免迂迴搜索，它是一種確定性的局部極小突跳策略。

禁忌搜索是人工智慧的一種體現，是局部領域搜索的一種擴展。禁忌搜索最重要的思想是標記對應已搜索的局部最優解的一些對象，並在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環），從而保證對不同的有效搜索途徑的探索。禁忌搜索涉及到領域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu 1ength）、候選解（candidate）、藐視准則（candidate）等概念，我們首先用一個示例來理解禁忌搜索及其各重要概念，而後給出演算法的一般流程。

2.禁忌搜索示例
組合優化是TS演算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索演算法的思想和操作。對於 n元素的置換問題，其所有排列狀態數為n!，當n較大時搜索空間的大小將是天文數字，而禁忌搜索則希望僅通過探索少數解來得到滿意的優化解。

首先，我們對置換問題定義一種鄰域搜索結構，如互換操作（SWAP），即隨機交換兩個點的位置，則每個狀態的鄰域解有Cn2=n（n一1）/2個。稱從一個狀態轉移到其鄰域中的另一個狀態為一次移動（move），顯然每次移動將導致適配值（反比於目標函數值）的變化。其次，我們採用一個存儲結構來區分移動的屬性，即是否為禁忌「對象」在以下示例中：考慮7元素的置換問題，並用每一狀態的相應21個鄰域解中最優的5次移動（對應最佳的5個適配值）作為候選解；為一定程度上防止迂迴搜索，每個被採納的移動在禁忌表中將滯留3步（即禁忌長度），即將移動在以下連續3步搜索中將被視為禁忌對象；需要指出的是，由於當前的禁忌對象對應狀態的適配值可能很好，因此在演算法中設置判斷，若禁忌對象對應的適配值優於「 best so far」狀態，則無視其禁忌屬性而仍採納其為當前選擇，也就是通常所說的藐視准則（或稱特赦准則）。

可見，簡單的禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中領域結構、候選解、禁忌長度、禁忌對象、藐視准則、終止准則等是影響禁忌搜索演算法性能的關鍵。需要指出的是：

（1）首先，由於TS是局部領域搜索的一種擴充，因此領域結構的設計很關鍵，它決定了當前解的領域解的產生形式和數目，以及各個解之間的關系。

（2）其次，出於改善演算法的優化時間性能的考慮，若領域結構決定了大量的領域解（尤其對大規模問題，如TSP的SWAP操作將產生Cn2個領域解），則可以僅嘗試部分互換的結果，而候選解也僅取其中的少量最佳狀態。

（3）禁忌長度是一個很重要的關鍵參數，它決定禁忌對象的任期，其大小直接進而影響整個演算法的搜索進程和行為。同時，以上示例中，禁忌表中禁忌對象的替換是採用FIFO方式（不考慮藐視准則的作用），當然也可以採用其他方式，甚至是動態自適應的方式。

（4）藐視准則的設置是演算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化的關鍵步驟。

（5）對於非禁忌候選狀態，演算法無視它與當前狀態的適配值的優劣關系，僅考慮它們中間的最佳狀態為下一步決策，如此可實現對局部極小的突跳（是一種確定性策略）。

（6）為了使演算法具有優良的優化性能或時間性能，必須設置一個合理的終止准則來結束整個搜索過程。

此外，在許多場合禁忌對象的被禁次數（frequency）也被用於指導搜索，以取得更大的搜索空間。禁忌次數越高，通常可認為出現循環搜索的概率越大。

3.禁忌搜索演算法流程
通過上述示例的介紹，基本上了解了禁忌搜索的機制和步驟。簡單TS演算法的基本思想是：給定一個當前解（初始解）和一種鄰域，然後在當前解的鄰域中確定若干候選解；若最佳候選解對應的目標值優於「best so far」狀態，則忽視其禁忌特性，用其替代當前解和「best so far」狀態，並將相應的對象加入禁忌表，同時修改禁忌表中各對象的任期；若不存在上述候選解，則選擇在候選解中選擇非禁忌的最佳狀態為新的當前解，而無視它與當前解的優劣，同時將相應的對象加入禁忌表，並修改禁忌表中各對象的任期；如此重復上述迭代搜索過程，直至滿足停止准則。

條理化些，則簡單禁忌搜索的演算法步驟可描述如下：

（1）給定演算法參數，隨機產生初始解x，置禁忌表為空。

（2）判斷演算法終止條件是否滿足？若是，則結束演算法並輸出優化結果；否則，繼續以下步驟。

（3）利用當前解工的鄰域函數產生其所有（或若干）鄰域解，並從中確定若干候選解。

（4）對候選解判斷藐視准則是否滿足？若成立，則用滿足藐視准則的最佳狀態y替代x成為新的當前解，即x=y，並用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換「best so far」狀態，然後轉步驟6；否則，繼續以下步驟。

（5）判斷候選解對應的各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素。

（6）轉步驟（2）。

同時，上述演算法可用如下流程框圖更直觀地描述，如圖4．1．1。

我們可以明顯地看到，鄰域函數、禁忌對象、禁忌表和藐視准則，構成了禁忌搜索演算法的關鍵。其中，鄰域函數沿用局部鄰域搜索的思想，用於實現鄰域搜索；禁忌表和禁忌對象的設置，體現了演算法避免迂迴搜索的特點；藐視准則，則是對優良狀態的獎勵，它是對禁忌策略的一種放鬆。需要指出的是，上述演算法僅是一種簡單的禁忌搜索框架，對各關鍵環節復雜和多樣化的設計則可構造出各種禁忌搜索演算法。同時，演算法流程中的禁忌對象，可以是搜索狀態，也可以是特定搜索操作，甚至是搜索目標值等。

同時，與傳統的優化演算法相比，TS演算法的主要特點是：

（1）在搜索過程中可以接受劣解，因此具有較強的「爬山」能力；

（2）新解不是在當前解的鄰域中隨機產生，而或是優於「best so far」的解，或是非禁忌的最佳解，因此選取優良解的概率遠遠大於其他解。由於TS演算法具有靈活的記憶功能和藐視准則，並且在搜索過程中可以接受劣解，所以具有較強的「爬山」能力，搜索時能夠跳出局部最優解，轉向解空間的其他區域，從而增強獲得更好的全局最優解的概率，所以TS演算法是一種局部搜索能力很強的全局迭代尋優演算法。

㈤ 向大神求兩道計算機方面的題！

建議將問題發到美國麻省理工學院詢問。

㈥ 禁忌搜索演算法的簡介

又名「tabu搜索演算法」
為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。禁忌搜索就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較，珠穆朗瑪峰脫穎而出。
當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best so far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。

㈦ 約束條件是怎麼加入禁忌搜索演算法中的

組合優化是TS演算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索演算法的思想和操作。對於n元素的置換問題，其所有排列狀態數為n!，當n較大時搜索空間的大小將是天文數字，而禁忌