1 簡(jiǎn)介

1.1 TSP介紹

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

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

1.2 禁忌搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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