推文作者：缪昌昊，张景琪，张云天

论文作者：Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee 论文原文：Bi, Jieyi, et al. "Learning generalizable models for vehicle routing problems via knowledge distillation." Advances in Neural Information Processing Systems 35 (2022): 31226-31238.​ 论文代码：

摘要：

近年来，用于求解车辆路径规划问题（Vehicle Routing Problem, VRP）的神经网络方法通常在相同的实例分布上对深度模型进行训练和测试（即均匀分布）。为了解决跨分布泛化问题，作者引入了知识蒸馏到这个领域，并提出了一种自适应多分布知识蒸馏（Adaptive Multi-Distribution Knowledge Distillation，AMDKD）方案，用于学习泛化能力更强的深度模型。AMDKD首先训练了提供分布知识的教师模型，而后将教师模型输出的知识（分布）作为学生模型的监督信息，训练学生模型。与此同时，作者为AMDKD配备了一种自适应策略，允许学生集中精力处理困难的分布，以更有效地吸收难以掌握的知识。AMDKD首先训练了提供分布知识的教师模型，而后将教师模型输出的知识（分布）作为学生模型的监督信息，训练学生模型。

大量的实验证明，与基线的神经网络方法相比，AMDKD在未见过的同一分布和不同分布实例上都能取得出色的结果，这些实例可以是随机合成的，也可以是从基准数据集（即TSPLIB和CVRPLIB）中选取的。值得注意的是，作者提出的AMDKD具有通用性，且在推断时消耗更少的计算资源。

1. 背景

​车辆路径规划问题是一个NP-hard的组合优化问题，其具有广泛的实际应用，例如货物配送、末端物流和网约车服务等。几十年来，该问题在计算机科学和运筹学领域得到了深入研究，且提出了许多精确和（近似）启发式算法。在实践中，尽管人们通常更喜欢使用计算效率相对较高的启发式算法，但是这些算法往往依赖于手工设计的规则和领域知识，且仍有改进的空间。近年来，深度（强化）学习作为一种有前景的替代方案，已经引起了广泛关注，它可以被用来以端到端的方式自动学习VRP的启发式（或策略）。与传统方法相比，基于深度模型的启发式学习方法可以进一步降低计算成本，同时保证理想的解决方案。

然而，现有的深度模型在不同的节点坐标分布上存在泛化性能较差的问题。具体而言，它们通常在相同分布的实例上对神经网络进行训练和测试，其主要是均匀分布。相比于传统的启发式算法，深度模型能够更有效地获得出色的结果。然而，当利用学习得到的策略对分布外（Out-of-Distribution）的实例进行推断时，求解结果的质量通常较低。这种跨分布的泛化问题不可避免地阻碍了深度模型的应用，特别是因为现实世界中的VRP实例可能遵循不同甚至未知的分布。

图1：不同的VRP实例分布。自左至右为均匀分布（Uniform）、簇状分布（Cluster）和二者的混合分布（Mixed）

如今，对于VRP中的泛化问题，人们主要利用（自动）数据增强和分布鲁棒优化的方法进行了一些初步的尝试。然而，在作者看来，这些方法并不是最佳选择。数据增强方法通常从指定的单一分布开始，这可能会对结果的质量有所限制。分布鲁棒优化方法需要手动定义主要和次要实例。与上述两种方法不同的是，在本文中，作者旨在通过将从不同分布中学到的各种策略转移到一个分布中来增强跨分布的泛化性能。作者利用了知识蒸馏技术来学习更具泛化性的VRP模型。

具体而言，作者提出了一种通用的自适应多分布知识蒸馏（Adaptive Multi-Distribution Knowledge Distillation，AMDKD）方案，用于训练一个具有良好的跨分布泛化性能的轻量级模型。为了传授广泛且专业的知识，作者利用了多个在各自示范分布上（预）训练过的教师模型。AMDKD利用这些教师模型轮流对一个学生模型进行训练，其灵感来自人类的学习范式。同时，作者还为AMDKD配备了一个自适应策略，用于追踪学生模型在每个示范分布上的实时学习表现，这使得学生能够集中精力吸收难以掌握的知识，以增强学习的有效性。

2. 模型构建

图2：AMDKD框架分为三个阶段：教师预训练、学生训练和推断。图中选择了均匀分布作为当前示范分布的示例。

在先前的研究中，深度模型通常是在单一分布上进行训练的。近年来，人们开始尝试通过增加非典型（次要）或困难实例来扩充训练数据。与这些方法不同，AMDKD通过知识蒸馏方法将不同分布下的专家知识传递到同一个模型中。由于其轻量级网络和高速推断的特点，生成的模型在性能上会优于现有的方法。此外，AMDKD是通用的，可以对各种VRP深度模型进行增强。

下面将对AMDKD算法的整体结构、教师（预）训练和自适应多分布学生训练进行详细介绍。

2.1 整体结构和教师（预）训练2.2 自适应多分布学生训练

在AMDKD方案中，基于给定的示范分布可以获得训练好的教师模型。在每个知识传递周期中，AMDKD学生选择一个分布及其对应的教师模型，并逐渐学习如何做出适当的决策。需要注意的是，还有另一类研究认为在蒸馏过程中同时应当使用多个教师，通过所有教师参与以提供加权损失的方法来训练学生。然而，这种设计可能需要通过监督学习对同质任务进行训练，这与使用强化学习处理异构分布的需求不符。

