Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization
Luca Maria Del Bono, Federico Ricci-Tersenghi, Francesco Zamponi
组合优化问题对于实际应用和优化方法的开发都是核心。 虽然经典和量子算法已经改进了几十年,但机器学习辅助方法相对较近,并且尚未持续优于简单,最先进的经典方法。 在这里,我们专注于一类二次无约束二进制优化(QUBO)问题,特别是在三维Ising自旋眼镜中找到最小能量配置的挑战。 我们使用Global Annealing Monte Carlo算法,该算法将标准本地移动与通过机器学习提出的全局移动集成。 我们表明,本地移动在实现最佳性能方面起着至关重要的作用。 针对模拟退火和人口退火的基准,我们证明全球退火不仅超越了模拟退火的性能,而且表现出比人口退火更大的稳健性,在问题硬度和系统尺寸方面保持有效性,无需超参数调优。 根据我们的知识,这些结果提供了第一个明确而有力的证据,证明机器学习辅助优化方法可以在组合优化设置中超越经典最先进的技术的能力。
Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning-assisted approaches are comparatively recent and have not yet consistently outperformed simple, state-of-the-art classical methods. Here, we focus on a class of Quadratic Unconstrained Binary Optimization (QUBO) problems, specifically the challenge of finding minimum energy configuration...
