局部搜索演算法

⑴ 禁忌搜索局部領域搜索

局部領域搜索，基於貪婪策略，簡單易行，易於理解，但它在搜索性能上受限於初始解和領域結構。它容易陷入局部最優，而非全局最優。為了克服這個問題，可以採取多種策略：如模擬退火演算法，通過可控概率接受較差解來逃離局部極小；TSP的2opt方法可以擴展到k-opt，擴大搜索范圍；進化計算則提倡多點並行搜索；變結構領域搜索（Mladenovic等人，1997）也提供了一種創新方法。禁忌策略在TS中起著關鍵作用，它通過標記已探索的局部最優，避免重復搜索，採用確定性的策略來跳出局部極小，這是一種對不同有效搜索路徑的積極探索。

禁忌搜索作為人工智慧的一個分支，是對局部領域搜索的擴展。其核心理念是記錄已搜索過的局部最優解，並在後續搜索中避開它們，而非徹底禁止。這個過程涉及到臨域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu length）、候選解（candidate）以及藐視准則（aspiration criterion）等關鍵概念，它們共同作用於提升搜索的全局優化性能。

禁忌搜索（Tabu Search或Taboo Search，簡稱TS）的思想最早由Glover(1986)提出，它是對局部領域搜索的一種擴展，是一種全局逐步尋優演算法，是對人類智力過程的一種模擬。TS演算法通過引入一個靈活的存儲結構和相應的禁忌准則來避免迂迴搜索，並通過藐視准則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。相對於模擬退火和遺傳演算法，TS是又一種搜索特點不同的 meta-heuristic演算法。