摘要

在这项工作中，我们介绍使用强化学习（RL）进行训练的图形指针网络（GPN），以解决旅行商问题（TSP）。 GPN通过在输入上引入图嵌入层来构建Pointer Networks，该图嵌入层捕获节点之间的关系。 此外，为了近似求解带有时间窗的约束组合优化问题（例如TSP），我们使用RL训练了分层GPN（HGPN），该学习了分层策略以在约束下找到最佳城市置换。 层次结构的每一层都设计有单独的奖励功能，从而可以稳定地进行训练。 我们的结果表明，针对小规模TSP50 / 100问题训练的GPN可以很好地推广到更大范围的TSP500 / 1000问题，具有较短的游程长度和更快的计算时间。
我们验证了对于受约束的TSP问题（例如带有时间窗的TSP），通过分层RL训练找到的可行解决方案优于先前的基准。 本着可重复研究的精神，我们公开提供我们的数据，模型和代码。

引言

作为计算机科学和运筹学中的一个基本问题，组合优化问题在过去的几十年中受到了广泛的关注。 最重要和实际的问题之一是旅行商问题（TSP）。 要介绍TSP，请考虑一个在一系列城市中旅行的推销员。 推销员必须精确访问所有城市一次，同时最大程度地缩短游览时间。 TSP被认为是一个NP完全问题[21]，它捕获了在多项式时间内找到有效精确解的困难。 为了克服这个复杂性障碍，已经提出了几种近似算法和启发式算法，例如2-opt启发式算法[1]，Christofides算法[4]，引导式局部搜索[26]和Lin-Kernighan启发式算法（LKH）[8]。 。
随着机器学习（ML）和强化学习（RL）的发展，越来越多的近期工作集中在使用ML或RL方法解决组合优化上[25，2，20，16，10，12，13，9] 。 一个称为指针网络[25]的seq2seq模型在近似解决几个组合优化问题（例如找到凸包和TSP）的解决方案方面具有巨大潜力。 它使用LSTM作为编码器，并使用注意力机制[24]作为解码器，以从中城市坐标中提取特征。
然后，它预测描述下一个可能动作的策略，以便对访问过的城市进行抽样。 已经提出了一种用于指针网络的RL框架[2]，其中该指针网络模型由Actor-Critic算法训练[18]，并且负巡回长度用作奖励。 事实证明，RL方法比以前的有监督的学习方法更有效，并且在具有多达100个节点的情况下，它比TSP上的大多数启发式方法都要好。 作为指针网络的扩展，Nazari等人。
[20]修改了指针网络的体系结构，以解决更复杂的组合优化问题，例如车辆路由问题（VRP）。
由于路由问题的性质，上述工作中使用的神经网络体系结构没有完全考虑问题实体之间的关系，这是路由问题的关键属性，并且在其他一些问题中也起着作用。 作为处理非欧氏数据和捕获图信息的强大工具，近年来，图神经网络（GNN）[11，28]得到了广泛的研究。 基于GNN，提出了两种新颖的方法[16，10]，它们利用了许多组合优化问题中固有的图结构信息。 Li等。 [16]应用图卷积网络（GCN）模型[11]以及引导树搜索算法来解决基于图的组合优化问题，例如最大独立集和最小顶点覆盖问题。 戴等。 文献[10]提出了一种经过深度Q学习训练的图嵌入网络，发现该网络很好地推广到了更大的问题。 最近，受Transformer架构的启发[24]，Kool等人。 提出了一种注意力模型[12，13]来解决诸如TSP，VRP和定向运动问题之类的路由问题。 在他们的模型中，使用REINFORCE算法中的推出基线，通过多头注意力机制捕获了图形节点之间的关系，这大大改善了小规模TSP的结果。 但是，规模仍然是注意力模型的问题。
先前的工作在各种组合优化问题上都取得了良好的近似结果，但是在约束条件下的组合优化问题，例如： 带有时间窗口（TSPTW）的TSP尚未得到充分考虑。 为了处理受约束的问题，Bello等人。 [2]提出了一种惩罚方法，为奖励函数的不可行解增加了惩罚项。 但是，惩罚方法可能导致训练不稳定，并且惩罚项的超参数通常难以调整。 更好的培训选择是使用分层RL方法，该方法已广泛用于解决复杂问题，例如奖励稀疏的视频游戏和机器人迷宫任务[14，19，6]。 分层RL的主要动机是将复杂的任务分解为几个简单的子问题，这些子问题可以在分层中学习。
Haarnoja等。 [6]介绍了用于分层RL的潜在空间策略，其中分层的较低层提供了可行的解决方案空间并约束了较高层的动作。 然后，高层根据来自较低层潜在空间的信息进行决策。 在这项工作中，我们探索使用分层RL方法来解决带有约束的组合优化问题，这些约束被分解为不同的子任务。 层次结构的每一层都学习在约束条件下搜索可行的解决方案，或者学习启发式算法以优化目标函数。
在这项工作中，我们旨在近似解决大型TSP问题，并解决约束组合优化问题。 这项工作的贡献包括三个方面：首先，我们提出了一个图形指针网络（GPN）来解决原始的TSP。 GPN通过图形嵌入层扩展了指针网络，并实现了更快的收敛。 其次，我们将向量上下文添加到GPN架构中，并使用提早停止进行训练，以便泛化我们的模型以应对更大范围的TSP实例，例如 TSP1000，来自在较小的TSP50实例上训练的模型。 第三，我们采用分层的RL框架和GPN架构来有效地解决带有时间窗约束的TSP。 对于每个任务，我们进行实验以将我们的模型性能与现有基准和以前的工作进行比较。
这项工作的结构如下。 在“初步”部分中，我们制定了TSP及其相应的强化学习框架。 “分层强化学习”部分介绍了分层RL框架以及分层策略梯度方法。 图指针网络部分描述了建议的GPN的体系结构及其分层版本。
然后，在“实验”部分中，我们分析了针对小规模TSP问题的方法，其对大规模TSP问题的泛化能力，以及它们在带有“时间窗”问题的TSP上的性能。

