面向动态变化问题的机器学习辅助高速组合优化：基于 Ising 机器的实现

《Nature Communications》：Machine learning-assisted high-speed combinatorial optimization with Ising machines for dynamically changing problems

　　

量子或量子启发式 Ising 机器近来已显示出在短时间内求解组合优化问题的潜力。现实世界与实际应用——例如无线多跳网络中的时分多址（TDMA）调度、金融交易以及新兴车载系统——要求对这类问题进行序贯求解，而问题规模与特征会动态变化。然而，将 Ising 机器用于实际部署仍面临若干挑战，包括：由于大型 Ising 模型传输或云端访问所导致的全系统时延压缩困难，以及针对每个问题确定参数的困难。研究人员在此展示了一种利用嵌入式 Ising 机器的组合优化方法，该方法能够在运行时无需参数调优的情况下高速求解多样化问题。研究人员对基于模拟分岔（SB）的 Ising 机器算法与电路架构进行了定制，以压缩 Ising 模型并加速计算，随后利用大规模训练数据构建机器学习模型，用于估计合适参数。在无线多跳网络的 TDMA 调度任务中，演示结果表明，该精细化系统能够适应问题变化，并在速度上优于传统方法。

该论文发表于《Nature Communications》，聚焦于动态变化问题（dynamically changing problems）下组合优化系统的实际部署瓶颈。组合优化广泛存在于通信、金融、交通与车载系统等场景，但在很多真实应用中，待求解问题并非静态单例，而是会随着时间连续变化，且后一轮优化任务往往依赖前一轮求解结果，因此无法并行预先展开。这使得评价指标不再只是单次求解器速度，而是跨多轮迭代的全系统时延（system-wide latency）。尽管 Ising 机器作为面向 Ising 模型或二次无约束二元优化（QUBO）的专用计算机，已被证明能够快速获得近似解，但以往研究多在固定问题设定下验证其可行性，尚未充分解决问题规模、图结构和参数需求均显著变化时的通用适应性问题。尤其在嵌入式或边缘部署环境中，数据传输开销、设备访存受限以及每个实例都需重新调参等因素，会显著削弱 Ising 机器的实际收益，因此开展本研究具有明确的工程与方法学意义。

围绕上述问题，研究人员提出了一种面向动态变化问题的低全系统时延组合优化框架，其核心是将嵌入式 Ising 机器、面向 J 矩阵的无损压缩计算架构，以及机器学习驱动的参数估计和求解器选择机制协同整合。论文以最大独立集（MIS，maximum independent set）问题为代表性 NP-hard 问题，并进一步将 MIS 求解器嵌入无线多跳网络的 TDMA 调度系统中，验证该框架面对多轮、异质、动态变化问题实例时的鲁棒性与速度优势。研究显示，该方法不仅能够压缩 Ising 模型传输与存储开销、提升 FPGA 上模拟分岔（SB，simulated bifurcation）算法的并行计算效率，还能利用轻量级机器学习模型在运行时无额外搜索代价地预测适宜参数，并在 CPU 与 FPGA 两类 Ising 机器之间自适应切换，从而兼顾小规模与大规模问题。结果表明，所提出 MIS 求解器在典型条件下较传统方法快 4000 倍以上，在 TDMA 调度场景中可根据问题变化实时调整并保持速度优势，显著增强了 Ising 机器在实际系统中的可用性。

就关键技术方法而言，研究主要采用了以下几类方法：第一，在硬件层面将 ballistic simulated bifurcation（bSB）实现于 FPGA，并构建可嵌入式部署的 Ising 机器；第二，针对 J 矩阵取值种类有限（limited variation）的 Ising/QUBO 形式，提出索引式快速计算架构（indexing fast-computation architecture），通过 indexed J-table 实现无损压缩，并利用编码态 MAC（multiply and accumulate）减少浮点解码与资源消耗；第三，使用 2840 个基于 Erd?s-Rényi（ER）、Barabási-Albert（SF）和 Watts-Strogatz（SW）随机生成图构成训练集，以 XGBoost 回归器建立参数估计器，以多项式逻辑回归建立机器选择器；第四，在应用层以无线多跳网络 TDMA 调度作为样例，样本来自不同节点数、不同通信半径及不同干扰水平的仿真网络场景。

下面结合论文“Results”各小节对主要研究结果进行解读。

