Skip to content
返回搜索结果

禁忌搜索 — 局部搜索元启发式算法

提出者
Fred Glover
年份
1989
类型
Local-search metaheuristic

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

禁忌搜索(Tabu Search)是由Fred Glover于1989年提出的一种局部搜索元启发式算法。它使用一个禁忌列表(tabu list)——一个记录近期访问过的解的短期记忆——来防止循环并跳出局部最优。通过明确禁止逆转近期决策的移动,该算法能够更广泛地探索搜索空间,并通过诸如渴望准则(aspiration criteria)之类的长期记忆结构,即使在大型、复杂的组合优化问题中,也能趋向于全局最优。

方法背后的直觉

想象一下在黑暗中导航崎岖的山地,试图找到最高的山峰。一个简单的局部搜索爬山者总是向上走,并被困在它到达的最近的山顶上。禁忌搜索则携带一个记录近期访问过的地点的笔记本,拒绝返回这些地点,即使回溯看起来很诱人。这种对近期移动的强制性遗忘迫使搜索走出死胡同,进入未探索的区域,使其最终能够发现比普通局部搜索高得多的“高度”,即更好的解。

历史学

禁忌搜索由Fred Glover在1989年发表于ORSA Journal on Computing的里程碑式论文中提出,他将其作为一种通过利用对过去移动的记忆来指导局部搜索的策略。基本思想在Glover和Laguna的1997年Springer专著中得到巩固和扩展,该专著确立了至今仍是该方法核心的经典短期禁忌列表、渴望准则以及长期多样化和强化策略。自提出以来,禁忌搜索已广泛应用于运筹学、调度、物流和组合设计领域,并且与模拟退火和遗传算法一起,它仍然是一种标准的基准元启发式算法。

何时使用

禁忌搜索非常适合组合优化和离散优化问题,这些问题的解空间对于精确方法来说过于庞大,并且问题结构允许定义有意义的邻域。典型应用包括调度、路径规划、分配和排序问题。当搜索景观存在许多困扰简单方法的局部最优时,它尤其有效。它不需要目标函数是可微的或连续的。必须仔细调整邻域定义和禁忌长度以适应特定问题;选择不当的邻域或过短或过长的禁忌长度会显著降低性能。至少需要几百次——理想情况下超过一千次——迭代才能充分探索搜索空间。

局限与注意事项

  • 性能对邻域定义和禁忌长度敏感;选择不当可能导致搜索陷入困境或在禁忌机制下循环。
  • 需要最小迭代预算——通常超过1000次迭代——才能充分探索邻域;迭代次数太少时,结果不比简单的局部搜索好。
  • 禁忌列表存储移动属性而非完整解,因此需要渴望准则来防止无意中阻止真正好的移动。
  • 与精确求解器不同,禁忌搜索不提供最优性保证,且结果质量可能因运行时的初始解或邻域而异(如果它们是随机的)。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 通过禁忌机制逃离局部最优,无需梯度信息。
  • 适用于组合问题、混合类型问题,甚至连续问题——不假设正态性或任何分布特性。
  • 在多个时间尺度上整合记忆(短期禁忌列表、长期多样化/强化),能够有原则地探索搜索空间。
  • 与精确方法相比,在大型实例上通常能以相对适中的计算预算找到高质量的解。

应用

  • 作业车间和流水车间调度——优化操作顺序以最小化完工时间或迟到时间。
  • 车辆路径规划——在容量和时间窗口约束下寻找有效的配送路线。
  • 分配和设施选址——将任务分配给资源或选址以最小化成本。
  • 图着色、网络设计和电信——解决离散结构优化问题。
  • 特征选择和超参数搜索——在机器学习管道中探索离散配置空间。

使用方式

使用方式

1

搜索从一个初始候选解开始,该解可以通过随机生成或使用贪婪启发式方法构建。禁忌列表被设置为一个空的固定长度队列,并记录迄今为止找到的最佳解。必须以对特定问题有意义的方式定义邻域结构——即定义哪些解距离当前解一步之遥的规则。

2

