導語

組合優化問題（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）變分近似：平均場分布逼近玻爾茲曼分布

對于組合優化問題，其目標函數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.