Python实现图神经网络和强化学习

以你之姓@ 2024-03-08 07:45 84阅读 0赞

[资源下载地址][Link 1]：https://download.csdn.net/download/sheziqiong/88294612  
[资源下载地址][Link 1]：https://download.csdn.net/download/sheziqiong/88294612

## 实验三实验报告 ##

## 图神经网络+强化学习 ##

### 一、实验要求 ###

> 复现以下论文的方法和结果：
> 
> Duan,L., Zhan,Y., Hu,H., Gong,Y., Wei,J., Zhang,X., Xu,Y.: Efficiently solving the practical vehicle routing problem: A novel joint learning approach. In: KDD. pp.3054–3063 (2020)
> 
> 1．为了节省时间，训练用10个（或以上）的城市规模的算例。测试算例用20个（或者以上）规模。
> 
> 2．显示出算法训练收敛过程，可视化最后的解。可能的情况下，对比OR-Tools的求解效果（后面详细描述）。

### 二、导言 ###

车辆路径规划问题（VRP）是运筹优化领域最经典的优化问题之一。在此问题中，有若干个客户对某种货物有一定量的需求，车辆可以从仓库取货之后配送到客户手中。客户点与仓库点组成了一个配送网络，车辆可以在此网络中移动从而完成配送任务。在求解此问题过程中，需要优化的决策变量为每个客户的配送任务应该分配到哪一辆车上，以及每辆车完成客户配送任务的先后顺序，优化目标为最小化车辆总行驶距离和使用的车辆数。

故核心优化的目标为车辆总的固定成本 + 运输成本，VRP问题最简单的形式就是使车辆具有容量的约束（装载量有限）。每辆车从给定的节点出发和返回，优化的目标就是车辆相关费用和配送距离的函数。目前的研究工作分为两个流派：一种是通过运筹学，另一种是深度学习。运筹学的方法是把VRP定义为数学优化问题，通过精确或启发式算法达到最优或者近似最优解，但是真实场景的数据量下需要花费的时间很多。而对于深度学习，之前的研究是在人工生成的数据集上，忽略了真实世界的运输网络。在真实VRP问题数据集上，没有一个方法能比得上OR-tools，于是便想着提出一种新的方法。

### 三、算法流程 ###

> 这里主要是将论文中的算法结合我自己的理解再描述一遍

#### 1. Problem Setup: Graph Optimization Perspective ####

首先从图优化的视角来形式化的描述以下VRP问题。 一个VRP实例，可以看做一张图  G = ( V , E ) G=(V, E) G=(V,E) ，其中顶点集合:  V = \{ 0 , … , n \} V=\\\{0, \\ldots, n\\\} V=\{ 0,…,n\}, 其中  i = 0 i=0 i=0 表示depot,  i = 1 , … , n i=1, \\ldots, n i=1,…,n 表示客户，边集合:  E = \{ e i j \} , i , j ∈ V \\quad E=\\left\\\{e\_\{i j\}\\right\\\}, i, j \\in V E=\{ eij\},i,j∈V。

depot节点只有坐标特征  x 0 c x\_\{0\}^\{c\} x0c ，而其他客户节点有坐标特征和需求量特征，因此是一个二维特征向量  x i = \{ x i c , x i d \} x\_\{i\}=\\left\\\{x\_\{i\}^\{c\}, x\_\{i\}^\{d\}\\right\\\} xi=\{ xic,xid\}，其中$ x\_\{i\}^\{c\}, x\_\{i\}^\{d\}$ 分别是坐标特征和需求量特征。每条边关联两个节点之间的距离为  m i j m\_\{i j\} mij 。

假设有： VRP是生成一个tour集合，每个tour代表了一个车辆的路径，从节点0出发，在节点0结束，每个客户被服务一次且仅一次，每辆车的负载不超过它本身的容量，目标是最小化总体花费。

那么，模型的目标是生成一个客户的序列:  π = ( π 1 , π 2 , π 3 , … , π T ) \\pi=\\left(\\pi\_\{1\}, \\pi\_\{2\}, \\pi\_\{3\}, \\ldots, \\pi\_\{T\}\\right) π=(π1,π2,π3,…,πT) 其中,  π t ∈ \{ 0 , 1 , … , n \} \\pi\_\{t\} \\in\\\{0,1, \\ldots, n\\\} πt∈\{ 0,1,…,n\}, 并且  π 0 \\pi\_\{0\} π0 可以出现多次，其他节点只能出现一次。因此，每两个  π 0 \\pi\_\{0\} π0 之间的序列就是一辆车的路线。模型目标如下：  
 min ⁡ c v Q v + c t ∑ t = 1 T − 1 m π t π t + 1 \\min c\_\{v\} Q\_\{v\}+c\_\{t\} \\sum\_\{t=1\}^\{T-1\} m\_\{\\pi\_\{t\} \\pi\_\{t+1\}\} mincvQv\+ctt=1∑T−1mπtπt\+1  
