《Nature Communications》：Real-time black-box optimization for dynamic discrete environments using embedded Ising machines
编辑推荐：
许多实时系统需要对离散变量进行优化。黑箱优化（BBO）算法和多臂老虎机（MAB）算法通过反复执行动作并观察相应的即时奖励来执行优化，无需任何先验知识。近年来，一种使用Ising机的BBO方法被提出，用于在静态环境中找到由离散值组合表示的最佳动作并最大化即时奖励
许多实时系统需要对离散变量进行优化。黑箱优化（BBO）算法和多臂老虎机（MAB）算法通过反复执行动作并观察相应的即时奖励来执行优化，无需任何先验知识。近年来，一种使用Ising机的BBO方法被提出，用于在静态环境中找到由离散值组合表示的最佳动作并最大化即时奖励。相比之下，实时系统在动态环境中运行，需要能够在重复试验中最大化平均奖励的MAB算法。由于离散优化的组合性质导致动作数量极其庞大，传统的MAB算法无法有效地优化动态离散环境中的动作。在此，研究人员展示了一种启发式方法，通过扩展BBO方法来最大化动态离散环境的平均奖励，其中Ising机在考虑变量之间的交互作用和环境变化的同时高效地探索动作。研究人员在具有移动用户的无线通信系统中证明了所提出方法对动态环境的适应性。
**研究背景、问题与意义**
实时系统通常需要对离散控制变量进行优化。黑箱优化（BBO）算法在有限的采样周期内寻求高即时奖励的动作；多臂老虎机（MAB）算法则在重复采样中最大化累计平均奖励。当动作由多个相互作用的离散变量构成时，动作空间随变量数指数增长，传统MAB算法因样本复杂度极高而难以应用。FMQA（Factorization Machine with Quantum Annealing）方法利用Ising机对静态环境中的离散BBO问题进行有效求解，但不适应环境变化。动态环境中的优化目标应改为平均奖励最大化，而现有非平稳MAB算法在组合动作空间中的性能保证仍十分有限。为此，研究人员提出RT-BBO（Real-Time Black-Box Optimization），将FMQA扩展至动态离散环境，利用嵌入式Ising机实现快速响应，并通过滑动窗口数据集、收缩（shrink）与探索激励等机制跟踪环境变化。实验表明RT-BBO在多种基准和实际无线通信场景中均优于基线、遗传算法（GA）与因子化老虎机（FB），为动态高维离散优化提供了实用方案。该成果发表在《Nature Communications》。
**关键方法**
研究人员采用二阶因子分解机（FM）作为二次代理模型逼近环境黑箱函数；用滑动窗口数据集保留近期样本，引入收缩操作使旧参数衰减，并设计探索激励以促进对未充分探索动作的搜索；还提出多奖励建模以分别逼近多个子奖励后线性组合。求解过程中，使用基于模拟分岔（SB）的嵌入式Ising机（FPGA实现）最大化获取函数，采用独热编码处理多值离散变量，并用mini-batch Adam和log-cosh损失训练模型。实验基于模拟无线蜂窝网络（37个基站）和随机生成的多项式基准问题。
**研究结果**
*算法*：RT-BBO在每个采样周期将最新样本存入滑动窗口数据集，对代理模型参数执行收缩，再通过梯度更新逼近当前环境。获取函数由代理模型、探索激励和独热编码惩罚项组成，由嵌入式Ising机近似最大化。探索激励根据每个自旋变量连续取值不变的次数动态调整，以避免陷入局部最优。多奖励建模将多个奖励信号分别建模后加权融合，在奖励可分解时提高近似质量。
*随机多项式评估*：研究人员构造了随时间线性过渡的两个多项式函数作为动态黑箱，并改变交互阶数与变量数进行评测。结果显示，RT-BBO对动态环境具有较强鲁棒性，性能优于基线FMSB；当变量数约200以上时，RT-BBO始终优于遗传算法，且变量数越多优势越明显。即使真实交互阶数高于二次代理模型，RT-BBO依然有效。在静态阶段，基线表现略好，说明动态机制在环境不变时会带来轻微代价。
*无线系统演示*：研究人员搭建了一个包含37个基站的无线蜂窝网络仿真器，用户沿小区边缘移动，瑞利衰落和干扰使吞吐量函数高度非线性。每个基站有9种预定义波束模式（4种方向形状与3种发射功率），故动作总数为9
37≈2.03×10
35。RT-BBO基于各基站吞吐量（子奖励）或总吞吐量（单一奖励）进行优化。结果显示，RT-BBO（单奖励与多奖励）均显著优于基线、GA、FB和随机选择；加入收缩、探索激励和多奖励建模后性能逐步提升。多奖励RT-BBO相比单奖励RT-BBO有额外优势，且在整个采样过程中保持高吞吐量。
**讨论与结论**
研究人员指出，RT-BBO适用的场景是：仅含少取值的离散变量、变量众多无法穷举、交互阶数不过高、无上下文且每次采样只有单个标量奖励、以及环境随时间变化。其意义在于为动态高维离散优化提供了一种不需要环境内部状态、仅依赖奖励反馈的实时启发式方法。未来方向包括应用于广告推荐、动态定价，以及引入外部上下文以提升自适应能力。研究结论为：RT-BBO通过在动态环境中引入滑动窗口数据集、收缩与探索激励，并借助低延迟嵌入式Ising机，实现了对平均奖励的有效最大化，特别适用于动作由大量交互变量组成且仅能获得bandit反馈的实际系统。
