這次是首次接觸這個算法，看了一些資料，總結一下。 ### 禁忌搜索算法簡介 禁忌搜索算法是組合優化算法的一種，是局部搜索算法的擴展。禁忌搜索算法是人工智能在組合優化算法中的一個成功應用。禁忌搜索算法的特點是采用了禁忌技術。所謂禁忌就是禁止重復前面的工作。禁忌搜索算法用一個禁忌表記錄下已經到達過的局部最優點，在下一次搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點。 禁忌搜索算法實現的技術問題是算法的關鍵。禁忌搜索算法涉及侯選集合、禁忌對象、評價函數、特赦規則、記憶頻率信息等概念。 ### 鄰域 在組合優化中，距離的概念通常不再適用，但是在一點附近搜索另一個下降的點仍然是組合優化數值求解的基本思想。因此，需要重新定義鄰域的概念。 一個組合優化問題可用三參數(D,F,f)表示，其中D表示決策變量的定義域，F表示可行解區域， F中的任何一個元素稱為該問題的可行解， f表示目標函數。滿足 f(x?)=min{f(x)|x∈F}的可行解x?稱為該問題的最優解。 定義 1 對于組合優化問題(D,F,f)，D上的一個映射： N:S∈D→N(S)∈2D 稱為一個鄰域映射，其中 2D 表示 D 的所有子集組成的集合， N(S) 稱為 S 的鄰域， S′∈N(S) 稱為 S 的一個鄰居。 ### 侯選集合 侯選集合由鄰域中的鄰居組成。常規的方法是從鄰域中選擇若干個目標值或評價值最佳的鄰居入選。 ### 禁忌對象和禁忌長度 禁忌表中的兩個主要指標是禁忌對象和禁忌長度。禁忌算法中，由于我們要避免一些操作的重復進行，就要將一些元素放到禁忌表中以禁止對這些元素進行操作，這些元素就是我們指的禁忌對象。禁忌長度是被禁對象不允許選取的迭代次數。一般是給被禁對象x一個數（禁忌長度） t ，要求對象x 在t 步迭代內被禁，在禁忌表中采用tabu(x)=t記憶，每迭代一步，該項指標做運算tabu(x)=t?1，直到tabu(x)=0時解禁。于是，我們可將所有元素分成兩類，被禁元素和自由元素。禁忌長度t 的選取可以有多種方法，例如t=常數，或t=[n√]，其中n為鄰域中鄰居的個數；這種規則容易在算法中實現。 ### 評價函數 評價函數是侯選集合元素選取的一個評價公式，侯選集合的元素通過評價函數值來選取。以目標函數作為評價函數是比較容易理解的。目標值是一個非常直觀的指標，但有時為了方便或易于計算，會采用其他函數來取代目標函數。 ### 特赦規則 在禁忌搜索算法的迭代過程中，會出現侯選集中的全部對象都被禁忌，或有一對象被禁，但若解禁則其目標值將有非常大的下降情況。在這樣的情況下，為了達到全局最優，我們會讓一些禁忌對象重新可選。這種方法稱為特赦，相應的規則稱為特赦規則。 ### 記憶頻率信息 在計算的過程中，記憶一些信息對解決問題是有利的。如一個最好的目標值出現的頻率很高，這使我們有理由推測：現有參數的算法可能無法再得到更好的解。根據解決問題的需要，我們可以記憶解集合、被禁對象組、目標值集合等的出現頻率。 頻率信息有助于進一步加強禁忌搜索的效率。我們可以根據頻率信息動態控制禁忌的長度。一個最佳的目標值出現的頻率很高，有理由終止計算而將此值認為是最優值。 ### 模型及求解 我們用禁忌搜索算法研究如下的兩個問題： （1）研究前幾篇現代優化算法解決的問題。 （2）我方有三個基地，經度、緯度分別為（70,40）,（72,45），（68,48）。假設我方所有無人偵察機的速度都為1000 公里/小時。三個基地各派出一架飛機偵察敵方目標，怎樣劃分任務，才能使時間最短，且任務比較均衡。 ### 問題（1）的求解 求解的禁忌搜索算法描述如下： （1）解空間 解空間S 可表為{1,2,…,101,102}的所有固定起點和終點的循環排列集合，即 S={(π1,…,π102)|π1=1,(π2,…,π101)為2,3,…,101}的循環排列,，π102=102。其中每一個循環排列表示偵察 100個目標的一個回路， πij = 表示第i次偵察 j點。 （2）目標函數 目標函數為偵察所有目標的路徑長度。我們要求 min?f(π1,π2,…,π102)=∑i=1101wπiπi+1 （3）候選集合 定義2 任選序號u,v（u<v）交換u與v之間的順序，此時的新路徑為： π1…πu?1πvπv+1…πu+1πuπv+1…π102 稱為原路徑二鄰域的一個鄰居。 定義 3 任選序號u,v 和 w，將u 和v之間的路徑插到 w 之后，（設u<v<w）對應的新路徑為： π1…πu?1πv+1…πwπu…πvπw+1…π102 稱為原路徑三鄰域的一個鄰居。 如果要考慮當前解的全部二鄰域（或三鄰域）的鄰居，將面臨著太大的工作量。因此我們用隨機選取的方法每次選取50 個鄰居組成的集合作為侯選集合。而將省下的時間作更多次搜索，這樣做同樣可以保證較高的精確度，同時可以大大提高算法的效率。 （4）禁忌長度及禁忌對象 對 于 上述定義的二鄰域中的鄰居總數為C2100， 我們的禁忌長度取為 t=70≈C2100????√ 。 我們把禁忌表設計成一個循環隊列，初始化禁忌表H=Φ 。從候選集合C中選出一個向量x??，如果x???H ，并且H 不滿，則把向量x添加到禁忌表中；如果H已滿，則最早進入禁忌表的向量出列，向量x??進入到出列的位置。 （5）評價函數(類似啟發式搜索的那種，大家有興趣可以百度一下算法A?，對評估函數的設計會更加理解) 可以用目標函數作為評價函數，但是這樣每選取一個新的路徑都得去計算總時間，計算量比較大。對于上述二鄰域中的鄰居作為侯選集合，每一個新路徑中只有兩條邊發生了變化，因此將目標函數的差值作為評價函數可以極大地提高算法的效率。評價函數取為 Δf=(wπu?1πv+wπuπv+1)?(wπu?1πu+wπvπv+1) **禁忌搜索算法的流程如下：** STEP1: ??????選定一個初始解xnow及給以禁忌表H=Φ； STEP2: ??????若滿足停止條件，停止計算；否則，在xnow的鄰域N(H,xnow)中選出滿足禁忌要求的侯選集Can_N(xnow )，在Can _ N(xnow ) 中選一個評價值最佳的解xnext，xnow:=xnext，更新禁忌表H ，重復 STEP2。 利用 Matlab 程序求得，我們的巡航時間大約在41 小時左右，其中的一個巡航路徑如下圖所示  ### 問題（2）的求解 對于這個問題，我們的基本想法是，先根據敵方基地的分布特點將敵方的基地大體劃分在三個區域之內，并使三架偵察機分別對這三個區域的敵軍基地進行偵察，求取各自的最短時間。然后對任務不均衡區域之中的點做適當調整。 我們解決問題的步驟如下： （1）劃分子圖。要達到比較均衡，應使每架飛機的巡航時間基本相同，由于敵方目標的分布較均勻，可以將敵方目標的地理位置圖分成面積基本相同的三部分。如過點（70，40）以斜率k1=45作一條斜線，過點（68，48）以斜率k2=4368作一個斜率，把基地所在的地區劃分成三部分G1,G2,G3。  （2）再對每個子圖Gi(i=1,2,3) 分別運用禁忌搜索算法求得其最短偵察路徑ψi，和最短偵察時間 t(ψi)(i=1,2,3)。 （3）均衡任務。定義均衡率 η=min{t(ψ1),t(ψ2),t(ψ3)}max{t(ψ1),t(ψ2),t(ψ3)}×100% 若η接近于1，則上面劃分的任務就可以接受。否則的話，根據t(ψi)(i=1,2,3)的大小用局部搜索算法，調整k1,k2的斜率，從而調整各分區內點的個數，直至任務達到均衡。 最后計算結果如下 兩直線的斜率分別為k1=0.68,k2=0.6484。 均衡率η=97.57% 三架飛機偵察完所有目標所用的時間分別為 t(ψ1)=20.401小時，t(ψ1)=20.910小時，t(ψ1)=20.729小時