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

编程入门行业动态更新时间:2024-10-19 00:28:58

Python实现图<a href=https://www.elefans.com/category/jswz/34/1769690.html style= 神经网络和强化学习"/>

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

资源下载地址：
资源下载地址：

实验三实验报告

图神经网络+强化学习

一、实验要求

复现以下论文的方法和结果：

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

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

可以看出整体的模型是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(θ)

四、代码实现

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

首先, 定义一个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。

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