组合优化问题广泛存在于科学研究与工程实践中，从图划分、逻辑推理，到芯片布图、任务调度，几乎所有涉及离散决策的问题，都可以归结为某种形式的组合优化。然而，由于这类问题通常属于 NP-hard 类型，随着规模的扩大，传统算法在效率和可拓展性上面临巨大挑战。如何在保持问题通用性的同时，又实现高效、可扩展的求解，一直是组合优化领域中的核心难题。
2024 年，Zi-Song Shen 等人提出了一种新的求解框架：Free-Energy Machine（简称FEM）。这一方法借助统计物理中的自由能最小化原理，结合机器学习中的自动微分与梯度优化技术，构建出一个统一、高效、可并行的组合优化求解器。在多项基准测试中，这一方法表现出了优异的精度和速度，并展现出极强的通用性和可扩展性。
全文共计：1911字
预计阅读：6分钟
01 · 理论基础与方法构建
FEM 的核心思想来源于统计物理。作者将组合优化问题抽象为一个“能量函数” E(σ)，其中 σ 表示所有待求的离散变量配置。在物理中，寻找系统的最低能量状态对应于在零温度下寻找其最稳定的结构，对应到优化问题中即为寻找最优解。
由于直接搜索最低能量配置非常困难，FEM 引入了变分自由能函数作为近似手段。它通过一个可调参数 β（即温度的倒数）对能量和熵进行加权，形成以下自由能表达：
其中 PMF (σ) 是通过变分方法构造的近似概率分布，采用的是变量之间相互独立的均值场（mean-field）形式。这一分布使用 softmax 函数进行参数化，所有变量的概率项都可以通过可微函数表示，使得整个优化过程可以通过自动微分工具求解。
在优化过程中，FEM 模拟了一个从高温（随机性大）逐步冷却到低温（趋向最优解）的“退火”过程，类似于模拟退火算法，但更加系统化地结合了统计物理理论和机器学习框架。
02 · 算法特点与技术优势
FEM 在设计上融合了多个优势：
通用性强
传统的许多近似优化方法，如 Ising 机器或 QUBO 求解器，只适用于特定形式的问题（如二值变量、二次能量函数）。而 FEM 不依赖于特定建模结构，可以原生支持多值变量、高阶交互项乃至约束项，具备极强的建模能力。
高并行性
所有优化操作均基于矩阵乘法、softmax 函数和向量化计算，非常适合 GPU 或 FPGA 等现代并行硬件平台，尤其适合大规模问题求解。
优化器成熟
FEM 使用了深度学习中广泛应用的优化器（如 Adam），支持自适应学习率和梯度一阶、二阶估计，在优化效率和稳定性上表现出色。
副本机制增强探索能力
受 replica symmetry breaking 理论启发，FEM 同时维持多个优化副本，共同探索解空间，从而有效避免陷入局部最优。
FIG. 1. The framework of implementing Free-Energy Machine.
03 · 应用验证与性能表现
作者在三类典型的组合优化问题中对 FEM 进行了深入测试：
1 · 最大割问题（Max-Cut）
FEM 在大规模图（如 K2000）上找到了已知最优解，并在 G-set 数据集中对比当前最强方法dSBM，显示出更优的时间效率与解质量。
FIG. 2. Benchmarking results for the maximum cut problem. 图 (a) 展示了 FEM 在 K2000 图上的解质量分布，图 (c) 展示了不同图类型上的时间效率对比。
2
多路平衡最小割（q-way balanced Min-Cut）
该问题引入了多值变量和全局平衡约束，对建模能力提出挑战。FEM 不仅可以灵活建模，还在多个真实图数据上超越了 METIS 和 KaFFPaE 等工业级划分器，尤其在高分组数场景下优势明显。在一个包含近 150 万节点的大型芯片验证问题中，FEM 的边界通信开销比 METIS 减少了 22%~26%。
3 · 最大 k-SAT 问题（Max k-SAT）：
该类问题涉及高阶逻辑关系。FEM 在 MaxSAT 2016 的 454 个测试实例中，448 个达到最优解，其余也仅差一条逻辑。平均求解时间为 0.074 秒，远快于传统 CPU 上的启发式方法（如 Max-CTDS）。
FIG. 3. Benchmarking results on the MaxSAT 2016 competition problems. 图 (a) 展示了解的最优性对比，图 (b) 展示了计算时间优势。
这些实验结果充分说明，FEM 在不同类型、不同结构、不同规模的组合优化问题中都具备强大的通用性和领先的求解能力。
04 · 潜在应用与未来方向
FEM 的建模通用性和执行效率，使其适用于一系列实际问题，包括：
-
图划分与负载均衡（例如芯片布局、并行计算资源分配）
-
社交网络与图神经网络中的社区发现
-
复杂逻辑推理与约束求解（SAT、规划问题等）
-
多任务调度与路径规划（如 UAV 任务、制造调度）
此外，FEM 的结构还可进一步扩展。例如，作者指出可以引入更精细的物理模型（如 TAP 自由能、Bethe 自由能）来增强模型表达能力；或者结合神经网络结构提升变分分布的表示能力。这些方向都为 FEM 的理论深化和实际落地提供了丰富的空间。
不过值得说明的是，FEM理论上通用，但是目前它默认处理的是无约束优化，在工程领域使用效果还有待商榷。
总结
Free Energy Machine（FEM）提供了一种面向组合优化的通用求解框架，既具备理论上的完整性，又具备工程上的可行性。它将统计物理中的自由能最小化思想，与机器学习中的梯度优化技术有机结合，打破了传统优化算法在结构限制和规模扩展上的瓶颈。
对于运筹优化研究者以及处理大规模离散决策问题的从业人员来说，FEM 不仅是一个值得关注的新工具，也可能成为今后组合优化的一种主流方向。
项目代码开源可得，读者可访问如下链接了解更多内容：
https://github.com/Fanerst/FEM
参考文献：
[1] Z.-S. Shen et al., “Free-Energy Machine for Combinatorial Optimization,” Dec. 12, 2024, arXiv: arXiv:2412.09285. doi: 10.48550/arXiv.2412.09285.
作者 | 杨颖
欢迎关注「久章智能」公众号
了解更多智能决策的前沿技术与行业应用
精准预测+动态补货，久章智能DDMRP方案解决库存痛点
旅行商问题（TSP）及开源代码
邮箱｜[email protected]
本文转载自久章智能微信公众号（原文发布于 2025-06-26），内容保持原貌。扫码关注公众号「久章智能」，第一时间获取智能决策系列文章。阅读原文 ↗