人工智慧/搜尋/啟發式搜尋/禁忌搜尋
禁忌搜尋
禁忌搜尋的概念最早由弗雷德·格洛弗在 20 世紀 60 年代初觀察他的研究生同學嘗試在計算機上模擬解決問題時提出的（Glover 1998）。在那段時間裡，他注意到他的同事並沒有使用形式邏輯來解決問題，而是透過避免以前嘗試過的步驟來縮小問題空間，如果這些步驟被證明是不可取的（Glover 1998）。禁忌這個名字來自禁忌這個詞，它恰當地描述了上述現象。禁忌搜尋是一種啟發式搜尋演算法，用於解決組合最佳化問題，其中一組離散的可行解是問題空間，目標是找到儘可能好的解（Glover 1989）。換句話說，它是一種元啟發式演算法，它可以幫助區域性搜尋啟發式演算法在搜尋解決方案時達到最佳效能。禁忌搜尋的獨特之處之一是它靈活的記憶系統，與其他具有固定或無記憶系統的搜尋方法不同（Glover 1990）。它還利用了一種約束和釋放搜尋的策略（即禁忌成分）。
工作原理：禁忌限制被用來防止搜尋陷入區域性最優解（Glover 1990）。這些約束被設定為防止禁忌搜尋進行重複的移動。例如，如果兩個位於附近的移動被認為是“最佳”的，那麼搜尋可能會在兩者之間無限地反彈（Glover 1990）。因此，這些重複的移動被標記為“禁忌”，並且在周圍的搜尋空間中不會返回（Glover 1990）。禁忌限制的最終目標是從區域性搜尋空間中跳出來，同時保持找到最優解的可能性（Glover 1990）。為了做到這一點，採用了願望標準來平衡禁忌限制的影響，並允許搜尋擴充套件到更大的搜尋範圍（Glover 1990）。被標記為“禁忌”的解決方案可以在搜尋離開之前有問題的區域性最優值後刪除其“禁忌”狀態。這樣一來，這些解決方案仍然會被視為找到全域性最優解的可能性（Glover 1990）。
圖示：以下是用流程圖顯示的通用禁忌過程。
Glover, Fred. (1990). 禁忌搜尋：一個教程，數學規劃實踐特刊，介面，20，74-94。
Glover, Fred. (1998). 禁忌搜尋——源泉與挑戰。歐洲運籌學雜誌，106，221-225。
Glover, Fred. (1989). 禁忌搜尋——第一部分。ORSA 計算機期刊，1，190-206。