前提条件

2.1旅行商问题
在这项工作中，我们专注于解决对称的二维欧氏旅行商问题（TSP）[15]。 对称TSP的图是完整的且无向。 给定N个城市坐标的列表{x 1，x 2，…，x N}⊂R 2，问题是要找到一条最佳路线，使得每个城市恰好被访问一次，并且该路线覆盖的总距离为 最小化。 换句话说，我们希望在城市上找到一个最佳置换σ，以使游览时间最小化[2]：
公式（1）
其中σ（1）=σ（N +1），σ（i）∈{1，…，N}，σ（i）6 =σ（j）对于>> i 6 = j，X = [x>∈RN×2是由1，…，x N]所有城市坐标xi组成的矩阵。 另外，在我们的工作中，我们考虑了具有附加约束的TSP。 通常，约束TSP编写为以下优化问题：
公式（2）
其中σ是一个排列，f（σ，X）和g（σ，X）表示约束函数。
2.2TSP问题的强化学习
我们首先介绍用于将TSP表示为强化学习问题的符号。 令S为状态空间，A为动作空间。 每个州s∈S被定义为所有先前访问过的城市的集合，即s t = {xσ（i）} ti = 1。 动作a t∈A被定义为下一个选定的城市，即t = xσ（t + 1）。 由于σ（1）=σ（N +1），因此得出N = xσ（N +1）= xσ（1），这意味着路线的最后选择是出发城市。
将策略表示为πθ（a t | s t），它是给定一组访问城市s t的候选城市a t的分布。 给定一组访问的城市，该策略将返回尚未选择的下一个候选城市的概率分布。 在我们的情况下，该策略由神经网络表示，参数θ表示神经网络的可训练权重。 此外，奖励函数被定义为从状态s t采取行动a t引起的负成本，即r（s t，a t）= -kxσ（t）-xσ（t + 1）k 2。 然后，预期奖励[23]定义如下：
公式（3）
其中X是城市集合的空间，Γ是X上所有可能置换σ的空间，pθ（Γ）是Γ的分布，这是由神经网络预测的。 为了最大化上述奖励功能，网络必须学习一种策略以最小化预期的行程长度。 我们采用策略梯度算法[23]来学习最大化奖励功能，如下所述。

