禁忌搜索算法

算法简介

禁忌搜索算法（Tabu Search，简称TS）是一种全局优化算法，由Glover教授于1986年提出。该算法模拟了人类的记忆机制，通过记录已经搜索过的解（称为"禁忌"），避免重复搜索，从而跳出局部最优，找到全局最优解。

禁忌搜索算法的核心思想是：在搜索过程中，禁止（禁忌）某些操作或解，以防止算法陷入循环或重复搜索。同时，通过特赦规则（Aspiration Criteria），允许在某些情况下接受禁忌解，以保证算法的全局搜索能力。

与贪心算法不同，禁忌搜索算法允许接受比当前解更差的解，这使得算法能够跳出局部最优，探索更大的搜索空间。

算法原理

基本概念

1. 解：问题的一个可能解
2. 邻域：当前解附近的其他解，通过某些操作可以得到
3. 移动：从一个解变换到另一个解的操作
4. 禁忌表：记录最近执行过的移动，禁止重复执行
5. 禁忌长度：移动在禁忌表中保留的迭代次数
6. 特赦规则：在某些情况下，允许接受禁忌解的规则
7. 候选解集：从当前解的邻域中选择的一些候选解

算法流程

1. 初始化：

   • 随机生成初始解
   • 初始化禁忌表（通常为空）
   • 设定禁忌长度
   • 设定终止条件（如最大迭代次数）

2. 生成候选解：

   • 从当前解的邻域中生成若干候选解
   • 排除禁忌表中的移动

3. 评估候选解：

   • 计算每个候选解的目标函数值
   • 根据特赦规则判断是否接受禁忌解

4. 选择最优解：

   • 从候选解中选择最优的解
   • 如果最优解是禁忌解，检查特赦规则

5. 更新：

   • 更新当前解
   • 将执行的移动加入禁忌表
   • 更新禁忌表（移除过期的移动）

6. 判断终止条件：

   • 如果满足终止条件，输出结果
   • 否则，返回步骤2

禁忌表机制

禁忌表是禁忌搜索算法的核心，它记录了最近执行过的移动，防止算法陷入循环。

禁忌表的工作原理：

1. 当执行一个移动时，将该移动加入禁忌表
2. 禁忌表中的移动在接下来的若干次迭代中不能被选择
3. 经过禁忌长度后，移动从禁忌表中移除，可以被再次选择

禁忌表的结构：

• 可以用队列、栈或数组实现
• 记录移动的类型和相关信息
• 每次迭代更新禁忌表，移除过期的移动

特赦规则

特赦规则允许在某些情况下接受禁忌解，以保证算法的全局搜索能力。

常见的特赦规则：

1. 基于目标函数值：如果禁忌解的目标函数值优于当前最优解，则接受
2. 基于改进程度：如果禁忌解比当前解有显著改进，则接受
3. 基于多样性：如果禁忌解能够增加解的多样性，则接受

特赦规则的作用：

• 防止算法错过全局最优解
• 增加算法的探索能力
• 避免算法过早收敛

参数说明

1. 禁忌长度：

   • 移动在禁忌表中保留的迭代次数
   • 通常取5-20次
   • 禁忌长度越大，避免循环的能力越强，但可能错过好解

2. 候选解数量：

   • 每次迭代从邻域中选择的候选解数量
   • 通常取10-100个
   • 候选解数量越多，搜索越充分，但计算量越大

3. 终止条件：

   • 最大迭代次数：通常取100-1000次
   • 最优解连续无改进的迭代次数
   • 达到目标函数值的阈值

举例说明

例子1：旅行商问题（TSP）

假设有4个城市，坐标分别为：

• A(0, 0)
• B(1, 2)
• C(3, 1)
• D(2, 0)

目标是找到访问所有城市并回到起点的最短路径。

问题建模：

• 解：一个访问顺序，如 [A, B, C, D]
• 邻域：交换路径中两个城市的顺序
• 目标函数：路径总长度（越小越好）

算法步骤：

1. 初始化：

   • 初始路径：[A, B, C, D]
   • 计算路径长度：AB + BC + CD + DA = √5 + √5 + √2 + 2 ≈ 7.89
   • 禁忌表：空
   • 禁忌长度：3

2. 第一次迭代：

   • 生成候选解（交换两个城市）：
     • 交换A和B：[B, A, C, D]，长度 ≈ 7.89
     • 交换A和C：[C, B, A, D]，长度 ≈ 8.49
     • 交换A和D：[D, B, C, A]，长度 ≈ 7.89
     • 交换B和C：[A, C, B, D]，长度 ≈ 9.64
     • 交换B和D：[A, D, C, B]，长度 ≈ 8.49
     • 交换C和D：[A, B, D, C]，长度 ≈ 8.49
   • 选择最优解：[A, B, C, D] 或 [A, D, C, B]（长度都是7.89）
   • 假设选择 [A, D, C, B]，移动是"交换B和D"
   • 将"交换B和D"加入禁忌表，禁忌长度为3

3. 第二次迭代：

   • 生成候选解（排除"交换B和D"）：
     • 交换A和B：[D, A, C, B]，长度 ≈ 8.49
     • 交换A和C：[C, D, A, B]，长度 ≈ 9.64
     • 交换B和C：[A, C, D, B]，长度 ≈ 8.49
     • 交换C和D：[A, B, D, C]，长度 ≈ 8.49
   • 选择最优解：[D, A, C, B]（长度8.49）
   • 将"交换A和B"加入禁忌表

4. 继续迭代：

   • 禁忌表记录了最近的移动，防止重复
   • 算法会探索不同的路径组合
   • 最终找到最短路径

结果：经过多次迭代，算法会找到最短路径

