[论文分享] NeurIPS 2020 POMO：用于强化学习的多优化策略优化

1. 摘要

在神经组合优化（CO）中，强化学习（RL）可以将深度神经网络转化为NP难问题的快速、强大的启发式求解器。这种方法在实际应用中具有很大的潜力，因为它允许在没有专家指导的情况下找到接近最优的解决方案，而专家指导需要掌握大量的领域知识。我们介绍了多优化策略优化（），这是一种构建这种启发式求解器的端到端方法。适用于广泛的CO问题。它旨在利用CO解表示的对称性。使用了一种改进的REINFORCE算法，该算法强制向所有最佳解决方案进行不同的部署。经验上，的低方差基线使RL训练快速而稳定，与以前的方法相比，它更能抵抗局部极小值。我们还介绍了一种新的基于增强的推理方法，它很好地结合。我们通过解决三个常见的NP难题，即旅行推销员（TSP）、容量限制车辆路径（CVRP）和0-1背包（KP），证明了的有效性。对于这三种算法，我们基于的求解器在性能上比所有最近学习的启发式算法都有了显著的改进。特别是，对TSP100实现了0.14%的最优差距，同时将推理时间减少了一个数量级以上。

2. 介绍

2.1 强化学习用于组合优化问题

在计算机视觉(CV)和自然语言处理(NLP)领域，基于专家手动特征工程的经典方法现在已经被自动化的端到端深度学习算法所取代。监督学习的巨大进步，学习了从训练输入到标签的映射，使这种显著的转变成为可能。不幸的是，监督学习在很大程度上不适合大多数CO问题，因为人们不能立即获得最优标签。相反，应该利用分数来训练模型，因为对于大多数CO解决方案来说，分数很容易计算，强化学习范式非常适合组合优化问题。

最近深度强化学习(RL)的方法很有前途，为NP难的CO问题(如TSP、CVRP、KP)找到接近最优的解。我们通过引入多优化策略优化()，为深度学习社区做出贡献。提供了一个简单直接的框架，可以自动生成一个相当好的的求解器。它可以应用于广泛的一般CO问题，因为它使用CO本身的对称性，即在CO解的顺序表示中发现对称性。

2.2 深度强化学习构造式方法和深度强化学习提升式方法

深度强化学习构造式方法：构造式方法即网络一次性生成问题的解，网络内部是迭代地生成解序列。Bello等人在他们的神经组合优化框架中使用了指针网络(PtrNet)。作为最早的深度强化学习方法之一，他们采用了actor-critic算法，并展示了神经组合优化在TSP和KP中实现了接近最优的结果。PtrNet模型基于sequence-to - sequence架构，并使用注意机制。与之前基于循环神经网络(RNN)的方法不同，注意力模型选择了Transformer架构。使用贪婪滚动基线训练注意力模型，类似于自我批评训练。注意力模型已被应用于路由问题，包括TSP、OP和VRP。

深度强化学习提升式方法：属于上述总结的深度强化学习构造式方法的范畴，其中由神经网络一次性生成CO解。然而，还有另一类重要的用于解决CO问题的强化学习方法，它将机器学习与现有的启发式方法相结合。神经网络可以被训练成引导局部搜索算法，该算法在之前的解的基础上迭代地找到更好的解，直到时间预算耗尽。这种改进型RL方法已经被许多人证明并取得了出色的成果。作者注意到，在之上制定改进启发式应该是可能的，并且可以成为一个重要的进一步的研究。

2.3 推理技术

一旦神经网络被完全训练，推理技术就可以用来提高它产生的解方案的质量。主动搜索在单个测试实例上优化策略。采用抽样方法从多个候选解中选择最佳解。波束搜索采用先进的策略来提高采样效率。作为后处理的经典启发式操作也可以应用于神经网络产生的解，以进一步提高其质量。

2.4 本文主要贡献

本文共有以下三个方面的贡献:(1)作者发现了解决CO问题的RL方法中的对称性，其会导致多重最优。这种对称性可以在神经网络训练过程中通过并行多次滚动来加以利用，每个轨迹都有一个不同的最优解作为其探索的目标。(2)作者为政策梯度设计了一个新的低方差基线。因为这个基线是从一组异构轨迹中衍生出来的，学习变得不那么容易受到局部最小值的影响.(3)我们提出了一种基于多重贪婪铺展的推理方法，它比传统的抽样推理方法更有效。我们还介绍了一种实例增强技术，可以在推理阶段进一步利用CO问题的对称性。

3. 本文动机

假设我们给定一个组合优化问题的一组结点，和一个通过参数化的可训练策略网络，该网络可以产生问题的有效解，一个解是由神经网络按照随机策略每次自回归一个节点生成，其中第i个动作可以选择一个结点，自回归地生成节点遵循以下策略：

