禁忌搜索

禁忌搜索是一種元啟發式搜索方法，它采用用于數學優化的局部搜索方法。它由FredW.Glover于1986年創建并于1989年正式化。

本地（鄰域）搜索采用問題的潛在解決方案并檢查其直接鄰居（即相似的解決方案，除了很少的小細節），以期找到改進的解決方案。局部搜索方法傾向于陷入次優區域或許多解決方案同樣適合的高原。

禁忌搜索通過放寬其基本規則來增強本地搜索的性能。首先，如果沒有可用的改進移動（例如當搜索卡在嚴格的局部最小值時），則在每一步都可以接受惡化移動。此外，還引入了禁令（以下稱為禁忌詞）以阻止搜索返回到先前訪問過的解決方案。

禁忌搜索的實現使用描述訪問過的解決方案或用戶提供的規則集的內存結構。如果某個潛在解決方案在某個短期內之前曾被訪問過或者它違反了規則，則將其標記為“禁忌”（禁止），以便算法不會重復考慮該可能性。

禁忌搜索(TS)是一種元啟發式算法，可用于解決組合優化問題（需要最佳排序和選項選擇的問題）。

TS的當前應用跨越資源規劃、電信、VLSI設計、財務分析、調度、空間規劃、能源分配、分子工程、物流、模式分類等領域、柔性制造、廢物管理、礦產勘探、生物醫學分析、環境保護和其他許多領域。近年來，各個領域的期刊都發表了教程文章和計算研究，這些文章和計算研究記錄了禁忌搜索在擴展可以有效處理的問題的前沿方面取得的成功——產生的解決方案的質量通常xxx超過以前應用的方法獲得的解決方案。完整的應用程序列表，包括從實際實現中獲得的收益的摘要描述，可以在中找到最近的TS開發和應用程序也可以在禁忌搜索小插圖中找到。

禁忌搜索與模擬退火有幾個相似之處，因為兩者都涉及可能的下坡移動。實際上，模擬退火可以看作是一種特殊形式的TS，其中我們使用“分級任期”，即一個移動以指定的概率成為禁忌。

禁忌搜索中使用的記憶結構大致可以分為三類：

• 短期：最近考慮的解決方案列表。如果潛在解決方案出現在禁忌列表中，則在達到到期點之前無法重新訪問。
• 中期：旨在將搜索偏向搜索空間的有希望的區域的強化規則。
• 長期：推動搜索進入新區域的多樣化規則（即當搜索陷入停滯或次優死胡同時的重置）。

短期、中期和長期記憶在實踐中可以重疊。在這些類別中，可以通過諸如頻率和所做更改的影響等措施進一步區分內存。

中期記憶結構的一個例子是禁止或鼓勵包含某些屬性的解決方案（例如，解決方案包含某些變量的不良或理想值）或防止或誘導某些移動的記憶結構（例如基于頻率記憶適用于與過去發現的不吸引人或有吸引力的解決方案具有共同特征的解決方案）。在短期記憶中，最近訪問過的解決方案中的選定屬性被標記為“禁忌活動”。禁止含有禁忌元素的溶液。采用超越解決方案禁忌狀態的吸氣標準，從而在允許的集合中包含否則排除的解決方案（假設解決方案根據質量或多樣性的度量“足夠好”）。一個簡單且常用的抽吸標準是允許比目前已知的最佳解決方案更好的解決方案。

單獨的短期記憶可能足以獲得優于傳統局部搜索方法找到的解決方案，但中間和長期結構通常是解決更困難的問題所必需的。禁忌搜索通常以其他元啟發式方法為基準——例如模擬退火、遺傳算法、蟻群優化算法、反應式搜索優化、引導式本地搜索或貪婪隨機自適應搜索。此外，禁忌搜索有時會與其他元啟發式方法相結合以創建混合方法。最常見的禁忌搜索混合是通過將TS與ScatterSearch結合而產生的，一類基于群體的程序，其根源與禁忌搜索相同，通常用于解決大型非線性優化問題。