禁忌搜索
- TS是Local Search（LS）的擴展，是一種全局逐步尋優(yōu)的全局性鄰域搜索算法。
- TS模仿人類的記憶功能，在搜索過程中標記已經(jīng)找到的局部最優(yōu)解及求解過程，并于之后的搜索中避開它們
- 算法通過禁忌策略實現(xiàn)記憶功能，通過破禁準則繼承LS的強局部搜索能力。使得TS一方面具備高局部搜索能力，同時又能防止算法在優(yōu)化中陷入局部最優(yōu)。
TS主要構成要素
- 評價函數(shù)（Evaluation Function）：用來評價鄰域中的鄰居、判斷其優(yōu)劣的衡量指標。
- 鄰域移動（Move Operator）：進行解轉移的關鍵，又稱“算子”，影響整個算法的搜索速度。
-
禁忌表（Tabu Table）：記錄被禁止的變化，以防出現(xiàn)搜索循環(huán)、陷入局部最優(yōu)。
對其設計中最關鍵的因素是禁忌對象（禁忌表限定的對象）和禁忌步長（對象的禁忌在多少次迭代后失效）。
禁忌表是禁忌搜索算法的核心，禁忌表的對象、步長及更新策略在很大程度上影響著搜索速度和解的質量。若禁忌對象不準確或者步長過小，算法避免陷入局部最優(yōu)的能力會大打折扣；若禁忌表步長過大，搜索區(qū)域將會限制，好的解就可能被跳過。 - 鄰居選擇策略（Neighbor Selection Strategy）：選擇最佳鄰域移動的規(guī)則。目前最廣泛采用的是“最優(yōu)解優(yōu)先策略”及“第一個改進解優(yōu)先策略”。
- 破禁準則（Aspiration Criterion）：對于禁忌表的適度放松。當某個被禁忌的移動可得到優(yōu)于未被禁忌的移動得到的最優(yōu)鄰域解和歷史所得到的最優(yōu)解時，算法應接受該移動，不受禁忌表的限制。
- 停止規(guī)則（Stop Criterion）：禁忌搜索中停止規(guī)則的設計多種多樣，如最大迭代數(shù)、算法運行時間、給定數(shù)目的迭代內不能改進解或組合策略等等。
TS算法性能
通過一系列關于TSP的實驗得到以下結論：
- 禁忌策略大大加強了算法的搜索能力
- 問題規(guī)模較小時，禁忌搜索能得到最優(yōu)解；
問題規(guī)模較大時，禁忌搜索能在規(guī)定時間內輸出滿意解。 - 禁忌對象的選擇對算法效果存在較大影響
干貨 | 十分鐘掌握禁忌搜索算法求解帶時間窗的車輛路徑問題(附C++代碼和詳細代碼注釋)
TS基本步驟
- 初始化
利用貪婪算法等局部搜索算法生成一個初始解，清空禁忌表，設置禁忌長度 - 鄰域搜索產(chǎn)生候選解
根據(jù)步驟1產(chǎn)生初始解，通過搜索算子（search operators），如relocation、exchange、2-opt等，產(chǎn)生候選解(candidate solution)，并計算各個候選解的適應值（即解對應的目標函數(shù)值） - 選擇最好的候選解
從步驟2產(chǎn)生的所有候選解中選出適應值最好的候選解，將其與當前最好解(即搜索算法開始到現(xiàn)在找到的最好解)進行比較
如果優(yōu)于當前最好解，那么就不考慮其是否被禁忌，用這個最好的候選解來更新當前最好解，并且作為下一個迭代的當前解，然后將對應的操作加入禁忌表；
如果不優(yōu)于當前最好解，就從所有候選解中選出不在禁忌狀態(tài)下的最好解作為新的當前解，然后將對應操作加入禁忌表。 - 判斷終止條件
若滿足終止條件，則立即停止并輸出當前最好解；否則繼續(xù)搜索。
一般終止條件為是否到達一定的迭代次數(shù)或者達到了一個時間限制
TS流程圖
禁忌搜索算法流程圖
禁忌搜索算法涉及編碼解碼（Encoding and decoding）、搜索算子（search operators）、鄰域 （Neighborhood）、禁忌表（Tabu list）、禁忌長度（Tabu tenure）、候選解（Candidate solution）、藐視準則（Aspiration criterion）等關鍵組成部分。
TS求解TSP
算例
5個城市的TSP算例
-
編碼和解碼
初始解
初始解對應的適應度F=37
-
搜索算子
（1）Relocation算子：在當前解中選擇并移除一個節(jié)點(node)，然后再選擇一個位置將選中的節(jié)點插入
relocation算子
適應度變化量△F=6
（2）Swap算子：在當前解中同時選擇兩個不同的節(jié)點，然后對這兩個節(jié)點的位置交換
swap算子
適應度變化量△F=4 -
鄰域
從當前解對一系列的搜索方向進行一次試探（通過算子搜索一次）能得到的所有解的集合，即僅經(jīng)過一次操作能得到的所有解
鄰域（候選解集合） -
禁忌表
記錄當前所選擇操作的狀態(tài)變化，一般包括禁忌對象和禁忌長度
候選解10改進最大，禁忌對象如圖所示 - 禁忌長度
禁止在之后的l次迭代中對禁忌表中所記錄的狀態(tài)進行改變，這里的l即稱為禁忌長度 - 候選解
當前鄰域中的解 - 藐視準則
從候選解集合中挑選出最好的候選解，將其與當前最好解進行比較，若其是被禁止的解但是優(yōu)于當前最好解，那么就將其解禁，用來作為下一迭代的當前解并及替代當前最好解。
藐視準則（Aspiration criterion）防止了因為禁忌表的存在，而錯過優(yōu)異解的情況出現(xiàn)。
TS求解VRPTW
VRPTW：帶時間窗的車輛路徑問題
問題描述
假設一個配送中心為周圍若干個位于不同地理位置、且對貨物送達時間有不相同要求的客戶點提供配送服務。其中，配送中心全部用于運行的車輛都是同一型號的（即擁有相同的容量）；配送中心對車輛出入的時間有限制；車輛在所有客戶點有相同的停留服務時間
操作設置
- 編碼方式采取自然數(shù)編碼，利用將車輛所需服務客戶點的集合（解集）作為集合內元素數(shù)目大小的自然數(shù)數(shù)組。數(shù)組中各個元素的值代表各個客戶點的編號，元素的順序代表服務客戶點的順序。
- 搜索算子采用插入算子：刪除原路徑中的客戶節(jié)點，遍歷插入到任意車輛路徑的任意位置，選取鄰域最好解或者非禁忌最好解作為下一迭代的當前解。鄰域為插入算子完全遍歷能得到的解的集合。
