1 簡介

1.1 TSP介紹

“旅行商問題”(Traveling Salesman Problem,TSP)可簡單描述為：一位銷售商從n個城市中的某一城市出發(fā)，不重復(fù)地走完其余n-1個城市并回到原出發(fā)點，在所有可能路徑中求出路徑長度最短的一條。

旅行商的路線可以看作是對n城市所設(shè)計的一個環(huán)形，或者是對一列n個城市的排列。由于對n個城市所有可能的遍歷數(shù)目可達(n-1)!個，因此解決這個問題需要O(n!)的計算時間。而由美國密執(zhí)根大學(xué)的Holland教授發(fā)展起來的遺傳算法，是一種求解問題的高效并行全局搜索方法，能夠解決復(fù)雜的全局優(yōu)化問題，解決TSP問題也成為遺傳算法界的一個目標(biāo)。

1.2 禁忌搜索算法

1 引言一個問題的求解過程就是搜索，它是人工智能的一個基本問題，而人工智能在各應(yīng)用領(lǐng)域中被廣泛地使用?，F(xiàn)在搜索技術(shù)滲透在各種人工智能系統(tǒng)中，可以說沒有哪一種人工智能的應(yīng)用不用搜索方法。禁忌搜索算法(Tabu Search or Taboo Search， TS) 的思想最早由美國工程院院士Glover教授于1986年提出[] ， 并在1989年和1990年對該方法做出了進一步的定義和發(fā)展[2-4]。在自然計算的研究領(lǐng)域中，禁忌搜索算法以其靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，在智能算法中獨樹一幟，成為一個研究熱點，受到了國內(nèi)外學(xué)者的廣泛關(guān)注。迄今為止，禁忌搜索算法在組合優(yōu)化、生產(chǎn)調(diào)度、機器學(xué)習(xí)、電路設(shè)計和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來又在函數(shù)全局優(yōu)化方面得到較多的研究，并有迅速發(fā)展的趨勢[5-8].所謂禁忌，就是禁止重復(fù)前面的操作。為了改進局部鄰域搜索容易陷入局部最優(yōu)點的不足，禁忌搜索算法引入一個禁忌表，記錄下已經(jīng)搜索過的局部最優(yōu)點，在下一次搜索中，對禁忌表中的信息不再搜索或有選擇地搜索，以此來跳出局部最優(yōu)點，從而最終實現(xiàn)全局優(yōu)化。禁忌搜索算法是對局部鄰域搜索的一種擴展，是一種全局鄰域搜索、逐步尋優(yōu)的算法。禁忌搜索算法是一種迭代搜索算法，它區(qū)別于其他現(xiàn)代啟發(fā)式算法的顯著特點，是利用記憶來引導(dǎo)算法的搜索過程；它是對人類智力過程的一種模擬，是人工智能的一種體現(xiàn)。禁忌搜索算法涉及鄰域、禁忌表、禁忌長度、候選解、藐視準(zhǔn)則等概念，在鄰域搜索的基礎(chǔ)上，通過禁忌準(zhǔn)則來避免重復(fù)搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進而保證多樣化的有效搜索來最終實現(xiàn)全局優(yōu)化。

2禁忌搜索算法理論2.1局部鄰域搜索局部鄰域搜索是基于貪婪準(zhǔn)則持續(xù)地在當(dāng)前的鄰域中進行搜索，雖然其算法通用，易于實現(xiàn)，且容易理解，但其搜索性能完全依賴于鄰域結(jié)構(gòu)和初始解，尤其容易陷入局部極小值而無法保證全局優(yōu)化。局部搜索的算法可以描述為：

