深度强化学习结合图注意力模型求解TSP问题

图1 本文提出的图注意力模型示意图

Fig.1 Schematic diagram of graph attention model proposed in this paper

2.1　多重初始点

TSP问题的策略（式（2））以 $a_{1}$ 为起点与 $(a_{2}, a_{3}, \dots, a_{N})$ 中任意起点得到的解是等价的，如果轨迹 $τ = (a_{1}, a_{2}, a_{3}, a_{4})$ 是一个最优解，那么轨迹 $τ^{'} = (a_{2}, a_{3}, a_{4}, a_{1})$ 也是一个最优解.图2展示了四个节点的多重选择.先前工作^［14-20］只考虑单一最优路径，而本文类似Kwon et al^［5］，采用 $N$ 种不同的点序列表征最优解，模型在编码、解码、推理阶段均放置 $N$ 种不同的初始起点 $\{a_{1}^{1}, a_{1}^{2}, \dots, a_{1}^{N}\}$ ，其中每个节点都能被策略网络选取.实验结果显示多重轨迹的构造可以防止陷入局部最优，能更有效地寻求最短路径，行为网络通过蒙特卡洛方法（Monte Carlo method）采样 $N$ 种不同初始起点的轨迹 $\{τ^{1}, τ^{2}, \dots, τ^{N}\}$ ，其中，每个轨迹被定义为（M为节点个数）：

τ^{i} = (a_{1}^{i}, a_{2}^{i}, \dots, a_{M}^{i}), i = 1,2, \dots, N

（3）

图2

图2 多重初始点示意图

Fig.2 Schematic diagram of multiple initial points

2.2　编码结构

本文针对TSP问题的编码类似Transformer架构^［6］的编码部分，考虑多重起点的嵌入（输入排列是变化的）.环境中生成的节点坐标进行线性嵌入操作时不能有效捕获每个节点的位置信息，因此本文模型采用PE操作，使得节点坐标在嵌入的过程中满足平移不变性，以便高层的NN能够提取更多有效的位置信息；再将处理后的向量嵌入到MHA层，提取深层网络的节点信息.其中，PE，MHA被定义为：

P E_{t, i} = \{\begin{matrix} s i n (t 10000^{\frac{d}{2 i}}), i 是 奇 数 \\ c o s (t 10000^{\frac{d}{2 i}}), i 是 偶 数 \end{matrix}, P E_{t} \in R^{d}

（4）

\begin{array}{l} A^{i} = A t t e n t i o n (Q^{i}; K^{i}; V^{i}) = \\ s o f t m a x (\frac{Q^{i} K^{i Τ}}{\sqrt[]{d}}) V^{i}, i = 1,2, \dots, H \end{array}

（5）

M H A (Q, K, V) = C o n c a t (A^{1}, A^{2}, \dots, A^{H}) W_{O}

（6）

其中，t表示编码节点的位置， $d = 512$ 为嵌入维度， $H = 8$ 为注意力机制的头部数， $Q, K, V$ 是查询、键、值向量.注意力机制的输出 $A^{i}$ 被连接并映射到 $W_{O} \in R^{d \times d}$ 空间，得到MHA层的输出；再传入批次正则化（Batch Normalization，BN）处理层，经过非线性函数ReLU激活后，传入前馈网络层（Feed Forward，FF）；再次由BN层处理输出编码向量.其中，BN层和FF层被定义为^［6］：

{\hat{f}}_{i} = B N (X_{i} + M H A_{i} (Q, K, V)), i = 1, \dots, N

（7）

f_{i} = B N ({\hat{f}}_{i} + F F ({\hat{f}}_{i})), i = 1, \dots, N

（8）

节点坐标经过上述MHA模型、BN层、FF层编码成序列向量，传入解码层继续做图嵌入（Graph Embedding，GE）、点嵌入（Node Embedding，NE）、上下文向量（Context）、掩码（Mask）等处理（详见2.3），输出选择下一个节点的概率，直到所有节点都被选择，构成一个环游策略.

2.3　解码结构

TSP问题中，每个节点信息具有一定的相似性且与邻居节点相关，将其抽象为节点和边集的关系可建模成图模型.因此，在GE层中所有被编码的城市坐标 $X$ 可由GNN中的聚合操作解码，使向量空间具有更强的灵活性和丰富多样的计算形式以便捕捉图的拓扑结构及点与点之间的潜在关系，让更多的信息被表征挖掘，那么解码后的嵌入将会有更好的表现.本文首次将GNN的聚合操作应用到Transformer架构的解码阶段中，其中，GE结构的表达式可刻画为：

x_{i}^{l} = γ x_{i}^{l - 1} Θ + (1 - γ) φ_{θ} (\frac{{\{x_{j}^{l - 1}\}}_{j \in Ν (i) ⋃ \{i\}}}{|Ν (i)|})

（9）

其中， $x_{i}^{l} \in R^{d_{l}}$ 是 $l$ 层 $(l \in \{1, \dots, L\})$ 的变量， $γ$ 是一个调整权重矩阵特征值的参数， $Θ \in R^{d_{l - 1} \times d_{l}}$ 是权重矩阵， $Ν (i)$ 是点 $i$ 的邻接集合， $φ_{θ} : R^{d_{l - 1}} \to R^{d_{l}}$ 是通过GNN表达的聚合函数^［24］.

考虑具有对称性质的TSP问题，即城市节点组成的图由一个完全图刻画，因此GE结构的表达式可写为：

X^{l} = γ X^{l - 1} Θ + (1 - γ) Φ_{θ} (\frac{X^{l - 1}}{|Ν (i)|})

（10）

其中， $X^{l} \in R^{N \times d_{l}}$ ， $Φ_{θ} : R^{N \times d_{l - 1}} \to R^{N \times d_{l}}$ 是通过GNN表达的聚合函数^［24］.

下一个解码阶段，类似Kool et al^［19］，引入上下文节点 $c$ ，经过多重起点随机选择初始节点后，加入遮掩技术（访问过的节点不能再次被访问），有效计算编码后节点的注意力分配，以较大概率输出下一个访问的城市节点.图3展示了最优路径 $π = (3,1, 2,4)$ 的构造过程.具体地，通过水平拼接操作将编码层的图嵌入、初始节点 $π_{1}$ 、先前节点 $π_{t - 1}$ 聚合成一个三维向量，记作 $h_{c}^{i}$ ，描述为：

h_{c}^{i} = \{\begin{matrix} [\bar{h}, h_{π_{t - 1}}, h_{π_{1}}] t > 1 \\ n o n e t = 1 \end{matrix}

（11）

其中， $t = 1$ 时，不采用解码控制第一个节点的选择，使用 $N$ 种不同的上下文节点嵌入，得到 $h_{c}^{1}, h_{c}^{2}, \dots, h_{c}^{N}$ ， $h_{c}^{i}$ 表示上下文节点 $c$ 的嵌入信息.因此，模型中查询、键、值向量可以被表示为：

\begin{array}{l} q_{c} = W^{Q} h_{c} \\ k_{i} = W^{K} h_{i} \\ v_{i} = W^{V} h_{i} \end{array}

（12）

为了计算 $p_{θ} (a_{t}| s, a_{1 : t - 1})$ 输出概率，最后一步采用单头的注意力机制处理解码向量，其中掩码技术和输出向量 $p_{i}$ 可表示为 $(C = 10)$ ：

u_{c j} = \{\begin{matrix} C \cdot t a n h (q_{c}^{Τ} k_{j}) i f j \neq π_{t^{'}}, \forall t^{'} < t \\ - \infty 其 他 \end{matrix}

（13）

p_{i} = p_{θ} (a_{t}| s, a_{1 : t - 1}) = \frac{e^{u_{c i}}}{\sum_{j} e^{u_{c j}}}, i 邻 接 j

（14）

图3

图3 四个节点的TSP问题解码示例图

Fig.3 Schematic diagram of TSP problem decoding for four nodes

2.4　模型训练

鉴于SL对标签的大量需求，实际工程应用中TSP问题的高质量标签又不易获得，而DRL的方法不需要大量的标签数据，因此本文采用DRL的方法训练网络模型.TSP问题的优化目标是路径长度 $L (π)$ 最小，总奖励即为路径总长度的负数 $- L (π)$ .由于REINFORCE算法^［25］是以总奖励作为参数更新的，因此该算法天然适用于训练求解TSP问题，大多数COP问题通常也采用该算法对策略参数 $θ$ 进行优化^［4］.此算法求解TSP问题的一个主要缺陷是不同路径之间的方差很大，导致训练不稳定，这是在高维离散空间中常见的问题，为了减小策略梯度（Policy Gradient，PG）的方差，本文引入一个和 $R (τ^{i})$ 相关的基准函数，记为 $\bar{r (τ^{i})}$ ，表达式如下：

\bar{r (τ^{i})} = \frac{1}{N} \sum_{i = 1}^{N} r (τ^{i})

（15）

受到交叉熵损失函数（Cross⁃Entropy Loss）^［26］的启发，在基准线 $\bar{r (τ^{i})}$ 上加入超参数 $β = 0.1$ ，调节奖励值的变化频率，防止过早收敛，以便更好地衡量不同城市间的差异分布程度.后文的实验结果证明该方法的收敛速度优于原始的基准线. $\bar{R (τ^{i})}$ 可表示为：

\bar{R (τ^{i})} = β \times r (τ^{i}) + (1 - β) \bar{r (τ^{i})}

（16）

PG法通过寻找一个参数 $θ$ 使得目标函数 $J (θ)$ 最大，参数 $θ$ 优化的方向是使得总回报 $R (τ^{i})$ 越大，即轨迹 $\{τ^{1}, τ^{2}, \dots, τ^{N}\}$ 的概率 $P_{θ} (τ^{i})$ 越大.因此， $J (θ)$ 的梯度可以被近似为：

\nabla_{θ} J (θ) \approx \frac{1}{N} \sum_{i = 1}^{N} (R (τ^{i}) - \bar{R (τ^{i})}) \nabla_{θ} l g p_{θ} (τ^{i}| s)

（17）

模型通过一个随机策略学习行为网络的参数 $θ$ ，上述公式对 $θ$ 的梯度进行计算并更新，不断迭代训练从而得到最优的策略 $π_{t} = p_{θ} (a_{t} | s)$ .算法1描述了模型训练流程，通过这种共享奖励值基准线的构造，代替模型中的评判网络，简化模型的结构，实现TSP问题序列到解序列的精准映射.

算法1 改进的REINFORCE算法

输入：训练集 $S$ ，每个起始点的数字 $N$ ，训练次数 $T$ ，批次大小 $B$ ，可微分的策略函数 $π_{θ} (a_{t}| s)$

输出：策略 $π_{θ}$

随机初始化网络参数 $θ$

Repeat

根据策略 $π_{θ} (a| s)$ 生成轨迹 $τ_{i}$

for $训练次数 = 1, \dots, T$ do

S_{i} \leftarrow S a m p l e i n p u t (S), \forall i = \{1, \dots, B\}

\begin{array}{l} \{α_{i}^{1}, α_{i}^{2}, \dots, α_{i}^{N}\} \leftarrow S e l e c t s t a r t n o d e s (S_{i}), \\ \forall i = \{1, \dots, B\} \end{array}

\begin{array}{l} τ_{i}^{j} \leftarrow S a m p l e r o l l o u t (α_{i}^{1}, S_{i}, π_{θ}), \\ \forall i = \{1, \dots, B\}, \forall j = \{1, \dots, N\} \end{array}

end for

\bar{r} \leftarrow \frac{1}{N} \sum_{j = 1}^{N} r (τ_{i}^{j}), \forall i = \{1, \dots, B\}

\bar{R} \leftarrow β \times r (τ_{i}^{j}) + (1 - β) \bar{r (τ_{i}^{j})}

θ \leftarrow θ + α \nabla_{θ} J_{θ}

until $θ$ 收敛（奖励值稳定）

2.5　模型推理

近年来基于DRL的方法已在COP问题中取得较好的成果，同时也看到，这些方法大多还需结合一些传统的运筹优化方法，如贪婪（Greedy），每次选取输出概率最高的节点（最优的解）；波束搜索（Beam Search），宽度受限广度优先搜索的方式；采样（Sampling），采样一定数量的解，取最优的解^［4］.TSP问题经过模型训练的整体框架如图4所示，模型训练后得到的序列向量，经上述方法推理改善后，其最优间隙能显著降低，进一步提高解的质量.Kwon et al^［5］提出一种八距离扩大的推理方法，由于模拟实验的坐标有对称性，本文采用四距离扩大的方法，即将所有节点坐标 $(x, y)$ 转换为 $(x, 1 - y) (1 - x, y) (1 - x, 1 - y)$ 三种形式，并在3.2的实验结果对比中放置单路径搜索、全路径搜索、八距离扩大三种推理方式.3.3给出了POMO模型推理方法的消融实验（Ablation Experiment），结果显示推理方法有效.

图4

图4 TSP问题编码解码结构示意图

Fig.4 Schematic diagram of encode⁃decode structure of TSP problem

3 数值实验

3.1　实验环境和超参数的设置

基于Pytorch⁃1.9.0深度学习平台，在Windows10操作系统上使用Nvidia RTX 1650 GPU运行本文模型和

POMO模型.分别在20，50，100个节点的TSP问题上进行训练和测试，每个训练批次和测试批次都分别放置在10万和1万的单位平方形中.最优间隙以目前Gurobi，Concorde等专业求解器（已得到100个节点内的最优解）为基准.LKH3、2⁃opt、最远插入、最邻近等传统算法在Intel Core i5⁃9300H CPU上运行.其他结果来自原始文献.所有节点实验中，每个城市的坐标由 $(x_{i}, y_{i})$ 表示，所有城市均放置在 $[0,1] \times [0,1]$ 单位平方形中，训练和测试阶段使用相同的数据分布.PG算法的每个批次放置64个节点，每个城市被嵌入128维的欧几里得空间，MHA中的头部 $H = 8$ ，FF输入层和输出层的维度都是512维，使用 $L = 3$ 的GNN聚合GE层的坐标嵌入，Adam优化器的学习率为 $η = 10^{- 4}$ ，权重衰减率为 $w = 10^{- 7}$ .

3.2　TSP问题实验结果对比

分配每个节点（N）作为一个初始节点，以N种轨迹 $τ^{i}$ 高效寻找二维欧几里得空间中TSP20，TSP50，TSP100的最短路径问题.首先通过目前最先进的专业求解工具Concorde^［9］和Gurobi^［8］计算获得TSP问题的最优解作为其他模型计算最优间隙的基准；其次，对比近年来基于DRL方法求解TSP问题的模型；最后放置本文模型的优化效果.表1针对TSP问题对比了本文的模型和其他模型的优化效果，但没有比较Vinyals，Bello，Nazari，Dai，Deudon^{［13-16，18］}的相关模型，因为已经被Kool et al^［19］的注意力机制模型超越.表中的黑体字表示本文模型优于目前基于DRL的方法， $n \times a u g m e n t$ 表示节点坐标变换为原来的n种形式.由表可见，本文模型在推理阶段的求解时间比部分传统算法更快，与目前基于DRL的方法相当.图5对比了Christofides算法^［10］、2⁃opt等传统方法和POMO框架、图指针网络（Graph Pointer Network，GPN）^［27］、PN网络、NCO模型、S2V⁃DQN模型等经典模型与本文模型的最优间隙.四距离扩大的推理方法使20⁃TSP的最优间隙达到0.00%（越低效果越好），50⁃TSP的最优间隙达到0.01%，100⁃TSP的最优间隙达到0.09%，均优于目前基于DRL的方法.

表1 不同模型在TSP问题上的优化结果比较

Table 1 Optimization results for TSP problem by different models

模型	20⁃TSP			50⁃TSP			100⁃TSP
模型	花费	间隙	时间	花费	间隙	时间	花费	间隙	时间
Concorde^[9]	3.83	0.00%	5 min	5.69	0.00%	13 min	7.76	0.00%	1 h
Gurobi^[8]	3.83	0.00%	7 s	5.69	0.00%	2 min	7.76	0.00%	17 min
OR⁃Tools	3.86	0.94%	1 min	5.85	2.87%	5 min	8.06	3.86%	23 min
LKH3^[12]	3.83	0.00%	42 s	5.69	0.00%	6 min	7.76	0.00%	25 min
2⁃opt ^[1]	3.95	3.13%	1 s	6.11	7.38%	7 s	8.50	9.53%	33 s
Farthest Insertion^[11]	3.89	1.56%	1 s	5.97	4.92%	2 s	8.34	7.47%	10 s
Nearest Neighbor^[1]	4.48	16.9%	1 s	6.94	21.9%	3 s	9.68	24.7%	7 s
Kool et al(Greedy)^[19]	3.85	0.34%	≪1 s	5.80	1.76%	2 s	8.12	4.53%	6 s
Kool et al(Sampling)^[19]	3.84	0.08%	5 min	5.73	0.52%	24 min	7.94	2.26%	1 h
Costa et al^[17]	3.83	0.00%	15 min	5.71	0.12%	29 min	7.83	0.87%	41 min
Wu et al^[22]	3.83	0.00%	1 h	5.70	0.20%	1.5 h	7.87	1.42%	2 h
Kwon et al(single trajec)^[5]	3.83	0.12%	≪1 s	5.74	1.03%	3 s	7.84	1.12%	8 s
Kwon et al(no augment)^[5]	3.83	0.04%	≪1 s	5.71	0.35%	10 s	7.79	0.50%	54 s
Kwon et al(8×augment)^[5]	3.83	0.00%	16 s	5.69	0.05%	1 min	7.77	0.14%	7 min
Ours (single trajec)	3.83	0.13%	≪1 s	5.73	0.70%	5 s	7.84	1.08%	8 s
Ours (no augment)	3.83	0.05%	≪1 s	5.70	0.28%	10 s	7.79	0.47%	55 s
Ours (8×augment)	3.83	0.00%	17 s	5.69	0.03%	1 min	7.77	0.12%	7 min
Ours (4×augment)	3.83	0.00%	9 s	5.69	0.01%	42 s	7.76	0.09%	3 min

图5

图5 经典模型最优间隙的对比图

Fig.5 Comparison diagram of optimal gap in classical models

3.3　消融实验

表2展示了本文模型在TSP问题上的消融实验结果，其中 $n \times a u g m e n t$ 表示节点坐标变换为原来的n种形式，证明了四距离扩大推理方法的有效性.其中，推理时间缩短了约50%，TSP50，TSP100的最优间隙也略有提高，说明此方法是合理的.

表2 POMO模型在TSP问题上的消融实验

Table 2 Results of ablation experiments for TSP problems by POMO model

模型	20⁃TSP			50⁃TSP			100⁃TSP
模型	花费	间隙	时间	花费	间隙	时间	花费	间隙	时间
POMO (8×augment)^[5]	3.83	0.00%	16 s	5.69	0.05%	1 min	7.77	0.14%	7 min
POMO (4×augment)^[5]	3.83	0.00%	7 s	5.69	0.03%	40 s	7.77	0.13%	3 min

3.4　收敛性对比

编码结构中引入PE操作后，对比POMO模型，本文模型在200个批次内可以稳定收敛到较优解，如图6所示.多重起点的初始解和PE层的处理提升了模型的整体优化性能，在训练过程中可得到高质量的解.

图6

图6 本文模型与POMO模型在TSP50/100 (a,b) 上的训练损失对比图

Fig.6 Training loss of our model and POMO model on TSP50/100 (a，b)

3.5　泛化能力对比

以DRL算法结合图注意力模型的求解方法摆脱了传统算法针对相同结构问题专门设计算法的弊端，模型一旦训练完成（得到求解问题的最优策略），即可对任意类似大小问题进行泛化求解.TSP问题的泛化能力的比较结果如表3所示，可见无论在小范围还是大范围的规模上，本文算法的泛化能力都有较好的表现.

表3 本文模型对TSP问题的泛化能力比较

Table 3 Generalization ability of our model for TSP problems

模型	20⁃TSP			50⁃TSP			100⁃TSP
模型	花费	间隙	时间	花费	间隙	时间	花费	间隙	时间
Ours (TSP20)	—	—	—	5.73	0.68%	1 min	8.05	3.73%	5 min
Ours (TSP50)	3.83	0.13%	3 s	—	—	—	7.84	1.03%	4 min
Ours (TSP100)	3.83	0.05%	1 s	5.71	0.33%	30 s	—	—	—

表4 本文模型在训练和推理阶段的时间花费

Table 4 Time cost for training and reasoning by our model

阶段	TSP20	TSP50	TSP100
训练模型	3 h	24 h	136 h
推理(single trajec)	≪1 s	5 s	8 s
推理(no augment)	≪1s	10 s	55 s
推理(8×augment)	17 s	1 min	7 min
推理(4×augment)	9 s	42 s	3 min

3.6　时间花费对比

本文模型分训练和推理两个阶段，每个阶段的耗时如表4所示.由表可见，TSP20在训练阶段耗时3 h，但TSP20在推理阶段仅耗时9 s就可得到最优解.所以综合来看，与传统算法相比，本文算法具有较大的优势.

4 结论和展望

本文提出一种基于DRL训练图注意力模型的框架.鉴于模型中多重起点的放置，编码初始阶段采用PE编码，使多重的初始节点坐标在嵌入的过程中满足平移不变性，进而高层的NN能够提取有效的位置信息，从而增强模型的稳定性，有效防止局部最优.首次将GNN的聚合操作应用于Transformer的解码中，使向量空间具有更强的灵活性和丰富多样的计算形式，以便捕捉图的拓扑结构及节点与节点之间的潜在关系，让更多的潜在信息被表征挖掘.模型训练以 $\bar{R (τ^{i})}$ 作为REINFORCE算法的基准函数，可以有效减小方差，优化了模型的整体性能.该模型求解TSP100问题的效果超越了目前基于DRL的方法和部分传统算法，推理速度超越目前最先进的专业求解器Concorde，且模型具有很好的泛化能力.

未来的工作将考虑求解更大规模的TSP问题，并采用DRL的方法求解更多类型的COP问题，提高模型的泛化能力.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Cook

W J

， Cunningham

W H

， Pulleyblank

W R

，et al. Combinatorial optimization. New York，NY，USA：Wiley⁃Interscience，2010：11-22.

[本文引用: 7]

[2]

Papadimitriou

C H

The Euclidean travelling salesman problem is NP⁃complete

Theoretical Computer Science，1977，4(3)：237-244.

[3]

林敏，刘必雄，林晓宇.

带Metropolis准则的混合离散布谷鸟算法求解旅行商问题

南京大学学报(自然科学)，2017，53(5)：972-983.

Lin

， Liu

B X

， Lin

X Y

Hybrid discrete cuckoo search algorithm with metropolis criterion for traveling salesman problem

Journal of Nanjing University (Natural Science)，2017，53(5)：972-983.

[4]

Bengio

， Lodi

， Prouvost

Machine learning for combinatorial optimization：A methodological tour d'horizon

European Journal of Operational Research，2021，290(2)：405-421.

[5]

Kwon

Y D

， Choo

， Kim

，et al.

POMO：Policy optimization with multiple optima for reinforcement learning

2020，arXiv:.

[本文引用: 8]

[6]

Vaswani

， Shazeer

， Parmar

，et al.

Attention is all you need

∥Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook，NY，USA：Curran Associates Inc.，2017，30：6000-6010.

[本文引用: 4]

[7]

Y X

Deep reinforcement learning：An overview

2017，arXiv:.

[8]

Optimization

I G

Gurobi optimizer reference manual

https:∥www.gurobi.com，2015.

[9]

Applegate

D L

， Bixby

D E

， Chvatal

，et al.

The traveling salesman problem：A computational study

Interfaces，2008，38(4)：344-345.

[10]

Christofides

. Worst⁃case analysis of a new heuristic for the travelling salesman problem. Pittsburgh，PA，USA：Carnegie⁃Mellon University，1976.

[11]

Johnson

D S

Local optimization and the traveling salesman problem

∥The 17^th International Colloquium on Automata，Languages and Programming. Springer Berlin Heidelberg，1990：446-461.

[12]

Helsgaun

An effective implementation of the Lin⁃Kernighan traveling salesman heuristic

European Journal of Operational Research，2000，126(1)：106-130.

[13]

Vinyals

， Fortunato

， Jaitly

Pointer networks

∥Proceedings of the 29th International Conference on Neural Information Processing System. Cambridge，MA，USA：MIT Press，2015(28)：2692-2700.

[14]

Bello

， Pham

， Le

Q V

，et al.

Neural combinatorial optimization with reinforcement learning

2017,arXiv:.

[15]

Deudon

， Cournut

， Lacoste

，et al.

Learning heuristics for the TSP by policy gradient

∥Proceedings of the 15th International Conference on the Integration of Constraint Programming，Artificial Intelligence and Operations Research. Springer Berlin Heidelberg，2018：170-181.

[16]

Nazari

， Oroojlooy

， Takáč

，et al.

Reinforcement learning for solving the vehicle routing problem

∥Proceedings of the 32nd International Conference on Neural Information Processing Systems. Red Hook，NY，USA：Curran Associates Inc.，2018(31)：9861-9871.

[17]

Costa

P R O D

， Rhuggenaath

， Zhang

Y Q

，et al.

Learning 2⁃opt heuristics for the traveling salesman problem via deep reinforcement learning

∥Proceedings of the 12th Asian Conference on Machine Learning. Bangkok，Thailand：JMLR，2020：465-480.

[18]

Dai

H J

， Khalil

E B

， Zhang

Y Y

，et al.

Learning combinatorial optimization algorithms over graphs

∥Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook，NY，USA：Curran Associates Inc.，2017，30：6351-6361.

[19]

Kool

， Van Hoof

， Attention

Welling M.

，learn to solve routing problems. 2019，arXiv：.

[本文引用: 5]

[20]

Chen

X Y

， Tian

Y D

Learning to perform local rewriting for combinatorial optimization

∥Proceedings of the 33^rd Neural Information Processing Systems. Vancouver，Canada：NIPS，2019：6278-6289.

[21]

K W

， Zhang

， Wang

Deep reinforcement learning for multiobjective optimization

IEEE Transactions on Cybernetics，2020，51(6)：3103-3114.

[22]

Y X

， Song

， Cao

Z G

，et al.

Learning improvement heuristics for solving routing problems

IEEE Transactions on Neural Networks and Learning Systems，2021：1-13.

[23]

Xin

， Song

， Cao

Z G

，et al.

Multi⁃decoder attention model with embedding glimpse for solving vehicle routing problems

∥Proceedings of the 35th AAAI Conference on Artificial Intelligence. Palo Alto，CA，USA：AAAI Press，2021：12042-12049.

[24]

Scarselli

， Gori

， Tsoi

A C

，et al.

The graph neural network model

IEEE Transactions on Neural Networks，2008，20(1)：61-80.

[25]

Williams

R J

Simple statistical gradient⁃following algorithms for connectionist reinforcement learning

Machine Learning，1992，8(3)：229-256.

[26]

， Wookey

The real⁃world⁃weight cross⁃entropy loss function：Modeling the costs of mislabeling

IEEE Access，2019(8)：4806-4813.

[27]

， Ge

S W

， He

D Y

，et al.

Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning

2019，arXiv:.