量子退火求解双目标旅行小偷问题：ε约束法与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存在几个核心挑战：

1. 多目标与单次求解的矛盾：量子退火一次运行通常只输出一个能量最低的解（对应一个单目标优化问题）。而BI-TTP需要得到一系列帕累托最优解。
2. 问题建模的复杂性：BI-TTP的目标函数中包含分式项（旅行时间 = 距离 / 速度，而速度又是背包累积重量的函数），这无法直接映射到量子退火器求解的标准模型——二次无约束二进制优化模型。
3. 硬件限制：当前处于含噪声中等规模量子时代，量子比特数量有限，相干时间短，直接求解大规模问题精度受限。

针对这些挑战，我们提出并实践了一种创新的混合求解框架：基于ε约束法的量子退火求解方法。这个框架的核心思想是，利用ε约束法将双目标问题分解为一系列单目标子问题，再通过巧妙的数学变换，将每个子问题（包含分式目标）转化为等价的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, ε_{s+1}]区间内以及背包容量约束的前提下，最小化总旅行时间。

为什么用ε约束法而不是加权求和法？加权求和法（将两个目标线性加权合并为一个目标）是另一种常见的标量化方法。但它在处理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是单调不减的。

基于这些变量，两个目标函数可以重写为：

1. 旅行时间f(X, Z)：总时间是各段路程时间之和。第i段路程（从第i个城市到第i+1个城市）的时间是距离除以速度。速度v_i是当前背包重量W_i的线性函数：v_i = v_max - (W_i / W) * (v_max - v_min)。因此，f(X, Z)是一个关于X和W_i（而W_i又是Z的函数）的复杂分式求和。
2. 总收益g(X, Z)：所有被偷物品的价值之和的相反数（因为我们统一处理为最小化问题）。

约束条件包括：背包总重量不超过容量W；X和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)来进一步降低目标函数值，这与最优性矛盾。

基于这个等价形式，我们设计了一个交替优化迭代算法：

1. 固定b，优化(X, Z)：此时目标函数是Σ [A_i(X, Z) / b_i]，由于b_i是常数，这变成了一个关于X和Z的二次函数（分子A_i是二次的）。结合所有线性/二次约束，这正好是D-Wave CQM求解器可以处理的格式。我们调用求解器得到一个候选解(X_QA, Z_QA)。
2. 应用LEA启发式：对量子求解器返回的解(X_QA, Z_QA)应用“延迟足量积累”启发式，得到改进的解(X, Z)。
3. 固定(X, Z)，更新b：根据等式b_i = B_i(X, Z)更新辅助变量。这一步是闭式更新，计算量很小。
4. 迭代：用新的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) ≤ ε_{s+1}。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_n149（150城149物）和a280_n279（280城279物）。后者是EMO-2019、GECCO-2019等国际竞赛的官方测试用例。物品重量分布考虑了三种典型情况：有界强相关、不相关、不相关但重量相似。

对比算法：我们选择了三个经典的多目标进化算法作为基线：

1. NSGA-II：采用非支配排序和拥挤度距离保持多样性。
2. U-NSGA-III：使用参考点集来引导搜索方向，旨在获得分布均匀的帕累托前沿。
3. 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）。结���表明：

• S=10是一个较好的权衡点。S=5时区间太宽，约束不够精细，解的质量较低；S=15时质量仅有轻微提升，但计算量几乎线性增加。
• 均匀初始化策略（将[g_min, g_max]均匀分割） consistently 优于随机初始化策略。均匀初始化能确保对目标空间的系统性和均匀探索，而随机初始化可能导致搜索资源浪费在某些区域，而其他区域探索不足。

5. 实操心得、常见问题与未来展望

5.1 实操心得与避坑指南

在实际实现和运行这个量子-经典混合框架时，我总结出以下几点经验：