例子2：图着色问题

假设有一个图，有4个顶点和5条边：

• 顶点：V1, V2, V3, V4
• 边：(V1, V2), (V1, V3), (V2, V3), (V2, V4), (V3, V4)

目标是给每个顶点着色，使得相邻顶点颜色不同，使用的颜色数量最少。

问题建模：

• 解：每个顶点的颜色分配，如 [红, 蓝, 红, 绿]
• 邻域：改变某个顶点的颜色
• 目标函数：冲突边数量 + 使用的颜色数量（越小越好）

算法步骤：

1. 初始化：

   • 初始解：[红, 红, 红, 红]（所有顶点红色）
   • 计算冲突：所有边都冲突，冲突数 = 5
   • 禁忌表：空
   • 禁忌长度：2

2. 第一次迭代：

   • 生成候选解（改变某个顶点的颜色）：
     • 改变V1为蓝色：[蓝, 红, 红, 红]，冲突 = 3
     • 改变V2为蓝色：[红, 蓝, 红, 红]，冲突 = 3
     • 改变V3为蓝色：[红, 红, 蓝, 红]，冲突 = 3
     • 改变V4为蓝色：[红, 红, 红, 蓝]，冲突 = 3
   • 选择最优解：任意一个冲突数为3的解
   • 假设选择 [蓝, 红, 红, 红]，移动是"改变V1为蓝色"
   • 将"改变V1"加入禁忌表

3. 第二次迭代：

   • 生成候选解（排除"改变V1"）：
     • 改变V2为蓝色：[蓝, 蓝, 红, 红]，冲突 = 2
     • 改变V3为蓝色：[蓝, 红, 蓝, 红]，冲突 = 2
     • 改变V4为蓝色：[蓝, 红, 红, 蓝]，冲突 = 2
   • 选择最优解：任意一个冲突数为2的解
   • 将对应的移动加入禁忌表

4. 继续迭代：

   • 禁忌表防止重复改变同一个顶点
   • 算法会尝试不同的颜色组合
   • 最终找到无冲突的解，使用的颜色数量最少

结果：最优解可能是 [红, 蓝, 绿, 红]，使用3种颜色，冲突数为0

使用场景

适用场景

1. 组合优化问题：

   • 旅行商问题（TSP）
   • 车辆路径问题（VRP）
   • 调度问题（作业调度、生产调度）
   • 装箱问题
   • 图着色问题
   • 最大团问题
   • 最小生成树问题

2. 实际应用：

   • 物流配送：车辆路径规划、货物装载
   • 生产调度：车间作业调度、资源分配
   • 网络设计：网络拓扑优化、路由规划
   • 金融领域：投资组合优化、风险管理
   • 电力系统：发电机组调度、电网规划
   • 通信系统：频率分配、信道分配

优势

1. 全局搜索能力强：通过禁忌机制避免陷入局部最优
2. 记忆机制：利用历史信息指导搜索
3. 灵活性强：可以根据问题特点设计邻域结构和禁忌规则
4. 收敛性好：相比模拟退火等算法，禁忌搜索收敛更快
5. 易于实现：算法原理清晰，代码实现相对简单

局限性

1. 参数敏感：禁忌长度、候选解数量等参数的选择对结果影响较大
2. 邻域设计困难：邻域结构的设计对算法性能影响很大
3. 内存消耗：禁忌表需要存储历史信息，可能占用较多内存
4. 初始解依赖：算法性能可能受初始解质量影响

算法改进

为了提高禁忌搜索算法的性能，研究者提出了多种改进版本：

1. 自适应禁忌搜索：

   • 根据搜索情况动态调整禁忌长度
   • 自适应调整候选解数量

2. 并行禁忌搜索：

   • 同时运行多个禁忌搜索过程
   • 加速搜索速度

3. 混合禁忌搜索：

   • 与其他算法结合，如遗传算法、模拟退火
   • 结合局部搜索算法进行精细搜索

4. 反应式禁忌搜索：

   • 根据搜索反应动态调整参数
   • 自动调整禁忌长度和候选解数量

5. 分散禁忌搜索：

   • 引入多样性机制，避免过早收敛
   • 定期重启搜索过程

参数选择建议

1. 禁忌长度：

   • 通常取5-20次
   • 问题规模越大，禁忌长度越长
   • 可以通过实验确定最优值

2. 候选解数量：

   • 通常取10-100个
   • 问题规模越大，候选解数量越多
   • 平衡搜索质量和计算时间

3. 终止条件：

   • 最大迭代次数：通常取100-1000次
   • 最优解连续无改进的迭代次数：通常取20-50次
   • 达到目标函数值的阈值

4. 邻域结构：

   • 根据问题特点设计合适的邻域
   • 邻域应该足够大，保证搜索的多样性
   • 邻域应该易于计算，保证算法效率

总结

禁忌搜索算法是一种强大的全局优化算法，通过禁忌机制和记忆机制来避免陷入局部最优，找到全局最优解。它的核心思想是：记录已经搜索过的移动，防止重复搜索；同时通过特赦规则，允许在某些情况下接受禁忌解，保证算法的全局搜索能力。

禁忌搜索算法具有全局搜索能力强、记忆机制、灵活性强、收敛性好等优点，广泛应用于各种组合优化问题。虽然存在参数敏感、邻域设计困难等局限性，但通过适当的改进和参数调优，TS可以在大多数优化问题中取得良好的效果。

对于初学者来说，禁忌搜索算法是一个很好的入门算法，因为它直观易懂，且容易编程实现。在实际应用中，建议根据具体问题设计合适的邻域结构和禁忌规则，调整参数，或使用改进版本的TS以获得更好的性能。