[Paper] TESO Tabu 增强仿真优化用于噪声黑箱问题

Source: arXiv - 2512.24007v1

概述

基于仿真的优化是许多工程和运营问题的主力工具，但噪声评估和昂贵的仿真使得快速找到优良解变得困难。本文提出了 Tabu‑Enhanced Simulation Optimization (TESO)，一种新的元启发式算法，它将自适应搜索与基于记忆的机制（短期禁忌表和长期精英记忆）相结合，即使在目标函数具有随机性的情况下，也能保持搜索的多样性和聚焦性。

关键贡献

• Hybrid metaheuristic 将经典 Tabu Search 思想与随机仿真优化相结合。
• Two‑level memory system：
  • Short‑term Tabu List 防止立即重新访问最近的解，减少循环。
  • Long‑term Elite Memory 存储高质量解并对其进行扰动，以强化搜索。
• Aspiration criterion 允许算法在候选解异常有前景时覆盖 tabu 状态。
• Open‑source implementation（Python）和可复现的基准数据已在 GitHub 上发布。
• Empirical validation 在真实的排队优化案例研究中进行，显示相较于标准 SO 基线的统计显著提升。

方法论

1. 问题设定 – 作者将优化器视为黑箱：每个候选解通过运行随机仿真（例如排队模型）进行评估，返回带噪声的性能估计。
2. 搜索循环 – 从随机解开始，TESO 迭代生成邻域（小幅扰动）。
3. 禁忌表 – 最近的移动记录在固定大小的列表中；任何会重新创建被禁忌标记的解的移动通常会被拒绝，迫使算法探索新区域。
4. 精英记忆 – 将迄今为止表现最好的解保存在单独的档案中。周期性地，算法选择一个精英解，施加更强的扰动，并将结果注入种群，推动搜索向有前景的基盆方向前进。
5. 志愿 – 如果被禁忌阻止的移动产生的解优于任何精英解，则解除禁忌限制，确保不会错过突破。
6. 停止准则 – 当仿真运行次数达到预设预算或改进停滞时，过程结束。

设计刻意保持轻量：只需要生成邻居并评估它们的能力，便于嵌入现有仿真流水线。

结果与发现

• 队列优化基准：TESO 实现了相较于普通随机梯度下降 12‑15 % 的平均队列长度降低，并且比不带精英记忆的标准禁忌搜索提升了 7‑9 %。
• 对噪声的鲁棒性：在多种噪声水平（注入仿真的方差）下，TESO 的性能下降幅度有限，而基线方法则急剧恶化。
• 统计显著性：配对 t‑检验（α = 0.05）确认这些提升不是偶然产生的。
• 消融研究：移除禁忌表或精英记忆任一部分，都会导致解的质量明显下降，凸显了多样化（禁忌）与强化（精英）的互补作用。

实际影响

• 即插即用优化器 – 开发者可以将 TESO 插入任何现有的基于仿真的工作流（例如供应链仿真器、网络流量模型、制造线研究），而无需重写仿真代码。
• 降低仿真预算 – 通过避免冗余评估并聚焦于精英区域，团队可以用更少的昂贵仿真运行实现相当或更好的结果，从而降低云计算成本。
• 更好地处理随机性 – 依赖 Monte‑Carlo 或离散事件仿真的行业（金融、物流、电信）可以受益于 TESO 内置的噪声鲁棒性，提供更可靠的决策支持。
• 开源基础 – 提供的 Python 包包含邻域生成、内存管理和日志记录工具，便于扩展（例如自定义邻域算子或并行评估）。

限制与未来工作

• 对高维空间的可扩展性 – 当前的邻域算子较为简单；在拥有数百个决策变量的问题上的性能尚未经过测试。
• 参数敏感性 – 禁忌表大小、精英档案容量以及扰动强度在案例研究中是手动调优的；自动化的自调机制可能提升开箱即用的鲁棒性。
• 并行性 – 实现目前顺序运行仿真；未来版本可以利用并行仿真来加速评估瓶颈。
• 更广泛的基准套件 – 在更大范围的噪声黑箱问题上进行验证（例如机器学习模型的超参数调优）将加强对通用性的论断。

总体而言，TESO 提供了一种实用的、增强记忆的噪声仿真优化方法，开发者可以轻松采用，以在昂贵的随机模型中挤出更多性能。

作者

• Bulent Soykan
• Sean Mondesire
• Ghaith Rabadi

论文信息

• arXiv ID: 2512.24007v1
• Categories: cs.NE, cs.AI
• 出版日期: December 30, 2025
• PDF: 下载 PDF