Skip to content
返回搜索结果

鲁棒禁忌搜索 — 一种抗不确定性扰动的基于禁忌的元启发式算法

提出者
Glover, F. (Tabu Search); robustness extensions by various authors
年份
1989 (TS); robust variant ~2000s
类型
Metaheuristic with robustness mechanism
类别
Simulation / optimization

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

字号

它有什么作用?

鲁棒禁忌搜索 (Robust Tabu Search, RTS) 扩展了经典的禁忌搜索元启发式算法,它不仅评估候选解的标称目标值,还评估其在不确定性下的表现。RTS 不寻求单一场景下的最优解,而是寻求在多种场景或实现下表现良好的解,以可靠性换取峰值最优性。

方法背后的直觉

经典的禁忌搜索通过禁止最近访问过的移动并引导搜索穿越邻域来找到优秀解。然而,在实践中,现实世界的输入——成本、需求、旅行时间——是变化的。在假设值下看起来最优的解,在现实偏离时可能表现不佳。鲁棒禁忌搜索将鲁棒性标准直接嵌入评估函数中:每个候选解都通过多个场景(抽样或枚举)进行评估,搜索倾向于表现稳定的、低方差的解。这使得最终解能够抵抗参数波动,而无需事后重新优化。

历史学

禁忌搜索由 Fred Glover 于 1989-1990 年引入,是一种基于记忆的元启发式算法,通过禁止最近反向的移动来逃离局部最优。鲁棒性扩展出现在 20 世纪 90 年代末和 21 世纪初,伴随着对鲁棒优化日益增长的兴趣;研究人员将基于场景和最坏情况的评估纳入 TS 邻域评估中,从而产生了鲁棒禁忌搜索,成为不确定性下工程和物流问题的实用工具。

何时使用

当您面临组合或离散优化问题,且关键输入参数不确定或可变时——例如,在需求或成本不确定性下的路径规划、调度、分配或网络设计问题——请使用鲁棒禁忌搜索。当部署后重新优化的成本很高,或者在实施前必须保证解的可靠性时,它尤其适用。当问题是纯确定性的(经典禁忌搜索足够)、不确定性集太大以至于无法进行可行的抽样(计算成本过高),或者问题是光滑且凸的(基于梯度的鲁棒方法会更快更可靠)时,应避免使用 RTS。

局限与注意事项

  • 在大量场景集上评估鲁棒性会将每次迭代的计算成本乘以 |S|,这可能是 prohibitive 的。
  • 鲁棒性的质量在很大程度上取决于场景集的质量;糟糕的场景覆盖可能导致虚假的信心。
  • 禁忌列表期限和邻域大小是需要调整的问题特定超参数。
  • 不保证全局最优性或解质量的证明。

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

优势

  • 在无需单独的事后鲁棒性检查的情况下,找到对输入变异性鲁棒的解。
  • 继承了禁忌搜索在困难组合问题(调度、VRP、TSP 变种)上的强大经验表现。
  • 灵活的鲁棒性标准:支持 minimax、期望值、均值-方差和基于百分位数的度量。
  • 不要求问题具有凸性或可微性——适用于黑箱和离散目标函数。
  • 禁忌机制可防止陷入局部鲁棒但全局平庸的解。

应用

  • 在随机旅行时间或客户需求下的鲁棒车辆路径规划
  • 具有不确定处理时间的作业车间和流水车间调度
  • 在需求波动下的网络设计和容量规划
  • 在不确定的供应商提前期或成本下的供应链优化
  • 在干扰不确定性下的电信频率分配
  • 使用组合约束下的不确定资产回报率的投资组合优化

使用方式

使用方式

1

定义组合或连续优化问题,识别不确定参数(例如,需求、成本、处理时间),并指定一个场景集 S 来表示可能的实现——通过从分布中抽样或构建离散不确定性集。设定鲁棒性目标:最小化最坏情况成本、最小化期望成本,或最小化均值和方差的加权组合。

2