這種鄰域搜索方法易于理解，易于實現(xiàn)，而且具有很好的通用性，但是搜索結(jié)果的好壞完全依賴于初始解和鄰域的結(jié)構(gòu)。若鄰域結(jié)構(gòu)設(shè)置不當(dāng)，或初始解選擇不合適，則搜索結(jié)果會很差，可能只會搜索到局部最優(yōu)解，即算法在搜索過程中容易陷入局部極小值。因此，若不在搜索策略上進行改進，要實現(xiàn)全局優(yōu)化，局部鄰域搜索算法采用的鄰域函數(shù)就必須是“完全”的，即鄰域函數(shù)將導(dǎo)致解的完全枚舉。而這在大多數(shù)情況下是無法實現(xiàn)的，而且窮舉的方法對于大規(guī)模問題在搜索時間上也是不允許的。為了實現(xiàn)全局搜索，禁忌搜索采用允許接受劣質(zhì)解的策略來避免局部最優(yōu)解。2.2禁忌搜索禁忌搜索算法是模擬人的思維的一種智能搜索算法，即人們對已搜索的地方不會再立即去搜索，而是去對其他地方進行搜索，若沒有找到，可再搜索已去過的地方。禁忌搜索算法從一個初始可行解出發(fā)，選擇一系列的特定搜索方向(或稱為“移動”)作為試探，選擇使目標(biāo)函數(shù)值減小最多的移動。為了避免陷入局部最優(yōu)解，禁忌搜索中采用了一種靈活的“記憶”技術(shù)，即對已經(jīng)進行的優(yōu)化過程進行記錄，指導(dǎo)下一步的搜索方向，這就是禁忌表的建立。禁忌表中保存了最近若干次迭代過程中所實現(xiàn)的移動，凡是處于禁忌表中的移動，在當(dāng)前迭代過程中是禁忌進行的，這樣可以避免算法重新訪問在最近若干次迭代過程中已經(jīng)訪問過的解，從而防止了循環(huán)，幫助算法擺脫局部最優(yōu)解。另外，為了盡可能不錯過產(chǎn)生最優(yōu)解的“移動”，禁忌搜索還采用“特赦準(zhǔn)則”的策略。對一個初始解，在一種鄰域范圍內(nèi)對其進行一系列變化，從而得到許多候選解。從這些候選解中選出最優(yōu)候選解，將候選解對應(yīng)的目標(biāo)值與“best so far”狀態(tài)進行比較。若其目標(biāo)值優(yōu)于“best sofar”狀態(tài)， 就將該候選解解禁， 用來替代當(dāng)前最優(yōu)解及其“best sofar”狀態(tài)， 然后將其加入禁忌表， 再將禁忌表中相應(yīng)對象的禁忌長度改變：如果所有的候選解中所對應(yīng)的目標(biāo)值都不存在優(yōu)于“best sofar”狀態(tài)， 就從這些候選解中選出不屬于禁忌對象的最佳狀態(tài)， 并將其作為新的當(dāng)前解，不用與當(dāng)前最優(yōu)解進行比較，直接將其所對應(yīng)的對象作為禁忌對象，并將禁忌表中相應(yīng)對象的禁忌長度進行修改。2.3禁忌搜索算法的特點禁忌搜索算法是在鄰域搜索的基礎(chǔ)上，通過設(shè)置禁忌表來禁忌一些已經(jīng)進行過的操作，并利用藐視準(zhǔn)則來獎勵一些優(yōu)良狀態(tài)，其中鄰域結(jié)構(gòu)、候選解、禁忌長度、禁忌對象、藐視準(zhǔn)則、終止準(zhǔn)則等是影響禁忌搜索算法性能的關(guān)鍵。鄰域函數(shù)沿用局部鄰域搜索的思想，用于實現(xiàn)鄰域搜索；禁忌表和禁忌對象的設(shè)置，體現(xiàn)了算法避免迂回搜索的特點：藐視準(zhǔn)則，則是對優(yōu)良狀態(tài)的獎勵，它是對禁忌策略的一種放松。與傳統(tǒng)的優(yōu)化算法相比，禁忌搜索算法的主要特點是：(1)禁忌搜索算法的新解不是在當(dāng)前解的鄰域中隨機產(chǎn)生，它要么是優(yōu)于“best so far”的解， 要么是非禁忌的最佳解， 因此選取優(yōu)良解的概率遠遠大于其他劣質(zhì)解的概率。(2)由于禁忌搜索算法具有靈活的記憶功能和藐視準(zhǔn)則，并且在搜索過程中可以接受劣質(zhì)解，所以具有較強的“爬山”能力，搜索時能夠跳出局部最優(yōu)解，轉(zhuǎn)向解空間的其他區(qū)域，從而增大獲得更好的全局最優(yōu)解的概率。因此，禁忌搜索算法是一種局部搜索能力很強的全局迭代尋優(yōu)算法。

