量子退火求解双目标旅行小偷问题：ε约束法与QUBO建模实践

1. 项目概述与核心挑战双目标旅行小偷问题Biobjective Traveling Thief Problem, BI-TTP是一个典型的NP难多目标组合优化问题。它巧妙地将两个经典的NP难问题——旅行商问题Traveling Salesman Problem, TSP和背包问题Knapsack Problem——融合在一个统一的框架内。在这个问题中一个小偷需要访问一组城市每个城市都有若干具有不同价值和重量的物品可供偷取。小偷的目标是在满足背包容量限制的前提下规划一条访问所有城市恰好一次的路线并决定在每个城市偷取哪些物品以同时最小化总旅行时间和最大化总物品价值。这两个目标本质上是冲突的。偷取更多、更重的物品能增加总收益但会降低小偷的旅行速度因为背包更重了从而增加旅行时间。反之为了快速旅行小偷可能不得不放弃一些高价值的物品。因此不存在一个单一的“最优解”而是一系列“帕累托最优解”Pareto Front每个解都在两个目标之间做出了不同的权衡。传统的经典算法如多目标进化算法MOEA/D, NSGA-II, U-NSGA-III在求解此类问题时随着问题规模城市数、物品数的增大会面临“组合爆炸”的挑战计算时间急剧增加且难以保证解的质量和多样性。近年来量子计算特别是量子退火为解决这类组合优化问题提供了新的可能性。量子退火器如D-Wave能够利用量子叠加和隧穿效应在庞大的解空间中并行搜索有望更快地找到高质量的解。然而直接将量子退火应用于BI-TTP存在几个核心挑战多目标与单次求解的矛盾量子退火一次运行通常只输出一个能量最低的解对应一个单目标优化问题。而BI-TTP需要得到一系列帕累托最优解。问题建模的复杂性BI-TTP的目标函数中包含分式项旅行时间 距离 / 速度而速度又是背包累积重量的函数这无法直接映射到量子退火器求解的标准模型——二次无约束二进制优化模型。硬件限制当前处于含噪声中等规模量子时代量子比特数量有限相干时间短直接求解大规模问题精度受限。针对这些挑战我们提出并实践了一种创新的混合求解框架基于ε约束法的量子退火求解方法。这个框架的核心思想是利用ε约束法将双目标问题分解为一系列单目标子问题再通过巧妙的数学变换将每个子问题包含分式目标转化为等价的QUBO模型最后交由D-Wave量子退火器求解并用一个定制化的启发式后处理步骤来提升解的质量。2. 核心思路ε约束法与量子退火的融合我们的方法可以概括为“分而治之”与“量子加速”的结合。其整体流程如下图所示概念性描述第一步确定目标范围。我们首先需要知道小偷可能获得的总收益第二个目标的范围。最小值g_min可以通过求解一个只关注最大化收益忽略旅行时间的背包问题得到最大值g_max很简单就是不偷任何物品收益为0。这个步骤本身也是一个QUBO问题可以直接用D-Wave求解。第二步均匀分割构造子问题。将收益范围[g_min, g_max]均匀分割成S个区间[ε_0, ε_1],[ε_1, ε_2], ...,[ε_{S-1}, ε_S]其中ε_0 g_min,ε_S g_max。对于第s个子问题我们将第二个目标总收益约束在这个区间内从而将原双目标问题转化为一个单目标优化问题在满足总收益在[ε_s, ε_{s1}]区间内以及背包容量约束的前提下最小化总旅行时间。为什么用ε约束法而不是加权求和法加权求和法将两个目标线性加权合并为一个目标是另一种常见的标量化方法。但它在处理BI-TTP这类目标间存在复杂非线性交互的问题时效果不佳。主要原因是权重难以选择且无法保证找到帕累托前沿上非凸部分的解。ε约束法则通过直接控制一个目标的取值区间能更系统、更均匀地探索整个目标空间尤其适合与每次只返回一个解的量子退火器结合。第三步数学变换适配量子硬件。这是技术上的关键一步。每个子问题的目标函数是分式求和的形式不满足QUBO的二次型要求。我们引入了一组辅助变量b_i并证明原问题等价于一个关于(X, Z, b)的优化问题其中目标函数的分母被b_i替代并增加约束b_i ≤ B_i(X, Z)。通过固定b迭代优化(X, Z)再根据当前解更新b的交替优化方法我们将每个迭代步中的子问题转化为了一个标准的、带线性/二次约束的二次优化问题这正是D-Wave混合约束二次模型求解器可以直接处理的格式。第四步量子求解与后处理。对每个子问题我们使用D-Wave的混合求解器来寻找(X, Z)的优化解。由于当前量子硬件的噪声限制返回的解可能不是全局最优。因此我们设计了一个名为“延迟足量积累”的启发式规则对解进行微调。其核心思想是在满足收益约束的前提下尽量将偷取物品的行为安排到旅行路线的后半段。因为背包重量越轻旅行速度越快。晚点偷东西意味着前面路程负重更轻、速度更快从而可能减少总时间。第五步整合帕累托前沿。求解完所有S个子问题后我们将得到S个候选解。最后我们从这组解中筛选出所有互不支配的解就构成了对真实帕累托前沿的一个近似。这个框架巧妙地将多目标优化的系统性与量子计算的并行搜索能力结合了起来。ε约束法确保了我们对目标空间的均匀探索而量子退火则为每个复杂的单目标子问题提供了高效的求解引擎。3. 从问题定义到QUBO模型的详细转换要让量子退火器工作我们必须将BI-TTP的数学描述“翻译”成它懂的语言——QUBO模型。这个过程充满了细节和技巧。3.1 问题形式化与二进制编码首先我们严格定义变量路线变量X定义一个二进制矩阵X其元素x_{v,i} 1表示城市v是旅行路线中第i个访问的城市。这自然地编码了一个排列。为了确保是有效的哈密顿回路每个城市访问一次且仅一次需要添加行约束和列约束。偷取变量Z定义一个二进制矩阵Z其元素z_{t,k} 1表示偷取位于城市t的第k个物品。背包重量W_i访问完第i个城市后背包的累积重量。由于物品一旦偷取就不能丢弃W_i是单调不减的。基于这些变量两个目标函数可以重写为旅行时间f(X, Z)总时间是各段路程时间之和。第i段路程从第i个城市到第i1个城市的时间是距离除以速度。速度v_i是当前背包重量W_i的线性函数v_i v_max - (W_i / W) * (v_max - v_min)。因此f(X, Z)是一个关于X和W_i而W_i又是Z的函数的复杂分式求和。总收益g(X, Z)所有被偷物品的价值之和的相反数因为我们统一处理为最小化问题。约束条件包括背包总重量不超过容量WX和Z的二进制变量约束以及X的行列约束确保是有效排列。3.2 处理分式目标辅助变量与迭代优化分式目标f(X, Z)是转化为QUBO的最大障碍。我们的策略是引入辅变量b_i将原问题24等价转化为问题25原问题 (24): minimize Σ [A_i(X, Z) / B_i(X, Z)] 等价问题 (25): minimize Σ [A_i(X, Z) / b_i], subject to 0 b_i ≤ B_i(X, Z)其中A_i是第i段路程的距离相关项B_i是速度分母项。关键证明在于在最优解处不等式约束b_i ≤ B_i(X, Z)一定会取等号b_i B_i(X, Z)。否则我们可以通过增大b_i到B_i(X, Z)来进一步降低目标函数值这与最优性矛盾。基于这个等价形式我们设计了一个交替优化迭代算法固定b优化(X, Z)此时目标函数是Σ [A_i(X, Z) / b_i]由于b_i是常数这变成了一个关于X和Z的二次函数分子A_i是二次的。结合所有线性/二次约束这正好是D-Wave CQM求解器可以处理的格式。我们调用求解器得到一个候选解(X_QA, Z_QA)。应用LEA启发式对量子求解器返回的解(X_QA, Z_QA)应用“延迟足量积累”启发式得到改进的解(X, Z)。固定(X, Z)更新b根据等式b_i B_i(X, Z)更新辅助变量。这一步是闭式更新计算量很小。迭代用新的b重复步骤1-3直到目标函数值不再下降或达到迭代次数上限。这个迭代过程是收敛的因为每次更新b后约束集{b_i ≤ B_i(X, Z)}变得更紧b_i增大搜索空间单调减小而目标函数值在每次迭代中不增。3.3 约束处理与模型规模在将问题提交给D-Wave CQM求解器时我们需要处理几种约束等式约束如Σ x_{v,i} 1每行每列约束。在QUBO框架下通常将其作为惩罚项λ * (Σ x_{v,i} - 1)^2加入目标函数。幸运的是D-Wave的混合CQM求解器可以原生处理线性等式和不等式约束无需手动设置惩罚系数λ这大大简化了建模过程。不等式约束如背包容量约束W_N ≤ W和收益区间约束ε_s ≤ g(X, Z) ≤ ε_{s1}。CQM求解器同样支持。变量规模分析是评估问题是否能在当前量子硬件上求解的关键。对于N个城市每个城市最多有M个物品的问题路线变量X需要N * N N^2个二进制变量。偷取变量Z最多需要N * M个二进制变量。 因此总变量数约为N^2 N*M。对于a280_n279这样的基准实例280个城市279个物品变量数将达到约280^2 280*279 ≈ 156, 520个。这超出了当前量子退火器原生硬件的直接映射能力但仍在D-Wave混合求解服务支持最多50万个变量和10万个约束的处理范围内。混合求解器会智能地将问题分解部分在量子处理器上计算部分在经典计算机上计算。4. 实验设置与结果分析我们通过系统的实验来验证所提方法的有效性并与经典的先进算法进行对比。4.1 实验配置与基准环境与硬件实验在Kaggle平台上进行使用Intel Xeon CPU。量子计算部分使用D-Wave Advantage2量子处理器通过其Leap云服务访问混合CQM求解器。报告的运行时间是求解器的总处理时间包括QPU访问时间和经典后处理时间。数据集采用了来自文献的标准BI-TTP基准实例ch150_n149150城149物和a280_n279280城279物。后者是EMO-2019、GECCO-2019等国际竞赛的官方测试用例。物品重量分布考虑了三种典型情况有界强相关、不相关、不相关但重量相似。对比算法我们选择了三个经典的多目标进化算法作为基线NSGA-II采用非支配排序和拥挤度距离保持多样性。U-NSGA-III使用参考点集来引导搜索方向旨在获得分布均匀的帕累托前沿。MOEA/D通过分解将多目标问题转化为多个单目标子问题并协同优化。评价指标超体积这是多目标优化中衡量帕累托前沿质量的黄金标准。它计算被解集所支配的目标空间体积相对于一个设定的参考点。HV值越大说明解集的质量越高更接近真实前沿且多样性越好覆盖范围更广。运行时间记录算法从开始到输出最终帕累托前沿所花费的总时间。4.2 性能对比质量与效率我们将所提的“QA-ε”方法与三个经典算法在a280_n279实例上进行了对比。图2展示了HV随进化代数对经典算法或等效运行过程的变化曲线。一个关键发现是我们的量子混合方法在单次运行中对应图中横坐标的起点就产生了一个完整且高质量的帕累托前沿。图中QA-ε曲线的轻微下降趋势并非解的质量退化而是因为我们在每个迭代点将经典算法当前产生的解集与QA-ε的固定解集合并计算HV经典算法初期较差的解拉低了整体HV值。从结果可以看出解的质量在所有三种物品分布下QA-ε方法获得的HV值始终高于0.7表明其产生的解集质量高、分布广。特别是在复杂的“有界强相关”分布下U-NSGA-III即使经过10,000代进化其HV也未能超越QA-ε单次运行的结果。解的分布图3直观展示了各算法产生的帕累托前沿。QA-ε方法由于采用了均匀的ε区间分割其解在第二个目标收益轴上分布非常均匀完整覆盖了从g_min到g_max的整个范围。而NSGA-II和U-NSGA-III的解分布则严重依赖于初始种群在某些实例上如a280_n279_unc解集中在中间区域未能探索到收益极高或极低的极端权衡点。MOEA/D的表现最差其解在收益目标上几乎坍缩到同一个值说明其分解策略在处理BI-TTP的复杂目标交互时失效了。运行时间优势更为显著。表2的数据显示在最大的a280_n279_bsc实例上QA-ε方法的总运行时间仅为NSGA-II的约1/8快了约8倍。随着问题规模从ch150_n149增大到a280_n279经典算法的运行时间增长幅度远大于QA-ε方法这凸显了量子混合方法在处理更大规模问题时的可扩展性优势。4.3 消融实验与深入分析为了深入理解我们方法中各组件的作用我们进行了一系列消融实验。ε约束法 vs. 加权求和法我们对比了使用ε约束法和加权求和法相同数量的子问题的QA求解效果。如表3所示在相同的运行次数下ε约束法获得的HV比加权求和法高出最多35%。这验证了我们的核心论点对于BI-TTP这类问题显式地控制一个目标的取值范围ε约束比简单地线性加权两个目标更有效能引导搜索找到更高质量、更多样化的解。LEA启发式的贡献LEA后处理步骤的计算开销极小不到总时间的0.5%但其效果显著。表3显示启用LEA后解的质量HV在所有测试实例上均有提升。图4给出了一个定性的例子对于a280_n279_bsc实例中旅行时间最短的那个解应用LEA后小偷的旅行速度曲线变得更加平缓前期负重更轻总旅行时间从约29,000秒大幅降低到约18,000秒提升了近40%。这直观地证明了“晚偷东西”这一直觉性启发式的强大威力。参数敏感性分析我们测试了分段数量S和ε值初始化策略的影响图5。结表明S10是一个较好的权衡点。S5时区间太宽约束不够精细解的质量较低S15时质量仅有轻微提升但计算量几乎线性增加。均匀初始化策略将[g_min, g_max]均匀分割 consistently 优于随机初始化策略。均匀初始化能确保对目标空间的系统性和均匀探索而随机初始化可能导致搜索资源浪费在某些区域而其他区域探索不足。5. 实操心得、常见问题与未来展望5.1 实操心得与避坑指南在实际实现和运行这个量子-经典混合框架时我总结出以下几点经验QUBO建模的“艺术”将现实问题转化为QUBO模型是一门艺术。对于BI-TTP最大的障碍是分式目标。我们的“辅助变量迭代优化”策略是一个通用性很强的技巧可以推广到其他含有分式或更复杂非线性项的组合优化问题中。关键在于找到合适的等价变换将非二次型项“吸收”或“线性化”。约束权重的自动调优早期我们尝试手动将约束作为惩罚项加入目标函数但惩罚系数λ的选择极其困难过大或过小都会导致求解失败。强烈推荐使用D-Wave的CQM求解器它内建了自动约束处理机制省去了手动调参的繁琐过程极大地提高了开发效率和求解稳定性。混合求解器的使用策略D-Wave的混合求解器并非“黑箱”。提交问题前尽量对变量进行预处理。例如对于BI-TTP我们可以预先计算城市间距离矩阵并确保其格式符合求解器输入要求。同时要合理设置求解时间限制time_limit。对于复杂问题给予更长的求解时间通常能获得更好的解但需要权衡成本。后处理的重要性在当前NISQ时代量子硬件返回的“原始解”往往不是完美的。设计一个与问题领域知识紧密相关的后处理启发式如我们的LEA是提升最终解质量的关键一步。这一步通常计算量很小但收益巨大。ε区间数量的选择S的选择需要平衡探索粒度与计算成本。我们的实验表明S取目标范围值的10%到20%左右是一个不错的起点。可以先用一个较小的S进行快速测试再根据解集的分布情况决定是否增加S以获取更精细的前沿。5.2 常见问题与排查问题求解器返回“无可行解”。排查首先检查ε区间[ε_s, ε_{s1}]是否在理论范围[g_min, g_max]内。如果ε_s g_max或ε_{s1} g_min子问题本身就是不可行的。其次检查背包容量W是否设置得过小导致任何非空的偷取方案都不可行。最后检查模型中的约束是否互相冲突例如某些城市物品的总价值下限ε_s设置得过高即使偷取所有物品也无法达到。问题量子求解时间过长超出预算。排查检查问题规模。如果变量数超过10万混合求解器可能需要较长时间。可以考虑以下优化1) 减少城市或物品数量如果允许2) 减少分段数量S3) 在CQM模型中设置更严格的time_limit参数。此外确保网络连接稳定因为与云端QPU的通信延迟也会计入总时间。问题帕累托前沿分布不均匀两端缺失解。排查这通常是因为ε区间设置不够“紧”或者量子求解器在极端区间内搜索能力不足。可以尝试1) 增加分段数量S2) 对于g_min和g_max附近的区间可以手动微调ε值或者在这些区间内进行更密集的采样非均匀分割3) 检查LEA启发式是否在极端情况下过于激进地丢弃了物品可以适当修改其接受准则。问题结果复现性差。排查量子退火本身具有一定概率性。为了获得可重复的结果务必在代码中设置随机数种子对于经典部分并为D-Wave求解器设置固定的random_seed参数如果支持。对于最终报告的结果应进行多次独立运行取统计指标如平均HV、标准差。5.3 未来展望与应用扩展这项工作为利用量子计算解决复杂的多目标组合优化问题打开了一扇门。我个人认为未来的方向可以从以下几个层面展开算法层面可以探索更智能的ε区间自适应调整策略而不是简单的均匀分割。例如根据前一轮求解结果的分布密度动态调整下一轮ε区间的疏密将计算资源集中在帕累托前沿变化剧烈的区域。模型层面我们的框架具有一定的通用性。可以尝试将其应用于其他具有类似“旅行”“资源收集”双目标结构的实际问题如带时间窗和装载约束的车辆路径问题、芯片设计中的布局与布线联合优化等。硬件与软件协同随着量子硬件的进步比特数增加噪声降低我们可以直接求解更大规模的QUBO模型减少对经典分解和迭代的依赖。同时期待量子软件开发工具链更加成熟提供更便捷的多目标优化原语支持。混合范式深化除了量子退火也可以考虑将ε约束法与量子近似优化算法、变分量子本征求解器等其他量子算法范式结合探索在不同类型问题上的性能表现。将量子计算应用于实际优化问题目前仍是一条需要不断探索和工程打磨的道路。这项研究展示了一条可行的技术路径通过严谨的数学建模将问题转化为量子硬件友好的形式再结合经典优化中的成熟思想如ε约束法和领域启发式知识构建高效的量子-经典混合求解方案。这条路或许漫长但每一次成功的应用都让我们离量子优势的实用化更近一步。