Pointer Networks

Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. "Pointer Networks.", Conference on Neural Information Processing Systems abs/1506.03134. (2015): 2692-2700.

的输出类别是固定的，比如对于问题，每次的输出是从固定大的词汇表中输出一个单词。但对于组合优化问题，比如，对于不同规模大小的问题，其点数不同，输出不是固定的。就是为了解决这种输出不固定的问题。

Sequence-to-Sequence Model

问题描述：比如对于：输入是个点，输出是一个长为的排列。

模型对于训练数据，拟合条件概率：其中为参数。

Content Based Input Attention

和都是。和的隐藏状态分别定义为和。模型第次输出为，注意力机制额外求出注意力向量，将二者连接后，作为隐藏状态来实现预测。表示和的距离。

Ptr-Net

用作为指向输入元素的指针。将输入作为查找的词典，而不是用事先固定的词典。

Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

Ma Qiang, Ge Suwen, He Danyang, Thaker Darshan, and Drori Iddo. "Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning", arXiv preprint arXiv 1911.04936 (2019)

即为找到一个最佳排列，使得路径长度最小：

Reinforcement Learning for TSP

奖励的期望为：是城市集合的空间，是上所有可能排列的空间。是上的分布，由神经网络预测。用策略梯度算法最大化奖励函数来训练。

Hierarchical RL for TSP

第层中，动作由策略采样得到。是前一层提供的潜在变量，该层为下一层提供潜在变量，即为。

Hierarchical Policy Gradient

第层的目标函数为。由算法得，其策略梯度为：其中为批量大小，为第层的。用梯度下降来更新参数。动作是用贪心采样得到。

对于这个层的分层策略，每个策略用一个表示。

GPN Architecture

Encoder

包含两部分，和。

将节点映射到维向量，并且所有节点共享映射变换的参数，然后通过进一步编码得到隐藏变量，会传递给和下一时刻的。

对进行编码后输入到里。

Graph Embedding Layer

的每一层为：是一个可训练的参数，用来正则化权重矩阵的特征值，是可训练的权重矩阵，是聚合函数，用神经网络来拟合。

考虑的是完全图，将每一层写成矩阵的形式为：具体实验中使用的聚合函数是单层的全连接神经网络，图嵌入层即为： Vector Context

一般的都是用城市的二维坐标，即，但这篇文章用的是一个城市指向其他城市的向量，称为。

设，为。图嵌入层就改为： Decoder

生成指针向量，定义为：其中和是可训练矩阵，为的隐藏变量，为中的，即。根据策略来抽样或者贪心来得到动作。

Experiments

小规模的问题：

大规模的问题：

Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem

Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. "Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem", CoRR abs/2304.09407 (2023): 8132-8140.

目标为最大化奖励：根据策略梯度定理得：

Reversible residual network based encoder

采取特征增强，将每个节点从表示改为，其中。同时翻转和旋转整张图，得到原图的个等效的图，得到的每个图节点的特征也作为节点的特征。这样每个节点就有个特征来作为初始嵌入层的输入了。

使用可逆残差网络，不同于剩余网络，其不需要存储所有剩余层的激活值来计算反向传播中的梯度。

因为可以从输出嵌入可以直接计算出输入嵌入，所以不需要存储所有激活值。

Multi-pointer network based decoder

Enhanced Context Embedding 是第一个节点的嵌入。是当前最后一个节点的嵌入。是对整张图的嵌入，，是第个节点嵌入。是当前已考虑节点的嵌入，。

被用作查询，，

A Multi-pointer Network

在每一步中，用于和和所有要访问的节点交互，来得到它们的概率分布。其中是当前得到的部分路径中的最后一个节点。这里减去能鼓励每次选择最近的节点来作为下一个访问的节点。是平衡探索和利用的一个参数。最后用来计算概率。

A modified REINFORCE algorithm

用算法来训练模型。

对于一个个节点的实例，将每个点都作为起始点来得到条可行路径，然后对这条路径进行蒙特卡洛采样。

对于一个包含个实例的批次，可以得到个路径。训练前进行归一化处理，这样能提高收敛速度和保证稳定训练。