其中是由问题实例定义的状态。在许多情况下，当CO问题的解决方案表示为节点序列时，其解可以采用多种形式，例如，包含循环的路由问题或寻找“一组”项目的CO问题都具有这样的特征。以TSP为例：若是5节点TSP问题的最优解，则也表示相同的最优解。

当被要求在其能力范围内产生最佳可能答案时，具有这些序列之间等效先验知识的完美逻辑智能体应该产生相同的解决方案，而不管它选择先输出哪个节点。然而，在以前的基于学习的模型中，情况并非如此。从上述策略可以清楚地看出起始节点严重影响其余行动过程，而事实上，对于的选择任何节点都应该同样好，我们试图找到一种可以充分利用这种对称性的策略优化方法。

4.

4.1 从多个起始节点进行搜索

首先指定N个不同的节点作为搜索的起点，如下图b所示，网络通过蒙特卡洛方法采样N个解轨迹，其中每一个轨迹被定义为一个序列：

在之前使用RNN或transformer风格的神经架构的工作中，网络总是选择来自多个采样轨迹的第一个节点。一个可训练的START令牌，一个来自NLP(这些模型的起源)的遗留令牌，被输入到网络中，并返回第一个节点，如下图a所示。通常，使用这样的START令牌是明智的，因为它允许机器学会找到通往最佳方案的正确的第一步。然而，在存在多个“正确”的第一步时，它迫使机器偏向特定的起点，这可能导致有偏见的策略。

因此，当所有的第一步动作都同样好时，应用熵最大化技术来改进探索是明智的。熵最大化通常是通过在强化学习的目标函数中加入熵正则化项来实现的。然而，通过强迫网络总是产生多个轨迹来直接最大化第一个动作的熵，所有这些轨迹在训练过程中贡献相等。请注意，这些轨迹与START令牌方案下重复采样的N个轨迹有着根本的不同，从START令牌出发的每个轨迹都接近于单个最优路径，但的N个解轨迹将紧密匹配最优解的N个不同节点序列表示。从概念上讲，的探索类似于引导学生从许多不同的角度反复解决同一个问题，使其接触到各种解决问题的技术。

4.2 策略梯度的共享基线

基于强化算法，一旦我们对一组解轨迹进行采样，我们就能计算出每个解决方案的回报，为了最大化奖励，使用梯度上升来近似:

其中。在上述方程中，是一个基线，人们有一些自由的选择去减少采样梯度的方差。在中，我们提出了共享基线：

与贪婪推理基线相比，基线在策略梯度上的方差更小。传统公式优势项，在的平均值为零，而贪婪推理基线在大多数情况下导致负值。这是因为在解决方案质量方面，抽样部署(遵循策略的softmax)很难超越贪婪部署(遵循策略的argmax)。此外，一个额外的好处是与之前深度强化学习构建方法中使用的其他基线相比，基线可以高效地计算，后者需要通过单独训练的网络(Critic)或克隆策略网络(greedy-rollout)进行前向传递。然而，最重要的是，使用的共享基线使得RL训练能够抵抗局部最小值。的训练方法如以下算法所示：

4.3 用于推理的多重贪婪轨迹

CO问题的构造型神经网络模型一般有两种推理模式。在“贪婪模式”中，使用策略上的argmax绘制单个确定性轨迹。在“采样模式”中，遵循概率策略从网络中采样多个轨迹。抽样解决方案的平均回报可能比贪婪解决方案的回报要小，但采样可以根据需要重复多次，但要付出计算代价。通过大量的采样解，可以找到一些奖励大于贪婪推理的解。然而，使用POMO的多起始节点方法，可以产生不止一个，而是多个贪婪轨迹，从N个不同的节点开始，可以确定性地获得N个不同的贪婪轨迹，从中选择最好的，类似于采样模式方法，在大多数情况下N个贪婪轨迹优于N个采样轨迹。

实例增强：的多贪婪推理方法的一个缺点是，N不能任意大，因为它受限于有限数量的可能起始节点。但是，在某些类型的CO问题中，可以通过引入实例扩展来避免这个限制。这是核心思想的自然延伸，寻求不同的方法来达到相同的最优解决方案。例如，可以翻转或旋转二维路径优化问题中所有节点的坐标并生成另一个实例，从中可以获得更贪婪的轨迹。实例增强的灵感来自自监督学习技术，该技术训练神经网络学习旋转图像之间的等效性。实例增强技术在CO任务上的适用性和乘法能力取决于问题的具体情况以及所使用的策略网络模型。下列算法描述了的推理过程(包括了实例增强)：

5. 实验及结论

5.1 实验设置