2.4禁忌搜索算法的改進方向禁忌搜索是著名的啟發(fā)式搜索算法，但是禁忌搜索也有明顯的不足，即在以下方面需要改進：(1)對初始解有較強的依賴性，好的初始解可使禁忌搜索算法在解空間中搜索到好的解，而較差的初始解則會降低禁忌搜索的收斂速度。因此可以與遺傳算法、模擬退火算法等優(yōu)化算法結(jié)合，先產(chǎn)生較好的初始解，再用禁忌搜索算法進行搜索優(yōu)化。(2)迭代搜索過程是串行的，僅是單一狀態(tài)的移動，而非并行搜索。為了進一步改善禁忌搜索的性能，一方面可以對禁忌搜索算法本身的操作和參數(shù)選取進行改進，對算法的初始化、參數(shù)設(shè)置等方面實施并行策略，得到各種不同類型的并行禁忌搜索算法[9]：另一方面則可以與遺傳算法、神經(jīng)網(wǎng)絡(luò)算法以及基于問題信息的局部搜索相結(jié)合。(3)在集中性與多樣性搜索并重的情況下，多樣性不足。集中性搜索策略用于加強對當(dāng)前搜索的優(yōu)良解的鄰域做進一步更為充分的搜索，以期找到全局最優(yōu)解。多樣性搜索策略則用于拓寬搜索區(qū)域，尤其是未知區(qū)域，當(dāng)搜索陷入局部最優(yōu)時，多樣性搜索可改變搜索方向，跳出局部最優(yōu)，從而實現(xiàn)全局最優(yōu)。增加多樣性策略的簡單處理手段是對算法的重新隨機初始化，或者根據(jù)頻率信息對一些已知對象進行懲罰。

3 禁忌搜索算法流程簡單禁忌搜索算法的基本思想是：給定一個當(dāng)前解(初始解)和一種鄰域，然后在當(dāng)前解的鄰域中確定若干候選解；若最佳候選解對應(yīng)的目標(biāo)值優(yōu)于“best so far”狀態(tài)， 則忽視其禁忌特性， 用它替代當(dāng)前解和“best so far”狀態(tài)， 并將相應(yīng)的對象加入禁忌表， 同時修改禁忌表中各對象的任期：若不存在上述候選解，則在候選解中選擇非禁忌的最佳狀態(tài)為新的當(dāng)前解，而無視它與當(dāng)前解的優(yōu)劣，同時將相應(yīng)的對象加入禁忌表，并修改禁忌表中各對象的任期。如此重復(fù)上述迭代搜索過程，直至滿足停止準(zhǔn)則。其算法步驟可描述如下：(1)給定禁忌搜索算法參數(shù)，隨機產(chǎn)生初始解x，置禁忌表為空。(2)判斷算法終止條件是否滿足：若是，則結(jié)束算法并輸出優(yōu)化結(jié)果：否則，繼續(xù)以下步驟。(3)利用當(dāng)前解的鄰域函數(shù)產(chǎn)生其所有(或若干)鄰域解，并從中確定若干候選解。(4)對候選解判斷藐視準(zhǔn)則是否滿足：若滿足，則用滿足藐視準(zhǔn)則的最佳狀態(tài)y替代x成為新的當(dāng)前解，即x=y，并用與y對應(yīng)的禁忌對象替換最早進入禁忌表的禁忌對象， 同時用y替換“best so far”狀態(tài)，然后轉(zhuǎn)步驟(6)：否則，繼續(xù)以下步驟。(5)判斷候選解對應(yīng)的各對象的禁忌屬性，選擇候選解集中非禁忌對象對應(yīng)的最佳狀態(tài)為新的當(dāng)前解，同時用與之對應(yīng)的禁忌對象替換最早進入禁忌表的禁忌對象。(6)判斷算法終止條件是否滿足：若是，則結(jié)束算法并輸出優(yōu)化結(jié)果：否則，轉(zhuǎn)步驟(3)。禁忌搜索算法的運算流程如圖8.1所示。

4 關(guān)鍵參數(shù)說明一般而言，要設(shè)計一個禁忌搜索算法，需要確定算法的以下環(huán)節(jié)：初始解、適配值函數(shù)、鄰域結(jié)構(gòu)、禁忌對象、候選解選擇、禁忌表、禁忌長度、藐視準(zhǔn)則、搜索策略、終止準(zhǔn)則[10，11]。面對如此眾多的參數(shù)，針對不同鄰域的具體問題，很難有一套比較完善的或非常嚴格的步驟來確定這些參數(shù)。初始解禁忌搜索算法可以隨機給出初始解，也可以事先使用其他啟發(fā)式算法等給出一個較好的初始解。由于禁忌搜索算法主要是基于鄰域搜索的，初始解的好壞對搜索的性能影響很大。尤其是一些帶有很復(fù)雜約束的優(yōu)化問題，如果隨機給出的初始解很差，甚至通過多步搜索也很難找到一個可行解，這時應(yīng)該針對特定的復(fù)雜約束，采用啟發(fā)式方法或其他方法找出一個可行解作為初始解；再用禁忌搜索算法求解，以提高搜索的質(zhì)量和效率。也可以采用一定的策略來降低禁忌搜索對初始解的敏感性。適配值函數(shù)禁忌搜索的適配值函數(shù)用于對搜索進行評價，進而結(jié)合禁忌準(zhǔn)則和特赦準(zhǔn)則來選取新的當(dāng)前狀態(tài)。目標(biāo)函數(shù)值和它的任何變形都可以作為適配值函數(shù)。若目標(biāo)函數(shù)的計算比較困難或耗時較長，此時可采用反映問題目標(biāo)的某些特征值來作為適配值，進而改善算法的時間性能。選取何種特征值要視具體問題而定，但必須保證特征值的最佳性與目標(biāo)函數(shù)的最優(yōu)性一致。適配值函數(shù)的選擇主要考慮提高算法的效率、便于搜索的進行等因素。鄰域結(jié)構(gòu)所謂鄰域結(jié)構(gòu)，是指從一個解(當(dāng)前解)通過“移動”產(chǎn)生另一個解(新解)的途徑，它是保證搜索產(chǎn)生優(yōu)良解和影響算法搜索速度的重要因素之一。鄰域結(jié)構(gòu)的設(shè)計通常與問題相關(guān)。鄰域結(jié)構(gòu)的設(shè)計方法很多，對不同的問題應(yīng)采用不同的設(shè)計方法，常用設(shè)計方法包括互換、插值、逆序等。不同的“移動”方式將導(dǎo)致鄰域解個數(shù)及其變化情況的不同，對搜索質(zhì)量和效率有一定影響。

