模拟退火与熵函数拐点

报告题目:模拟退火与熵函数拐点

报告人:周海军研究员  中国科学院理论物理研究所

报告时间:2018-11-26(周一) 下午1400

报告地点:物理科技楼409

报告邀请人:施夏清

报告摘要:模拟退火算法是一种广泛用于求解优化问题的经验算法,其核心思想是通过逐步降低模拟温度使系统往最低能量构型演化。我将通过一个模型系统演示模拟退火算法可能永远无法接近基态的可能性。在网络科学和计算机科学中,常常需要对给定网络构造一个尽可能稠密又尽可能小的子网络。最小防御同盟问题就是这样一种组合优化问题。一个防御同盟包含网络的一部分节点,属于该集合的每一个节点都至少有一半的最近邻节点也同时属于该集合。我们发现构造一个接近最小的防御同盟是特别困难的,用模拟退火的方法求解得到的防御同盟比最小防御同盟要大许多。我们通过自旋玻璃理论和计算机模拟发现出现这一计算复杂性的原因是防御同盟的解空间有两个分支,即高能量分支和低能量分支,二者之间存在一个非连续平衡相变,低能量分支的熵是能量的凹 (convex) 函数。我们发展了一种消息传递算法,通过把能量钳制在接近于基态的目标值,成功实现了在低能量分支搜寻接近最小的防御同盟。这项工作的方法和结论可能也可推广到其它与稠密子网络有关的网络结构问题。

报告人简介:1995年毕业于南开大学物理系,2000年于中国科学院理论物理研究所获得理学博士学位。2000年至2005年在德国Max-Planck胶体与界面研究所从事博士后研究,并获德国洪堡基金会资助。2005年起全职在中国科学院理论物理研究所工作,目前为研究员职称。一直在统计物理与复杂系统方向开展理论研究:研究生阶段以单分子生物聚合物结构相变理论为主,博士后阶段关注复杂网络社区结构挖掘和组合优化问题,成立科研团队后则主要研究自旋玻璃平均场理论及其在组合优化问题上的交叉学科应用,近年来进一步将研究拓展到博弈论、统计推断、神经网络和机器学习等问题。共发表八十余篇学术论文和自旋玻璃专著一部。2010 年获中国青年科技奖、2012 年获国家杰出青年基金资助、2015年入选国家百千万工程、2017年担任中国科学院理论物理前沿重点实验室常务副主任。目前担任《中国科学:物理、天文和力学》、《理论物理通讯》及统计物理领域几份国际知名期刊的编委。

返回原图
/