1. 项目概述在物流调度、芯片设计、金融投资这些我们每天都会打交道的领域背后都藏着一类让人又爱又恨的数学问题——组合优化。简单说就是从一大堆可能的方案里找出那个“最好”的。比如给10个客户派3辆车送货怎么安排路线总距离最短且每辆车的活儿差不多这种问题可能的路线组合数量是天文数字用穷举法算到地老天荒也算不完。所以工程师和科学家们一直在寻找更聪明的求解方法。模拟退火Simulated Annealing, SA就是其中一员“老将”它模仿金属退火的过程通过引入“温度”参数让搜索过程有一定概率跳出局部最优的“坑”去探索更优的区域是解决这类NP难问题的经典启发式算法。近年来一种受量子物理启发的专用硬件——伊辛机Ising Machine崭露头角它本质上是一个快速寻找伊辛模型或与之等价的二次无约束二进制优化QUBO模型最低能量状态的“物理加速器”。QUBO模型只允许目标函数是二进制变量的线性项和二次项这成了它的“阿喀琉斯之踵”。因为现实世界中很多问题天然就包含三次、四次甚至更高阶的变量交互作用。为了把这些问题塞进QUBO这个“标准接口”就必须进行“降阶”通过引入额外的辅助变量和惩罚项把高阶项拆解成二次项。这个过程就像把一台复杂的机器拆成标准零件再组装虽然能装进去但零件变多了结构也变复杂了很可能影响最终机器的性能。那么一个很自然的问题就来了如果我们有一个能直接处理高阶项的求解器绕开降阶这一步是不是就能得到更好的结果这就是本文要探讨的核心。我们利用Fixstars Amplify Annealing Engine这个高性能模拟退火求解器它同时支持QUBO和能直接处理至四阶项的多项式无约束二进制优化PUBO模型。我们在完全相同的硬件和算法平台上用两个经典的、天然包含四阶交互的问题作为试金石低自相关二进制序列LABS问题和带距离均衡的车辆路径问题VRP。我们的目标很明确抛开算法差异纯粹对比“直接处理高阶项PUBO”和“降阶为二次项再处理QUBO”这两种问题表述形式谁在求解质量和稳定性上更胜一筹。2. 核心概念与问题建模解析在深入对比之前我们必须先理解这场比拼中的几位“主角”PUBO、QUBO以及它们与伊辛模型和模拟退火的关系。这不仅仅是名词解释更关乎我们如何正确地“翻译”一个现实世界的问题让它能被计算机高效求解。2.1 从伊辛模型到QUBO与PUBO伊辛模型最初是个物理模型用来描述磁性材料中原子磁矩自旋的相互作用。每个自旋可以向上1或向下-1其系统的能量哈密顿量由两部分组成每个自旋受外部磁场影响的能量以及自旋两两之间相互作用的能量。寻找系统的最低能量状态基态就对应着找到自旋的最佳排列。在组合优化中我们巧妙地将这个物理模型“借用”过来。我们把问题的每一个决策变量比如“某辆车是否在某个时间访问某个客户”映射成一个自旋或者一个二进制变量。问题的目标函数比如总距离和约束条件比如每个客户只能被访问一次则被编码成这个模型的能量函数。这样寻找问题的最优解就等价于寻找这个物理系统的最低能量状态。这里就产生了两种主流的“编码语言”QUBO二次无约束二进制优化这是目前绝大多数伊辛机硬件的“普通话”。它要求目标函数必须是二进制变量x_i ∈ {0, 1}的二次多项式。形式如下E_QUBO(x) Σ_{i≤j} Q_{ij} x_i x_j其中Q_{ij}是系数矩阵。注意x_i^2 x_i对于二进制变量恒成立所以线性项实际上被包含在了对角元Q_{ii}中。这种形式简洁硬件执行效率高。PUBO多项式无约束二进制优化这是一种更通用的“方言”。它允许目标函数是二进制变量的任意高阶多项式例如包含x_i x_j x_k这样的三次项或x_i x_j x_k x_l这样的四次项。形式如下E_PUBO(x) Σ c_{ijk...} x_i x_j x_k ...它能够更自然、更紧凑地表达许多复杂问题中固有的高阶交互关系。两者可以通过简单的变量变换s_i 2x_i - 1相互转换将{0, 1}映射到{-1, 1}。关键区别在于PUBO 的表达能力更强而 QUBO 是目前硬件的通用标准。2.2 高阶问题的降阶之痛替代法当一个问题天然是PUBO形式包含高阶项但你的硬件只懂QUBO时你就必须进行“降阶编译”。最常用的方法之一是替代法。它的核心思想是引入新的辅助二进制变量来替换掉高阶乘积。举个例子对于一个三次项x1 x2 x3我们引入一个辅助变量y_{12}并希望它等价于x1 x2。原项x1 x2 x3被重写为y_{12} x3。为了强制y_{12} x1 x2这个关系成立我们需要增加一个惩罚项P * (x1 x2 - 2*y_{12}*(x1 x2) 3*y_{12})。这个惩罚项的设计非常巧妙只有当y_{12}的值恰好等于x1和x2的逻辑与AND结果时其值才为0否则为一个正数增加系统能量使得该解不优。于是原三次项被转化为一个二次表达式x1 x2 x3 y_{12} x3 P * (x1 x2 - 2*y_{12}*(x1 x2) 3*y_{12})。这个过程会带来两个直接影响变量膨胀每引入一个辅助变量问题的搜索空间就翻一倍。对于包含大量高阶项的问题变量数量会呈爆炸式增长。问题变形惩罚系数P的选取成了一门艺术。太小约束不起作用求解器可能输出无效解太大可能会扭曲原始问题的能量地貌让最优解“沉没”在惩罚项构成的“高山”之中同样难以找到。2.3 基准问题选型为什么是LABS和VRP为了公平、全面地检验PUBO直接求解的优势我们选择了两个在结构上互补的基准问题。2.3.1 低自相关二进制序列问题LABS问题是一个纯粹的、无约束的优化问题。目标是找到一个由1和-1组成的长度为N的序列s使其非周期自相关函数的平方和最小。其能量函数定义为E(s) Σ_{k1}^{N-1} [ Σ_{i1}^{N-k} s_i s_{ik} ]^2当你把平方项展开时自然会产生s_i s_{ik} s_j s_{jk}这样的四阶交互项。因此它的PUBO形式是原生的、最紧凑的。这个问题是量子优化领域的经典试金石其能量地貌复杂非常适合检验求解器处理本质高阶交互的能力。2.3.2 带距离均衡的车辆路径问题VRP是一个经典的、有约束的、多目标的现实世界问题。我们研究其一个变体不仅要最小化所有车辆的总行驶距离还要最小化各车辆之间行驶距离的方差即均衡工作量。其目标函数如下f1(x): 总行驶距离二次项。f2(x): 行驶距离的方差由于是平方差展开后包含四阶项。总能量函数为E(x) (1-α)f1(x) αf2(x) μ * (约束项)。 其中α权衡两个目标的重要性μ是约束惩罚系数。这个问题包含了现实优化问题的典型要素多目标、硬约束、以及由方差项带来的固有高阶交互。它能够检验求解器在更复杂、更贴近实际场景下的表现。通过这两个问题我们以观察PUBO直接求解在“纯粹高阶”和“现实复杂”两种不同场景下是否都能展现出相对于QUBO降阶的稳定优势。3. 实验设计与性能对比实战理论说得再好不如实验跑一跑。我们所有的实验都在同一个平台——Fixstars Amplify Annealing Engine上进行它同时内置了QUBO求解器和PUBO求解器支持至四阶项。这确保了比较的公平性算法都是模拟退火硬件环境完全相同唯一的变量就是问题表述形式是PUBO还是降阶后的QUBO。3.1 实验设置与评估指标为了保证结果的可比性和无偏性我们设定了严格的实验条件求解器使用Amplify AE的PUBO求解器和QUBO求解器。降阶方法QUBO求解器使用替代法进行降阶惩罚系数p先采用系统默认值1.0后续会专门分析其影响。算法参数模拟退火采用几何冷却方案。每次实验运行时间固定为60秒。重复性每个问题配置如不同的序列长度N、不同的权重α均独立运行10次取统计结果。参数调优刻意避免对特定问题实例进行精细的参数调优所有求解器内部参数保持默认。这是为了测试两种表述形式的“开箱即用”鲁棒性防止调参带来的偏差。可行性验证对于VRP问题我们会严格检查所有约束条件只有完全满足约束的解才被纳入目标函数的评估。我们的评估指标聚焦于两个方面解的质量对于LABS问题使用相对于已知最优解的归一化能量\tilde{E} E(s) / E*_N越接近1越好。对于VRP问题直接比较总距离、方差以及加权后的总目标函数值。解的稳定性通过10次独立运行结果的标准差来评估。标准差小说明求解器输出稳定可重复性强。多目标优化能力针对VRP使用超体积指标。它衡量的是在目标空间中所找到的帕累托最优解集所支配的区域体积。超体积越大说明解集的质量越高、多样性越好越能覆盖不同的权衡偏好。3.2 LABS问题结果PUBO的稳定碾压我们测试了序列长度N从5到99的情况。下图清晰地展示了两者的差距 注此处用文字描述图表结果实际报告中应包含类似图3的曲线图 随着序列长度N的增加QUBO求解器得到的归一化能量平均值显著高于PUBO求解器并且其波动范围标准差急剧增大。这意味着对于QUBO不仅找到的解更差而且每次运行的结果好坏靠运气非常不稳定。相反PUBO求解器的曲线始终紧贴更低的能量值且波动范围非常窄。即使在N增大到接近100时它依然能保持稳定的高性能输出。这直观地证明对于这种原生高阶问题降阶过程引入的额外变量和复杂的能量地貌严重干扰了模拟退火搜索的效率和稳定性。PUBO直接求解保留了问题最简洁的本质结构让求解器能够更高效、更稳定地找到优质解。3.3 VRP问题结果多目标权衡下的全面胜出对于VRP问题我们进行了更细致的分析。3.3.1 单实例深度分析我们固定客户点P11车辆V3然后调节权重参数α从0只关心总距离到1只关心距离均衡。结果如图所示 注此处用文字描述类似图4的三个子图总距离与方差权衡随着α增大更注重均衡两种方法的总距离都会略有增加因为为了均衡可能需要绕路但PUBO的增长更平滑、波动更小。在方差指标上PUBO能稳定地将方差降到更低水平。总目标函数值在所有α取值下PUBO得到的总目标函数值(1-α)f1 αf2都系统性地低于QUBO。这说明在综合考量下PUBO找到了更优的折衷方案。解集分布我们将所有α下得到的可行解画在“总距离-方差”二维图上类似图5的散点图。PUBO的解密集地分布在靠近坐标原点的帕累托前沿附近形成了一个清晰的权衡边界。而QUBO的解则非常分散很多解既距离长又不均衡只有少数解能勉强接近PUBO的边界且无法达到方差最小的区域。这揭示了一个关键问题降阶过程可能破坏了方差项包含四阶交互的内在结构导致求解器在优化这个目标时“力不从心”。3.3.2 多实例超体积对比为了进行更具统计意义的比较我们生成了30个随机的VRP实例客户点位置随机分布。对每个实例我们都用两种方法求解并计算其帕累托解集的超体积指标。结果呈现出一边倒的趋势类似图6所有30个数据点都落在yx参考线的下方。这意味着在每一个随机生成的实例上PUBO求解器得到的解集超体积都大于QUBO求解器。这是一个非常强有力的证据表明PUBO直接求解在多目标优化中能更一致地获得质量更高、多样性更好的解集这不是个别例子下的偶然而是其表述优势的普遍体现。3.3.3 可扩展性分析问题规模增大时会发生什么我们进一步增加了客户点数量P观察两种方法的可扩展性。结果非常说明问题类似图7可行性率当P较小时≤11两者都能100%找到可行解。但随着P增大QUBO求解器找到可行解的成功率开始显著下降。而PUBO求解器直到P17仍能保持很高的可行性率。降阶引入的额外约束使得满足所有条件的难度激增。超体积衰减随着P增大两种方法得到的解集超体积都会下降问题变难了但QUBO的下降速度明显更快。在P17时其超体积值已远低于PUBO。这表明问题规模越大降阶带来的负面效应变量膨胀、搜索空间扭曲就越凸显PUBO直接求解的鲁棒性优势就越明显。4. 核心优势拆解与深度讨论实验数据已经清晰地指向了结论但我们还需要深入挖掘背后的“为什么”。PUBO的优势并非空中楼阁而是源于其避免了QUBO降阶带来的几个根本性代价。4.1 变量膨胀搜索空间的指数级爆炸这是最直观的代价。降阶过程每引入一个辅助变量问题的搜索空间就扩大一倍。我们对比了两种表述下变量数量随问题规模的增长类似图8。对于LABS问题变量数随序列长度N的增长QUBO formulation 的曲线斜率远大于PUBO。对于一个大规模问题QUBO所需的变量数可能是PUBO的数十倍。对于VRP问题随着客户点P增加变量数的差距也迅速拉大。这意味着什么模拟退火等搜索算法是在由所有变量构成的解空间中进行漫游。变量数量直接决定了这个空间的维度。维度爆炸就是著名的“维度灾难”搜索算法需要探索的角落呈指数级增长找到高质量解的难度和所需时间也随之剧增。PUBO通过保留紧凑的原生形式从根本上遏制了这种维度膨胀。4.2 惩罚系数调优一个棘手的黑箱在替代法中惩罚系数p的选取至关重要。我们针对LABS问题系统测试了不同序列长度N下惩罚系数p从1.0到10.0对解质量的影响类似图9的热力图。结果发现不存在一个“放之四海而皆准”的最优p值。对于不同的N能取得最好结果的p值各不相同。这张热图看起来就像一幅变化莫测的抽象画。在实际应用中这意味着如果你想用好QUBO求解器处理高阶问题你必须为每一具体问题、甚至每一个问题规模去费力地调整这个惩罚系数。这无疑增加了巨大的工程成本和不确定性。而PUBO求解器完全避开了这个陷阱因为它根本不需要引入这个额外的惩罚项。4.3 能量地貌的扭曲当平坦山谷变成崎岖山地这是更深层次、也更关键的一点。模拟退火算法的核心是接受准则它以一定概率接受使能量变高的“坏”移动以跳出局部最优。这个概率取决于能量差ΔE与当前温度T的比值ΔE/T。降阶过程通过引入辅助变量和惩罚项改变了原始问题的能量地貌。虽然从全局最优解的数学等价性上看两者是一致的但搜索路径上的风景被彻底改变了。原本平缓的斜坡可能变成陡峭的悬崖宽阔的谷底可能布满碎石局部极值点。这种扭曲会导致两个后果可行性陷阱与约束相关的惩罚项如果设置得很大会在可行域边界竖起极高的能量壁垒。模拟退火在有限温度下可能没有足够的“热能”翻越这些壁垒从而被困在不可行区域导致可行性率下降——这在我们的VRP可扩展性实验中得到了印证。搜索效率降低扭曲的地貌增加了局部最优点的数量使得算法更容易陷入其中。同时它也可能模糊了不同目标之间的真实权衡关系导致在多目标优化中无法有效探索帕累托前沿——这解释了为什么QUBO在VRP问题中得到的解集分布更散、超体积更小。PUBO直接求解则忠实地保留了原始问题的能量地貌。求解器是在最真实的地形上搜索自然能更高效、更准确地找到最优区域。4.4 对实际工作的启示基于以上分析对于从事组合优化相关研究和应用的工程师、研究员来说可以得出以下几点实操建议优先评估问题结构在接手一个新问题时首先分析其数学形式。如果目标函数或约束中天然包含了三次及以上的变量乘积项那么它就是一个高阶问题。不要下意识地就去着手降阶。探索直接求解的可能性调研可用的工具。像本文使用的Amplify AE这类支持PUBO的求解器正在增多。如果存在应优先尝试直接使用PUBO formulation进行建模和求解。这往往能省去降阶的麻烦并获得更优、更稳定的结果。如果必须降阶例如硬件限制意识到代价明确知道你会面临变量膨胀、惩罚系数调优和能量地貌扭曲三大挑战。精心设计降阶策略对于结构化的问题像替代法这样能复用辅助变量的方法可能更优。对比不同降阶方法如Ishikawa-KZFD方法带来的变量增长可参考原文附录A的对比图。系统化调参将惩罚系数的调优作为一个必须的步骤。可以采用网格搜索、基于问题规模的经验公式或自适应方法来确定相对合适的p值。管理预期对于大规模问题要对QUBO求解器的性能下降解质量波动、可行性率降低有心理准备并在系统设计时留有余地。5. 常见问题与实战避坑指南在实际操作中从理论理解到成功运行一个优化模型中间可能会遇到不少坑。这里结合我的经验总结几个常见问题和注意事项。5.1 如何判断我的问题是否是“高阶”的这听起来简单但有时容易忽略。不仅仅要看目标函数。一个常见误区是只检查目标函数是否为二次型。必须同时检查约束条件。例如一个经典的“恰好一个”约束Σ_i x_i 1在转化为惩罚项(Σ_i x_i - 1)^2时展开后就是二次型。但是如果你有一个约束要求“最多一个” (Σ_i x_i ≤ 1)通常需要引入辅助变量将其转化为等式约束这个过程可能会产生高阶项。再比如涉及逻辑“与”AND或“或”OR的条件用二次型精确表达往往需要技巧有时直接使用高阶项更自然。建模时务必展开所有惩罚项检查变量的最高次幂。5.2 使用PUBO求解器建模时有什么不同最大的不同是自由度和简洁性。你不再需要费尽心机地把一个x1*x2*x3拆成y12*x3 P*(...)。你可以直接写出x1*x2*x3。这大大降低了建模的复杂度也减少了出错的可能。但是这也要求你对问题有更本质的理解能直接写出其多项式形式。同时要注意当前求解器支持的最高阶数例如Amplify AE支持到四阶。如果你的问题包含五阶及以上项可能仍需部分降阶或寻找其他支持更高阶的求解器。5.3 惩罚系数μ在PUBO中还存在吗是的但含义不同了。在PUBO模型中惩罚系数μ仍然存在但它用于处理约束条件而不是用于处理降阶。例如在VRP问题中μ用来加权约束惩罚项g1(x)g2(x)g3(x)。这个μ的调优同样重要但它调优的是“约束的严格程度”而不是“降阶的准确性”。一般来说μ需要设置得足够大以确保搜索过程倾向于满足约束的解但也不能过大以免掩盖了原始目标函数的细节。一个实用的启发式方法是将μ设置为与目标函数典型值相当或略大的量级。5.4 对于超大规模问题PUBO是否一定比QUBO快本文主要对比了解的质量和稳定性。在计算时间上实验设定为固定时间60秒两者表现相当。但这并不意味着在所有场景下时间都一样。变量数量直接影响求解器单次迭代的计算开销。QUBO模型变量多意味着每次计算能量差ΔE时需要求和更多的项。虽然现代求解器如基于GPU的Amplify AE对此有高度优化但在极端大规模下变量数的差异最终可能会转化为实际计算时间的差异。PUBO模型变量少单次迭代可能更快从而在固定时间内进行更多次搜索。这一点需要结合具体求解器的实现来评估。5.5 除了模拟退火其他算法也能受益于PUBO吗非常可能。本文的结论虽然基于模拟退火但其核心逻辑——避免降阶带来的变量膨胀和问题变形——是普适的。其他元启发式算法如遗传算法、禁忌搜索、粒子群优化等同样在一个定义好的解空间由变量定义和能量地貌由目标函数定义上搜索。一个更紧凑、更真实的搜索空间和地貌对任何搜索算法都是有利的。事实上近期一些基于量子近似优化算法QAOA和模拟分岔机的研究也显示了直接处理PUBO的优势。因此当你使用任何优化算法时如果它支持直接处理高阶项都值得优先尝试PUBO formulation。5.6 实战避坑清单建模第一步先画变量交互图在纸上画出变量之间的依赖关系。如果出现三个或以上变量同时在一个约束或目标项中交互就要警惕高阶项。优先使用原生支持高阶的建模库例如Amplify SDK它允许你直接用数学表达式定义高阶项库会自动处理底层表述无需手动降阶。从小规模实例开始验证无论用PUBO还是QUBO先用一个极小规模的问题比如LABS的N5VRP的P3跑通整个流程。验证解的正确性是否满足约束目标值是否合理。监控可行性率对于约束问题在调试阶段务必输出每次运行的约束违反程度。如果可行性率很低首先检查惩罚系数μPUBO或pQUBO降阶是否设置合理而不是盲目增加运行时间。解的可视化对于像VRP这样的问题将求得的路线画出来。一个看起来乱七八糟的路线图比任何数字都更能告你求解可能出了问题无论是建模错误还是参数设置不当。理解你的求解器阅读求解器的文档了解它对PUBO的支持程度最高阶数、性能特点、默认的参数设置以及推荐的调参范围。不要把它当黑盒。直接使用PUBO formulation处理高阶组合优化问题在模拟退火框架下展现出了显著且稳定的优势。它通过避免降阶过程从根本上消除了变量膨胀、惩罚系数调优和能量地貌扭曲三大痛点从而在解质量、稳定性和多目标权衡表达能力上均优于传统的QUBO降阶方法。随着支持高阶项直接求解的软硬件工具日益成熟对于物流、调度、芯片设计、金融等领域的从业者而言在遇到天然包含高阶交互的复杂优化问题时将PUBO作为首选的建模和求解路径是一个值得认真考虑的高效策略。这不仅仅是技术选型的变化更是一种思维方式的转变从“如何把问题塞进硬件”转向“如何最自然地表达问题本身”。
高阶组合优化新思路：PUBO直接求解对比QUBO降阶的全面优势
发布时间：2026/5/27 15:27:37
1. 项目概述在物流调度、芯片设计、金融投资这些我们每天都会打交道的领域背后都藏着一类让人又爱又恨的数学问题——组合优化。简单说就是从一大堆可能的方案里找出那个“最好”的。比如给10个客户派3辆车送货怎么安排路线总距离最短且每辆车的活儿差不多这种问题可能的路线组合数量是天文数字用穷举法算到地老天荒也算不完。所以工程师和科学家们一直在寻找更聪明的求解方法。模拟退火Simulated Annealing, SA就是其中一员“老将”它模仿金属退火的过程通过引入“温度”参数让搜索过程有一定概率跳出局部最优的“坑”去探索更优的区域是解决这类NP难问题的经典启发式算法。近年来一种受量子物理启发的专用硬件——伊辛机Ising Machine崭露头角它本质上是一个快速寻找伊辛模型或与之等价的二次无约束二进制优化QUBO模型最低能量状态的“物理加速器”。QUBO模型只允许目标函数是二进制变量的线性项和二次项这成了它的“阿喀琉斯之踵”。因为现实世界中很多问题天然就包含三次、四次甚至更高阶的变量交互作用。为了把这些问题塞进QUBO这个“标准接口”就必须进行“降阶”通过引入额外的辅助变量和惩罚项把高阶项拆解成二次项。这个过程就像把一台复杂的机器拆成标准零件再组装虽然能装进去但零件变多了结构也变复杂了很可能影响最终机器的性能。那么一个很自然的问题就来了如果我们有一个能直接处理高阶项的求解器绕开降阶这一步是不是就能得到更好的结果这就是本文要探讨的核心。我们利用Fixstars Amplify Annealing Engine这个高性能模拟退火求解器它同时支持QUBO和能直接处理至四阶项的多项式无约束二进制优化PUBO模型。我们在完全相同的硬件和算法平台上用两个经典的、天然包含四阶交互的问题作为试金石低自相关二进制序列LABS问题和带距离均衡的车辆路径问题VRP。我们的目标很明确抛开算法差异纯粹对比“直接处理高阶项PUBO”和“降阶为二次项再处理QUBO”这两种问题表述形式谁在求解质量和稳定性上更胜一筹。2. 核心概念与问题建模解析在深入对比之前我们必须先理解这场比拼中的几位“主角”PUBO、QUBO以及它们与伊辛模型和模拟退火的关系。这不仅仅是名词解释更关乎我们如何正确地“翻译”一个现实世界的问题让它能被计算机高效求解。2.1 从伊辛模型到QUBO与PUBO伊辛模型最初是个物理模型用来描述磁性材料中原子磁矩自旋的相互作用。每个自旋可以向上1或向下-1其系统的能量哈密顿量由两部分组成每个自旋受外部磁场影响的能量以及自旋两两之间相互作用的能量。寻找系统的最低能量状态基态就对应着找到自旋的最佳排列。在组合优化中我们巧妙地将这个物理模型“借用”过来。我们把问题的每一个决策变量比如“某辆车是否在某个时间访问某个客户”映射成一个自旋或者一个二进制变量。问题的目标函数比如总距离和约束条件比如每个客户只能被访问一次则被编码成这个模型的能量函数。这样寻找问题的最优解就等价于寻找这个物理系统的最低能量状态。这里就产生了两种主流的“编码语言”QUBO二次无约束二进制优化这是目前绝大多数伊辛机硬件的“普通话”。它要求目标函数必须是二进制变量x_i ∈ {0, 1}的二次多项式。形式如下E_QUBO(x) Σ_{i≤j} Q_{ij} x_i x_j其中Q_{ij}是系数矩阵。注意x_i^2 x_i对于二进制变量恒成立所以线性项实际上被包含在了对角元Q_{ii}中。这种形式简洁硬件执行效率高。PUBO多项式无约束二进制优化这是一种更通用的“方言”。它允许目标函数是二进制变量的任意高阶多项式例如包含x_i x_j x_k这样的三次项或x_i x_j x_k x_l这样的四次项。形式如下E_PUBO(x) Σ c_{ijk...} x_i x_j x_k ...它能够更自然、更紧凑地表达许多复杂问题中固有的高阶交互关系。两者可以通过简单的变量变换s_i 2x_i - 1相互转换将{0, 1}映射到{-1, 1}。关键区别在于PUBO 的表达能力更强而 QUBO 是目前硬件的通用标准。2.2 高阶问题的降阶之痛替代法当一个问题天然是PUBO形式包含高阶项但你的硬件只懂QUBO时你就必须进行“降阶编译”。最常用的方法之一是替代法。它的核心思想是引入新的辅助二进制变量来替换掉高阶乘积。举个例子对于一个三次项x1 x2 x3我们引入一个辅助变量y_{12}并希望它等价于x1 x2。原项x1 x2 x3被重写为y_{12} x3。为了强制y_{12} x1 x2这个关系成立我们需要增加一个惩罚项P * (x1 x2 - 2*y_{12}*(x1 x2) 3*y_{12})。这个惩罚项的设计非常巧妙只有当y_{12}的值恰好等于x1和x2的逻辑与AND结果时其值才为0否则为一个正数增加系统能量使得该解不优。于是原三次项被转化为一个二次表达式x1 x2 x3 y_{12} x3 P * (x1 x2 - 2*y_{12}*(x1 x2) 3*y_{12})。这个过程会带来两个直接影响变量膨胀每引入一个辅助变量问题的搜索空间就翻一倍。对于包含大量高阶项的问题变量数量会呈爆炸式增长。问题变形惩罚系数P的选取成了一门艺术。太小约束不起作用求解器可能输出无效解太大可能会扭曲原始问题的能量地貌让最优解“沉没”在惩罚项构成的“高山”之中同样难以找到。2.3 基准问题选型为什么是LABS和VRP为了公平、全面地检验PUBO直接求解的优势我们选择了两个在结构上互补的基准问题。2.3.1 低自相关二进制序列问题LABS问题是一个纯粹的、无约束的优化问题。目标是找到一个由1和-1组成的长度为N的序列s使其非周期自相关函数的平方和最小。其能量函数定义为E(s) Σ_{k1}^{N-1} [ Σ_{i1}^{N-k} s_i s_{ik} ]^2当你把平方项展开时自然会产生s_i s_{ik} s_j s_{jk}这样的四阶交互项。因此它的PUBO形式是原生的、最紧凑的。这个问题是量子优化领域的经典试金石其能量地貌复杂非常适合检验求解器处理本质高阶交互的能力。2.3.2 带距离均衡的车辆路径问题VRP是一个经典的、有约束的、多目标的现实世界问题。我们研究其一个变体不仅要最小化所有车辆的总行驶距离还要最小化各车辆之间行驶距离的方差即均衡工作量。其目标函数如下f1(x): 总行驶距离二次项。f2(x): 行驶距离的方差由于是平方差展开后包含四阶项。总能量函数为E(x) (1-α)f1(x) αf2(x) μ * (约束项)。 其中α权衡两个目标的重要性μ是约束惩罚系数。这个问题包含了现实优化问题的典型要素多目标、硬约束、以及由方差项带来的固有高阶交互。它能够检验求解器在更复杂、更贴近实际场景下的表现。通过这两个问题我们以观察PUBO直接求解在“纯粹高阶”和“现实复杂”两种不同场景下是否都能展现出相对于QUBO降阶的稳定优势。3. 实验设计与性能对比实战理论说得再好不如实验跑一跑。我们所有的实验都在同一个平台——Fixstars Amplify Annealing Engine上进行它同时内置了QUBO求解器和PUBO求解器支持至四阶项。这确保了比较的公平性算法都是模拟退火硬件环境完全相同唯一的变量就是问题表述形式是PUBO还是降阶后的QUBO。3.1 实验设置与评估指标为了保证结果的可比性和无偏性我们设定了严格的实验条件求解器使用Amplify AE的PUBO求解器和QUBO求解器。降阶方法QUBO求解器使用替代法进行降阶惩罚系数p先采用系统默认值1.0后续会专门分析其影响。算法参数模拟退火采用几何冷却方案。每次实验运行时间固定为60秒。重复性每个问题配置如不同的序列长度N、不同的权重α均独立运行10次取统计结果。参数调优刻意避免对特定问题实例进行精细的参数调优所有求解器内部参数保持默认。这是为了测试两种表述形式的“开箱即用”鲁棒性防止调参带来的偏差。可行性验证对于VRP问题我们会严格检查所有约束条件只有完全满足约束的解才被纳入目标函数的评估。我们的评估指标聚焦于两个方面解的质量对于LABS问题使用相对于已知最优解的归一化能量\tilde{E} E(s) / E*_N越接近1越好。对于VRP问题直接比较总距离、方差以及加权后的总目标函数值。解的稳定性通过10次独立运行结果的标准差来评估。标准差小说明求解器输出稳定可重复性强。多目标优化能力针对VRP使用超体积指标。它衡量的是在目标空间中所找到的帕累托最优解集所支配的区域体积。超体积越大说明解集的质量越高、多样性越好越能覆盖不同的权衡偏好。3.2 LABS问题结果PUBO的稳定碾压我们测试了序列长度N从5到99的情况。下图清晰地展示了两者的差距 注此处用文字描述图表结果实际报告中应包含类似图3的曲线图 随着序列长度N的增加QUBO求解器得到的归一化能量平均值显著高于PUBO求解器并且其波动范围标准差急剧增大。这意味着对于QUBO不仅找到的解更差而且每次运行的结果好坏靠运气非常不稳定。相反PUBO求解器的曲线始终紧贴更低的能量值且波动范围非常窄。即使在N增大到接近100时它依然能保持稳定的高性能输出。这直观地证明对于这种原生高阶问题降阶过程引入的额外变量和复杂的能量地貌严重干扰了模拟退火搜索的效率和稳定性。PUBO直接求解保留了问题最简洁的本质结构让求解器能够更高效、更稳定地找到优质解。3.3 VRP问题结果多目标权衡下的全面胜出对于VRP问题我们进行了更细致的分析。3.3.1 单实例深度分析我们固定客户点P11车辆V3然后调节权重参数α从0只关心总距离到1只关心距离均衡。结果如图所示 注此处用文字描述类似图4的三个子图总距离与方差权衡随着α增大更注重均衡两种方法的总距离都会略有增加因为为了均衡可能需要绕路但PUBO的增长更平滑、波动更小。在方差指标上PUBO能稳定地将方差降到更低水平。总目标函数值在所有α取值下PUBO得到的总目标函数值(1-α)f1 αf2都系统性地低于QUBO。这说明在综合考量下PUBO找到了更优的折衷方案。解集分布我们将所有α下得到的可行解画在“总距离-方差”二维图上类似图5的散点图。PUBO的解密集地分布在靠近坐标原点的帕累托前沿附近形成了一个清晰的权衡边界。而QUBO的解则非常分散很多解既距离长又不均衡只有少数解能勉强接近PUBO的边界且无法达到方差最小的区域。这揭示了一个关键问题降阶过程可能破坏了方差项包含四阶交互的内在结构导致求解器在优化这个目标时“力不从心”。3.3.2 多实例超体积对比为了进行更具统计意义的比较我们生成了30个随机的VRP实例客户点位置随机分布。对每个实例我们都用两种方法求解并计算其帕累托解集的超体积指标。结果呈现出一边倒的趋势类似图6所有30个数据点都落在yx参考线的下方。这意味着在每一个随机生成的实例上PUBO求解器得到的解集超体积都大于QUBO求解器。这是一个非常强有力的证据表明PUBO直接求解在多目标优化中能更一致地获得质量更高、多样性更好的解集这不是个别例子下的偶然而是其表述优势的普遍体现。3.3.3 可扩展性分析问题规模增大时会发生什么我们进一步增加了客户点数量P观察两种方法的可扩展性。结果非常说明问题类似图7可行性率当P较小时≤11两者都能100%找到可行解。但随着P增大QUBO求解器找到可行解的成功率开始显著下降。而PUBO求解器直到P17仍能保持很高的可行性率。降阶引入的额外约束使得满足所有条件的难度激增。超体积衰减随着P增大两种方法得到的解集超体积都会下降问题变难了但QUBO的下降速度明显更快。在P17时其超体积值已远低于PUBO。这表明问题规模越大降阶带来的负面效应变量膨胀、搜索空间扭曲就越凸显PUBO直接求解的鲁棒性优势就越明显。4. 核心优势拆解与深度讨论实验数据已经清晰地指向了结论但我们还需要深入挖掘背后的“为什么”。PUBO的优势并非空中楼阁而是源于其避免了QUBO降阶带来的几个根本性代价。4.1 变量膨胀搜索空间的指数级爆炸这是最直观的代价。降阶过程每引入一个辅助变量问题的搜索空间就扩大一倍。我们对比了两种表述下变量数量随问题规模的增长类似图8。对于LABS问题变量数随序列长度N的增长QUBO formulation 的曲线斜率远大于PUBO。对于一个大规模问题QUBO所需的变量数可能是PUBO的数十倍。对于VRP问题随着客户点P增加变量数的差距也迅速拉大。这意味着什么模拟退火等搜索算法是在由所有变量构成的解空间中进行漫游。变量数量直接决定了这个空间的维度。维度爆炸就是著名的“维度灾难”搜索算法需要探索的角落呈指数级增长找到高质量解的难度和所需时间也随之剧增。PUBO通过保留紧凑的原生形式从根本上遏制了这种维度膨胀。4.2 惩罚系数调优一个棘手的黑箱在替代法中惩罚系数p的选取至关重要。我们针对LABS问题系统测试了不同序列长度N下惩罚系数p从1.0到10.0对解质量的影响类似图9的热力图。结果发现不存在一个“放之四海而皆准”的最优p值。对于不同的N能取得最好结果的p值各不相同。这张热图看起来就像一幅变化莫测的抽象画。在实际应用中这意味着如果你想用好QUBO求解器处理高阶问题你必须为每一具体问题、甚至每一个问题规模去费力地调整这个惩罚系数。这无疑增加了巨大的工程成本和不确定性。而PUBO求解器完全避开了这个陷阱因为它根本不需要引入这个额外的惩罚项。4.3 能量地貌的扭曲当平坦山谷变成崎岖山地这是更深层次、也更关键的一点。模拟退火算法的核心是接受准则它以一定概率接受使能量变高的“坏”移动以跳出局部最优。这个概率取决于能量差ΔE与当前温度T的比值ΔE/T。降阶过程通过引入辅助变量和惩罚项改变了原始问题的能量地貌。虽然从全局最优解的数学等价性上看两者是一致的但搜索路径上的风景被彻底改变了。原本平缓的斜坡可能变成陡峭的悬崖宽阔的谷底可能布满碎石局部极值点。这种扭曲会导致两个后果可行性陷阱与约束相关的惩罚项如果设置得很大会在可行域边界竖起极高的能量壁垒。模拟退火在有限温度下可能没有足够的“热能”翻越这些壁垒从而被困在不可行区域导致可行性率下降——这在我们的VRP可扩展性实验中得到了印证。搜索效率降低扭曲的地貌增加了局部最优点的数量使得算法更容易陷入其中。同时它也可能模糊了不同目标之间的真实权衡关系导致在多目标优化中无法有效探索帕累托前沿——这解释了为什么QUBO在VRP问题中得到的解集分布更散、超体积更小。PUBO直接求解则忠实地保留了原始问题的能量地貌。求解器是在最真实的地形上搜索自然能更高效、更准确地找到最优区域。4.4 对实际工作的启示基于以上分析对于从事组合优化相关研究和应用的工程师、研究员来说可以得出以下几点实操建议优先评估问题结构在接手一个新问题时首先分析其数学形式。如果目标函数或约束中天然包含了三次及以上的变量乘积项那么它就是一个高阶问题。不要下意识地就去着手降阶。探索直接求解的可能性调研可用的工具。像本文使用的Amplify AE这类支持PUBO的求解器正在增多。如果存在应优先尝试直接使用PUBO formulation进行建模和求解。这往往能省去降阶的麻烦并获得更优、更稳定的结果。如果必须降阶例如硬件限制意识到代价明确知道你会面临变量膨胀、惩罚系数调优和能量地貌扭曲三大挑战。精心设计降阶策略对于结构化的问题像替代法这样能复用辅助变量的方法可能更优。对比不同降阶方法如Ishikawa-KZFD方法带来的变量增长可参考原文附录A的对比图。系统化调参将惩罚系数的调优作为一个必须的步骤。可以采用网格搜索、基于问题规模的经验公式或自适应方法来确定相对合适的p值。管理预期对于大规模问题要对QUBO求解器的性能下降解质量波动、可行性率降低有心理准备并在系统设计时留有余地。5. 常见问题与实战避坑指南在实际操作中从理论理解到成功运行一个优化模型中间可能会遇到不少坑。这里结合我的经验总结几个常见问题和注意事项。5.1 如何判断我的问题是否是“高阶”的这听起来简单但有时容易忽略。不仅仅要看目标函数。一个常见误区是只检查目标函数是否为二次型。必须同时检查约束条件。例如一个经典的“恰好一个”约束Σ_i x_i 1在转化为惩罚项(Σ_i x_i - 1)^2时展开后就是二次型。但是如果你有一个约束要求“最多一个” (Σ_i x_i ≤ 1)通常需要引入辅助变量将其转化为等式约束这个过程可能会产生高阶项。再比如涉及逻辑“与”AND或“或”OR的条件用二次型精确表达往往需要技巧有时直接使用高阶项更自然。建模时务必展开所有惩罚项检查变量的最高次幂。5.2 使用PUBO求解器建模时有什么不同最大的不同是自由度和简洁性。你不再需要费尽心机地把一个x1*x2*x3拆成y12*x3 P*(...)。你可以直接写出x1*x2*x3。这大大降低了建模的复杂度也减少了出错的可能。但是这也要求你对问题有更本质的理解能直接写出其多项式形式。同时要注意当前求解器支持的最高阶数例如Amplify AE支持到四阶。如果你的问题包含五阶及以上项可能仍需部分降阶或寻找其他支持更高阶的求解器。5.3 惩罚系数μ在PUBO中还存在吗是的但含义不同了。在PUBO模型中惩罚系数μ仍然存在但它用于处理约束条件而不是用于处理降阶。例如在VRP问题中μ用来加权约束惩罚项g1(x)g2(x)g3(x)。这个μ的调优同样重要但它调优的是“约束的严格程度”而不是“降阶的准确性”。一般来说μ需要设置得足够大以确保搜索过程倾向于满足约束的解但也不能过大以免掩盖了原始目标函数的细节。一个实用的启发式方法是将μ设置为与目标函数典型值相当或略大的量级。5.4 对于超大规模问题PUBO是否一定比QUBO快本文主要对比了解的质量和稳定性。在计算时间上实验设定为固定时间60秒两者表现相当。但这并不意味着在所有场景下时间都一样。变量数量直接影响求解器单次迭代的计算开销。QUBO模型变量多意味着每次计算能量差ΔE时需要求和更多的项。虽然现代求解器如基于GPU的Amplify AE对此有高度优化但在极端大规模下变量数的差异最终可能会转化为实际计算时间的差异。PUBO模型变量少单次迭代可能更快从而在固定时间内进行更多次搜索。这一点需要结合具体求解器的实现来评估。5.5 除了模拟退火其他算法也能受益于PUBO吗非常可能。本文的结论虽然基于模拟退火但其核心逻辑——避免降阶带来的变量膨胀和问题变形——是普适的。其他元启发式算法如遗传算法、禁忌搜索、粒子群优化等同样在一个定义好的解空间由变量定义和能量地貌由目标函数定义上搜索。一个更紧凑、更真实的搜索空间和地貌对任何搜索算法都是有利的。事实上近期一些基于量子近似优化算法QAOA和模拟分岔机的研究也显示了直接处理PUBO的优势。因此当你使用任何优化算法时如果它支持直接处理高阶项都值得优先尝试PUBO formulation。5.6 实战避坑清单建模第一步先画变量交互图在纸上画出变量之间的依赖关系。如果出现三个或以上变量同时在一个约束或目标项中交互就要警惕高阶项。优先使用原生支持高阶的建模库例如Amplify SDK它允许你直接用数学表达式定义高阶项库会自动处理底层表述无需手动降阶。从小规模实例开始验证无论用PUBO还是QUBO先用一个极小规模的问题比如LABS的N5VRP的P3跑通整个流程。验证解的正确性是否满足约束目标值是否合理。监控可行性率对于约束问题在调试阶段务必输出每次运行的约束违反程度。如果可行性率很低首先检查惩罚系数μPUBO或pQUBO降阶是否设置合理而不是盲目增加运行时间。解的可视化对于像VRP这样的问题将求得的路线画出来。一个看起来乱七八糟的路线图比任何数字都更能告你求解可能出了问题无论是建模错误还是参数设置不当。理解你的求解器阅读求解器的文档了解它对PUBO的支持程度最高阶数、性能特点、默认的参数设置以及推荐的调参范围。不要把它当黑盒。直接使用PUBO formulation处理高阶组合优化问题在模拟退火框架下展现出了显著且稳定的优势。它通过避免降阶过程从根本上消除了变量膨胀、惩罚系数调优和能量地貌扭曲三大痛点从而在解质量、稳定性和多目标权衡表达能力上均优于传统的QUBO降阶方法。随着支持高阶项直接求解的软硬件工具日益成熟对于物流、调度、芯片设计、金融等领域的从业者而言在遇到天然包含高阶交互的复杂优化问题时将PUBO作为首选的建模和求解路径是一个值得认真考虑的高效策略。这不仅仅是技术选型的变化更是一种思维方式的转变从“如何把问题塞进硬件”转向“如何最自然地表达问题本身”。