通過移動，目標(biāo)函數(shù)值將產(chǎn)生變化，移動前后的目標(biāo)函數(shù)值之差，稱之為移動值。如果移動值是非負的，則稱此移動為改進移動：否則，稱之為非改進移動。最好的移動不一定是改進移動，也可能是非改進移動，這一點能保證在搜索陷入局部最優(yōu)時，禁忌搜索算法能自動把它跳出局部最優(yōu)。

禁忌對象所謂禁忌對象，就是被置入禁忌表中的那些變化元素。禁忌的目的則是為了盡量避免迂回搜索而多搜索一些解空間中的其他地方。歸納而言，禁忌對象通常可選取狀態(tài)本身或狀態(tài)分量等。

候選解選擇候選解通常在當(dāng)前狀態(tài)的鄰域中擇優(yōu)選取，若選取過多將造成較大的計算量，而選取較少則容易“早熟”收斂，但要做到整個鄰域的擇優(yōu)往往需要大量的計算，因此可以確定性地或隨機性地在部分鄰域中選取候選解，具體數(shù)據(jù)大小則可視問題特征和對算法的要求而定。禁忌表不允許恢復(fù)(即被禁止) 的性質(zhì)稱作禁忌(Tabu) 。禁忌表的主要目的是阻止搜索過程中出現(xiàn)循環(huán)和避免陷入局部最優(yōu)，它通常記錄前若干次的移動，禁止這些移動在近期內(nèi)返回。在迭代固定次數(shù)后，禁忌表釋放這些移動，重新參加運算，因此它是一個循環(huán)表，每迭代一次，就將最近的一次移動放在禁忌表的末端，而它的最早的一個移動就從禁忌表中釋放出來。從數(shù)據(jù)結(jié)構(gòu)上講，禁忌表是具有一定長度的先進先出的隊列。禁忌搜索算法使用禁忌表禁止搜索曾經(jīng)訪問過的解，從而禁止搜索中的局部循環(huán)。禁忌表可以使用兩種記憶方式：明晰記憶和屬性記憶。明晰記憶是指禁忌表中的元素是一個完整的解，消耗較多的內(nèi)存和時間：屬性記憶是指禁忌表中的元素記錄當(dāng)前解移動的信息，如當(dāng)前解移動的方向等。

禁忌長度所謂禁忌長度，是指禁忌對象在不考慮特赦準(zhǔn)則的情況下不允許被選取的最大次數(shù)。通俗地講，禁忌長度可視為禁忌對象在禁忌表中的任期。禁忌對象只有當(dāng)其任期為0時才能被解禁。在算法的設(shè)計和構(gòu)造過程中，一般要求計算量和存儲量盡量小，這就要求禁忌長度盡量小。但是，禁忌長度過小將造成搜索的循環(huán)。禁忌長度的選取與問題特征相關(guān)，它在很大程度上決定了算法的計算復(fù)雜性。一方面，禁忌長度可以是一個固定常數(shù)(如t=c，c為一常數(shù))，或者固定為與問題規(guī)模相關(guān)的一個量(如t=√n，n為問題維數(shù)或規(guī)模)，如此實現(xiàn)起來方便、簡單，也很有效：另一方面，禁忌長度也可以是動態(tài)變化的，如根據(jù)搜索性能和問題特征設(shè)定禁忌長度的變化區(qū)間，而禁忌長度則可按某種規(guī)則或公式在這個區(qū)間內(nèi)變化。

