基于“记忆”的智能探索
想象一下，你在爬山（寻找最高点），使用最速上升法（总是向当前位置附近最高的点走），这种方法很容易陷入一个小山丘的顶部（局部最优解），而错过了远处更高的山峰（全局最优解）。
禁忌搜索的核心思想就是： 为了避免在局部最优解附近循环往复，算法会“最近已经探索过的步骤或解，并在短期内禁止（即“禁忌”）返回这些状态，从而迫使搜索走向新的、未被探索的区域。
两个关键机制
禁忌表
这是算法的“短期记忆”核心。
- 是什么：一个存储了最近若干次移动（或解的特征）的列表。
- 作用：表中的移动在接下来的若干次迭代中被禁止使用。
- 关键参数：
- 禁忌对象：什么被放入表中？可以是解本身（简单但限制过强）、解的属性（如TSP中交换的两个城市）或移动（从解A到解B的操作）。
- 禁忌长度：一个禁忌对象在表中保留的迭代次数，太小容易循环，太大限制搜索,可以是固定值或动态调整。
特赦准则
这是算法的“赦免金牌”,防止错过好机会。
- 是什么：一个破例规则,允许被禁忌的移动被执行。
- 最常见的准则：基于评价值的特赦，如果某个被禁忌的移动能产生一个比历史最好解还要好的解，那么就无视禁忌,执行该移动并更新历史最好解。
算法基本流程（迭代步骤）
- 初始化：生成一个初始解,清空禁忌表。
- 迭代搜索：
a. 生成候选集：基于当前解，在其“邻域”内生成一系列候选移动（新解）。
b. 评估与筛选：评估所有候选移动。
- 找出不被禁忌的移动中的最佳移动。
- 检查被禁忌的移动是否满足特赦准则（通常指能产生新的全局最优解）。 c. 选择移动：执行（b）中确定的最佳移动（可能是不被禁忌的最佳者，也可能是满足特赦的被禁忌者），从而更新当前解。 d. 更新禁忌表：
- 将本次采用的移动（或其属性）加入禁忌表。
- 如果表已满，则移除最早进入的条目（先进先出）。 e. 更新历史最优：如果新解优于历史最优解,则更新历史最优解。
- 终止判断：重复步骤2，直到满足终止条件（如达到最大迭代次数、历史最优解在长时间内无改进等）。
- 输出：返回找到的历史最优解。
邻域结构
这是算法的基础“操作集”,定义了如何从当前解生成新解。
- 旅行商问题：交换两个城市、逆序一段路径等。
- 调度问题：交换两个工序、插入一个工序等。
- 邻域结构的设计极大地影响搜索效率和质量。
优点与缺点
优点：
- 结构简单，易于实现。
- 能有效跳出局部最优解,全局搜索能力强。
- 对初始解的依赖性相对较低。
- 参数较少,核心是禁忌长度。
- 在复杂约束问题中表现良好。
缺点：
- 搜索性能严重依赖于参数设置（尤其是禁忌长度和邻域结构）。
- 对连续优化问题处理能力较弱（主要针对组合优化）。
- 搜索是串行的（不同于遗传算法等种群并行算法）。
- 如果问题规模极大,单次邻域搜索的计算成本可能很高。
典型应用场景
- 路径规划：车辆路径问题、旅行商问题。
- 生产调度：作业车间调度、流水线调度。
- 资源分配。
- 图着色问题。
- 机器学习中的特征选择等。
总结与形象比喻
你可以把禁忌搜索想象成一个 “有记性的登山者”：
- 目标：找到最高的山（全局最优）。
- 基本行动：总是尽量往高处走（局部搜索）。
- 遇到的麻烦：容易在小山包顶上来回打转（陷入局部最优）。
- 禁忌表的妙用：他随身带了一支粉笔，在走过的路上标记 “此路刚走过，暂时勿回” （禁忌表）,这迫使他尝试新的方向。
- 特赦准则的智慧：当他发现某条被标记的路似乎通向一个明显更高的地方（满足特赦准则）时，他会毫不犹豫地擦掉标记,走那条路。
通过这种“短期记忆”和“灵活破例”的机制，禁忌搜索在局部深度搜索和全局广度探索之间取得了巧妙的平衡,成为解决复杂组合优化问题的一柄经典利器。
版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。
