科研动态

科学研究

科研动态

熵函数拐点与模拟退火瓶颈的研究进展

文章来源: 发布时间: 2018-11-23 【字体:      

  模拟退火是一种被广泛使用的求解复杂优化问题的经验算法,它的核心思想是在动力学模拟过程中逐步降低系统温度,期待系统微观状态能有很大机会逃离能量图景中的亚稳区域,最终在温度足够低时趋向于最低能量构型。模拟退火算法背后隐含了一个基本假设,那就是系统的熵(定义为给定能量面上微观构型数目的对数)是能量的凹函数,在图像上表现为熵函数的切线随能量的降低变得越来越陡峭(见示意图中的曲线 A)。近日,中国科学院理论物理研究所周海军研究员与合作者在该研究方向上取得重要进展,指出熵函数不一定总是凹函数,而是可能在包括基态构型在内的低能量区域是凸函数而在高能量区域为凹函数,两个区域的接合点就是熵函数的拐点(见示意图中的曲线 B)。研究结果已发表于《物理评论快报》:Physical Review Letters 121, 210602 (2018)。

 
 

 

    

  

  熵函数低能区域的凸性带来的物理效果就是该区域的微观构型在平衡统计物理的正则系综是不可见的导致它们不可能通过逐步降低温度的模拟退火算法来采样。这就给求解最低能量构型带来极大的困难。周海军研究员和合作者提出一种称为 “能量钳子” 的算法思想,通过事先将目标能量固定在某个很低的值,然后采用消息传递迭代的方法调节系统温度和微观构型,以实现在接近基态能量面的微观构型采样。他们在一个代表性组合优化问题,网络最小防御同盟上测试了该算法,发现其效果远远超过模拟退火,能够获得接近基态的微观构型。这项工作对于理解自旋玻璃系统的低能性质和计算复杂性有重要意义,提出的算法思想也可以用于其它存在熵函数拐点的组合优化问题。 

  参与该合作研究工作的研究人员包括中国科学院理论物理研究所博士研究生许亿志、香港教育大学杨志豪(Chi Ho Yeung)博士、周海军研究员、英国Aston大学 David Saad教授。该研究得到国家自然科学基金委和中国科学院前沿科学与教育局的项目资助。该研究的计算机模拟工作主要在中国科学院理论物理研究所的HPC计算集群上完成。 

  原文链接:https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.121.210602. 

附件下载: