禁忌搜尋算法（Tabu Search, TS）是一種現代啟發式算法，由美國科羅拉多大學教授Fred Glover在1986年左右提出，主要用於跳出局部最優解。該算法從一個初始可行解開始，選擇一系列特定搜尋方向的移動，目標是讓目標函式值最大化或最小化。為避免陷入局部最優，TS採用了一種靈活的「記憶」技術，即禁忌表，記錄和指導後續搜尋方向。
禁忌搜尋的核心在於禁忌表的使用。禁忌表模擬了人類的短期記憶功能，用於防止搜尋過程中的循環和陷入局部最優。它通常記錄最近接受的若乾次移動，並在一定次數內禁止這些移動再次被訪問。禁忌長度是禁忌對象在禁忌表中的生存時間，搜尋過程中禁忌長度每經歷一次疊代減少1。
禁忌搜尋的流程大致如下：
初始化：給出一個初始解，並清空禁忌表。
鄰域搜尋產生候選解：基於當前解，通過鄰域移動產生一組候選解，並計算各候選解的適應度。
選擇最好的候選解：從候選解中選擇適應度最好的解。如果這個解優於當前最好解，即使它被禁忌，也會用來更新當前最好解。否則，選擇一個不在禁忌狀態下的最好解作為新的當前解。
更新禁忌表：將選擇的移動加入禁忌表。
判斷終止條件：若滿足（如達到最大疊代次數或時間限制），則停止並輸出當前最好解；否則返回步驟2。
禁忌搜尋在組合最佳化和函式全局最佳化方面取得了顯著成功，其變種如並行禁忌搜尋算法等，通過分解搜尋空間實現並行化，進一步提高搜尋效率。