其中  c v c\_\{v\} cv 是每辆车的固定费用,  Q v Q\_\{v\} Qv 是使用的车辆数,  c t c\_\{t\} ct 是行驶的单位消耗。

#### 2. Graph Convolutional Networks with Node Sequential Prediction and Edge Classification ####

模型整体架构如下图（摘自论文）：

![在这里插入图片描述][01c44d9ef9f14b698175b7fe36c63620.png_pic_center]

可以看出整体的模型是GCN模型（graph convolutional networks）以及两个单独的decoder。其中一个是sequential prediction decoder，基于RNN，用node embedding作为输入，输出一个序列，作为VRP实例的一个解；另一个是classification decoder，基于MLP，输入edge embedding，输出一个概率矩阵，矩阵元素的值代表了边出现在车辆路径中的概率，当然也可以根据这个概率矩阵转化成VRP实例的解。同时将sequential prediction decoder的输出当作classification decoder输出的label，学习两个decoder的时候可以相互促进。用强化学习的方式来训练sequential prediction decoder，然后用监督学习的方式做策略采样，是为了训练classification decoder。最后，为了训练完整的模型，使用了一种结合的策略在可接受的时间内返回高质量的解。

##### ① 输入 #####

给定VRP实例的图  G = ( V , E ) \\mathbb\{G\}=(\\mathcal\{V\}, \\mathcal\{E\}) G=(V,E), 除了depot, 每个节点  i ∈ V \\ \{ 0 \} i \\in \\mathcal\{V\} \\backslash\\\{0\\\} i∈V\\\{ 0\}的输入是需求和坐标，节点depot 0 只有坐标信息。它们通过一个Relu全联接网络， 初始化为一个  d x d\_\{x\} dx 维的特征向量。  
 x i = \{ Relu ⁡ ( W 1 x c 0 + b 1 ) , if i = 0 , Relu ⁡ ( \[ W 2 x i c + b 1 ; W 3 x i d + b 2 \] ) , if i ≥ 0 x\_\{i\}=\\left\\\{\\begin\{array\}\{l\} \\operatorname\{Relu\}\\left(W\_\{1\} x\_\{c\_\{0\}\}+b\_\{1\}\\right), \\quad \\text \{ if \} i=0, \\\\ \\operatorname\{Relu\}\\left(\\left\[W\_\{2\} x\_\{i\}^\{c\}+b\_\{1\} ; W\_\{3\} x\_\{i\}^\{d\}+b\_\{2\}\\right\]\\right), \\text \{ if \} i \\geq 0 \\end\{array\}\\right. xi=\{ Relu(W1xc0\+b1), if i=0,Relu(\[W2xic\+b1;W3xid\+b2\]), if i≥0  
其中,  \[ ; \] \[;\] \[;\] 是concat操作。  W 1 , W 2 , W 3 , b 1 , b 2 , b 3 W\_\{1\}, W\_\{2\}, W\_\{3\}, b\_\{1\}, b\_\{2\}, b\_\{3\} W1,W2,W3,b1,b2,b3 是可训练的参数。 对每个  e i j ∈ E ， e\_\{i j\} \\in E ， eij∈E， 边上的特征  y i j y\_\{i j\} yij 是跟节点  ( i , j ) (i, j) (i,j) 之间的邻接关系和距离相关的。尽管  G G G 是全连接的， 仍然会定义邻接矩阵  A ∈ R ( n + 1 ) × ( n + 1 ) : A \\in R^\{(n+1) \\times(n+1)\}: A∈R(n\+1)×(n\+1):  
 a i j = \{ 1 , if i and j are k − nearest neighbors − 1 , if i = j 0 , others a\_\{i j\}=\\left\\\{\\begin\{array\}\{l\} 1, \\text \{ if \} i \\text \{ and \} j \\text \{ are \} k-\\text \{ nearest neighbors \} \\\\ -1, \\text \{ if \} i=j \\\\ 0, \\text \{ others \} \\end\{array\}\\right. aij=⎩⎨⎧1, if i and j are k− nearest neighbors −1, if i=j0, others   
因此，如果  i i i 和  j j j 是  k k k 近邻 (本文  k = 10 k=10 k=10 )，那么他们就是邻接的，否则就不邻接。同时，用-1表示自连接。同样，边特征  y i j y\_\{i j\} yij 初始化为  d y d\_\{y\} dy 维的特征：  
 y i j = Relu ⁡ ( \[ W 4 m i j + b 4 ; W 5 a i j + b 5 \] ) y\_\{i j\}=\\operatorname\{Relu\}\\left(\\left\[W\_\{4\} m\_\{i j\}+b\_\{4\} ; W\_\{5\} a\_\{i j\}+b\_\{5\}\\right\]\\right) yij=Relu(\[W4mij\+b4;W5aij\+b5\])  
其中  W 4 , W 5 , b 4 , b 5 W\_\{4\}, W\_\{5\}, b\_\{4\}, b\_\{5\} W4,W5,b4,b5 是可训练的参数。

##### ② GCN Encoder #####

给定  d x d\_\{x\} dx 维的节点特征  x i x\_\{i\} xi 和  d y d\_\{y\} dy 维的边特征  y i j y\_\{i j\} yij, encoder首先分别计算出  d h d\_\{h\} dh 维的节点和边的embedding , 记做  h i 0 h\_\{i\}^\{0\} hi0 和  h e i j 0 h\_\{e\_\{i j\}\}^\{0\} heij0, 用到的线性映射的参数分别为  W E 1 , W E 2 , b E 1 , b E 2 W\_\{E 1\}, W\_\{E 2\}, b\_\{E 1\}, b\_\{E 2\} WE1,WE2,bE1,bE2 。  
 h i 0 = W E 1 x i + b E 1 h e i j 0 = W E 2 y i j + b E 2 . \\begin\{array\}\{r\} h\_\{i\}^\{0\}=W\_\{E 1\} x\_\{i\}+b\_\{E 1\} \\\\ h\_\{e\_\{i j\}\}^\{0\}=W\_\{E 2\} y\_\{i j\}+b\_\{E 2\} . \\end\{array\} hi0=WE1xi\+bE1heij0=WE2yij\+bE2.  
然后这些embedding会通过一个  L L L 层的图卷积  ( G C ) (G C) (GC) 层, 每一层包含两个子层： aggregation和combination。

在一个标准的  L L L 层GCN中，每一层  l ( l = 1 , 2 , … , L ) l(l=1,2, \\ldots, L) \\quad l(l=1,2,…,L)都有aggregation和combination两个子层。通过  l l l 层之后的节点embedding定义如下：  
 h N ( i ) ℓ = σ ( W ℓ A G G ( \{ h i ′ ℓ − 1 , ∀ i ′ ∈ N ( i ) \} ) ) h i ℓ = C O M B I N E ( h i ℓ − 1 , h N ( i ) ℓ ) \\begin\{array\}\{c\} h\_\{N(i)\}^\{\\ell\}=\\sigma\\left(W^\{\\ell\} A G G\\left(\\left\\\{h\_\{i^\{\\prime\}\}^\{\\ell-1\}, \\forall i^\{\\prime\} \\in N(i)\\right\\\}\\right)\\right) \\\\ h\_\{i\}^\{\\ell\}=C O M B I N E\\left(h\_\{i\}^\{\\ell-1\}, h\_\{N(i)\}^\{\\ell\}\\right) \\end\{array\} hN(i)ℓ=σ(WℓAGG(\{ hi′ℓ−1,∀i′∈N(i)\}))hiℓ=COMBINE(hiℓ−1,hN(i)ℓ)  
其中,  h N ( i ) l h\_\{N(i)\}^\{l\} hN(i)l 表示节点  i i i 邻接节点的聚合特征,  N ( i ) N(i) N(i) 表示节点  i i i 的邻接节点。  A G G A G G AGG 是一个 聚合函数，可定制，例如max-pooling, mean-pooling, 或者基于注意力的加权求和。  W l W^\{l\} Wl 是 可训练的矩阵，被第  l l l 层上所有节点共享。  σ \\sigma σ 是一个非线性激活函数，例如Relu。  C O M B I N E C O M B I N E COMBINE 是一个组合自身embedding和邻接节点聚合embedding的函数，同样是可定制的，例如 GraphSAGE中用的concat函数。 在本文中，考虑到VRP的图，作者改造了标准的  G C N \\mathrm\{GCN\} GCN 。标准的GCN把所有节点看作一样的，没有边特征。而这里的GCN同时输入了节点和边特征，并且同时更新他们。

###### Aggregation sub-layer ######

对于两个子层，首先是**Aggregation sub-layer**，对于节点  v i ∈ V v\_\{i\} \\in V vi∈V ，具体的节点聚合embedding  h N ( i ) l h\_\{N(i)\}^\{l\} hN(i)l 如下:  
 h N ( i ) ℓ = σ ( W I ℓ A G G I ℓ ( A T T N ( h i ℓ − 1 , \{ h v r ℓ − 1 , ∀ v , ∈ N ( i ) \} ) ) h\_\{N(i)\}^\{\\ell\}=\\sigma\\left(W\_\{I\}^\{\\ell\} A G G\_\{I\}^\{\\ell\}\\left(A T T N\\left(h\_\{i\}^\{\\ell-1\},\\left\\\{h\_\{v r\}^\{\\ell-1\}, \\forall v, \\in N(i)\\right\\\}\\right)\\right)\\right. hN(i)ℓ=σ(WIℓAGGIℓ(ATTN(hiℓ−1,\{ hvrℓ−1,∀v,∈N(i)\}))  
其中,  W I l W\_\{I\}^\{l\} WIl 是可训练参数,  A T T N A T T N ATTN 是一个函数：  f : h key × H val → h v a l f: h\_\{\\text \{key \}\} \\times H\_\{\\text \{val \}\} \\rightarrow h\_\{v a l\} f:hkey ×Hval →hval, 把特征向量  h k e y h\_\{k e y\} hkey 和候选特征向量集合  H v a l H\_\{v a l\} Hval 映射到一个特征向量的加权和。attention的权重可以是scaled dotproduct attention。 对于边  e i j ∈ E e\_\{i j\} \\in E eij∈E ，考虑这条边连接的两个节点。因此, 这条边的聚合embedding  h N ( e i j ) l h\_\{N\\left(e\_\{i j\}\\right)\}^\{l\} hN(eij)l 可 以定义为：  
 h N ( e i j ) ℓ = σ ( W E ℓ A G G E ℓ ( \{ h e i j ℓ − 1 , h i ℓ − 1 , h j ℓ − 1 ) ) A G G E ℓ ( \{ h e i j ℓ − 1 , h i ℓ − 1 , h j ℓ − 1 ) = W e 1 ℓ h e i j ℓ + W e 2 ℓ h i ℓ + W e 3 ℓ h j ℓ \\begin\{array\}\{c\} h\_\{N\\left(e\_\{i j\}\\right)\}^\{\\ell\}=\\sigma\\left(W\_\{E\}^\{\\ell\} A G G\_\{E\}^\{\\ell\}\\left(\\left\\\{h\_\{e\_\{i j\}\}^\{\\ell-1\}, h\_\{i\}^\{\\ell-1\}, h\_\{j\}^\{\\ell-1\}\\right)\\right)\\right. \\\\ A G G\_\{E\}^\{\\ell\}\\left(\\left\\\{h\_\{e\_\{i j\}\}^\{\\ell-1\}, h\_\{i\}^\{\\ell-1\}, h\_\{j\}^\{\\ell-1\}\\right)=W\_\{e 1\}^\{\\ell\} h\_\{e\_\{i j\}\}^\{\\ell\}+W\_\{e 2\}^\{\\ell\} h\_\{i\}^\{\\ell\}+W\_\{e 3\}^\{\\ell\} h\_\{j\}^\{\\ell\}\\right. \\end\{array\} hN(eij)ℓ=σ(WEℓAGGEℓ(\{ heijℓ−1,hiℓ−1,hjℓ−1))AGGEℓ(\{ heijℓ−1,hiℓ−1,hjℓ−1)=We1ℓheijℓ\+We2ℓhiℓ\+We3ℓhjℓ  
其中,  W E l , W e 1 l , W e 2 l , W e 3 l \\quad W\_\{E\}^\{l\}, W\_\{e 1\}^\{l\}, W\_\{e 2\}^\{l\}, W\_\{e 3\}^\{l\} WEl,We1l,We2l,We3l 都是可训练参数。

###### Combination sub-layer ######

接下来是**Combination sub-layer**。在得到了聚合embedding之后，可以按如下策略定义组合子层：  
 h i ℓ = \[ V I ℓ h i ℓ − 1 ; h N ( i ) ℓ \] h e i j ℓ = \[ V E ℓ h e i j ℓ − 1 ; h N ( e i j ) ℓ \] \\begin\{array\}\{c\} h\_\{i\}^\{\\ell\}=\\left\[V\_\{I\}^\{\\ell\} h\_\{i\}^\{\\ell-1\} ; h\_\{N(i)\}^\{\\ell\}\\right\] \\\\ h\_\{e\_\{i j\}\}^\{\\ell\}=\\left\[V\_\{E\}^\{\\ell\} h\_\{e\_\{i j\}\}^\{\\ell-1\} ; h\_\{N\\left(e\_\{i j\}\\right)\}^\{\\ell\}\\right\] \\end\{array\} hiℓ=\[VIℓhiℓ−1;hN(i)ℓ\]heijℓ=\[VEℓheijℓ−1;hN(eij)ℓ\]  
其中,  V I l V\_\{I\}^\{l\} VIl 和  V E l V\_\{E\}^\{l\} VEl 分别是节点和边的可训练的权重矩阵。  h i l h\_\{i\}^\{l\} hil 和  h e i j l h\_\{e\_\{i j\}\}^\{l\} heijl 是节点和边在第  l l l 层的隐状态。另外，这些可训练的参数每层都是单独的。还有，每个子层会增加一 个skip-connection和layer normalization操作。

##### ③ The Decoders #####

得到了GCN的编码embedding之后，作者提出了两个网络独立的decode它们。

###### Sequential prediction decoder ######

用GRU和基于上下文的attention机制，将节点embedding映射成一个序列  π \\pi π 。之所以选用序列模型而不是self-attention机制，是因为序列的解严重依赖前序的步骤。 给定任意一个输入  S S S, 该过程会生成一个长度为  T T T 的序列， π = \{ π t , t = 1 , … , T \} \\pi=\\left\\\{\\pi\_\{t\}, t=1, \\ldots, T\\right\\\} π=\{ πt,t=1,…,T\} ， 长度有可能超过n+1，因为depot节点可能会出现多次。同时也可以用符号  π t \\pi\_\{t\} πt 表示时间步  t t t 时刻已生成的序列。我们便希望找到一个随机策略  p ( π ∣ S ; θ ) p(\\pi \\mid S ; \\theta) p(π∣S;θ) ，可以生成一个序列  π \\pi π, 最小化目标。这个随机策略是一个联合概率，根据链式法则可以分解如下:  
 P ( π ∣ s ; θ ) = ∏ t = 0 T p ( π t + 1 ∣ S , π t ; θ ) = ∏ t = 0 T p ( π t + 1 ∣ f ( S , θ e ) , π t ; θ d ) \\begin\{equation\} \\begin\{aligned\} P(\\boldsymbol\{\\pi\} \\mid s ; \\theta) &=\\prod\_\{t=0\}^\{T\} p\\left(\\pi\_\{t+1\} \\mid S, \\pi\_\{t\} ; \\theta\\right) \\\\ &=\\prod\_\{t=0\}^\{T\} p\\left(\\pi\_\{t+1\} \\mid f\\left(S, \\theta\_\{e\}\\right), \\pi\_\{t\} ; \\theta\_\{d\}\\right) \\end\{aligned\} \\end\{equation\} P(π∣s;θ)=t=0∏Tp(πt\+1∣S,πt;θ)=t=0∏Tp(πt\+1∣f(S,θe),πt;θd)

其中,  f ( S ; θ e ) f\\left(S ; \\theta\_\{e\}\\right) f(S;θe) 是编码器,  θ d \\theta\_\{d\} θd 是可训练的参数。这里用一个GRU单元，通过引入一个状 态向量  z t z\_\{t\} zt 来估计最后一项， embeds了已生成的序列  π t − 1 \\pi\_\{t-1\} πt−1 ，例如:  
 p ( π t ∣ f ( S , θ e ) , π t − 1 ; θ d ) = p ( π t ∣ f ( S , θ e ) , z t ; θ d ) . p\\left(\\pi\_\{t\} \\mid f\\left(S, \\theta\_\{e\}\\right), \\boldsymbol\{\\pi\}\_\{t-1\} ; \\theta\_\{d\}\\right)=p\\left(\\pi\_\{t\} \\mid f\\left(S, \\theta\_\{e\}\\right), z\_\{t\} ; \\theta\_\{d\}\\right) . p(πt∣f(S,θe),πt−1;θd)=p(πt∣f(S,θe),zt;θd).  
解码过程也是序列的，在decode时间步  t ∈ \{ 1 , … , T \} t \\in\\\{1, \\ldots, T\\\} t∈\{ 1,…,T\}, 序列decoder根据GCN生成的节点 embedding和GRU的隐状态  z t z\_\{t\} zt 来生成节点  π t 。 \\pi\_\{t\} 。 πt。 具体的方法是  p ( π t ∣ z t , f ( S , u ; θ e ) ; θ d ) p\\left(\\pi\_\{t\} \\mid z\_\{t\}, f\\left(S, u ; \\theta\_\{e\}\\right) ; \\theta\_\{d\}\\right) p(πt∣zt,f(S,u;θe);θd) 通过一 个特殊的attention机制：Pointer网络，它会跟encode网络中的每一个节点计算一个attention score, 然后经过softmax来得到概率分布。它允许decoder随时查看整个图  G ( V , E ) G(V, E) G(V,E), 并且最终选中一个输入节点作为最终的输出  π \\pi π 。 为了符号方便，假设  h i L h\_\{i\}^\{L\} hiL 是embeded好的输入。在decode的时间步  t t t, 节点  i i i 的上下文权重  u t i u\_\{t i\} uti 计算方法如下：  
 u t i = \{ − ∞ , ∀ j ∈ N m t h a T tanh ⁡ ( W G \[ v i ; z t \] ) , otherwise u\_\{t i\}=\\left\\\{\\begin\{array\}\{ll\} -\\infty, & \\forall j \\in N\_\{m t\} \\\\ h\_\{a\}^\{T\} \\tanh \\left(W^\{G\}\\left\[v\_\{i\} ; z\_\{t\}\\right\]\\right), & \\text \{ otherwise \} \\end\{array\}\\right. uti=\{ −∞,haTtanh(WG\[vi;zt\]),∀j∈Nmt otherwise   
其中,  N m t N\_\{m t\} Nmt 是时间步  t t t 时刻mask住的节点集合。  h a T ∈ R d h , W G ∈ R 1 × 2 h\_\{a\}^\{T\} \\in R^\{d\_\{h\}\}, \\quad W^\{G\} \\in R^\{1 \\times 2\} haT∈Rdh,WG∈R1×2 是参数。注意到，在开始计算上下文attention之前，有一个将时间步  t t t 时刻不可用的节点mask掉的过程。 mask的规则跟问题的约束有关。 在VRP问题中，每辆车的容量  c > 0 c>0 c>0, 每个节点有各自的需求量  x i d x\_\{i\}^\{d\} xid, 假设  0 < x i d < c , ∀ i ∈ \{ 1 , 2 , … , N \} 0<x\_\{i\}^\{d\}<c, \\forall i \\in\\\{1,2, \\ldots, N\\\} 0<xid<c,∀i∈\{ 1,2,…,N\}, 并且  x 0 d = 0 x\_\{0\}^\{d\}=0 x0d=0 。有一个可行性的约束, 就是每条线路的需求量, 不能超过车的容量，也就是说  ∑ i ∈ R j x i d < c \\sum\_\{i \\in R\_\{j\}\} x\_\{i\}^\{d\}<c ∑i∈Rjxid<c, 其中,  R j R\_\{j\} Rj 是路径  j j j 上的节点集合。 为了满足容量约束，始终关注每个节点在时间步  t t t 尚未满足的需求  x i d , i ∈ \{ 1 , … , N \} x\_\{i\}^\{d\}, i \\in\\\{1, \\ldots, N\\\} xid,i∈\{ 1,…,N\} 和 车辆的剩余容量  c t ~ \\tilde\{c\_\{t\}\} ct~ 。如果一个节点遍历过了, 设  x ~ i d = 0 \\tilde\{x\}\_\{i\}^\{d\}=0 x~id=0 。剩余容量更新如下:  
 c ~ t = \{ c , π t = 0. max ⁡ ( 0 , c ~ t − 1 − x π t d ) , π t ≠ 0 \\tilde\{c\}\_\{t\}=\\left\\\{\\begin\{array\}\{ll\} c, & \\pi\_\{t\}=0 . \\\\ \\max \\left(0, \\tilde\{c\}\_\{t-1\}-x\_\{\\pi\_\{t\}\}^\{d\}\\right), & \\pi\_\{t\} \\neq 0 \\end\{array\}\\right. c~t=\{ c,max(0,c~t−1−xπtd),πt=0.πt=0  
另外，在时间步  t t t ，不允许节点的需求量超过车辆的剩余装载量。也不允许depot出现在两个相邻的时间步中，因此，得出了如下的mask节点的方法：  
 N m t = \{ N m ( t − 1 ) ∪ \{ 0 \} π t − 1 = 0 or t = 1 ∪ \{ i ∣ x ~ i d = 0 or x ~ i d ≥ c ~ t \} , others N\_\{m t\}=\\left\\\{\\begin\{array\}\{ll\} N\_\{m(t-1)\} \\cup\\\{0\\\} & \\pi\_\{t-1\}=0 \\text \{ or \} t=1 \\\\ \\cup\\left\\\{i \\mid \\tilde\{x\}\_\{i\}^\{d\}=0 \\text \{ or \} \\tilde\{x\}\_\{i\}^\{d\} \\geq \\tilde\{c\}\_\{t\}\\right\\\}, & \\text \{ others \} \\end\{array\}\\right. Nmt=\{ Nm(t−1)∪\{ 0\}∪\{ i∣x~id=0 or x~id≥c~t\},πt−1=0 or t=1 others   
然后用softmax函数得出指向输入节点的分布：  
 p ( π t ∣ f ( S , θ e ) , π t − 1 ; θ d ) = softmax ⁡ ( u t i ) , j ∈ \{ 1 , … , N \} p\\left(\\pi\_\{t\} \\mid f\\left(S, \\theta\_\{e\}\\right), \\pi\_\{t-1\} ; \\theta\_\{d\}\\right)=\\operatorname\{softmax\}\\left(u\_\{t i\}\\right), j \\in\\\{1, \\ldots, N\\\} p(πt∣f(S,θe),πt−1;θd)=softmax(uti),j∈\{ 1,…,N\}

###### Classification decoder ######

之前有工作利用GCN和边embedding特征，并且利用最优解作为label来解决TSP问题。但是这里的场景并不适用，因为目标是解决大数据量的真实VRP问题，最优解很难给出来。 由此也促使作者想出一个新方法。从直觉看，由于节点embedding和边embedding都包含了图 的信息，并且相互影响，因此从序列decoder得出的解和分类器decoder得出的解应该一致才符合逻辑，当方法收敘的时候。因此，作者把序列decoder得出的解  π \\pi π 作为分类器decoder的 监督label。另外，一个节点的序列可以唯一转化为一条车辆路径上边的序列。例如，序列  \{ 0 , 4 , 5 , 1 , 0 , 2 , 3 , 0 \} \\\{0,4,5,1,0,2,3,0\\\} \{ 0,4,5,1,0,2,3,0\} 对应着边的集合  \{ e 04 , e 45 , e 51 , e 10 , e 02 , e 23 , e 30 \} \\left\\\{e\_\{04\}, e\_\{45\}, e\_\{51\}, e\_\{10\}, e\_\{02\}, e\_\{23\}, e\_\{30\}\\right\\\} \{ e04,e45,e51,e10,e02,e23,e30\} 。不论是节点序列还是边序列，都可以表示VRP实例的一个解。假设出现在车辆路径上的边权重为1，未出现的为0，便可以获得一个0-1矩阵，对应着一个序列，使得  P E V R P ∗ = \{ p e i j V R ∗ \} e i j ∈ E P\_\{E\}^\{V R P^\{\*\}\}=\\left\\\{p\_\{e\_\{i j\}\}^\{V R^\{\*\}\}\\right\\\} e\_\{i j\} \\in E PEVRP∗=\{ peijVR∗\}eij∈E。  
把  P E V R P ∗ P\_\{E\}^\{V R P^\{\*\}\} PEVRP∗ 作为label，然后把边embedding的GCN最后一层输出  h e i j L h\_\{e\_\{i j\}\}^\{L\} heijL 经过一个MLP, 然 后获得一个softmax分布，可以看作边  e i j e\_\{i j\} eij 出现的概率。形式化的表示就是：  
 p e i j V R P = softmax ⁡ ( M L P ( h e i j L ) ) ∈ \[ 0 , 1 \] 2 p\_\{e\_\{i j\}\}^\{\\mathrm\{VRP\}\}=\\operatorname\{softmax\}\\left(M L P\\left(h\_\{e\_\{i j\}\}^\{L\}\\right)\\right) \\in\[0,1\]^\{2\} peijVRP=softmax(MLP(heijL))∈\[0,1\]2  
在下文中，作者用  P E V R P P\_\{E\}^\{V R P\} PEVRP 来表示MLP得到的概率矩阵。这个输出需要尽可能接近  P E V R P ∗ P\_\{E\}^\{V R P^\{\*\}\} PEVRP∗ 。 该架构可以通过一个预测精准的序列，使得分类器decoder得到提升。反过来，利用提升的边特征，可以是的序列decoder效果更好，从而形成良性循环。

##### ④A Joint Learning Strategy #####

上述模型结合了强化学习和监督学习。为了训练它，同样需要两者结合的策略。

###### REINFORCE with rollout baseline ######

首先把reinforced损失作为期望损失：  L r ( θ e , θ d ∣ S ) = E P ( π ∣ f ( S ; θ e ) ; θ d ) L ( π ) L\_\{r\}\\left(\\theta\_\{e\}, \\theta\_\{d\} \\mid S\\right)=E\_\{P\\left(\\pi \\mid f\\left(S ; \\theta\_\{e\}\\right) ; \\theta\_\{d\}\\right)\} L(\\pi) Lr(θe,θd∣S)=EP(π∣f(S;θe);θd)L(π) ， 其中  L ( π ) L(\\pi) L(π)是解  π \\pi π 的整体cost。作者使用带有baseline  b ( S ) b(S) b(S) 的REINFORCE算法来训练策略。损失函数推导如下：  
 L r ( θ e , θ d ) = ∑ S E π ∼ P ( π ∣ S ; θ e , θ d ) ( L ( π ) − b ( s ) ) = ∑ S ( L ( π ) − b ( S ) ) ∑ i = 1 T log ⁡ p ( π i ∣ π i − 1 , S ; θ e , θ d ) \\begin\{equation\} \\begin\{aligned\} \\mathcal\{L\}\_\{r\}\\left(\\theta\_\{e\}, \\theta\_\{d\}\\right) &=\\sum\_\{S\} \\mathbb\{E\}\_\{\\boldsymbol\{\\pi\} \\sim P\\left(\\boldsymbol\{\\pi\} \\mid S ; \\theta\_\{e\}, \\theta\_\{d\}\\right)\}(L(\\boldsymbol\{\\pi\})-b(s)) \\\\ &=\\sum\_\{S\}(L(\\boldsymbol\{\\pi\})-b(S)) \\sum\_\{i=1\}^\{T\} \\log p\\left(\\pi\_\{i\} \\mid \\boldsymbol\{\\pi\}\_\{i-1\}, S ; \\theta\_\{e\}, \\theta\_\{d\}\\right) \\end\{aligned\} \\end\{equation\} Lr(θe,θd)=S∑Eπ∼P(π∣S;θe,θd)(L(π)−b(s))=S∑(L(π)−b(S))i=1∑Tlogp(πi∣πi−1,S;θe,θd)

###### SUPERVISE with policy-sampling ######

根据上文所述，分类器decoder的损失函数如下:  
 L s ( θ e , θ c ) = − ∑ S , π crossEntropy ( P E V R P , P E V R P ⋆ ) \\mathcal\{L\}\_\{s\}\\left(\\theta\_\{e\}, \\theta\_\{c\}\\right)=-\\sum\_\{S, \\boldsymbol\{\\pi\}\} \\text \{ crossEntropy \}\\left(P\_\{E\}^\{V R P\}, P\_\{E\}^\{\\mathrm\{VRP\}^\{\\star\}\}\\right) Ls(θe,θc)=−S,π∑ crossEntropy (PEVRP,PEVRP⋆)  
其中,  θ c \\theta\_\{c\} θc 是可训练参数，为了结合REINFORCE和SUPERVISE，可以简单地把二者的损失函数做线性组合，最终的损失函数如下:  
 L θ = α × L s ( θ ) + β × L r ( θ ) \\mathcal\{L\}\_\{\\boldsymbol\{\\theta\}\}=\\alpha \\times \\mathcal\{L\}\_\{s\}(\\boldsymbol\{\\theta\})+\\beta \\times \\mathcal\{L\}\_\{r\}(\\boldsymbol\{\\theta\}) Lθ=α×Ls(θ)\+β×Lr(θ)

### 四、代码实现 ###

首先，整个算法的流程如论文中的算法流程一致，如下：（摘自论文）

![在这里插入图片描述][91cab38a956e49dc8b4b82dfb16ee470.png_pic_center]

首先, 定义一个baseline策略  P θ B L P\_\{\\theta^\{B L\}\} PθBL 作为训练策略  P θ P\_\{\\theta\} Pθ, 在训练过程中，模型在不断变化, 但是baseline策略会冻结一定数量的steps（每个epoch) 直到效果显著提升（配对样本  T T T 检验的  γ = 5 % \\gamma=5 \\% γ=5% ) 。第6行是通过GCN编码器生成节点embedding  H I i H\_\{I\_\{i\}\} HIi 和边embedding  H E i H\_\{E\_\{i\}\} HEi 。然后用序列预测 decoder将节点embedding  H I i H\_\{I\_\{i\}\} HIi, 通过两个策略  P θ P\_\{\\theta\} Pθ 和  P θ B L P\_\{\\theta^\{B L\}\} PθBL 输出两个解：  π i \\pi\_\{i\} πi,  π i B L \\pi\_\{i\}^\{B L\} πiBL 。第9行是把解  π i \\pi\_\{i\} πi 转化成0-1矩阵作为分类器decoder的label。

我们在复现的时候主要也是参考了助教所给出的代码，最终完成了复现。

### 四、实验结果 ###

我们使用G-20数据集训练10轮，最终结果图如下：

因为训练一轮的时间过久，我们只训练了10轮，所以现在的结果可能还并不是很好。

loss结果如下：  
![在这里插入图片描述][08696ab4a1c649619a909668513c20fe.png_pic_center]

由于这里的loss为访问当前客户行驶的路径长度的**负值** ，所以不断增长代表着路径长度在不断减小，所以路径总长度是在不断减小的。

[资源下载地址][Link 1]：https://download.csdn.net/download/sheziqiong/88294612  
[资源下载地址][Link 1]：https://download.csdn.net/download/sheziqiong/88294612

[Link 1]: https://download.csdn.net/download/sheziqiong/88294612
[01c44d9ef9f14b698175b7fe36c63620.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/67b6ece127c5400488ec67968f297240.png
[91cab38a956e49dc8b4b82dfb16ee470.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/9568df2a9d254e7194b06df363ad266a.png
[08696ab4a1c649619a909668513c20fe.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/e730ac0b2d834cf0b8ddc50f65d741ef.png