3分层加固学习

3.1TSP的分层强化学习
我们工作的一个关键方面是解决TSP的限制。 用惩罚项增强传统RL奖励功能可鼓励解决方案处于可行的范围内[2]； 但是，我们发现这种方法导致训练不稳定。 相反，我们提出了一个分层的RL框架来更有效地解决带有约束的TSP。
受Haarnoja等人工作的激励。 [6，7]，我们采用概率图形模型进行控制，如图1所示。层次结构的每一层都定义了一个策略，从中可以对操作进行采样。 在给定的层k∈{0，。 。 。 ，K}，当前的（k）（k）（k）（k）动作是从策略πθk（at | st，ht）采样的，其中（k）ht∈H（k）是一个潜在变量 从层次结构中的上一层开始，H（k）是其对应的潜在空间。 图1（b）所示的最低层是一个简单的马尔可夫决策过程（MDP）（0）（0）（0），作用是从策略πθ0（在| st）采样，pro（1）提供a 较高层的潜在向量ht。 中间层（k）不仅取决于第（k-1）层的潜在变量h t（k + 1），而且还为下一个较高层提供了潜在变量h t。
为方便起见，在第k层上，我们将策略扩展为对操作进行采样并提供潜在变量，即 （k）（k + 1）（k）（k）a t，h t〜πθk（·| s t，h t）。
每层对应于一个不同的RL任务，因此将奖励功能手动设计为各层不同。 有两种自然的方法可以以分层方式制定受约束的TSP优化问题。 首先，我们设置较低层的奖励函数，以简单地将约束解决方案约束在约束优化问题的可行集中，并将较高层的奖励函数作为原始优化目标。 相反，我们按递增的顺序对奖励函数进行排序，从而增加了优化的难度：第一层尝试求解香草TSP，第二层给出具有一个约束的TSP实例，依此类推。 对于我们的实验，我们使用第一种配方，因为我们发现分层的方式会产生更好的结果。 首先，我们设置较低层的奖励函数，以简单地将约束解决方案约束在约束优化问题的可行集中，并将较高层的奖励函数作为原始优化目标。 相反，我们按递增的顺序对奖励函数进行排序，从而增加了优化的难度：第一层尝试求解香草TSP，第二层给出具有一个约束的TSP实例，依此类推。 对于我们的实验，我们使用第一种配方，因为我们发现这会产生更好的结果。
3.2分层策略梯度
我们使用策略梯度方法来学习分层策略。
考虑分级策略，第k层的目标函数为J（θk）= -Eσ〜pθk（σ），X〜X [L（σ，X）]。 基于REINFORCE算法，第k层策略的梯度表示为[2，27]：
公式（4）
其中B是批次大小，πθk是第k层策略，rk（·，·）是第k层的奖励函数，bi，k是第k层基线，并且（k） ht是来自较低层的潜在变量。 基于等式4，通过更新规则θk←θk +α∇θk J（θk）使用梯度下降来优化参数θk。
3.2.1Central Self-Critic
我们介绍了中心自我批评基线b i，k，它类似于自我批评基线[22]和注意力模型[12]中的推出基线。 中心自我批评基线b i，k表示为：
公式（5）
其中动作ãi，t〜πθGreedy来自贪婪策略πθGreedy，k k（k），即对该动作进行贪婪采样，并且s̃ i，t是相应的状态。
公式5的第二项是采样方法与贪婪方法之间的奖励差距，其目的是使REINFORCE算法中的优势项居中[27]。 与使用奖励的指数移动平均值相比，使用中心的自我批评基准可以加快收敛速度​​。
由于层次结构的最低层是马尔可夫决策过程（MDP），因此可以直接学习最低层策略，并为较高层提供潜在变量。 换句话说，我们使用自下而上的方法来学习分层策略和训练神经网络。
3.2.2Layer-wise Policy Optimization
假设我们需要学习（K +1）层的分层策略，其中包括πθ0，πθ1，…，πθK。 每个策略均由GPN代表。 为了学习策略πθK，我们首先需要针对k = 0，…，K -1训练所有较低层πθk并固定神经网络的权重。 然后，对于k = 0，…，K − 1的（k）（k），我们基于πθk采样（st，at），并且（k + 1）为下一个更高的层提供潜变量 。 最后，我们（K）可以从h t学习策略πθK。 算法1提供了详细的伪代码。

