用于学习路由的混合量子-经典神经网络

# 用于学习路由的混合量子-经典神经网络
来源：https://arxiv.org/html/2609.00489
Alexsandro Santos da Rosa Júnior1 Marcoss Vinicius Reballo1 Cesar Augusto do Amaral1,2 Fernando Augusto Caletti de Barros1  
1Eldorado 研究院 – 阿雷格里港 – 南里奥格兰德州 – 巴西  
2物理系，圣卡塔琳娜联邦大学，弗洛里亚诺波利斯 88040-900，圣卡塔琳娜州，巴西  
3计算机系，南里奥格兰德州联邦大学，阿雷格里港，巴西  
\{marcus\.ritt\.BE, alexsandro\.junior, marcos\.reballo, cesar\.amaral\.BE, fernando\.barros\}@eldorado\.org\.br

###### 摘要

本工作研究了混合量子-经典神经网络在学习路由启发式算法方面的应用。具体而言，本文探讨了小型量子神经网络能否在保持解质量的前提下，替代基于注意力机制的竞争性路由模型中的参数密集模块。针对带容量约束的车辆路径问题，编码器前馈层替换被证明是最有前景的设计方案：它在模型参数数量减少56.6%的同时，使混合模型在小规模和中等规模实例上接近经典神经网络基线，尽管在较大规模实例上差距会扩大。本研究还与经典路由算法进行了比较，后者在固定的欧几里得测试集上仍然具有高度竞争力且通常表现更优。因此，我们的结果并未表明存在量子优势或求解器主导地位，而是确定了编码器前馈层替换作为一种针对神经组合优化的可行混合模块压缩策略。

###### 关键词

车辆路径问题，混合量子-经典神经网络，神经组合优化，量子机器学习。

## 1 引言

关于通过学习解决组合优化问题的研究仍在持续进行中，特别是通过训练神经网络从采样实例中求解问题，而非手动设计特定问题的算法。然而，当前用于此任务的神经架构参数过多，在近期设备上难以完全由量子神经网络替代。

