导语ag百家乐苹果app
组合优化问题（COPs）在科学和工业领域无处不在，从物流调度到芯片设想，从酬酢辘集分析到东谈主工智能算法，其高效求解一直是推敲热门。但是，传统步调往往受限于问题的复杂性和规画资源。近日，中国科学院表面物理推敲所的张潘推敲员过火博士生沈子松，新加坡科技设想大学助理素养潘峰、国科大杭州高等推敲院博士生门一丁、硕士生徐闻彪与配合者们在《Nature Computational Science》发表了一项冲破性推敲，该推敲将统计物理学中的目田能最小化步调旨趣、平均场表面、模拟退火想想与机器学习中的自动微分与梯度优化本领相结合，提议了一种名为“目田能机器”（Free-Energy Machine, FEM）的新步调，FEM辅助在GPU/FPGA等大领域并行规画拓荒运行，通过目田能最小化、自动微分和梯度下跌三个枢纽，已毕了组合优化问题的调治高效求解。实验放荡标明，FEM在最大割问题、均衡最小割问题和最大K-SAT问题等多个问题上推崇优异，在速率和性能上越过了多个针对单一问题定制的起初进算法，同期放荡也展示了其在处理组合优化领域的多值状况和多体互相作用问题上的优越性能。该推敲充领悟释，统计物理学与机器学习的跨学科交融，为开发具有粗鲁科学影响和工业应用远景的顶端步调论开启了新的可能。
要害词：组合优化、统计物理、机器学习、高性能规画
曾利丨作家
蒲天乐丨译者
论文题目：Free-energy machine for combinatorial optimization 论文贯穿：https://www.nature.com/articles/s43588-025-00782-0 代码贯穿：https://github.com/Fanerst/FEM
一、组合优化：数字期间的“高精尖”难题
组合优化问题（COPs）普遍存在于统计物理、运筹学和东谈主工智能等多个领域，也被公以为数字期间的“高精尖”难题。由于大多数COPs属于NP-hard问题，带来了盛大的规画挑战。除非NP=P的假定修复，不然精准算法难以提供高效管理决策。因此，模拟退火和多样局部搜索算法等经典类似算法在本质中被粗鲁接纳。值得能干的是，这些算法主要基于串行规画，专为CPU设想。固然某些具有特殊结构的问题不错高效求解，但大多数骨子难题仍难以用标准器具管理。
比年来，跟着GPU和FPGA等大领域并行规画智商的权贵栽培，东谈主们对创新步调的期待日新月异，已有很多新步调被开发出来。举例模拟相关伊辛机、噪声平均场退火和模拟分岔机等算法，这些算法最初受启发于对伊辛机硬件拓荒的平均场能源学模拟，其性能致使越过了硬件原型。除了高精度上风外，这些算法的权贵特质是能同步更新变量，从而有用专揽GPU和FPGA加快大领域问题求解。
但是这些算法主要局限于二次无管制二值优化（QUBO）问题或伊辛模子。当处理具有非二次（如布尔k可愉快性问题的高阶p自旋玻璃模子）或非二值特征（如Potts玻璃、着色问题和社区检测）的COPs时，这一局限性尤为昭彰。将这些复杂问题结构适配到伊辛模子需要额外的转机枢纽和可不雅的支出，使得优化问题愈加复杂深奥。那么能否开发一种既保抓物理模子的高效性，又能径直处理复杂管制的通用框架？
二、物理启发的创新：
目田能机器FEM的设想玄学
张潘憨厚团队所提议的Free-Energy Machine从统计物理角度登程，旨在愉快组合优化问题求解在通用性、性能和速率方面的需求。该步调区别于现存本领的要害在于，无需依赖伊辛模子即可求解通用COPs。图1展示了该算法的翔实经由图。
图1. FEM管理组合优化问题（COPs）的旨趣与框架。a图展示FEM不错管理的四种不同类型的COPs问题，即伊辛模子, 波茨模子,p-自旋玻璃模子和通用模子;b图展示，在通用COPs中，每个自旋变量σᵢ可处于q种不同状况（标志为1, 2, ..., q），其状况概率由边际概率Pᵢ(σᵢ)透露。彩色条形图直不雅展示各状况概率散布;c图：通过变分目田能最小化迫临基态解的过程；d图为FEM的中枢规画框架，包括了局部场参数化、概率转机、梯度规画和并行优化四个枢纽；e图展示了在退火过程中能量与熵的演化情况；f图展示了边际概率{Pᵢ(σᵢ)}在退火过程中呈现出的三阶段的演化特征：①高温阶段（β较小），熵主导，概率均匀散布，②临界阶段（β≈βc）时，能量开动主导，概率散布分化, ③ 低温阶段（β→∞）：敛迹至基态概率散布;g图展示了赢得最终问题解的格式，即从悉数批量平均场散布中推断解，从中采用能量最低的成就动作最终解。
（一）表面基础：从物理系统到优化问题
图2：组合优化和自旋玻璃问题中复杂的能量景不雅透露图。奈何跨过由能量壁垒所阻隔的能量极小点找到全局能量最低的解，是一个困难的问题。图片来源：Joshua Sortino,Unsplash
从统计物理视角看，组合优化问题在统计物理中被称为自旋玻璃的基态能量问题，变量赋值映射为自旋构型，求解主见函数最小的变量赋值即为求解系统零温下的玻尔兹曼散布。而求解自旋玻璃基态问题的困难之处在于系统的能量景不雅极度复杂，存在多样由能量壁垒所阻隔的能量极小值。在自旋玻璃表面中，这一征象用副本对称破缺（RSB）表面姿色，该表面通过平均场解的不动点来描绘能量景不雅的险阻特征。
受RSB表面启发，该推敲提议了一种基于变分目田能最小化的通用步调。目田能是批处理（即稳固副本）变分平均场散布的函数，通过机器学习中的梯度优化器进行最小化。该步调具有两大特征：
（1）目田能梯度可通过机器学习中的自动微分规画，使其具有通用性并能径直应用于各种COPs；
（2）变分目田能接纳深度学习社区开发的进修优化本领（如Adam）进行最小化。
值得能干的是，悉数批处理中的平均场概率都并行更新，从而充分专揽GPU的规画智商已毕高效践诺，大幅加快大领域问题的求解。
（二）步调创新：四步冲破
（1）变分类似：平均场散布迫临玻尔兹曼散布
对于组合优化问题，ag百家乐网址其主见函数E(σ)可映射为物理系统的能量模子，其零温玻尔兹曼散布：
则对应着的基态对应最优解。而规画上述公式属于#P难问题，在统计物理中，变分平均场步调通过假定系统各目田度互相稳固来简化复杂概率散布的姿色，即用可领悟的乘积散布，因此FEM接纳如下所示的平均场变分散布来迫临原始的玻尔兹曼散布：
其中Pᵢ(σᵢ)为第i个自旋的边际概率，通过优化上述两个散布之间的KL距离来已毕对问题的求解，而这一主见函数等价于优化以下变分目田能函数：
其中内能公式为：
熵的公式为：
按照上述公式，不错将推导出各个组合优化问题（COPs）对应的目田能函数，从而不错对皆进行可微分求解，该推敲职责中推导了以三类典型问题的目田能公式，辞别是：
①最大割问题（对应图1中的Ising问题）：
②均衡最小割问题（bMinCut问题，对应图1中的多值问题）：
③ 最大可愉快性问题（MaxSAT问题，对应图1中的多体交互问题）：
（2）目田能优化：能量-熵均衡的泛函最小化
通过将边际概率Pᵢ(σᵢ)参数化为局部场的hᵢ(σᵢ)softmax函数:
最终上述目田能最小化问题不错转机对目田能对于hᵢ(σᵢ)的泛函最小化问题，其梯度的神情如下所示：
（3）自动微分：基于梯度的反向传播
基于上述问题转机后不错径直通过PyTorch/TensorFlow自动微分本领对各个问题通过反向传播算法进行求解，同期该推敲还手工推导了各个问题的梯度的具体神情。
（4）退温战术：温度调制的渐进优化
由于温度对于目田能的规画影响较大，该推敲接纳常见的两种退温战术进行覆按：
①指数退温格式
②逆线性退温战术
除了上述手段，该推敲还充分辩论问题自身的性情，基于副本步调对悉数批处理中的平均场概率都并行更新，从而充分专揽GPU的规画智商已毕高效践诺，大幅加快大领域问题的求解。
三、性能考证：全面越过现存本领
为了考证FEM算法的恶果，该职责要点辩论了三类组合优化问题：
在最大割问题（MaxCut）测试中，FEM在2000节点全勾通图K_{2000}上仅用1000次退火枢纽即达到已知最优解（33,337），并在G-set基准测试的54个实例中，有33个实例的求解速率越过现时最优算法dSBM：
图3：FEM算法在MaxCut问题上的推崇
针对均衡最小割问题（bMinCut），FEM在Chris Walshaw归档的真正世界图（如add20、3elt）上全面优于METIS，尤其在32分组时权贵越过竞赛优厚算法KaFFPaE：
表1：FEM算法在bMinCut问题上的推崇
在百万节点马上图在bMinCut问题上的测试中，FEM的归一化割值比METIS低22-26%（图4）：
图4：FEM算法在百万领域马上图的bMinCut问题上的推崇
同期该推敲还在FPGA芯片考证任务进行了实验，放荡标明FEM算法不错已毕22.5-26.6%的通讯量优化（图5）。
图5：FEM算法在FPGA芯片考证任务上的推崇
对于高阶交互的最大可愉快性问题（Max k-SAT），FEM在MaxSAT 2016竞赛的454个实例中，对标了SsMonteCarlo, Ramp, borealis, SC2016, CCLS, CnC-LS, Swcca-ms, HS-Greedy和CCEHC等多个求解器，其中FEM在448个问题上找到最优解，其余6个仅差1个子句，全面最初Max-CTDS算法（图6a），且GPU加快权贵栽培求解效率（图6b）。
图6：FEM算法在MaxSAT问题上的推崇和时期对比
四、学科交融的范式冲破：
从物理表面到智能规画的跳动
该职责提议了目田能机器（FEM）这一通用框架用于求解组合优化问题。多量基准测试解释了该步调的优越性，突显了统计物理与机器学习交融的盛大后劲。这一创新步调在科学与工业领域具有粗鲁应用远景。但是，作家以为现时列法仍存在以下更正空间：来源，参数调优依赖东谈主工且受限于现存优化器性能，异日需开发自动化超参数调遣机制；其次，固然FEM在马上图上的均衡最小割问题已权贵优于METIS，但肤浅的平均场假定在副本对称破缺（RSB）场景下可能堕入局部最优，需引入更复杂的散布透露，如基于音信传递的微正则系综步调可能更具表面上风。针对十足RSB问题，现存框架的效力可能受限，但通过更正退火战术和优化器设想有望栽培性能。异日咱们将探索将更高等的表面（如Thouless-Anderson-Palmer方程、置信传播等）融入FEM框架。这项推敲最真切的启示在于：19世纪提议的目田能意见通过学科交叉在当代规画领域粗犷重生，这既印证了基础科学的弥远价值，也揭示了学科鸿沟交融催生创新的轨则，更标明物理建模想想已经鼓动规画变革的老成携带。
参考文件
[1] Shen, ZS., Pan, F., Wang, Y. et al. Free-energy machine for combinatorial optimization. Nat Comput Sci (2025). https://doi.org/10.1038/s43588-025-00782-0
[2] 中国科学院表面物理推敲所.Free Energy Machine: 结合统计物理与机器学习的组合优化新步调[EB/OL].https://itp.cas.cn/kxyj/kydt/202503/t20250328_7571836.html, 2025–03–28/2025–04–03.
[3]Huang, Haiping. Statistical mechanics of neural networks. Vol. 310. Singapore: Springer, 2021.
作家
审校
非均衡统计物理念书会启动！
2024年诺贝尔物理学奖授予东谈主工神经辘集，这是一场统计物理激励的机器学习改革。统计物理学不仅能解释热学征象，还能匡助咱们和会从微不雅粒子到宏不雅全国的各个层级奈何关系起来，复杂征象奈何流露。它通过推敲多量粒子的集体行径，告成地将微不雅世界的马上性与宏不雅世界着实定性关系起来，为咱们和会当然界提供了遒劲的器具，也为机器学习和东谈主工智能领域的发展提供了老成推能源。
为了深入探索统计物理前沿进展，集智俱乐部筹划西湖大学理学院及交叉科学中心讲席素养汤雷翰、纽约州立大学石溪分校化学和物理学系素养汪劲、德累斯顿系统生物学中心博士后推敲员梁师翎、香港浸会大学物理系助理素养唐乾元，以及多位国表里闻明学者共同发起。念书会旨在探讨统计物理学的最新表面冲破，统计物理在复杂系统和生命科学中的应用，以及与机器学习等前沿领域的交叉推敲。念书会从12月12日开动，每周四晚20:00-22:00进行，抓续时期瞻望12周。咱们诚挚邀请列位一又友参与臆测打算调换，一谈探索爱因斯坦眼中的普适表面！
笃定请见：
1.
2.
3.
4.
5.
6.
