论文阅读——Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
该论文的Abstract:
该论文以组合优化问题中的旅行商问题为例，采用了指针网络（Pointer Networks）和图神经网络（Graph Neural Networks）相结合的图指针网络（Graph Pointer Networks），并且采用了分层强化学习（Hierarchical Reinforcement Learning）将约束组合问题分成不同的子任务。
该论文的Contributions：
①提出了GPN来解决TSP问题，使用图嵌入层扩展指针网络并实现更快的收敛。
②在GPN中加入了context向量并使用早停进行训练，来处理更大规模的TSP实例。
③采用分层 RL 框架和 GPN 架构来有效地解决具有时间窗口约束的 TSP。
TSP问题
该论文专注于解决2维对称欧几里得TSP问题。对称的TSP问题可以看成一个完全无向图。给定一个 
个城市坐标的列表 
，找到一条最优路线，使每个城市只访问一次并且路线中覆盖的总距离最小。换句话说，在城市上找到一个最优排列 
，使行程长度最小。
其中，对任意的 
来说， 
，并且
是由各个城市坐标 
组成的矩阵。除此之外，该论文考虑了 TSP 的约束条件。则约束优化问题如下：
其中， 
是一个排列， 
和 
表示约束条件。
TSP在强化学习中的使用
首先介绍用于将 TSP 表述为强化学习问题的符号。让 
表示状态空间， 
表示动作空间。每个状态 
定义为所有之前已经访问过的城市的集合，例如 
。动作 
定义为接下来选择的城市，
。由于 
，因此 
，表示最后选择的城市是起始城市。
将策略表示为 
。给定一组访问过的城市 
，该策略将返回下一个尚未选择的候选城市 
的概率分布。 在本例中，策略由神经网络表示，参数 
表示神经网络的可训练权重。此外，奖励函数被定义为从状态 
采取动作 
所产生的负成本（negative cost），例如，
。则期望奖励被定义为：
其中，
表示城市组成的空间，
表示所有在 
上的可能城市排列 
的空间，
表示由神经网络预测的 
的分布。为了最大化上述奖励函数，网络必须学习一个策略来最小化预期的旅行长度。 这里采用策略梯度算法来学习最大化奖励函数，如下所述。
分层强化学习
分层强化学习在TSP上的应用
用惩罚项增加传统的 RL 奖励函数鼓励解决方案在可行集中，但这种方法会导致训练不稳定。 为此，本文提出了一个分层 RL 框架，以更有效地处理具有约束的 TSP。
受 Haarnoja 等人的启发，这里采用了一种概率图形模型框架，如图 1 所示。层次结构每一层都定义了一个策略，我们可以从中取样 actions 。在一个给定的层 
，当前的动作 
从策略 
中抽样出来，其中 
是来自层次结构中前一层的隐藏变量， 
是相应的隐藏空间。如图 1(b) 所示，最低层是一个简单的马尔可夫决策过程（MDP），
从策略 
抽样获得，同时最低层向更高一层提供一个隐藏变量 
。中间层不仅仅从第 
层的获取隐藏变量 
，而且为更高层提供隐藏变量 
。为了方便标记，在第 
层，将策略扩展为既对动作进行抽样，又提供隐藏变量，例如，
。
每层对应一个不同的 RL 任务，因此每个层的奖励函数都是手工设计的。 有两种自然的方法可以以分层方式制定受约束的 TSP 优化问题。首先，我们将下层奖励函数设置为简单地将解决方案偏置到约束优化问题的可行集中，并将上层奖励函数设置为原始优化目标。 相反，我们按照优化难度对奖励函数进行排序：第一层尝试解决简单TSP，第二层被赋予一个具有一个约束的 TSP 实例，依此类推。 对于我们的实验，我们使用第一个公式，因为我们发现这会产生更好的结果。
