禁忌搜索（TS）

名称

禁忌搜索（Tabu Search, TS）

分类

查看分类思维导图

禁忌搜索是一种元启发式优化算法，属于局部搜索技术领域。它与其他局部搜索算法密切相关，例如爬山算法（Hill Climbing）和模拟退火（Simulated Annealing）。

• 人工智能
  • 优化
    • 元启发式
      • 局部搜索
        • 禁忌搜索

策略

禁忌搜索是一种局部搜索算法，其通过维护一个禁忌表来跳出局部最优。禁忌表是一种短期记忆机制，用于记录最近访问过的解或移动。算法通过从当前解移动到其邻域中的最佳解来探索解空间，即使该移动会导致目标函数值变差，也仍然可以被接受。为防止搜索回到先前访问过的解，禁忌表会在一定迭代次数内禁止某些移动或解，这一期限称为禁忌长度（tabu tenure）。

算法从一个初始解开始，并通过应用局部搜索移动不断迭代改进该解。在每次迭代中，算法都会在当前解的邻域内生成一组候选解。随后，从这些候选解中选出最佳解作为新的当前解，即使它比前一个当前解更差也可以接受。若所选移动位于禁忌表中，则只有在其满足特赦准则（aspiration criterion）时才会被接受。特赦准则允许算法在某一禁忌移动能够产生优于迄今最优解的解时，覆盖该移动的禁忌状态。

禁忌搜索还结合了强化（intensification）与多样化（diversification）策略，以平衡对解空间的开发与探索。强化侧重于更深入地搜索解空间中有前景的区域，而多样化则鼓励算法探索新的区域，以跳出局部最优。

过程

1. 初始化：

• 生成一个初始解 s
• 设置最优解 s_best = s
• 将禁忌表初始化为空
• 设置禁忌长度 t
• 设置最大迭代次数 max_iter
• 设置当前迭代计数器 iter = 0

2. 当 iter < max_iter 时：

• 在 s 的邻域中生成一组候选解 N(s)
• 从 N(s) 中选择最佳候选解 s'，要求其不在禁忌表中，或满足特赦准则
• 更新最优解：若 f(s') < f(s_best)，则令 s_best = s'
• 更新当前解：s = s'
• 更新禁忌表：
  • 将生成 s' 的移动加入禁忌表
  • 若禁忌表大小超过禁忌长度 t，则移除表中最早加入的移动
• 迭代计数器加一：iter = iter + 1

3. 返回找到的最优解 s_best

数据结构

• 解（Solution）：表示解空间中的一个候选解
• 禁忌表（Tabu List）：用于存储最近访问过的解或移动的列表
• 特赦准则（Aspiration Criterion）：允许算法覆盖某一移动禁忌状态的条件

参数

• 禁忌长度（Tabu Tenure）：某个移动或解在禁忌表中保持禁忌状态的迭代次数
• 最大迭代次数（Maximum Iterations）：算法终止前允许执行的最大迭代次数
• 邻域规模（Neighborhood Size）：每次迭代中生成的候选解数量

注意事项

优点

• 禁忌搜索允许接受劣解，并通过防止回到先前访问过的解来跳出局部最优
• 禁忌表提供了一种短期记忆机制，有助于算法探索解空间中的新区域
• 禁忌搜索具有较强灵活性，易于适配多种优化问题

缺点

• 禁忌搜索的性能依赖于禁忌长度及其他参数的合理设置
• 算法可能需要大量迭代才能收敛到高质量解
• 对于高度受约束的问题或具有大量局部最优的问题，禁忌搜索可能表现不佳

启发式建议

禁忌长度

• 禁忌长度应根据问题的规模与复杂度进行设置
• 较小的禁忌长度允许更多探索，但可能导致循环；较大的禁忌长度有利于多样化，但可能减缓搜索速度
• 一种常见经验是将禁忌长度设置在 7 到 20 之间，具体取决于问题规模

特赦准则

• 最常见的特赦准则是：当某个禁忌移动能够产生优于当前已知最优解的解时，允许执行该禁忌移动
• 也可采用其他特赦准则，例如当某个禁忌移动在一定迭代次数内未被访问过时，允许接受该移动

强化与多样化

• 可通过将搜索集中于解空间中有前景的区域来实施强化策略，例如从迄今为止的最优解重新启动搜索，或修改邻域结构以重点探索与当前最优解相似的解
• 可通过向当前解引入随机扰动、采用更大的邻域规模，或周期性地将搜索重置到新的初始解来实施多样化策略

停止准则

• 算法可以在达到固定迭代次数、消耗预定计算时间，或在连续若干次迭代未取得改进时终止
• 常见做法是根据问题规模与复杂度设置最大迭代次数，并在连续若干次迭代未观察到改进时提前终止

邻域结构

• 邻域结构的选择取决于具体求解问题，并会对算法性能产生显著影响
• 常见邻域结构包括交换移动（交换两个元素）、插入移动（移除一个元素并将其插入到另一位置），以及与具体问题领域相关的更复杂移动
• 邻域规模应足够大，以保证充分探索；但也不宜过大，否则会显著降低搜索效率