注意力模型：所有的实验都使用了Kool等人引入的名为注意力模型(Attention Model, AM)的策略网络。AM特别适合于，尽管我们强调POMO是一种通用的RL方法，与策略网络的特定结构无关。AM由两个主要部件组成，一个编码器和一个解码器，大部分计算发生在沉重的多层编码器内部，通过编码器，每个节点的信息及其与其他节点的关系作为向量嵌入。然后，解码器使用这些向量作为其点积注意机制的Key，自回归地生成解序列。为了应用，我们需要为CO问题的一个实例绘制多个(N)轨迹。这不会影响AM上的编码过程，因为无论需要生成的轨迹数量如何，编码只需要一次，而解码器需要处理N倍以上的计算。通过将N个查询堆叠到单个矩阵中并将其传递给注意机制，可以有效地并行生成N个轨迹。

推理：定义一个epoch生成100000个实例。我们遵循惯例并报告解决每个问题的10,000个随机实例所需的时间。对于路由问题，我们使用下图中列出的坐标转换执行了有或没有×8实例扩展的推理。KP没有使用实例扩展，因为没有直接的方法。最初，Kool等人使用带有贪婪rollout基线的强化来训练AM。有趣的是当用于训练时，性能有多大的提高。然而，对于消融实验，两个单独训练的神经网络必须以相同的方式进行评估。由于推理方法从多个答案中选择最佳答案，即使没有实例扩展，这也使具有不公平的优势。因此，我们在训练的网络上额外执行了“单轨迹模式”的推理，其中随机选择一个起始节点来绘制单个贪婪推理。

5.2  TSP

我们使用的起始节点数(N)为TSP20-20, TSP50-50, TSP100-100。在下表中，我们比较了在TSP上与其他基线的性能。顶部显示的第一组基线是Concorde和其他一些代表性的非基于学习的启发式方法的结果。第二组基线来自文献中发现的深度强化学习改进型方法。在第三组，我们展示由我们使用贪婪的rollout基线而不是实现的强化训练得到的AM的结果。

给定TSP20和TSP50的10,000个随机实例，POMO在秒和几十秒内分别找到最优性差距为0.0006%和0.025%的近最优解。对于TSP100, POMO在一分钟内实现了0.14%的最优性差距，在解决方案的质量和解决所需的时间方面都明显优于所有其他基于学习的启发式方法。表中为“AM”方法和“POMO，单轨迹”方法下的结果，方法都来自同一网络结构，并通过相同的推理技术进行测试。唯一的区别是训练，所以大幅度的提高(例如TSP100的最优性差距从3.51%提高到1.07%)表明POMO训练方法的优越性。至于推理技术，结果表明，结合使用POMO的多个贪婪推理和×8实例增强可以进一步减小最优性差距，减少一个数量级。

5.3 CVRP

当POMO训练一个政策网时，理想情况下它应该只使用"好的"起始节点，从其开始可以退出最优解决方案。但是，与TSP不同的是，CVRP中的并非所有节点都可以是最优轨迹的起始节点，并且如果没有实际的最优先验解，就无法确定哪些节点是好的。解决此问题的一种方法是添加一个辅助网络，该网络返回供使用的最佳起始节点的候选节点。然而，在我们的CVRP实验中，我们坚持使用与TSP相同的策略网络，而不进行升级。我们简单地使用所有节点作为POMO探索的起始节点，而不管它们是好是坏。

上表展示了CVRP在20、50和100个客户节点上的实验结果，结果表明POMO的性能大大优于简单的强化学习方法。请注意，目前还没有一种算法可以找到10000个随机的最优解。在CVRP100中的差距(0.32%)比CVRP50中的差距(0.45%)小，这可能是由于随着问题规模的增长，LKH3的性能下降速度比快。

5.3 0-1背包问题

我们选择KP是为了证明在路由问题之外的灵活性。与CVRP的情况类似，我们将神经网络重新用于TSP，并使用实例中给定的所有item作为部署的第一步，避免设计额外的，更复杂的“SelectStartNodes”网络。在求解KP时，每一项的权重和值代替TSP各节点的x坐标和y坐标。当网络生成一系列物品时，我们将这些物品逐一放入背包中，直到袋子装满，此时我们终止序列生成。在下表中，我们将结果与基于动态规划的最优解、贪婪启发式算法的最优解以及我们实现的PtrNet和原始AM方法进行了比较。即使没有实例增强，也大大提高了从深度神经网络获得的解的质量。

6. 总结及未来工作

是一种基于深度强化学习的纯数据驱动组合优化方法，它避免了由领域专家手工构建的启发式方法。在训练和推理阶段，利用CO问题的多个最优解的存在来有效地引导自己走向最优。

事实上，Lu等人最近开发的L2I的性能优于LKH3，使其成为第一个击败经典非基于学习的OR方法的基于深度强化学习的CVRP求解器。他们的成就是深度学习在运筹学应用的一个里程碑。为了强调和L2I之间的区别(除了速度之外)，POMO是一种通用的RL工具，可以以纯数据驱动的方式应用于许多不同的CO问题。另一方面，L2I是一个专门的路由问题解决器，它基于一组手工制作的改进操作符。由于是一种构建方法，而L2I是一种改进方法，因此可以将两种方法结合起来产生更好的结果。