日期：
2023-05-01 21:02:36
来源：集智俱乐部收集 编辑：集智编辑部
关键词：模拟退火法算法，图着色问题，玻璃相变，非平衡统计物理，复杂系统
论文题目：Limits and Performances of Algorithms Based on Simulated Annealing in Solving Sparse Hard Inference Problems 论文链接：https://journals.aps.org/prx/abstract/10.1103/PhysRevX.13.021011 种植着色问题（the planted-coloring problem，图着色算法的一种）是一个典型的推理问题，对此，贝叶斯最优算法的阈值，如置信度传播（belief propagation, BP）可以解析计算。模拟退火法（simulated annealing，SA）是一种基于蒙特卡罗的算法，比置信度传播更加通用和稳健，因此具有更广泛的适用性。 这篇 Physical Review X 文章分析了模拟退火法的局限性和性能。作者表明，模拟退火在恢复种植解方面是次优的，因为它被玻璃态所吸引，而玻璃态并不影响置信度传播算法。与以前的猜想不同，该研究通过比较顺磁相的拐点和动态临界温度，提出了对模拟退火法算法阈值的解析估计。这是热力学相变和 Glauber 动力学的失衡行为之间的一个基本联系。 作者还研究了模拟退火法的改进版本，称为副本模拟退火法（replicated SA, RSA），其中几个弱耦合的副本被一起冷却。副本模拟退火法的算法阈值与贝叶斯最优阈值相吻合。最后，该研究发展了一个近似解析理论，解释了副本模拟退火法的最佳性能，并预测了在非常多副本的极限下，向种植解转变的位置。对副本模拟退火法的研究结果支持这样的观点，即先验参数与生成模型的参数不匹配可能会产生一种最佳的、非常稳健的算法。 图2. 副本模拟退火中，改变复制的数量y，能量密度是温度的函数。 图3. 不同问题大小的种植着色，模拟退火过程中能量密度与温度的函数。 图4. 寻找种植着色信号的退火过程所面临的一般情景的示意图。
推荐阅读