4图形指针网络

4.1GPN架构
我们基于指针网络[2]提出了一种图形指针网络（GPN），用于近似求解TSP。 如图2所示，GPN体系结构由一个编码器和一个解码器组件组成。
编码器编码器包括两部分：点编码器和图形编码器。 对于点编码器，每个城市坐标x i都嵌入到较高维度的向量x̃ i∈R d中，其中d是隐藏维度。 该线性变换在所有城市x i上分配权重。 然后，由LSTM对当前城市x i的矢量x̃ i进行编码。
LSTM的隐藏变量x hi既传递给当前步骤中的解码器，又传递给下一时间步骤中的编码器。 对于图编码器，我们使用图嵌入层对所有>>坐标X = [x> 1，…，x N]进行编码，然后将其传递给解码器。
图嵌入层在TSP中，城市节点的上下文信息包括城市的邻居信息。 在GPN中，上下文信息是通过图形神经网络（GNN）对所有城市坐标X进行编码而获得的[11，28]。 GNN的每一层表示为：
公式（6）
其中x li∈R dl是第l层变量，其中l∈{1，…，L}，x 0 i = xi，γ是可训练参数，用于规范权重矩阵的特征值Θ∈R dl -1×dl是可训练的权重矩阵，N（i）是节点i的邻接集，且φθ：R dl-1→R dl是聚合函数[11]，在此由神经网络表示 工作。
此外，由于我们仅考虑对称TSP，因此TSP的图是完整的图。 因此，图形嵌入层进一步表示为：
公式（7）
向量上下文在先前的工作[2，12]中，上下文是根据所有城市的2D坐标计算的，即X∈R N×2。 我们将此上下文称为点上下文。 相反，在本文中，我们直接使用从当前城市指向所有其他城市的向量作为上下文，而不是直接使用坐标特征，将其称为向量上下文。 对于当前城市x i，假设>>∈R N×2是具有相同行x i的矩阵。
X i = [x> i，…，x i]我们定义X̄i = X − X i为向量上下文。 X̄i的第j行是从节点i指向节点j的向量。 然后将X̄i传递到图形嵌入层。 图形嵌入层被重写为X̄li =γX̄l-1θ+（1-γ）ΦθX̄l-1 / | N（i）| 。 实际上，使用向量上下文的GPN会产生更多可转移的表示形式，这使模型可以在较大规模的TSP上很好地执行。
解码器解码器基于注意力机制并输出指针向量u i，然后将其传递到softmax层以生成下一个候选城市的分布。 类似于指针网络[2]，注意力机制和指针向量u i定义为：
公式（8）
其中ui是向量ui的第j个条目，W r和W q是可训练的矩阵，q是来自LSTM隐藏变量的查询向量，ri是包含所有城市上下文信息的参考向量 。 确切地说，我们将点编码器中的隐藏变量x hi用作查询向量q，并将图嵌入层中的上下文X L用作参考，即q = x hi和r j = X L j。
所有候选城市的分配政策如下：
公式（9）
我们通过采样或从策略πθ（a i | s i）中贪婪地选择来预测下一个访问的城市a i = xσ（i + 1）。
4.2分层GPN架构
在本节中，我们使用建议的GPN来设计层次结构。 两层分层GPN（HGPN）的体系结构

5实验