1. QUBO建模的“艺术”：将现实问题转化为QUBO模型是一门艺术。对于BI-TTP，最大的障碍是分式目标。我们的“辅助变量+迭代优化”策略是一个通用性很强的技巧，可以推广到其他含有分式或更复杂非线性项的组合优化问题中。关键在于找到合适的等价变换，将非二次型项“吸收”或“线性化”。
2. 约束权重的自动调优：早期我们尝试手动将约束作为惩罚项加入目标函数，但惩罚系数λ的选择极其困难，过大或过小都会导致求解失败。强烈推荐使用D-Wave的CQM求解器，它内建了自动约束处理机制，省去了手动调参的繁琐过程，极大地提高了开发效率和求解稳定性。
3. 混合求解器的使用策略：D-Wave的混合求解器并非“黑箱”。提交问题前，尽量对变量进行预处理。例如，对于BI-TTP，我们可以预先计算城市间距离矩阵，并确保其格式符合求解器输入要求。同时，要合理设置求解时间限制（time_limit）。对于复杂问题，给予更长的求解时间通常能获得更好的解，但需要权衡成本。
4. 后处理的重要性：在当前NISQ时代，量子硬件返回的“原始解”往往不是完美的。设计一个与问题领域知识紧密相关的后处理启发式（如我们的LEA）是提升最终解质量的关键一步。这一步通常计算量很小，但收益巨大。
5. ε区间数量的选择：S的选择需要平衡探索粒度与计算成本。我们的实验表明，S取目标范围值的10%到20%左右是一个不错的起点。可以先用一个较小的S进行快速测试，再根据解集的分布情况决定是否增加S以获取更精细的前沿。

5.2 常见问题与排查

• 问题：求解器返回“无可行解”。
  • 排查：首先检查ε区间[ε_s, ε_{s+1}]是否在理论范围[g_min, g_max]内。如果ε_s > g_max或ε_{s+1} < g_min，子问题本身就是不可行的。其次，检查背包容量W是否设置得过小，导致任何非空的偷取方案都不可行。最后，检查模型中的约束是否互相冲突（例如，某些城市物品的总价值下限ε_s设置得过高，即使偷取所有物品也无法达到）。
• 问题：量子求解时间过长，超出预算。
  • 排查：检查问题规模。如果变量数超过10万，混合求解器可能需要较长时间。可以考虑以下优化：1) 减少城市或物品数量（如果允许）；2) 减少分段数量S；3) 在CQM模型中设置更严格的time_limit参数。此外，确保网络连接稳定，因为与云端QPU的通信延迟也会计入总时间。
• 问题：帕累托前沿分布不均匀，两端缺失解。
  • 排查：这通常是因为ε区间设置不够“紧”或者量子求解器在极端区间内搜索能力不足。可以尝试：1) 增加分段数量S；2) 对于g_min和g_max附近的区间，可以手动微调ε值，或者在这些区间内进行更密集的采样（非均匀分割）；3) 检查LEA启发式是否在极端情况下过于激进地丢弃了物品，可以适当修改其接受准则。
• 问题：结果复现性差。
  • 排查：量子退火本身具有一定概率性。为了获得可重复的结果，务必在代码中设置随机数种子（对于经典部分），并为D-Wave求解器设置固定的random_seed参数（如果支持）。对于最终报告的结果，应进行多次独立运行，取统计指标（如平均HV、标准差）。

5.3 未来展望与应用扩展

这项工作为利用量子计算解决复杂的多目标组合优化问题打开了一扇门。我个人认为，未来的方向可以从以下几个层面展开：

1. 算法层面：可以探索更智能的ε区间自适应调整策略，而不是简单的均匀分割。例如，根据前一轮求解结果的分布密度，动态调整下一轮ε区间的疏密，将计算资源集中在帕累托前沿变化剧烈的区域。
2. 模型层面：我们的框架具有一定的通用性。可以尝试将其应用于其他具有类似“旅行”+“资源收集”双目标结构的实际问题，如带时间窗和装载约束的车辆路径问题、芯片设计中的布局与布线联合优化等。
3. 硬件与软件协同：随着量子硬件的进步，比特数增加，噪声降低，我们可以直接求解更大规模的QUBO模型，减少对经典分解和迭代的依赖。同时，期待量子软件开发工具链更加成熟，提供更便捷的多目标优化原语支持。
4. 混合范式深化：除了量子退火，也可以考虑将ε约束法与量子近似优化算法、变分量子本征求解器等其他量子算法范式结合，探索在不同类型问题上的性能表现。

将量子计算应用于实际优化问题，目前仍是一条需要不断探索和工程打磨的道路。这项研究展示了一条可行的技术路径：通过严谨的数学建模将问题转化为量子硬件友好的形式，再结合经典优化中的成熟思想（如ε约束法）和领域启发式知识，构建高效的量子-经典混合求解方案。这条路或许漫长，但每一次成功的应用，都让我们离量子优势的实用化更近一步。