本文研究混合量子-经典解决方案是否能以更少的参数实现良好性能，从而为可能用量子版本替换经典神经网络特定组件指明方向。本工作聚焦于经典的带容量约束的车辆路径问题，这是一个具有直接实际相关性的强NP难路由问题（Dantzig and Ramser, 1959 (https://arxiv.org/html/2609.00489#bib.bib1)）。

解决CVRP的经典方法范围从精确的分支切割建模到各种各样的构造性、局部搜索启发式以及元启发式算法，这些在实践中仍然非常有效（Toth and Vigo, 2014 (https://arxiv.org/html/2609.00489#bib.bib15); Bogyrbayeva et al., 2024 (https://arxiv.org/html/2609.00489#bib.bib14)）。与此同时，人们对量子优化方法如QAOA和VQE的兴趣日益增长，这些方法通常将路由问题编码为QUBO公式，然后转换为等效的伊辛哈密顿量以在量子硬件上实现，并将其作为变分混合量子-经典程序来解决。最近，提出了量子机器学习方法，其中参数化量子电路充当更大模型中的可学习组件。然而，当前的量子设备和模拟器严重限制了电路的宽度和深度，这使得替换整个路由神经架构变得困难。因此，本工作关注一个更具体的问题：小型量子神经网络模块能否在保持大部分解质量的前提下，替代竞争性经典神经模型的参数密集子组件。

CVRP可以定义如下。设 $V=\{0,1,...,n\}$ 为节点集合，其中 $0$ 代表车场，$N=\{1,...,n\}$ 表示客户。节点 $i$ 和 $j$ 之间的距离为 $d_{ij}$，客户 $i$ 的需求为 $q_{i}$，其中 $q_{0}=0$。问题假设使用同质车队，所有车辆的容量均为 $Q$。目标是服务所有客户，同时最小化所有车辆的总行驶距离。

该问题可以理解为对客户集合 $N$ 的一个划分，其中每个部分与车场一起构成一条路线，使得路线的总成本最小。对于一条路线 $r$，令 $V(r)$ 为该路线服务的客户集合，对于任意客户集合 $S \subseteq N$，用 $\mathcal{R}$ 表示服务它们的一组可行路线，其中路线 $r \in \mathcal{R}$ 是可行的，如果
$$
\sum_{i \in V(r)} q_{i} \leq Q. \tag{1}
$$
那么，$k(S)$ 可以定义为服务 $S \subseteq N$ 中客户所需的最少车辆数：
$$
k(S)=\min\left\{|\mathcal{R}|:S \subseteq \bigcup_{r \in \mathcal{R}} V(r), \text{可行路线集 } \mathcal{R}\right\}. \tag{2}
$$
引入二元决策变量 $x_{ij}$，当车辆从节点 $i$ 行驶到节点 $j$ 时取值为 $1$，否则为 $0$，该问题的标准基于弧的整数规划公式如下。目标是最小化总行驶距离，约束条件确保流量守恒和车场容量，容量切割约束保证可行性并消除子回路：

$$
\displaystyle \min. \sum_{\begin{subarray}{c}(i,j)\in V^{2}\\ i\neq j\end{subarray}} d_{ij} x_{ij}, \tag{3}
$$
$$
\displaystyle \text{s.t.} \sum_{j\in V\setminus\{i\}} x_{ij} = \sum_{j\in V\setminus\{i\}} x_{ji} = 1, \quad \forall i\in N, \tag{4}
$$
$$
\displaystyle \sum_{j\in N} x_{0j} \leq K, \tag{5}
$$
$$
\displaystyle \sum_{i\in S} \sum_{j\notin S} x_{ij} \geq k(S), \quad \forall S \subseteq N, S\neq\emptyset, \tag{6}
$$
$$
\displaystyle x_{ij} \in \{0,1\}, \quad \forall i,j \in V. \tag{7}
$$
这里，公式 (3) 最小化总距离，公式 (4) 确保每个客户恰好被进入和离开一次，公式 (5) 限制离开车场的车辆数至多为 $K$，公式 (6) 是容量切割约束，要求每个客户子集 $S$ 至少有 $k(S)$ 条弧离开，公式 (7) 强制整数性。注意约束 (6) 的数量是指数级的，因此该模型通常通过分支切割方法求解。

本文对解决CVRP做出了三个主要贡献。提出了一种用于解生成的混合量子-经典神经网络，通过实验验证了其鲁棒性，结果表明在将所需参数数量减少超过50%的同时，可以达到具有竞争力的性能。

## 2 混合量子-经典神经网络

该方法借鉴了 Kool et al. (2018) (https://arxiv.org/html/2609.00489#bib.bib4) 的工作，他们提出了一种用于学习二维欧几里得实例路由的经典神经网络。他们的模型包括一个编码器，该编码器接收车场和客户的位置以及客户需求，为每个节点生成一个表示。这些表示经过若干层处理，每一层结合了一个注意力机制（遵循 Vaswani et al. (2017) (https://arxiv.org/html/2609.00489#bib.bib8) 的 Transformer 架构）和一个前馈层。编码器之后，一个解码器（也采用注意力机制）迭代地扩展部分路径，直到获得完整路径。对于CVRP，该方法在20到100个客户的问题实例上取得了良好结果，涵盖了本工作所考虑的小到中等规模范围。

图 1 (https://arxiv.org/html/2609.00489#S2.F1) 展示了编码器，图 2 (https://arxiv.org/html/2609.00489#S2.F2) 展示了解码器。编码器包括一个初始节点嵌入，将每个节点的坐标和容量 $(x_i, y_i, q_i)$ 映射到一个维度为 $d_h$ 的潜在空间，接着是 $L$ 层，每层包含一个多头注意力（MHA）步骤（$M=8$ 个注意力头），后接一个带有一个隐藏层和 ReLU 激活函数的前馈（FF）网络，两者均带有残差连接。此外，在 MHA 和 FF 部分之后应用了批归一化。编码器为每个节点 $i \in V$ 产生最终的节点嵌入 $h_i$，以及一个图嵌入 $\overline{h}=\sum_{i\in V} h_i / |V|$。

解码器有一个单一的上下文节点，该节点由图、当前路径的第一个节点和当前路径的最后一个节点的嵌入组成。这个上下文节点关注所有其他节点的嵌入，以生成当前路径所有可能延续的离散概率分布。已经访问过的客户以及会使车辆容量超限的客户被遮蔽。基于此概率分布，路径被迭代地构建，可以在每一步贪心选择最可能的节点，或者通过采样。当没有可行的后续节点时，开启一条新路径。重复此过程直到所有客户被服务。

Kool et al. (2018) (https://arxiv.org/html/2609.00489#bib.bib4) 提议的隐藏层大小为 $d_h=128$，前馈网络中的隐藏层大小为 $512$。因此，各组件的大小以及每个前向步骤的评估次数如表 1 (https://arxiv.org/html/2609.00489#S2.T1) 所示。注意，解码器不使用通常的全局注意力机制，而是使用上下文节点到所有其他节点的一对多注意力。这是出于性能原因，因为解码器步骤必须重复 $n+k$ 次才能产生具有 $k$ 辆车的完整路由。尽管如此，这仍然是最热的路径，每次前向传播需要 $|V|^2$ 次评估。

表 1：经典注意力模型中组件的大小和每次前向传播的评估次数。
对于 $L=3$，超过一半的模型参数集中在前馈层，这些层位于关键的解码器路径之外。这一观察突出了混合化的一个有前景的机会，促使我们用量子神经网络替换前馈组件。如图 3 (https://arxiv.org/html/2609.00489#S2.F3) 所示，首先通过一个经典投影将隐藏维度 $d_h$ 映射到一个维度为 $q$ 的低维空间，$q$ 对应于 QNN 使用的量子比特数。投影后的表示通过 $R_X$ 旋转编码到 QNN 中，然后由变分部分处理，该部分实现为一个砖墙式拟设，包含可训练的 $R_X$、$R_Y$ 和 $R_Z$ 旋转，随后是 CNOT 门。输出在计算基中测量，并上投影回原始维度 $d_h$。为了减少总参数数量，通过选择 $q \ll d_h$ 来施加强瓶颈；这种设计选择的影响通过实验进行评估。

图 1：经典注意力模型的编码器架构。该图显示了节点嵌入和 $L$ 层中的一层。
图 2：经典注意力模型的解码器架构。
图 3：编码器前馈块的混合替代。
## 3 方法论

### 3.1 问题实例

本节报告将所提出的学习方法与经典算法进行比较的计算结果。训练在随机生成的欧几里得实例上进行，节点数 $n \in \{10, 20, 50, 100\}$，节点坐标在单位正方形 $[0,1]^2$ 上均匀采样。客户需求是从 $\{1, 2, \ldots, 9\}$ 中随机抽取的整数，车辆容量分别设置为 $20, 30, 40, 50$，对应于 $n=10, 20, 50, 100$ 个客户的实例。

### 3.2 模型和训练设置

经典和混合神经网络都使用批量大小为 $2^7$ 个样本、每个 epoch $2^8$ 个批次进行训练，导致每个 epoch 的样本数为 $2^{15}$，总训练 epoch 数为 $2^7$。此设置在两个方面偏离了 Kool et al. (2018) (https://arxiv.org/html/2609.00489#bib.bib4) 的训练机制。首先，每个 epoch 的样本数量比其使用的 $1,280\mathrm{K}$ 个样本减少了约40倍。其次，初步实验表明，改进的性能通常在后期的 epoch 中实现，这激励了增加总训练 epoch 数。

遵循 Kool et al. (2018) (https://arxiv.org/html/2609.00489#bib.bib4)，策略使用 REINFORCE 算法（Williams, 1992 (https://arxiv.org/html/2609.00489#bib.bib9)）进行端到端训练，并结合一个贪心滚动基线，该基线在先前工作中表现出优越性能。优化使用 Adam 优化器进行，学习率为 $10^{-4}$。QNN 组件通过模拟和反向传播进行训练。采用紧凑的 QNN 配置，包括 $q=4$ 个量子比特和 $L_q=2$ 层。在此设置下，混合 FF-QNN 模型包含 $1,156$ 个经典参数和 $24$ 个量子参数。对于 $L=3$ 个编码器层，此设计将总参数数量减少了 $391,596$，相当于减少了 $56.6\%$。

训练后的模型在包含 $N=1,000$ 个新生成实例的测试集上，使用贪心解码和随机采样进行评估。对于基于采样的评估，报告 $1,280$ 个样本中的最佳解。

### 3.3 基准算法

在相同的测试实例上，性能与五种经典启发式求解器进行了比较：(i) CW，Clarke-Wright 节约算法（Clarke and Wright, 1964 (https://arxiv.org/html/2609.00489#bib.bib10)），以及 RCW，其随机变体（如 Nazari et al. (2018) (https://arxiv.org/html/2609.00489#bib.bib5) 中所述），在每一步从 top $m$ 个可行候选中随机选择一个合并，$m \in \{1, \dots, 10\}$，并返回 $10$ 次重复中的最佳结果；(ii) GOT，来自 Google OR-Tools v9.15 的 CVRP 实现（Furnon and Perron, 2024 (https://arxiv.org/html/2609.00489#bib.bib11)）；(iii) LKH3，Lin-Kernighan-Helsgaun 启发式算法（Helsgaun, 2000 (https://arxiv.org/html/2609.00489#bib.bib3)）；(iv) RSW，一种随机有容量约束的角扫描启发式算法，返回在随机选择起始角度的 $5$ 次运行中的最佳解，同样由 Nazari et al. (2018) (https://arxiv.org/html/2609.00489#bib.bib5) 引入。

## 4 实验结果

所有报告的解都经过明确的可行性检查。对于神经网络模型，解码器遮蔽从设计上保证了可行性，并且在我们的实验中没有观察到无效路线。

为了评估训练稳定性，注意到 Kool et al. (2018) (https://arxiv.org/html/2609.00489#bib.bib4) 报告了经典注意力模型在不同随机种子下的稳健性能。表 2 (https://arxiv.org/html/2609.00489#S4.T2) 展示了 FF-QNN 模型在五次独立训练运行上的结果，报告了均值和标准差。均值用于表 3 (https://arxiv.org/html/2609.00489#S4.T3) 中的 FF-QNN 条目。结果表明，基于混合 QNN 的方法同样表现出稳定的训练行为，各次运行间变异性低。

表 2：FF-QNN 目标值在五次独立训练运行上的平均值。