在我们的实验中，我们使用L = 3的图形嵌入层在GPN中编码上下文。 使用的聚合函数是单层完全连接的神经网络。 图形嵌入层表示为
公式（10）
其中g（·）是ReLU激活函数，W∈R dl−1×da和b∈RN×da是可训练的权重，对于l = 1，2，3，dl = da = 128的偏差。 TSP20 / 50等小规模问题，TSP500等大问题的向量上下文。 训练数据是根据[0，1] 2均匀分布随机生成的。 在每个时期，训练数据都是动态生成的。 RL培训期间使用*自我批评基线。 除非另有说明，否则以下实验将使用表1中所示的超参数。
OR-工具设置我们使用或工具[5]作为比较结果的基准之一。 为了与大型TSP实例进行比较，在OR-Tools中选择了Savings和Christofides算法作为第一个解决方案策略。 每个TSP实例的搜索时间限制设置为5秒。 当运行OR-Tools时，我们选择Guided Local Search作为metaheuristic。 对于带有“时间窗”的TSP（TSPTW），“节省”算法被选为OR-Tools中的第一个解决方案策略。 我们将默认设置用于其搜索限制和元启发法。
5.1小型TSP的实验我们使用TSP20和TSP50实例训练GPN模型。 使用一个NVIDIA Tesla P100 GPU，每个时期的训练时间对于TSP20是7分钟，对于TSP50是30分钟。 我们将模型在小规模TSP上的性能与先前的工作进行了比较，例如注意力模型[12]，s2v-DQN [10]，指针网络[2]以及其他启发式方法，例如 2选启发式，Christofides算法和随机插入。 结果显示在图4中，该图将近似间隙与最佳解决方案进行了比较。 间隙越小表示结果越好。 最佳解是从LKH算法获得的。 我们观察到，对于小规模的TSP实例，GPN的性能优于Pointer Network，这证明了图嵌入的有用性，但得出的近似度比Attention模型差。
5.2大规模TSP的实验在实际应用中，大多数实际的TSP实例具有数百或数千个节点，并且最佳解决方案无法高效计算。 我们发现，提出的GPN模型很好地概括了从小型TSP问题到大型问题。
泛化能力增加了一个数量级。
在表2中，我们针对具有10个历元的TSP50数据训练了具有矢量上下文的GPN模型，并使用该模型来预测TSP250 / 500/750/1000上的路由。 此外，我们使用局部搜索算法2-opt [1]来改善预测后的结果。 指针网络（PN）[2]，s2v-DQN [10]和注意力模型（AM）[12]也使用TSP50数据进行了训练，我们还检查了这些模型对更大范围问题的可移植性。 结果是对1000个TSP实例的平均值。 由于内存限制，我们在推理所有模型时将批次大小设置为B = 50。 还将结果与LKH，最近邻居，2-opt，最远插入和Google OR-Tools [5]进行比较。
表2显示，当我们训练TSP50实例并将其推广到更大范围的问题时，我们的GPN模型优于PN和AM。 添加本地搜索后，GPN + 2opt具有与s2v-DQN相似的游程长度，但节省了大约20％的运行时间。 与2opt启发式算法相比，GPN + 2opt使用的运行时间减少了≈25％，这意味着GPN模型可以视为一种很好的初始化方法。
GPN + 2opt在TSP1000上也胜过OR-Tools。 在表2上，GPN的性能不超过最新的TSP求解器。 LKH和最远的插入。 但是，由于GPN具有良好的泛化能力并且可以并行解决TSP实例，因此它仍有可能成为有效的初始化方法。 图5中显示了一些示例巡视。
如前所述，GPN模型的泛化能力大约比训练模型的实例大小大一个数量级。 更具体地说，我们在TSP20 / 50/100上训练GPN模型，并使用这些模型在TSP500 / 1000上进行预测。
结果显示在表3中，这表明如果我们增加用于训练的TSP实例的大小，结果会有所改善
带有时间窗口的TSP的实验最后，我们考虑一个众所周知的受约束的TSP问题，即带有时间窗口的TSP（TSPTW）。 在TSPTW中，每个节点i都有自己的节点服务时间间隔[e i，l i]，其中e i是进入时间，l i是离开时间。 离开城市后无法访问城市。 如果访问该节点的时间早于输入时间，则推销员必须等待，直到服务开始，即直到输入时间。 在此实验中，我们考虑以下带有时间窗问题的TSP形式化：
公式（11）
其中c i是第i个城市的时间成本。 在这个问题中，并不总是存在可行的解决方案。 为了确保训练和测试数据的存在，我们首先从[0，1] 2均匀分布生成TSP20实例。 然后在生成的实例上使用2-opt局部搜索，我们求解i∈{1，…，N}的近似解c̃ i。 我们设置ei = max {c̃ i −ẽ i，0}和li = c̃ i + ̃ li，其中ẽi〜均匀（0，2）和̃ li〜均匀（0，2）+1。因此，ei≤ c̃ i≤li，这意味着在训练和测试数据中始终存在可行的解决方案。 通过对以上实例中的所有城市进行混洗获得数据集。 在RL训练中使用指数移动平均评论家基线[12]。
在带有时间窗口（TSPTW）的TSP实验中，我们构造了一个两层的分层GPN（HGPN）。 首先我们定义：
公式（12）
如果到达时间超过离开时间，则作为罚款，其中l i是离开时间，c i是到达时间。 然后，下层的奖励函数是违反离开时间约束r 1 =β∗ρ（c，l）的惩罚，其中β是惩罚因子。 较高层的奖励是TSPTW的总时间成本加上惩罚
公式（13）
对于推理阶段，我们使用ρ（c，l）来衡量准确性，即成功解决的实例数。 对于任何情况，如果ρ（c，l）> 0，则至少存在一个城市，使得到达时间超过离开时间，这表明该解决方案不可行。
下层以1个时期的TSPTW20数据进行训练，而高层则以19个时期进行训练。 对于TSPTW数据，每个节点x i是一个元组（x i，y i，e i，l i），其中（x i，y i）是二维坐标，而e i，l i是进入和离开的时间。 我们将10000个问题实例的平均结果与OR-Tools和蚁群优化（ACO）算法进行比较[3]。
在预测时，我们同时使用贪婪和抽样方法。
通过采样100或500次可以改善结果。 表4证明了我们的HGPN框架优于TSPTW上的所有其他基线，包括单层GPN。 即使所有实例都基于我们的训练设置都有可行的解决方案，但有时算法仍无法找到可行的解决方案。 为了捕捉这一点，我们使用可行解的百分比作为评估指标。 与基线相比，HGPN可以实现的解决方案百分比要高得多。 图6中显示了一些示例性游览。
5.2真实世界的TSP实例
我们已使用少于1500个节点的实例在真实世界的TSPLIB数据集上评估了我们的模型。 我们报告了结果与最佳解决方案之间的平均差距，如表5所示。

