Yukthi Opus: A Multi-Chain Hybrid Metaheuristic for Large-Scale NP-Hard Optimization

📄 arXiv: 2601.01832v1 📥 PDF

作者: SB Danush Vikraman, Hannah Abagail, Prasanna Kesavraj, Gajanan V Honnavar

分类: cs.NE, cs.AI

发布日期: 2026-01-05

备注: 22 pages, 9 figures, includes extensive ablation studies and benchmark comparisons

💡 一句话要点

提出Yukthi Opus混合元启发式算法，解决大规模NP难优化问题，适用于评估预算受限场景。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 元启发式算法 NP难优化 混合优化 马尔可夫链蒙特卡洛 模拟退火

📋 核心要点

  1. NP难优化问题在评估预算受限的情况下极具挑战，现有方法难以兼顾全局探索和局部利用。
  2. Yukthi Opus (YO) 算法融合MCMC、贪婪搜索和模拟退火，构建多链混合框架，提升优化性能。
  3. 实验表明，YO在Rastrigin、TSP和Rosenbrock函数上表现出色，尤其在稳定性和方差控制方面有显著优势。

📝 摘要（中文）

本文提出了一种名为Yukthi Opus (YO) 的多链混合元启发式算法，专门用于在显式评估预算约束下解决 NP 难优化问题。YO 在结构化的两阶段架构中集成了三种互补机制：用于全局探索的马尔可夫链蒙特卡洛 (MCMC)、用于局部利用的贪婪局部搜索，以及具有自适应重热的模拟退火，以实现对局部最小值的受控逃逸。一个专门的预热阶段将评估分配给概率探索，之后混合优化循环细化有希望的候选者。YO 进一步结合了空间黑名单机制，以避免重复评估不良区域，以及多链执行策略，以提高鲁棒性并降低对初始化的敏感性。我们在三个基准上评估了 YO：具有消融研究的 Rastrigin 函数（5D）、具有 50 到 200 个城市的旅行商问题，以及具有与包括 CMA-ES、贝叶斯优化和加速粒子群优化等已建立的优化器进行比较的 Rosenbrock 函数（5D）。结果表明，MCMC 探索和贪婪细化对于解决方案质量至关重要，而模拟退火和多链执行主要提高稳定性和方差减少。总体而言，YO 在大型和多模态问题上实现了具有竞争力的性能，同时保持了可预测的评估预算，使其适用于昂贵的黑盒优化设置。

🔬 方法详解

问题定义：论文旨在解决大规模NP难优化问题，尤其是在计算资源或评估预算有限的情况下。现有方法通常难以在全局探索和局部精细搜索之间取得平衡，容易陷入局部最优解，且对初始参数敏感。

核心思路：YO算法的核心在于结合多种互补的优化策略，形成一个强大的混合框架。通过MCMC进行全局探索，快速定位有希望的区域；利用贪婪局部搜索进行精细化搜索，提高解的质量；采用模拟退火机制，避免陷入局部最优，并提高算法的鲁棒性。多链执行策略进一步增强了算法的稳定性，降低了对初始化的依赖。

技术框架：YO算法采用两阶段架构。第一阶段是预热（burn-in）阶段，主要利用MCMC进行全局探索，为后续优化提供良好的初始点。第二阶段是混合优化循环，交替执行MCMC探索、贪婪局部搜索和模拟退火。此外，算法还包含一个空间黑名单机制，用于记录已经探索过的较差区域，避免重复搜索，提高效率。

关键创新：YO算法的关键创新在于其多链混合架构，将MCMC、贪婪搜索和模拟退火有机结合。与传统的单一优化算法相比，YO能够更好地平衡全局探索和局部利用，从而在NP难问题上取得更好的性能。空间黑名单机制也是一个重要的创新，能够有效避免无效搜索，提高算法的效率。

关键设计：YO算法的关键设计包括：MCMC的采样策略、贪婪局部搜索的邻域定义、模拟退火的退火策略和重热机制、空间黑名单的更新策略，以及多链执行的链数和并行策略。这些参数的设置需要根据具体问题进行调整，以达到最佳的优化效果。自适应重热策略是模拟退火中的关键，它根据优化过程中的状态动态调整重热的温度，从而更好地控制算法的探索和利用。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，YO算法在Rastrigin函数、旅行商问题和Rosenbrock函数上均取得了具有竞争力的性能。消融研究表明，MCMC探索和贪婪细化对解的质量至关重要，而模拟退火和多链执行主要提高了稳定性和方差控制。与CMA-ES、贝叶斯优化和加速粒子群优化等现有优化器相比，YO在大型和多模态问题上表现出更强的鲁棒性和效率。

🎯 应用场景

该研究成果可应用于各种NP难优化问题，例如：旅行商问题、车辆路径问题、调度问题、资源分配问题等。尤其适用于评估成本高昂的黑盒优化场景，例如：超参数优化、材料设计、药物发现等。该算法能够在有限的预算下，找到高质量的解决方案，具有重要的实际应用价值。

📄 摘要（原文）

We present Yukthi Opus (YO), a multi-chain hybrid metaheuristic designed for NP-hard optimization under explicit evaluation budget constraints. YO integrates three complementary mechanisms in a structured two-phase architecture: Markov Chain Monte Carlo (MCMC) for global exploration, greedy local search for exploitation, and simulated annealing with adaptive reheating to enable controlled escape from local minima. A dedicated burn-in phase allocates evaluations to probabilistic exploration, after which a hybrid optimization loop refines promising candidates. YO further incorporates a spatial blacklist mechanism to avoid repeated evaluation of poor regions and a multi-chain execution strategy to improve robustness and reduce sensitivity to initialization. We evaluate YO on three benchmarks: the Rastrigin function (5D) with ablation studies, the Traveling Salesman Problem with 50 to 200 cities, and the Rosenbrock function (5D) with comparisons against established optimizers including CMA-ES, Bayesian optimization, and accelerated particle swarm optimization. Results show that MCMC exploration and greedy refinement are critical for solution quality, while simulated annealing and multi-chain execution primarily improve stability and variance reduction. Overall, YO achieves competitive performance on large and multimodal problems while maintaining predictable evaluation budgets, making it suitable for expensive black-box optimization settings.