人工智能文章分享：L2I 强化学习learn to improve 方法的应用

本文将介绍人工智能会议ICLR 2020上的一篇文章《A learning-based iterative method for solving vehicle routing problems》。

该文章提出了一个“Learn to Improve” (L2I)方法，更加高效，并且与OR方法进行了比较更优。该文章重点关注解决组合优化问题，尤其是带容量限制的车辆路径规划问题（CVRP）。其核心思想就是在元启发式迭代搜索的过程中，加入了RL来帮助更有效的选择算子。

   文章的基本思路是：

1、构造初始可行解；

2、强化学习(RL)来选择improvement operator（改进算子）来迭代地优化解决方案；

3、perturbation operator（扰动算子）来避免搜索到局部最优解。

相关文献

通过机器学习解决旅行商问题（TSP）和车辆路径规划问题（VRP）一般有两种方式：

1、端到端方法（ Pointer Network +Attention Model）

ü  Vinyals 等人（2015）首先引入了Pointer Network，以序列到序列模型为灵感，以解决TSP。 他们使用注意力模型以监督方式学习不同节点的顺序。

ü  Bello 等人（2016年）开发了一种RL算法来训练Pointer Network。 他们的框架从问题实例中学习最佳策略，不需要监督解决方案。

ü  Nazari 等人（2018）用新设计改进了Pointer Network ，使输入序列的模型不变性得以扩展，并对其进行扩展以解决VRP。

ü  Kool 等人（2019）提出了一个基于注意力层的模型，以及一种RL算法来训练具有简单但有效基线的模型。

2、强化学习方法（Policy Gradient、Actor Critic）

ü  Chen＆Tian（2019）提出了针对VRP的NeuRewriter Model。 他们定义了重写规则集，并训练了两个策略网络（区域选择策略和规则选择策略）以获得下一个状态。 给定一个初始解决方案，他们的目标是找到以最小的成本实现解决方案的一系列步骤。

CVRP

CVRP最终的解决方案是一组路线，保证每个客户都仅拜访一次，并且每个路线的总需求少于车辆的容量。该文章是基于原本的启发是方法，首先生成初始解决方案，然后迭代地改进或扰动该解决方案。

算子（Operator）：是从一种解决方案到另一种解决方案的映射。

模型框架

上图是模型的框架，在保证解决方案可行性的基础下，该算法将用改进算子或扰动算子对可行空间进行探索，在T（预先设置）步骤之后，我们选择旅行费用最小的方法作为最终解决方案。探索的方向可以基于规则，可以通过机器学习或混合学习，该方法可以进行不同的集成机器学习和OR方法的实验，其中某些方法可能会导致更好的解决方案质量或计算效率方面的优越方法。

对于改进算子还是扰动算子的选择将通过阈值来确定：

1、改进算子（improvement operator）

如果确定仍可以改进当前解决方案，则将使用基于RL的控制器来选择改进算子之一，并尝试使用所选算子来改进解决方案。该文拥有丰富的改进算子集，其中路径内的尝试通过将客户转移到各个路线的不同位置来降低当前解决方案的成本，而路径间的则尝试通过在不同路线之间转移客户来降低成本。鉴于改进算子具有鲜明的特征，因此要事先知道哪个对于所研究的问题最有效是不容易的。 也很难知道最适合该问题的运算符的预定义顺序。 因此，基于RL的控制器是学习对问题更有效的改进算子集的理想选择。

2、扰动算子（perturbation operator）

另一方面，在达到局部最小值时，扰动控制器随机选择破坏(全部或部分)并重建多条路线的扰动算子，以生成新的起始解。 具体地说，如果没有对L个改进步骤进行成本降低，则我们扰动该解并重新开始改进迭代。 由于扰动会极大地改变解决方案(通过产生一个通常比当前解决方案更差的完全不同的解决方案)，我们发现从一个相对好的起点重新开始改进迭代是有用的(例如，通过过滤掉比当前解决方案或当前最佳解决方案差得多的重新开始的解决方案)。

很明显，我们有意将改进算子与扰动算子分开，另一种设计方案是将它们混合在一起，由一个控制器来决定下一步应用哪个算子。 然而，改进算子与扰动算子的性质不同，其影响也不同，因为扰动算子通过影响整个改进迭代而具有长期效应。 我们的经验还表明，只将RL集中在改进运算符上会使学习变得更容易。 最后值得一提的是，虽然基于规则的扰动控制器被证明是有效的，但我们不排除它也可以是基于学习的。

改进控制器和改进算子

    本文的核心思想就是通过强化学习设计改进控制器，来对改进算子进行选择。

动作空间：一组改进算子（improvement Operators）

状态空间：问题实例，解决方案和运行历史记录的特征

策略网络（Policy Network）：通过给定的状态，输出一系列动作发生的概率

策略网络参数更新方法：REINFORCE算法（Williams，1992）

整个策略网络的结构如下图所示：

输入：

ü  问题信息和当前解决方案的输入特征被转换为D维（D = 64）的Embedding

ü  该Embedding被馈送到注意力网络（Attention Network）（Vaswani等，2017）（我们使用具有8个头部和64个输出单元的注意力模型）。

ü   然后注意力网络的输出与历史动作及其影响相连接。

两层全连接的神经网络（MLP）：

ü  第一层使用64个单元和Relu激活函数

ü  第二层使用Softmax，产生| A |个动作概率，其中A是一组动作

输出：算子选择的概率

奖励函数：

ü  第一个奖励函数（由RF1表示）专注于改进算子的中间影响。如果改进当前解决方案，则奖励为+1，否则为-1；

ü  第二奖励函数（由RF2表示）基于优势。在第一个改进迭代中，针对问题实例所达到的总距离被视为基线。对于每个后续迭代，在此迭代期间应用的所有算子都将获得等于迭代期间达到的距离与基线之间的差的奖励。由于改进会越来越难，因此不能给早期算子更大的奖励，算子应该得到同等的奖励，并且不会出现衰减（衰减因子γ为1）

​