学生网络

作者规定学生模型与教师模型具有相似的架构，但可以根据需要减少网络参数以加快推断速度。然而，较大的学生模型通常会拥有更好的性能。因此，在求解质量和计算成本之间需要进行权衡。在本文中，作者考虑将节点嵌入的维度从128（教师模型）降低到64（学生模型），这导致将AMDKD应用于AM和POMO后模型参数分别减少了61.8%和59.2%。同时，作者也考虑了减少编码器层数，但结果低于预期。

自适应多分布蒸馏策略损失函数

图3：AMDKD算法流程

3. 实验分析

作者在TSP和CVRP上进行了实验，节点数量分别为20、50和100，与之前的研究类似。正如前面所提到的，作者采用均匀分布（Uniform）、簇状分布（Cluster）和混合分布（Mixed）作为训练的示范分布；而在测试中，作者使用扩张分布（Expansion）、坍塌分布（Implosion）、爆炸分布（Explosion）和网格分布（Grid）作为未见过的分布。所有实验均在NVIDIA RTX 3090 GPU和Intel Xeon Silver 4216 CPU 2.10GHz 的计算机上实现。

论文代码可公开获取：

3.1 AMDKD的有效性分析

图4：AMDKD在三个示范分布上的蒸馏有效性

3.2 AMDKD的泛化性分析

作者对AMDKD的跨分布泛化性能进行了评估分析。除了AM与POMO模型外，作者还与以下方法进行比较：

（1） 其他深度模型，包括DACT、LCP

（2）专门用于泛化的其他方法，包括HAC、DROP、GANCO和PSRO（又称LIH）

因为DROP、GANCO和PSRO并没有开源，作者只比较了它们在原论文中展示的几个基准实例上的结果（见图6）。

图5：AMDKD对ID和OoD算例的泛化性能分析

此外，作者将AMDKD-POMO（64）模型与最近提出的高效主动搜索（EAS）相结合，并在CVRP-100上取得了非常出色的效果，甚至超过了LKH3，并且所需时间更短。因此，利用主动搜索在推断特定实例时的优势，AMDKD+EAS能使得AMDKD的性能进一步提升。

图6：对TSPLIB和CVRPLIB数据集的泛化性能分析

如图6所示，作者在基准数据集TSPLIB和CVRPLIB上对AMDKD的泛化性能进行了评估。AMDKD-AM（64）显著提高了AM（128）的泛化性能，同时也优于其他基线方法。同样，AMDKD-POMO（64）也明显优于其他基线方法，除了在TSPLIB上的POMO#（128）。相较于所有其他基线算法，AMDKD+EAS在TSP和CVRP上都表现出了最好的性能。

3.3 AMDKD的进一步分析不同组件的影响

图7：AMDKD的消融实验

学生网络结构的影响

在图8中，作者展示了使用不同学生网络架构（不同网络维度和不同编码器层数）的AMDKD-POMO在求解CVRP-50时的平均优度箱线图。如图所示，模型越大，性能越好。因此，作者认为当学生（64）与其教师（128）使用相同的结构时，AMDKD的性能可以进一步提升。具体而言，对于CVRP-50，AMDKD-POMO（128）的平均Gap为0.81%，低于AMDKD-POMO（64）的0.90%。然而，该优势以三方面计算成本的增加为代价：（1）更多的训练时间；（2）更多的参数；（3）更慢的推断时间。因此，求解性能和计算成本之间需要进行权衡。

图8：学生网络结构对性能的影响

不同示范分布的影响

作者通过改变示范分布的选择来验证AMDKD的有效性。以POMO和CVRP-50为例，作者将Expansion、Implosion、Explosion和Grid作为示范分布的模型称为AMDKD-POMO。结果如图9所示，AMDKD-POMO的整体性能仍然优于在这四个分布上单独训练的POMO。因此，AMDKD在不同的示范分布下均可以对跨分布泛化性能进行改善。

图9：利用不同示范分布训练的AMDKD在CVRP-50上的性能表现

4. 总结

在本文中，作者提出了一种自适应多分布知识蒸馏（AMDKD）方案，以改善VRP的深度模型在不同分布下的泛化问题。与现有的泛化方法不同，作者旨在通过一种高效的知识蒸馏方案，将从示范分布中学到的各种策略转移到同一个分布中，以增强分布泛化性能。为了促进学习的有效性，作者设计了一种自适应策略，即多个教师轮流训练一个学生网络。实验结果显示，AMDKD在推广到其他未见分布的实例时拥有出色的性能，且需要较少的计算资源。

尽管AMDKD是通用的，但它在未见分布上的性能提升并不总是显著。因此，对于未来的研究，作者将会围绕以下方面展开研究：（1）将AMDKD推广到不同/更大规模的问题；（2）考虑将类似DACT这样的改进模型作为主体模型；（3）利用在线蒸馏对教师和学生模型共同训练；（4）评估验证数据集质量对蒸馏的影响；（5）加强AMDKD的可解释性。

参考文献：

Bi, Jieyi, et al. "Learning generalizable models for vehicle routing problems via knowledge distillation." Advances in Neural Information Processing Systems 35 (2022): 31226-31238.