Skip to content
返回搜索结果

随机禁忌搜索 — 带有记忆的随机元启发式算法

提出者
Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
年份
1990s
类型
Stochastic metaheuristic optimizer
类别
Simulation / optimization

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

字号

它有什么作用?

随机禁忌搜索(Stochastic Tabu Search, STS)是经典禁忌搜索(Tabu Search, TS)的扩展,它在邻域探索和移动选择阶段引入了随机性。通过将禁止近期访问解的禁忌记忆与概率接受或随机候选采样相结合,STS能更有效地跳出局部最优解,并探索确定性TS可能难以穿越的崎岖解空间。

方法背后的直觉

经典的禁忌搜索通过总是移动到允许的最佳邻居来导航解空间,并使用短期记忆(禁忌列表)来防止循环。然而,在实践中,最佳允许移动仍可能将算法困在某个区域。随机禁忌搜索注入了受控的随机性:下一个移动不是贪婪地选择,而是从一组候选邻居中概率性地选择,并偶尔引入随机扰动来使搜索多样化。这保留了TS的记忆引导原则,同时增加了纯粹确定性下降法所缺乏的探索能力。

历史学

禁忌搜索由Fred Glover于1986年正式提出,并在1989-1990年的里程碑式论文中得到阐述。随着研究人员认识到大规模问题中确定性邻域评估是一个瓶颈,随机扩展在20世纪90年代出现。随机候选采样、概率移动接受和噪声注入被整合进来以改善多样化,从而产生了广义上的随机禁忌搜索。该技术广泛应用于运筹学、工程设计和机器学习超参数优化。

何时使用

在解决具有崎岖、多模态特征空间的组合优化或连续黑盒优化问题时使用随机禁忌搜索,这些问题中的确定性局部搜索会持续陷入困境(例如,调度、路由、特征选择)。当完全评估邻域在计算上成本高昂,使得随机子采样成为必要时,它尤其有价值。请勿在问题是凸的或单峰时使用STS — 基于梯度或精确方法更快且最优。如果您需要全局最优性的保证,请避免使用它,因为STS除了启发式找到的最佳解外,不提供收敛保证。当目标函数易于完全评估且可以使用穷举邻域搜索的确定性TS时,也请避免使用。

局限与注意事项

  • 没有找到全局最优解的理论保证;解的质量在很大程度上取决于参数设置。
  • 禁忌期限和候选列表大小需要针对具体问题进行调整;选择不当会导致过早收敛或进展缓慢。
  • 随机运行在没有固定随机种子的情况下是不可复现的,这给基准测试和审计带来了困难。
  • 内存开销随禁忌列表大小而增长;对于大型解空间,需要基于属性的禁忌表示。

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

优势

  • 通过结合记忆和概率探索,比确定性禁忌搜索更有效地跳出局部最优解。
  • 通过对候选进行子采样,减少每次迭代的计算成本,从而扩展到大型邻域结构。
  • 禁忌记忆可防止循环,这是纯随机方法(如随机重启爬山法)常见的失败模式。
  • 灵活的框架:扰动概率和禁忌期限可以调整,以平衡强化和多样化。
  • 适用于组合问题(TSP、调度)和连续优化(稍作调整)。

应用

  • 不确定需求下的车辆路径和物流优化
  • 具有随机处理时间的作业车间和开放车间调度
  • 高维机器学习数据集中的特征选择
  • 网络设计和拓扑优化
  • 具有组合资产选择约束的投资组合优化
  • 复杂模拟模型超参数调优

使用方式

使用方式

1

生成一个初始解 x0(随机或启发式)。将禁忌列表 T 设置为空,定义禁忌期限 tau,迭代次数上限 I_max,以及随机参数(例如,候选列表大小 k,扰动概率 p_perturb)。

2

在每次迭代中,随机采样完整邻域 N(x_current) 的一个子集 N_s,而不是评估所有邻居。这降低了每次迭代的成本,并引入了对空间哪些区域进行探索的随机性。

3

从 N_s 中选择下一个解 x_next:(a) 以 1-p_perturb 的概率选择最佳的非禁忌候选,或 (b) 以 p_perturb 的概率选择一个随机的非禁忌候选以实现多样化。如果 x_next 改进了已知最佳解,则可能使用渴望准则(aspiration criteria)覆盖禁忌状态。

4

将 x_current(或移动属性)添加到禁忌列表 T。如果 |T| > tau,则移除最旧的条目。如果 f(x_next) < f(x_best),则更新当前最佳解 x_best。

5

重复 neighborhood_sampling 直到 tabu_update,直到达到 I_max 次迭代、满足目标目标值或在耐心窗口内没有发生改进。返回 x_best 作为最终解。

常见陷阱

  • 将禁忌期限设置得太短会导致尽管有禁忌列表但仍发生循环;设置得太长则不必要地阻碍了有希望的区域。
  • 使用太小的候选列表(激进的子采样)可能导致搜索持续错过好的邻居。
  • 忽略渴望准则会导致算法拒绝全局改进的移动,而这些移动恰好是禁忌的。
  • 仅报告单次运行而不进行多次重启或种子会误导性地反映典型解的质量。
  • 将随机禁忌搜索与模拟退火混淆:两者都是随机的,但根本不同 — STS使用显式记忆,而SA使用基于温度的概率接受,没有记忆。

常见问题

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

两者都是随机元启发式算法,但STS使用显式的禁忌记忆来禁止最近访问的移动,从而防止循环。SA没有记忆 — 它以随时间(温度表)降低的概率接受较差的解。STS通常在组合问题上更强大,因为在这些问题中重新访问移动是一个明显的危险。

我应该运行多少次迭代(I_max)?

没有普遍规则。一种常见做法是进行多次独立试验(例如,10-30次重启),预算与问题规模成比例,然后报告最佳和平均结果。对于基准测试,请匹配竞争方法使用的总函数评估预算。

随机禁忌搜索可以处理连续变量吗?

可以,但需要定义连续邻域(例如,当前解周围的高斯扰动)和禁忌列表的合适属性(例如,区域或方向)。大多数STS文献针对组合问题;对于连续空间,差分进化或CMA-ES通常是更自然的替代方案。

渴望准则的作用是什么?

如果接受一个移动能产生比迄今为止找到的最佳解更好的解,渴望准则就会覆盖该移动的禁忌状态。没有渴望准则,算法可能会永久拒绝恰好是禁忌的全局改进移动,严重限制了解的质量。

我应该固定随机种子以保证可复现性吗?

是的,在报告研究结果时固定种子以确保可复现性。在实践中,使用多个种子运行并报告统计数据(平均值、最佳值、标准差),以提供算法在随机空间中性能的可靠图景。

相关方法

参考文献

  1. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.

    打开 DOI 文献
    已复制。
  2. Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.

    打开 DOI 文献
    已复制。