6讨论

6.1通用
向量上下文在我们的GPN模型中，我们在编码之前使用向量顶点。 向量上下文有助于获取城市之间的成对信息。 因此，在每个步骤中，我们的模型都知道当前城市与所有其他城市之间的相对位置，这有助于良好的概括性。 在实验中，具有矢量上下文的GPN在大规模TSP上的性能优于带有点上下文的GPN，如图7所示。
提前停止为了很好地推广到较大规模的实例并避免在小规模问题上过度拟合，我们在训练期间使用了提前停止，并使用针对10个时期进行训练的模型来求解大规模TSP。 表6中显示了在不同级别的提前停止之间的性能比较结果。基于性能，我们仍将PN，s2v-DQN，AM训练了100个时间段。
裁剪范围在我们的模型中，我们将指针向量u的范围裁剪为[-C，C]。 代替先前工作[2]中使用的C = 10，我们选择C = 100可以更好地权衡勘探与开发。
6.2分层体系结构在TSPTW问题中，分层GPN（HGPN）的性能优于单层GPN。 HGPN和单层GPN的训练曲线如图8所示。对于单层GPN，奖励函数既包括罚分，也包括TSPTW的目标，这会导致早期的不稳定训练，如图2中的蓝色曲线所示。 8.相比之下，我们训练HGPN的下层以最小化惩罚项，这很容易学习，并且可以在一个纪元内快速收敛。 然后，较低的层为较高的层提供了可能的可行解决方案的事先分配。 给定可行解决方案的潜在信息，与单层GPN相比，较高层的HGPN收敛速度更快，并且可以生成更好的解决方案。

7结论

在这项工作中，我们提出了一种图指针网络（GPN）框架，该框架通过使用图嵌入层有效地解决了大规模TSP。 训练分层RL模型可以使我们的方法进一步解决受约束的组合优化问题，例如带有时间窗的TSP。 我们的实验结果表明，GPN可以很好地将小规模问题推广到大范围问题，其性能优于以前的RL方法。 我们使数据，模型和代码公开可用[17]。