arXiv:2601.01832cs.NEcs.AI2026-01

YO通过多链混合策略,高效解决高维复杂优化问题。

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

  • 分两阶段:先用MCMC全局探索,再结合贪心与模拟退火精炼解
  • 在50-200城市的旅行商问题上优于CMA-ES等主流算法
  • 适合评估预算严格、黑箱且多峰的大型优化任务

我们提出Yukthi Opus(YO),一种针对显式评估预算约束下的大规模NP-hard优化问题的多链混合元启发式方法。YO采用结构化双阶段架构,集成马尔可夫链蒙特卡洛(MCMC)用于全局探索、贪心局部搜索用于利用,以及带自适应重加热的模拟退火以可控逃离局部极小。专用预烧阶段分配评估次数进行概率性探索,随后进入混合优化循环精炼优质候选解。YO还引入空间黑名单机制避免重复评估劣质区域,并采用多链执行策略提升鲁棒性、降低对初始化的敏感性。我们在三个基准上评估:5维Rastrigin函数(含消融实验)、50至200个城市的旅行商问题,以及5维Rosenbrock函数,对比了CMA-ES、贝叶斯优化和加速粒子群优化等经典方法。结果表明,MCMC探索与贪心精炼对解质量至关重要,而模拟退火与多链策略主要提升稳定性与方差控制。总体而言,YO在大型多峰问题上表现竞争,同时保持可预测的评估预算,适用于昂贵的黑箱优化场景。

原文摘要 · Abstract (English)

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.

优化算法多链策略黑箱优化元启发式

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。