Indexing fast-computation architecture
该部分首先从 Ising 模型的表示瓶颈出发，指出耦合矩阵 J 具有 ^O(N²) 规模，在常规 float32 或 float64 表示下，数据传输、片上存储与 MAC 计算都将成为系统瓶颈。研究人员观察到，大量离散组合优化问题在转化为 Ising 模型后，虽然 J_i,j 以实数表示，但可取值种类 N_v 实际很小。例如 MIS、加权二分图最大匹配（WMMBG）和 G-set 对应的 J 矩阵只包含两种或三种不同值。基于这一结构性特征，论文提出 indexed J-table：从 J 矩阵值分布中提取唯一值并赋予索引 t，再以索引值 J_i,j^c 取代原始浮点值，实现无损编码。对 MIS 而言，N_v=2，因此 J 数据量可压缩至原来的 1/32。该结果说明，在特定 Ising/QUBO 问题族中，模型压缩并不需要牺牲精度即可显著降低数据传输和存储开销。

进一步地，研究人员并未停留于“压缩后再解码”的常规思路，而是提出基于编码态直接进行大部分 MAC 运算的 indexed J-specialized MAC。其关键在于将累加过程按索引分组，把 x_j 的选择性累加先在编码域完成，再通过表项 TBL[t] 恢复对应实值并参与乘法。由于 bSB 中位置变量 x 的动态范围预先已知且受限于 ?1.0≤x≤1.0，累加器可使用定点表示，从而减少浮点运算资源和时延。由此可见，索引架构不仅提升了 CPU 到 FPGA 的离线传输效率，也直接增加了硬件并行 MAC 的密度，进而缩短 Ising 机的核心执行时间。论文据此得出结论：对于 J 矩阵取值种类有限的离散优化问题，编码表示与专用 MAC 设计可在保持无损表达的同时显著提升系统级速度。

ML-assisted scalable and diversified architecture
该部分聚焦于动态变化问题中另一个核心挑战：不同问题实例往往需要不同的 SB 控制参数 c、dt 和 step，而逐实例搜索最优参数在运行时不可行。研究人员因此构建了基于机器学习的参数估计器。训练数据由 2840 个随机图组成，覆盖 ER、SF 与 SW 三类网络结构，并提取节点数、边密度、平均度与 Gini 系数作为图特征。目标变量不是直接独立学习 c、dt 和 step，而是考虑到参数间依赖关系，学习 c、c/dt 与 dt×step。研究中还引入了时间到分段目标（TTST，time-to-sectional-target）指标，用于在未知精确最优解的随机图场景中评估速度与解质量折中。通过该设计，参数估计器能够在运行时低开销地产生针对当前图结构的适宜参数。该结果表明，机器学习可有效捕捉图特征与 SB 参数之间复杂而非线性的映射关系，从而替代昂贵的在线网格搜索。

在可扩展性方面，论文提出两项补充机制。其一是 batch mapping：针对 FPGA Ising 机器具有固定最大规模 N_MAX=2048 的特点，当实际问题规模 N 明显更小时，将同一小问题复制多份并映射到 J 存储器的对角块中，通过零填充保证副本间互不耦合。这样，一次执行即可并行得到 ?N_MAX/N? 个近似解，相当于提升了小规模问题的有效吞吐量，并可从多解中选择最佳结果。其二是 machine selector：当问题过小或 step 很小时，CPU 实现可能因避免 FPGA 卸载开销而更快。研究人员因此训练了一个二分类模型，利用 N 与参数估计器输出的 step，在 CPU 型与 FPGA 型 Ising 机器之间自适应切换。该部分结论是，单一硬件后端不足以覆盖从极小到大规模问题的全区间，而“参数估计+批处理映射+机器切换”的联合架构可以提升对动态问题规模变化的敏捷性。

Evaluation on the MIS problem
在 MIS 系统性评估中，研究人员比较了三种 SB-MIS 配置：传统 SB 基线、采用通用索引流程的 Proposed (Generic)，以及采用针对 MIS 优化路径的 Proposed (Optimized)。系统级时延分解结果显示，在多个代表性设定下，Proposed (Optimized) 均显著优于基线。主要原因包括：其一，Ising 机器执行时间因 indexed J-specialized MAC 而约缩短 3 倍；其二，J 矩阵压缩使 CPU 到 FPGA 的卸载开销约降低 30 倍；其三，优化版通过将 Ising 模型转换与索引编码融合，进一步减少额外处理开销。与此同时，特征提取与参数估计模块只引入约 2–2.8 ms 的时间代价，并未成为瓶颈。该部分说明，所提改进并非只提升单一算子速度，而是对建模、编码、传输、执行到调度各环节进行了协同优化，因此才真正降低了全系统时延。