藐視準(zhǔn)則在禁忌搜索算法中，可能會出現(xiàn)候選解全部被禁忌，或者存在一個優(yōu)于“best so far”狀態(tài)的禁忌候選解， 此時特赦準(zhǔn)則將某些狀態(tài)解禁，以實現(xiàn)更高效的優(yōu)化性能。特赦準(zhǔn)則的常用方式有：(1) 基于適配值的原則：某個禁忌候選解的適配值優(yōu)于“bestso far”狀態(tài)， 則解禁此候選解為當(dāng)前狀態(tài)和新的“best so far”狀態(tài)。(2)基于搜索方向的準(zhǔn)則：若禁忌對象上次被禁忌時使得適配值有所改善，并且目前該禁忌對象對應(yīng)的候選解的適配值優(yōu)于當(dāng)前解，則對該禁忌對象解禁。

搜索策略搜索策略分為集中性搜索策略和多樣性搜索策略。集中性搜索策略用于加強對優(yōu)良解的鄰域的進一步搜索。其簡單的處理手段可以是在一定步數(shù)的迭代后基于最佳狀態(tài)重新進行初始化，并對其鄰域進行再次搜索。在大多數(shù)情況下，重新初始化后的鄰域空間與上一次的鄰域空間是不一樣的，當(dāng)然也就有一部分鄰域空間可能是重疊的。多樣性搜索策略則用于拓寬搜索區(qū)域，尤其是未知區(qū)域。其簡單的處理手段可以是對算法的重新隨機初始化，或者根據(jù)頻率信息對一些已知對象進行懲罰。

終止準(zhǔn)則禁忌搜索算法需要一個終止準(zhǔn)則來結(jié)束算法的搜索進程，而嚴格理論意義上的收斂條件，即在禁忌長度充分大的條件下實現(xiàn)狀態(tài)空間的遍歷，這顯然是不可能實現(xiàn)的。因此，在實際設(shè)計算法時通常采用近似的收斂準(zhǔn)則。常用的方法有：(1)給定最大迭代步數(shù)。當(dāng)禁忌搜索算法運行到指定的迭代步數(shù)之后，則終止搜索。(2)設(shè)定某個對象的最大禁忌頻率。若某個狀態(tài)、適配值或?qū)Q等對象的禁忌頻率超過某一閾值，或最佳適配值連續(xù)若干步保持不變，則終止算法。(3)設(shè)定適配值的偏離閾值。首先估計問題的下界，一旦算法中最佳適配值與下界的偏離值小于某規(guī)定閾值，則終止搜索。

2 部分代碼

function ActionList=CreatePermActionList(n) ? ?nSwap=n*(n-1)/2; ? ?nReversion=n*(n-1)/2; ? ?nInsertion=n^2; ? ?nAction=nSwap+nReversion+nInsertion; ? ?ActionList=cell(nAction,1); ? ?c=0; ? ?% Add SWAP ? ?for i=1:n-1 ? ? ? ?for j=i+1:n ? ? ? ? ? ?c=c+1; ? ? ? ? ? ?ActionList{c}=[1 i j]; ? ? ? ?end ? ?end ? ?% Add REVERSION ? ?for i=1:n-1 ? ? ? ?for j=i+1:n ? ? ? ? ? ?if abs(i-j)>2 ? ? ? ? ? ? ? ?c=c+1; ? ? ? ? ? ? ? ?ActionList{c}=[2 i j]; ? ? ? ? ? ?end ? ? ? ?end ? ?end ? ?% Add Insertion ? ?for i=1:n ? ? ? ?for j=1:n ? ? ? ? ? ?if abs(i-j)>1 ? ? ? ? ? ? ? ?c=c+1; ? ? ? ? ? ? ? ?ActionList{c}=[3 i j]; ? ? ? ? ? ?end ? ? ? ?end ? ?end ? ?ActionList=ActionList(1:c);end

3 仿真結(jié)果

4 參考文獻

[1]賀一,劉光遠. 禁忌搜索算法求解旅行商問題研究[J]. 西南師范大學(xué)學(xué)報(自然科學(xué)版)(3):341-345.

博主簡介：擅長智能優(yōu)化算法、神經(jīng)網(wǎng)絡(luò)預(yù)測、信號處理、元胞自動機、圖像處理、路徑規(guī)劃、無人機等多種領(lǐng)域的Matlab仿真，相關(guān)matlab代碼問題可私信交流。

部分理論引用網(wǎng)絡(luò)文獻，若有侵權(quán)聯(lián)系博主刪除。