[Paper] Yukthi Opus：一种用于大规模 NP 难优化的多链混合元启发式

发布: 2周前 (2026年1月5日 GMT+8 14:51)

8 min read

原文: arXiv

Source: arXiv - 2601.01832v1

概述

本文介绍了 Yukthi Opus (YO)，这是一种新的混合元启发式算法，能够在严格的评估预算限制下处理大规模 NP 难优化问题。YO 通过在多个并行搜索链中融合概率探索、贪婪细化和自适应模拟退火，能够为诸如旅行商问题（TSP）和多模态基准函数等极具挑战性的任务提供高质量的解。

两阶段混合架构，将 burn‑in MCMC 探索阶段与结合贪婪局部搜索和模拟退火的 refinement 循环清晰分离。
多链执行，以降低对初始种子的敏感性并提升跨运行的鲁棒性。
空间黑名单，记录并避免重新评估已知表现不佳的区域，节省有限的评估预算。
自适应再加热调度 用于模拟退火，使得在不大幅增加预算的情况下实现受控地逃离局部最小值。
全面的实证评估，在 Rastrigin（5‑D）、Rosenbrock（5‑D）以及城市数量在 50 到 200 之间的 TSP 实例上进行，并通过消融研究孤立出每个组件的影响。
竞争性的性能，相较于 CMA‑ES、贝叶斯优化和加速粒子群优化等最先进的优化器表现出竞争力，尤其在多模态和大规模问题上。

Burn‑in Phase (MCMC Exploration)
- 一组并行的马尔可夫链从提议分布中抽取候选解。
- 接受遵循经典的 Metropolis‑Hastings 规则，确保在预分配的评估预算内对搜索空间进行多样化覆盖。
Hybrid Optimization Loop
- Greedy Local Search: 对每个有前景的候选解进行局部细化，迭代应用问题特定的移动算子（例如 TSP 的 2‑opt 交换），直至找不到立即的改进。
- Simulated Annealing with Adaptive Reheating: 在局部细化之后，温度调度控制偶尔的上坡移动。当算法停滞时，依据简单的启发式（例如最近的接受率）对温度进行“再加热”，使搜索能够跳出浅层局部最优。
Spatial Blacklist
- 算法维护一个空间索引（如超立方体），记录产生低质量解的区域。落入黑名单区域的后续提议将直接被拒绝，从而节省评估次数。
Multi‑Chain Coordination
- 多条独立链并行运行，定期共享各自的最佳解。这种交叉授粉降低了所有链收敛到同一子最优区域的可能性。

整个流程具备预算感知：MCMC 步数、局部搜索迭代次数以及退火移动次数均在事前计算，以保证昂贵的目标函数评估总次数永远不超过用户指定的上限。

Source: …

基准	预算（评估次数）	最佳发现目标 (YO)	最佳竞争者	相对提升
Rastrigin（5‑D）	10 k	0.0012	CMA‑ES (0.0035)	≈ 65 % 改进
Rosenbrock（5‑D）	12 k	1.04	Bayesian Opt. (1.27)	≈ 18 % 改进
TSP‑50	15 k	5 842	PSO‑Accel (5 910)	≈ 1.2 % 改进
TSP‑200	30 k	23 467	CMA‑ES (23 689)	≈ 0.9 % 改进

总体而言，YO 的表现匹配或超越了已发表的最佳结果，同时保证总的昂贵函数评估次数不超过设定预算。

Black‑Box Optimization Services: 黑盒优化服务： 提供昂贵仿真 API（例如 CFD、金融风险模型）的公司可以采用 YO，在固定查询预算下挤出更多性能，从而降低云成本。
Automated Hyper‑Parameter Tuning: 自动超参数调优： YO 的预算感知特性使其在训练运行成本极高或需要严格评估上限时，可直接替代贝叶斯优化。
Routing & Logistics Software: 路由与物流软件： 对于需要即时近最优 TSP 解的路径规划引擎（如配送无人机），YO 的多链并行可以映射到多核或分布式环境，在严格的延迟约束下提供高质量路线。
Embedded / Edge Devices: 嵌入式/边缘设备： 由于 YO 的评估预算是预先确定的，开发者可以在边缘硬件（如机器人）上分配固定的计算预算，仍然获得可靠且高质量的解，不会出现运行时意外。

算法的模块化设计（MCMC、贪婪、退火）还允许实践者替换为特定领域的移动算子或自定义提议分布，从而将 YO 定制到各种组合和连续问题。

可扩展性到极高维度: 实验仅在 5‑D 连续空间中进行；在数百维度下的性能仍未测试。
黑名单开销: 对于极大的搜索空间，维护空间黑名单可能会占用大量内存，进而抵消部分预算节省。
参数敏感性: 虽然多链方法可以减轻初始化偏差，但 MCMC 提议方差和再加热阈值的选择仍需适度调优。
未来方向: 作者建议将 YO 与代理模型（例如高斯过程）结合，以进一步减少昂贵的评估；探索自适应链数策略；以及在真实工业数据集（如供应链优化）上进行基准测试。