随后论文比较 CPU 与 FPGA 实现随 step 和节点规模 |V| 变化时的时延曲线。结果显示，随着 step 或 |V| 增长，FPGA 的时间增长率明显更缓；但在小 step 或小 |V| 区域，CPU 反而更快。该交叉行为直接支持机器切换机制的必要性。进一步与 NetworkX、OR-Tools、ReduMIS 以及固定参数 SB 基线比较后发现：在中大规模问题（|V|≥100）中，SB 类求解器明显快于软件基线；尤其在 |V|=2000 且 p=0.1 时，所提方法较 NetworkX 快 5500 倍、较 ReduMIS 快 4300 倍。OR-Tools 在更大实例下甚至无法在 3600 s 超时前返回结果。解质量方面，ReduMIS 在多数设定下最高或接近最高，OR-Tools 与 ReduMIS 在小规模问题上更优；但所提方法整体优于 NetworkX，并且除个别条件外普遍优于固定参数 SB 基线。这一结果表明，该框架在“低时延—较高解质量”之间实现了更适合动态场景的折中。

Demonstration
在应用演示部分，研究人员将所提 MIS 求解器嵌入无线多跳网络的 TDMA 调度。该问题中，每次迭代从当前树形传输图中抽取叶节点构造子图 G，并在干扰约束下求解其 MIS，以决定可在同一时隙同时发送的数据节点集合。随着叶节点不断移除，后续迭代中的 G 在节点数、边密度、平均度和异质性等方面持续变化，因而构成典型的动态变化问题。研究分别在低干扰场（L.I.F）和高干扰场（H.I.F）中，针对不同传感器节点数 N_s 与通信半径 r 进行仿真评估。结果显示，在所有条件下，基于 SB 的所提 MIS 求解器在总计算时间上均优于 NetworkX，而生成的总时隙数 #Slots 无显著劣势。对于 N_s=2000 的高干扰场，论文进一步展示了迭代过程中图特征、所选参数（c、dt、step）及选用 CPU/FPGA 机器的动态变化，证明机器学习模型确实根据问题特征在宽动态范围内进行了自适应决策。该部分结论是，所提框架在真实应用风格任务中不仅保持了速度优势，也具备针对问题时变性的在线适应能力。

Discussion
讨论部分指出，本研究的核心贡献在于提出了一种面向动态变化问题的系统感知型 Ising 优化框架：一方面，以嵌入式 bSB Ising 机器和索引式快速计算架构实现高速、低资源的求解；另一方面，以机器学习建立图特征与多参数间关系，在运行时实现几乎无开销的参数选择与后端切换。与既有工作依赖固定代表参数、忽视问题尺度适配或仅报告退火时间不同，该研究从 wall-clock time 出发评估全系统时延，更贴近实际部署条件。论文同时强调，该方法并非替代量子退火，而是为独立使用或联合新型量子硬件提供一种低时延、面向系统工程的补充框架。作者也指出当前局限：参数学习策略尚未证明可泛化至更多类型组合优化问题；图神经网络（GNN，graph neural networks）等更强模型值得进一步探索；此外，该方法适合可反复分解为 QUBO/Ising 子问题的实时系统，而不直接面向连续时间控制等不满足此结构的问题。

研究结论部分可译述如下：为实现动态变化问题的高速组合优化，研究人员提出了一种将基于量子启发式 SB 算法的嵌入式 Ising 机器、利用数据压缩实现高速计算的索引式快速计算架构，以及机器学习相结合的方法体系。研究人员定义了表征问题图的特征，并利用随机生成图得到的训练数据学习这些特征与多个相互依赖的 Ising 参数之间的关系。基于该方法构建的 MIS 求解器已显示出相较传统方法超过 4000 倍的速度优势。在无线多跳网络 TDMA 调度这一实际应用原型中，机器学习模型能够依据问题特征有效选择参数，证明了所提方法在计算时间方面的有效性。该研究增强了 Ising 机器的实际应用可行性，并促进了量子计算、机器学习、计算机科学与离散数学交叉领域的发展。