1. 简介
在本篇文章中，我们将深入解析禁忌搜索（Tabu Search, TS）算法。这是一种用于解决组合优化问题的局部搜索元启发式算法。TS 的核心思想是通过引入“禁忌机制”来避免局部搜索过程中常见的陷入局部最优和循环问题。
2. 禁忌搜索与优化问题
优化方法通常分为精确算法和近似算法两大类。而元启发式算法（Metaheuristics）是近似算法中非常重要的一类，常用于解决复杂优化问题。
常见的元启发式算法包括：
- 遗传算法（Genetic Algorithm）
- 蚁群优化（Ant Colony Optimization）
- 粒子群优化（PSO）
- 模拟退火（Simulated Annealing）
Tabu Search 属于局部搜索元启发式算法，专门用于求解组合优化问题（Combinatorial Optimization Problems），例如旅行商问题（TSP）、作业车间调度等。
2.1 局部搜索的局限性
局部搜索的基本思路是从一个初始解出发，搜索其邻域中的更优解，并不断迭代，直到满足停止条件或找到最优解。
但它存在两个明显问题：
✅ 陷入局部最优或平台区：搜索容易停留在局部最优解或目标函数值不变的区域
❌ 循环问题（Cycling）：反复访问相同的解或解集合，导致无法继续探索
如下图所示，即使在单维搜索空间中，也可能出现这些问题：
Tabu Search 正是为了解决这些问题而设计的。
3. Tabu Search 的核心要素
Tabu Search 在每次迭代中评估当前解的邻域样本，并选择其中最优的解作为下一步的起点，即使它比当前解更差。这种机制帮助算法跳出局部最优。
其核心机制包括：
- 禁忌表（Tabu List）
- 邻域定义（Neighborhood）
- 期望准则（Aspiration Criteria）
3.1 禁忌表（Tabu List）
Tabu Search 每次迭代都会检查并更新禁忌表。禁忌表中包含的是被禁止访问的解，通常是最近访问过的解。
- 如果一个解在禁忌表中停留超过预设的迭代次数
，它将被移除 - 禁忌表中也可以包含禁忌规则（Tabu Rules），比如某些特定操作或状态应被禁止
⚠️ 注意：一个解被标记为“禁忌”并不意味着它一定被访问过，它可能因为触发了某些规则而被禁止访问。
3.2 邻域（Neighborhood）
对于某个解 
，其邻域 
表示在第 
次迭代中，与 邻近的解集合。
举个例子：
- 可以定义 为所有与 距离不超过
的解 - 如果
随迭代变化，那么邻域是自适应的；否则它是固定的
3.3 期望准则（Aspiration Criteria）
期望准则是用于解除某个解的禁忌状态的规则。例如：
- 如果某个解的目标函数值优于当前迭代中所有其他解，那么即使它在禁忌表中，也可以被选中
我们用 
来表示第 次迭代中解 是否满足期望准则。
Tabu Search 是否选择一个解取决于以下两个条件之一：
- 该解不在禁忌表中 ✅
- 该解虽然在禁忌表中，但满足期望准则 ✅
4. 算法伪代码
设目标函数为 
，最大迭代次数为 
，则 Tabu Search 的伪代码如下：
algorithm TabuSearch(S, maxIter, f, neighborhoods, aspirationCriteria):
// S: 搜索空间
// maxIter: 最大迭代次数
// f: 目标函数
// neighborhoods: 邻域定义
// aspirationCriteria: 期望准则
s ← 初始解
s* ← s // 当前最优解
k ← 1
T ← 空禁忌表
while k ≤ maxIter:
// 生成当前解的允许邻域 V(s, k)
V(s, k) ← { s' ∈ N(s, k) | s' ∉ T 或 a(k, s') = true }
// 从 V(s, k) 中选择最优解
s ← V(s, k) 中使 f 最小的解
// 更新全局最优解
if f(s) < f(s*):
s* ← s
// 更新禁忌表和期望准则
更新 T 和 a
// 进入下一轮迭代
k ← k + 1
return s*
Tabu Search 的参数设置决定了算法在搜索过程中是更偏向集中化（Intensification）还是多样化（Diversification）。两者之间的平衡对于解决组合优化问题至关重要。
5. 总结
Tabu Search 是一种基于局部搜索的元启发式算法，通过引入禁忌机制和期望准则，有效避免了局部搜索中的局部最优和循环问题。
它的优势在于：
- 不局限于当前最优解，允许向劣解移动
- 通过禁忌表记忆搜索路径，防止重复搜索
- 使用期望准则灵活解除禁忌限制，提高搜索效率
Tabu Search 广泛应用于 TSP、调度、资源分配等复杂组合优化问题中，是一种非常实用的启发式优化工具。