从当前解出发,生成并根据目标函数评估定义邻域中的所有移动。每个移动对应一个小的扰动,例如交换序列中的两个元素或翻转一个二元变量。邻域必须足够丰富以允许有意义的探索,但又足够小以便在每次迭代中都能处理。

3

每个候选移动都会根据禁忌列表进行测试。如果该移动——或表征该移动的属性——出现在列表中,则被归类为禁忌移动并被禁止,除非它满足渴望准则:通常,如果产生的解会优于迄今为止找到的最佳解,则禁忌状态将被覆盖,允许该移动。这种渴望机制在不放弃其反循环纪律的情况下,赋予了算法灵活性。

4

在所有非禁忌移动(以及所有通过渴望准则的禁忌移动)中,选择表现最佳的移动并执行它,即使它会使目标值变差。这种接受劣化的意愿使得算法能够跳出局部最优,这是禁忌搜索与简单爬山法相比的决定性特征。

5

执行移动后,通过添加刚刚进行的移动的逆向(或其表征属性)来更新禁忌列表,如果列表已满,则移除最旧的条目,保持其固定长度——即禁忌长度(tabu tenure)。如果新解优于记录的最佳解,则更新最佳解。可选的长期记忆结构可以跟踪解的频率或近期性,以指导向较少访问区域的多样化探索或向有希望区域的强化。

6

算法继续迭代,直到满足停止标准:达到最大迭代次数、达到目标目标值,或在固定次数的迭代中没有改进。在整个搜索过程中找到的最佳解将作为结果返回。选择足够的迭代预算至关重要——迭代次数太少会阻碍充分的邻域探索。

常见陷阱

  • 将禁忌长度设置得太短会导致循环再次发生,从而破坏禁忌机制的目的;禁忌长度应根据问题规模进行调整。
  • 将禁忌长度设置得太长会过度限制搜索,并阻止算法重新访问可能包含改进的区域。
  • 运行少于大约1000次迭代意味着搜索尚未充分探索邻域——如果计算资源有限,可以回退到模拟退火,模拟退火可以在更少的迭代次数中更快地产生有用的结果。
  • 使用过于狭窄的邻域(例如,在复杂结构上仅进行单次交换移动)会导致搜索深度不足;确保邻域足够丰富以连接解空间的所有有希望的区域。
  • 忽略渴望准则可能会永久阻止通往全局最优的移动,如果该移动恰好是禁忌的;至少始终实现标准的最佳解覆盖。

常见问题

禁忌搜索与模拟退火有何不同?

两种方法都接受劣质移动以跳出局部最优,但它们的机制不同。模拟退火根据冷却温度参数的指导,以概率方式接受较差的移动。禁忌搜索则根据对近期移动的明确记忆,确定性地接受可用的最佳非禁忌移动。禁忌搜索通常在结构化的组合优化问题上更有效;模拟退火在具有连续或近乎连续景观的问题上更容易调整,并且在迭代预算较少(低于约1000次迭代)时更可取。

禁忌列表应该有多长?

禁忌长度——一个移动被禁止的迭代次数——取决于具体问题。一个常用的起点是与问题规模平方根成比例的长度,但这应该通过经验进行调整。过短的禁忌长度会导致循环;过长的禁忌长度会过度限制搜索。自适应或随机的禁忌长度策略可以降低对该选择的敏感性。

禁忌搜索能保证找到全局最优解吗?

不能。禁忌搜索是一种元启发式算法,不提供最优性保证。它旨在高效地找到高质量的解,但结果取决于邻域结构、禁忌长度、迭代次数和初始解。要获得最优性保证,需要精确方法,如整数规划,尽管对于大型实例,精确方法可能在计算上不可行。

什么是渴望准则,为什么需要它?

渴望准则是一种在特殊条件下覆盖移动禁忌状态的规则。最常见的准则是:如果执行一个禁忌移动会产生一个优于迄今为止找到的最佳解的解,则解除禁忌限制并允许该移动。没有这种覆盖,如果通往全局最优的路径经过一个近期访问过的移动,禁忌机制可能会永久地阻止该路径。

相关方法

参考文献

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    打开出版物文献
    已复制。
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN:9780792349907
    已复制。