在搜索过程中遇到的每个候选解 x,评估其在 S 中每个场景 s 下的目标 f(x, s)。计算鲁棒性度量 R(x)——例如,对于 minimax 鲁棒性,R(x) = max_{s in S} f(x,s);或者对于均值-方差鲁棒性,R(x) = E[f(x,s)] + lambda * Var[f(x,s)]。这取代了经典禁忌搜索中使用的单一标称评估。

3

生成当前解 x 的邻域 N(x),方法是应用所有可行移动(交换、插入、反转等)。评估每个邻居 x' 的 R(x'),排除当前在禁忌列表中的移动,除非满足了允许标准。选择具有最佳鲁棒性值 R(x*) 的邻居 x*。

4

移动到 x*,并将所应用移动的反向操作以禁忌期限 t(通常为 5–20 次迭代)记录在禁忌列表中。禁忌列表可防止循环并鼓励探索。允许标准——例如,如果一个禁忌移动产生了全局最优鲁棒解,则接受该移动——可以覆盖禁忌限制。

5

如果 R(x*) 优于当前最佳值,则更新已知最佳鲁棒解。继续迭代,直到满足停止标准:最大迭代次数、已用时间或在规定步数内无改进。返回找到的最佳鲁棒解及其场景表现概况。

常见陷阱

  • 使用过少的场景会低估真实不确定性,并产生看似鲁棒但在实践中失败的解。
  • 将鲁棒禁忌搜索与随机禁忌搜索混淆:鲁棒优化旨在最小化对最坏情况的暴露,而随机 TS 通过抽样来近似期望值——目标和解释不同。
  • 在最坏情况场景的概率可以忽略不计时应用 minimax 鲁棒性,会导致过度保守的解,成本不必要地增加。
  • 忽略允许标准可能导致搜索错过碰巧涉及禁忌移动的全局鲁棒解。
  • 设置过高的禁忌期限会产生过度限制;过低则会导致循环——两者都会降低解的质量。

常见问题

鲁棒禁忌搜索与随机禁忌搜索有何不同?

随机禁忌搜索通常在搜索过程本身中使用随机抽样(例如,概率接受或随机邻域抽样)来近似期望值。鲁棒禁忌搜索明确优化一个鲁棒性标准——例如最坏情况或均值-方差表现——该标准在定义的で不确定性集上进行评估。鲁棒 TS 的目标是在场景中的解的稳定性,而不仅仅是期望表现。

场景集 S 应该有多大?

没有普遍规则。对于离散不确定性集,如果可行,则枚举所有可信场景。对于连续分布,通常 50-500 个抽样场景可以提供足够的覆盖;诸如拉丁超立方体抽样之类的方差缩减技术可以提高效率。在确定最终场景数量之前,建议对 |S| 进行敏感性分析。

鲁棒禁忌搜索可以处理多目标问题吗?

可以。当与多目标禁忌搜索框架结合时,鲁棒性成为一个额外的目标或约束。可以探索(标称表现、鲁棒性)的帕累托前沿,产生一组在最优性和可靠性之间进行权衡的解——当利益相关者必须在风险容忍和风险规避选项之间进行选择时,这很有用。

我应该选择哪种鲁棒性度量?

当故障是灾难性的,即使是低概率的坏结果也是不可接受的,此时 minimax(最坏情况)是合适的。期望值适合风险中性的决策者。均值-方差平衡了平均表现和变异性,在工程设计中很常见。在金融和物流应用中,当基于百分位数的保证很重要时,会使用在险价值 (VaR) 或条件在险价值 (CVaR) 度量。

鲁棒禁忌搜索是否适用于非常大的实例?

这取决于场景评估的成本。如果每个 f(x,s) 评估成本很低(毫秒),即使对于大型实例,在数百个场景下的鲁棒性也仍然是可行的。如果每次评估都需要模拟或昂贵的求解器调用,则需要进行积极的场景缩减或使用代理模型。跨线程或机器并行评估场景是常见的缓解措施。

相关方法

参考文献

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

    打开 DOI 文献
    已复制。
  2. Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.

    打开出版物文献
    已复制。