深度学习、强化学习求解组合优化问题——论文解读来一波
1.以下解读尽量避开 深度学习或强化学习在组合优化方面有哪些应用？中的论文~~~~
2.（好想研究ml/rl+组合优化的小伙伴赶紧冒出来，把积极的拉个群好好讨论呀，这块要做出新意和效果来太难了哈哈哈，如果过期了就加我微信jjnuxjp5x，我拉您入群哈~目前群里聊得火热呀。btw，欢迎大家帮忙宣传，感激不尽我会尽力为社区做贡献的！）
机器学习与优化前沿资料分享群，满200的话拉您进2群，加我微信 jjnuxjp5x
End to End Learning and Optimization on Graphs
我们都知道Bengio老爷子在相关综述中提到rl+组合优化的挑战是解的可行性、建模难（如在组合优化中处理图形数据难）、scale到大问题难、数据生成难。
而，dl+组合优化难点则是：
如果我们能对问题relax+differentiate，则后续解决起来轻松很多，但，
https://slideslive.com/38923998/graph-representation-learning-for-optimization-on-graphs中讲者的建议：
graph learning+graph optimization
在这项工作中，我们将较简单的问题实例化为k均值聚类的可微分形式。
因为图神经网络将节点嵌入到连续空间中，使我们得以通过在连续嵌入空间中优化来达到对离散图近似优化的目的，所以clustering is motivated。 然后，我们将 cluster assignments解释为离散问题的解。 我们针对两类优化问题实例化了该方法：需要对图形进行微分的问题（例如，社区检测或最大割），以及需要选择K个节点的子集的问题（设施位置，影响最大化，免疫接种等）。 我们并不是说聚类是适用于所有任务的正确算法结构，但足以解决本文所述的许多问题。
简言之，我们做了三个贡献。 首先，我们介绍一个用于集成图学习和优化的通用框架，并以连续空间中的更简单优化问题作为更复杂离散问题的代理。 其次，我们展示了如何通过集群层进行微分，从而将其用于深度学习系统。 第三，我们展示了在两个阶段的基线以及一系列示例域上端到端方法的实验性改进。
Attention, Learn to Solve Routing Problems!
下图是这篇paper的海报节选。
Improving Optimization Bounds Using Machine Learning: Decision Diagrams Meet Deep Reinforcement Learning
找到与最优解的tight bounds是解决离散优化问题的关键要素之一。 在过去的十年中，决策图（DD）为获取上限和下限带来了新视角，该上限和下限可能比经典的约束机制（如线性松弛）好得多。 众所周知，通过这种灵活的边界方法获得的边界质量高度依赖于为构建图表而选择的变量的排序，而找到优化标准度量的排序是一个难题。 在本文件中，我们提出了一种基于深度强化学习的创新且通用的方法，该方法用于获得有序的命令，以收紧使用宽松和受限DD所获的界限。 我们将该方法应用于最大独立套问题和最大割问题。 合成实例的实验结果表明，通过实现更严格的目标函数界，深度强化学习方法通常胜过已知实例分布时文献中常用的排序方法。 就“我们”所知，这是第一篇将机器学习应用于直接证明通过通用约束机制获得组合优化问题的松弛边界的论文, 它为different domains that utilize DDs as constraint programming, planning or verification of systems提供了新视角、新方向。
Solving Combinatorial Problems with Machine Learning Methods
Ptr-Net无法解决点匹配问题，因为它没有充分利用两个点集间的对应关系。我们提出了多指针网络，它从多标签分类中汲取idea，使用sigmoid函数代替Ptr-Net的softmax函数，更能体现点与点间的对应关系。 我们也介绍了一个框架（a unique combination of reinforcement learning and graph embedding network）来解决图形优化问题，尤其是最大割（MAXCUT）和最小顶点覆盖（MVC）问题。
Data-Driven Approximations to NP-Hard Problems
slides： http://www.milanton.de/files/aaai2017/aaai2017-anton-nphard-slides.pdf
再看TSP问题！
我们向传统的监督学习范例中引入了一种简单而有效的修改方法。 我们建议不要仅依靠近似的预测相似性度量（损失），而是利用真实的、不可微分的目标作为附加组件来对解进行排名，并不断改进可用的近似“ground truth”。 这使我们能在无需强监督的情况下，利用深度架构和反向传播的威力，同时又能探索解空间的很大部分。
Learning Combinatorial Optimization Algorithms over Graphs
方法：Q-learning+合适的图嵌入->效果：泛化性好、在大小图上表现都不错、能作用于许多类图（问题实例）。
An Effificient Graph Convolutional Network Technique for the Travelling Salesman Problem
（此paper解读部分摘自 https://zhuanlan.zhihu.com/p/96634714）
github
以2D图作为输入，Graph ConvNet模型输出一个边邻接矩阵，该矩阵表示TSP巡回中出现的边的概率，之后用波束搜索将边邻接矩阵转换为有效的巡回路线。算法是有监督训练的，且作者自称所有组件都高度并行化，
Input layer：
Node input feature：
\alpha_{i}=A_{1} x_{i}+b_{1} \\
The edge input feature：
\beta_{i j}=A_{2} d_{i j}+b_{2} \| A_{3} \delta_{i j}^{k-N N} \\
GCN：
Node feature vector：
x_{i}^{\ell+1}=x_{i}^{\ell}+\operatorname{ReLU}\left(\mathrm{BN}\left(W_{1}^{\ell} x_{i}^{\ell}+\sum_{j \sim i} \eta_{i j}^{\ell} \odot W_{2}^{\ell} x_{j}^{\ell}\right)\right) \text { with } \eta_{i j}^{\ell}=\frac{\sigma\left(e_{i j}^{\ell}\right)}{\sum_{j^{\prime} \sim i} \sigma\left(e_{i j^{\prime}}^{\ell}\right)+\varepsilon} \\
Edge feature vector：
e_{i j}^{\ell+1}=e_{i j}^{\ell}+\operatorname{ReLU}\left(\mathrm{BN}\left(W_{3}^{\ell} e_{i j}^{\ell}+W_{4}^{\ell} x_{i}^{\ell}+W_{5}^{\ell} x_{j}^{\ell}\right)\right) \\
MLP classififier：
p_{i j}^{\mathrm{TSP}}=\operatorname{MLP}\left(e_{i j}^{L}\right) \\
损失函数：
给定 ground-truth TSP tour permutation Π，作者将tour permutation转换为邻接矩阵，其中每个元素 \hat{p}_{i j}^{\mathrm{TSP}} 表示TSP tour中节点i和j之间是否存在边缘。 作者最小化了迷你批次平均的加权二进制交叉熵损失。 随着问题规模的增加，分类任务在消极类别上变得高度不平衡，这需要适当的类别权重来平衡这种影响。
波束搜索解码：
模型的输出是在tour connections的邻接矩阵上的概率热图。每个\hat{p}_{i j}^{\mathrm{TSP}}∈[0，1]^2表示节点i和j之间的边预测强度。 根据概率链规则，可以将partial TSP tour π'‘的概率表示为：
其中每个节点j’在partial tour π‘中跟随节点i’。 但是，通过argmax函数将概率热图直接转换为预测的TSP tour \hat{π} 的邻接矩阵表示通常会产生无效的行程，而在\hat{π}中有多余或不足的边。 因此，作者在评估时采用了三种可能的搜索策略，以将概率边缘热图转换为\hat{π}的有效排列。
贪婪搜索
通常，贪心算法会选择局部最优解以提供全局最优解的快速近似。 从第一个节点开始，作者根据有最高概率的边从其邻居中贪婪地选择下一个节点。 访问所有节点后，搜索终止。 作者掩盖了以前访问过的节点以构造有效的解决方案。
波束搜索
波束搜索是有限宽度的广度优先搜索[Medress et al，1977]，它十分流行。波束搜索可以从生成的模型中获得用于自然语言处理任务的一组高概率序列[Wu et al，2016]。
从第一个节点开始，作者通过在节点的邻居间扩展b个最可能的边连接来探索热图。 作者迭代扩展每个阶段的前b个partial tour，直到访问了图中的所有节点。 作者遵循与贪婪搜索相同的掩蔽策略来构造有效的游览。 最终预测是波束搜索结束时，在b个完整tour中概率最高的tour（b表示波束宽度）。
波束搜索和最短tour heuristic
作者在b个完整tour中选择最短的tour作为最终tour解，而不是在波束搜索结束时选择概率最高的tour。 这种基于启发式的波束搜索可以直接与TSP的强化学习技术相提并论，后者可以从学习到的策略中抽取一组解决方案并从中选择最短的旅程作为最终解决方案[Bello等，2016； Kool等， 2019]。
其他边角料：
结合学习启发式和传统启发式
从Deudon等人 [2018]的结果可以看出，将学习的启发式和传统的启发式结合起来，自回归模型可能不会产生局部最优，我们似乎可以通过使用学习算法与局部搜索启发式算法（如2-OPT）的混合方法来提高性能。 作者的非自回归模型也具有相同的观察结果。 在波束搜索中添加最短的巡回启发法会以评估时间为代价来提高性能。 当将诸如2-OPT之类的启发式方法结合到波束搜索解码中时，未来的工作将探索性能与效率之间的进一步权衡。
SL与RL的样品效率
与强化学习相比，作者的监督式训练设置具有更高的样本效率，因为SL使用有关问题的完整信息来训练模型，而RL训练则由稀疏的奖励函数来指导。要注意，每个训练图都是动态生成的，且对于RL是唯一的。 相反，监督方法从固定的一百万个实例集中随机选择并重复训练图（及其ground truth解决方案）。
Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization
与结合了深度神经网络和树搜索的强化学习算法一起使用时，两人游戏中的对抗性self-play玩法已经让人印象深刻。 诸如AlphaZero和Expert Iteration之类的算法可以学习tabula rasa，并在运行中即时生成高度有用的训练数据。 但是，self-play训练策略不能直接应用于单人游戏。 最近，一些实用的重要组合优化问题，例如旅行推销员问题和集装箱问题已被重新表述为强化学习问题，这似乎增加了使self-play游戏的收益超越两人游戏的重要性。 作者提出了排名奖励（R2）算法，该算法通过对单个agent在多个游戏中获得的奖励进行排名以创建相对性能指标来实现此目的。 将R2算法应用于二维和三维集装箱问题实例的结果表明，R2算法优于常规的Monte Carlo树搜索，启发式算法和整数规划求解器。 作者还提出了对排名奖励机制的分析，特别是对具有不同难度和不同排名阈值的问题实例的影响。
在两人游戏中使用self-play游戏时，一个有趣的agent总是会面对一个完全合适的对手，因为无论它有多弱或强，对手总是会为agent提供适当的对等水平，以便agent从中学习。 R2算法通过根据单个agent在最近游戏中的相对表现来调整单个agent的报酬，从而重现了普通单人MDP self-play的好处。 算法1给出了详细描述。
B指伯努利分布。
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
（此paper介绍部分摘自 https://zhuanlan.zhihu.com/p/58244275）
前人的研究和想法建立的基础
- 近似算法
- 启发式算法（大量人工调整和领域经验）
- 贪心算法
- 局部搜索
- 遗传算法
- 模拟退火
- 蚁群粒子群
- 基于学习
- 模仿学习：分支限界的选点策略
- RL：围棋
- Pointer Network: n<=50的二维TSP
- Pointer Network + RL: n<=100的人造二维TSP,n<=200的人造随机背包问题
- RL(DQN)+S2V: graph-based NP-hard Problems
- GNN: n<=50的人造随机指派问题，n<=20的随机二维TSP,结果不如Pointer Network和传统启发式算法
与前人的区别：
- 不基于RL，而是基于监督学习
- 不同的预测模型GCN
- 训练网络一次生成很多组不同的解，提升探索性。
算法概述：
首先，将输入图简化为等效的较小图。 然后将其喂入图卷积网络f，该卷积网络生成多个概率图，这些图编码每个顶点处于最佳解中的可能性。 概率图用于迭代标记顶点，直到标记完所有顶点。 完整的标签对应于搜索树中的叶子。 搜索树中的内部节点表示沿途生成的不完整标签。 通过树状搜索生成的完整标签可通过快速本地搜索进行完善。最佳结果用作最终输出。
详细赞美与吐槽见 https://zhuanlan.zhihu.com/p/58244275。
Differentiation of Blackbox Combinatorial Solvers
面对很多组合优化问题，传统求解器需要我们定义明确的结构化输入，而端到端的学习方式则没有这个严格的要求。理想情况下，我们希望能以端到端的方式将功能强大的函数逼近器（如神经网络）与有效的组合求解器进行组合， 而不做任何妥协（compromise），这正是我们这篇论文中实现了的目标，该论文获得了最高评分，并在ICLR 2020上被重点演讲。
对于以下各节，需要牢记的是，我们并不是在尝试改进求解器本身，而是要与函数逼近协同使用现有求解器。
Gradients of Blackbox Solvers
我们考虑组合求解器的方式是根据连续输入（例如图形边缘的权重）到离散输出（例如最短路径，选定的图形边缘）之间的映射来定义的。此过程中原本我们参考的损失函数是分段固定的.这意味着该函数相对于表示自变量的梯度几乎处处为0，且在跳跃点上没有定义。坦率地说，梯度原样（gradient as-is）对于最小化损失函数没有用。
迄今为止，已经有一些方法依赖于解算器对上述问题进行松弛，此过程必须就最终的最优性做出牺牲。 相比之下，我们开发了一种不影响求解器最优性的方法：通过定义原始目标函数的分段仿射插值来实现此目的，其中插值本身由超参数λ控制，如下图所示：
f的定义域是多维的。 超参数λ的作用是通过对求解器输入ω的扰动来移动f构成的多边形。 定义分段仿射目标的插值器g将该多边形的偏移边界连接到原始边界，如下图。 已有证明说明了后者可以提供有用的梯度。
缺点：无法很好地学习约束。
Learning to Search via Retrospective Imitation
将计算上的挑战转移给监督学习的Oracle。
slides http://www.cs.cmu.edu/~ckingsf/AutoAlg2019/slides/learning_to_optimize%20Yisong%20Yue.pdf 上半部分
Co-training for Policy Learning
slides http://www.cs.cmu.edu/~ckingsf/AutoAlg2019/slides/learning_to_optimize%20Yisong%20Yue.pdf 下半部分
A note on learning algorithms for quadratic assignment with graph neural networks
Reinforcement Learning for Solving the Vehicle Routing Problem
指针网络的缺点在于它假设系统是稳定不变的，而VRP问题中的需求有可能随时间变化。如果需求变化了，为了计算下一个决策点的概率，需要更新整个指针网络。为了解决这个问题，作者提出了一种比指针网络更简单的方法，即一个带有注意力机制（attention mechanism）的递归神经网络（RNN）解码器。如下图所示，左边的嵌入层将输入映射到高维的向量空间，右边的RNN解码器存储解码序列的信息。然后，RNN隐含状态和嵌入输入使用注意力机制在下一个输入上生成概率分布。
【优化】人工智能顶级会议NeurIPS 2018中优化与AI的融合
训练方法：
作者将随机的问题作为训练输入，使用著名的策略梯度方法REINFORCE。它具有两个网络：（i）预测下一个位置概率分布的actor网络（ii）评估任何问题实例回报的critic网络
这篇paper自称其框架很吸引人，因为它利用了一种自我驱动的学习过程，该过程仅需要基于生成的输出来计算奖励； 只要算法可以观察到奖励并验证生成序列的可行性，就可以学习所需的元算法。 例如，如果一个人不知道如何解决VRP，但可以计算给定解决方案的成本，则可以使用算法提供解决问题所需的“信号”。 与大多数经典的启发式方法不同，这篇paper自称其算法对问题的更改具有鲁棒性，这意味着当输入以任何方式更改时，算法都可以自动调整解决方案。
另外，使用经典启发式方法进行VRP必须重新计算整个距离矩阵，并且必须从头开始重新优化系统，这通常是不切实际的，尤其是在问题规模较大的情况下。 相反，这篇paper的算法不需要明确计算距离矩阵，这将极大提高计算效率。
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
这篇paper提供了强化学习和GNN representation的统一框架，用于学着去近似图上的不同问题。 该框架是第一个使用line graph for operating on either nodes or edges的框架（paper将所有图先转化为paper中定义的line graph，再进行encode、decode操作）。它通过更改奖励函数来解决不同的问题。 文章对”从小型到大型随机图“，不同类型的随机图“及”从随机图到真实世界图的泛化“进行了全面研究。 最后，文章在理论和实验中都证明了算法的线性运行时间，其运行速度比其他具有很好的最佳间隔的方法快了几个数量级。（？？？） 在未来工作中，作者计划学着将极大实例分解为多个部分，并求解每个子部分再合并，他们还计划研究图上的元学习组合优化问题，方法是在不同可归约问题间进行迁移学习。
Reinforcement Learning for Combinatorial Optimization: A Survey
关键点摘录：
1.记combinatorial optimization为CO，RL方法已通过两种不同的范例与CO集成： principal and joint learning。 在principal principal中，agent在没有优化求解器反馈的情况下直接决策。 例如在TSP问题中，可通过神经网络对agent进行参数化，该网络从一组顶点逐步构建路径，当路径达一定长度时获得奖励，该奖励用于更新agent的政策。 另一种方法是在与已经存在的求解器的联合训练中学习，它也许可改进特定问题的某些度量。 例如在MILP问题中，一种常用的方法是分枝定界法，该方法在每一步都会选择树节点上的分支规则。 这可能会对树的整体大小及算法运行时间产生重大影响。 分支规则是一种启发式方法，通常需要一些领域专业知识或超参数调整。 但是，给定已解决问题实例的数据集，参数化的RL agent可以学着去模仿节点选择的策略，从而减少算法运行时间。
2.基于价值的组合优化方法
最大切割[Barrett，2019]，最小顶点覆盖率[Khalil，2017，Song ，2019]，旅行推销员[Khalil，2017]，集合覆盖问题[Khalil等人，2017年]，最大独立集[Cappart等人，2019年]和最大公共子图[Bai等人，2020年] 已被DQN“较好地”解决。
大多数工作中使用的CO任务找到最佳解决方案的常见策略是主要学习。 然而，[Cappart等人，2019]引入了另一种解决CO问题的方法：为收紧最大独立集问题和最大割问题的松弛边界，使用RL算法查找决策图（DD）中变量的最优排序。 作者还表明，对受限的DD公式使用强化学习可以找到针对上述问题的良好启发式解决方案。
以上每篇文章本质都是对Q-learning算法本身、图网络表示形式或[Barrett等，2019； Bai等，2020]进行一些特定的修改。
它们的主要区别是状态，动作和奖励表示。 对于[Khalil et al，2017]，状态是p维图嵌入向量，对于时间步t处的当前节点序列，而动作是选择还没选的其他节点。，奖励是在采取某些动作a时从状态s过渡到状态s'后成本函数的差。
在[Cappart et al，2019]的工作中，状态s是一个元组（sL，sB），其中sL是变量的有序序列，而sB是在sL上构造的DD。动作是选择一个尚未选择的变量，奖励则是在将变量添加到决策图之后，根据上下限的变化来计算的，下限和上限与部分构建的DD的最长路径相关。
最后，[Bai et al，2020]的文章着重于解决最大公共子图问题，因此，为了仅使用一个网络以有意义的方式嵌入两个图形，作者构建了一个称为联合子图节点（JSNE）的新颖的图形嵌入网络。
但是，这三项工作都遇到了与[Mnih等人，2015]相同的问题，即，递归构造最佳解决方案不允许算法重新考虑导致次优解决方案的先前决策。
为了解决这些问题，[Barrett et al，2019]，[Song et al，2019]的作者对通用神经Q学习方法进行了一些改动。 [Song et al，2019]使用在分类领域中越来越流行的协同训练方法来构造用于CO任务的顺序策略。 文章描述了两种针对最小顶点覆盖问题的policy-learning策略：第一种策略来自[Khalil等人，2017年] ，即S2V with neural Q-learning。第二种是通过分支定界法解决的整数线性规划方法。 作者创建了CoPiEr算法，该算法在本质上类似于“模仿学习”，其中 the two strategies induce two policies,，对他们进行估计以找出哪种更好，然后在它们之间交换信息，最后执行更新。
ECO-DQN [Barrett et al，2019]直接针对the better state-space exploration and the scalability of the learned Q-function的任务。 为了实现这一目标，他们提出了一种不同于[Khalil et al，2017]的特殊培训框架，即，它并不是每步只学解的一部分。 相反，在每个episode开始时，它将随机实例化某些解，并允许agent“翻转”其顶点。 奖励是专门为激励探索而设计的，不会因agent执行了某些动作而惩罚agent。 相反，当agent找到一些局部最佳解决方案时（尚未探索）时，该算法可提供 \frac{1}{|\text{number_of_vertices}|} 的奖励。 作者使用的图嵌入网络是消息传递神经网络[Gilmer et al，2017]，其权重以与前几篇文章相同的方式参数化了Q函数。
3.基于策略的组合优化方法
[Bello et al，2016]进行了将策略梯度算法应用于组合优化问题的尝试，即，使用具有学习基线的REINFORCE算法来解决TSP和背包问题。 在此，[Vinyals等，2015]提出了指针网络架构用来更方便地编码输入序列。该方案是使用解码器的指针机制根据输入的分布顺序构造的，它且类似于[Mnih等，2016]异步并行地进行训练。 此外，文章还提出了贪婪解码和采样等推理策略来构造问题的解，提出了主动搜索方法。文章称，通过主动搜索，不论从经过训练还是未经训练的模型开始，我们都能为单个测试问题实例学习到解决方案。
[Bello et al，2016]提出的方法由于其动态特性而无法直接用于解决车辆路由问题，即，一旦访问该节点，该节点的需求就为零。 [Nazari等人，2018]扩展了用于解决TSP的先前方法来规避此问题，并找到用于VRP及其随机变体的解决方案。 具体而言，它们通过将LSTM单元替换为一维卷积嵌入层来简化编码器，从而使模型对于输入序列顺序不变，因此能够处理动态状态变化。 然后使用REINFORCE算法对TSP和VRP进行策略学习，使用A3C对随机VRP进行策略学习（[Mnih et al，2016]）。
[Deudon et al，2018]通过使用增强的编码器解码器体系结构修改[Bello et al，2016]的方法来解决TSP。 特别是，除了包含LSTM单元以外，此体系结构还完全基于关注机制，输入被编码为一个集合而不是一个序列。 此外，作者还研究了将强化学习代理提供的解决方案与2-opt启发式方法结合起来[Croes，1958]以进一步改善推理结果。
与[Deudon et al，2018]平行，[Kool et al，2018]提出了一种方法可以同时解决TSP、VRP的两个变体，定向运动问题（OP），奖品收集TSP（PCTSP）和随机PCTSP（SPCTSP）问题 。 在这项工作中，作者已经实现了类似的编码器-解码器体系结构，并使用了一个简单的 rollout baseline instead of the learned critic one。
[Hu et al，2017]以类似于[Bello et al，2016]的方式解决了另一个重要的CO问题-3D Bin Packing。 他们利用强化学习来制定策略，该策略代表了物料的最佳包装顺序。 在提供的入库商品序列的特征上训练该算法，同时通过计算包装商品的表面面积值来评估结果策略。 作者建议使用由启发式算法生成的装箱计划表面积作为基线。 为了进行推断，作者使用了贪婪解码及带有波束搜索的采样。 [Duan et al，2018]的进一步工作通过结合强化和监督学习将这种方法扩展到learning orientations along with sequence order of items。
[Chen and Tian，2018]的工作提出了通过迭代地改进现有解决方案来解决VRP，简化表达和在线作业调度问题的另一种观点。 该算法没有按顺序构建解决方案，而是重写解决方案的不同部分，直到收敛为止。 状态空间表示为问题的所有解决方案的集合，而动作集则由区域及其相应的重写规则组成。 作者使用LSTM编码器（它特定于每个被涵盖的问题），并通过应用Q-Actor-Critic算法共同训练区域选择和规则选择策略。
为了学习构建完整的解决方案而不是按顺序构建，[Emami and Ranka，2018]提出了一种特定的方法。 作者设计了策略梯度方法Sinkhorn Policy Gradient（SPG），专门用于涉及置换的组合优化问题。 在这种情况下，动作空间是一组置换矩阵。 使用特殊的Sinkhorn层产生置换矩阵的连续且可区分的松弛，作者能够训练类似于深度确定性策略梯度（DDPG）的actor-critic算法[Lillicrap等，2015]，并产生 最大重量匹配问题，欧几里得的TSP和整数排序问题的竞争性解决方案。
[Ma et al，2019]提出了另一种解决带有时间窗的TSP变体的方法。 主要思想是使用受[Haarnoja et al，2018]启发的分层RL框架，每层代表不同复杂度的策略：从最低层出发-使解决方案满足问题的约束；到最高层，负责为原始TSP优化问题找到解决方案。手动设计的特定于层的奖励函数和各层间共享的潜在向量h_t^(k）使不同策略层的上述行为成为可能。 原则上，潜在向量由层k的策略输出，被用作从下一层策略中采样动作的附加条件。为找到每一层的最佳策略，作者使用REINFORCE 他们有自己的 central self-critic baseline，这与self critic baseline [Rennie et al., 2017] 、 rollout baseline[Kool et al., 2018]相似。
4.用于组合优化的具有自演功能的神经MCTS（Neural MCTS with Self-play）
[Laterre et al，2018]结合了可学习的政策和价值函数及MCTS和自演的组合。 为解决单人游戏形式的2D和3D装箱问题，Neural MCTS通过添加排名奖励机制来构建最佳解决方案，该机制根据近期游戏的相对表现重塑了奖励。 旨在为单个agent提供自然课程，这有点类似于两人游戏中的自然对手。
[Xu and Lieberherr，2019]以类似的方式引入了另一种方法，通过将组合优化问题转换为Zermelo Games来解决问题。 文章将具有自学习功能的神经MCTS用于学习获胜策略，该策略可以解释为原始组合问题的特定实例的解决方案。
[Huang et al，2019]通过添加称为FastColorNet的高效策略和价值函数神经网络架构，使用类似的方法来解决大型图的图着色问题。 另外，他们使用了一些技术将MCTS减少到有限的数量，以处理具有数百万个顶点的图的学习。
同样，[Abe et al，2019]提出使用图神经网络，即图形同构网络（GIN），以解决搜索树中状态表示的可变大小，并通过对值函数归一化来修改AlphaGo Zero算法 。 这些技巧被用于解决图上的最大独立集问题和其他NP-hard问题。
5.未来方向
前面的部分讨论了通过利用强化学习算法来解决canonical组合优化问题的几种方法。 这个领域正在迅速发展，我们期望出现新的算法和方法来解决当前工作的一些缺点和局限性。
a)处理大的问题实例；b)开发特定算法和训练策略以提高通用性，即在较小问题实例上进行训练并将其泛化到较大的问题。 In the same line of research,应该研究归纳为分布不同的其他问题实例。 努力设计出可以”work with various combinatorial problem classes to some specifific problems’ formulations“的算法；c)更有效的表示学习（representation learning）技术。
文章被以下专栏收录
