用深度强化学习求解组合优化（路径、调度）问题

2022-10-18 05:10

©作者 | 小雷同学

前言

深度强化学习求解组合优化问题近年来受到广泛关注，是由于其结合了强化学习 (Reinforcement learning) 强大的决策 (decision-making) 能力和深度学习 (deep learning) 的各种模型 (RNN、Transformer、GNN等等) 强大的信息提取表征能力 (representative)，同时又结合神经网络强大的函数近似功能，可以采用神经网络近似 Value-based RL 中的 Q 值函数或 V 值函数，或者直接将其当作 Policy-based RL 中的策略 (policy)。

三巨头之一的 Yoshua Bengio 在 EJOR 期刊上发表的文章 [1] 对机器学习 (Machine learning) 用于组合优化 (Combinatorial Optimization，CO) 提出了三类范式：

1.1 End-to-end ML for CO

采用机器学习算法端到端地求解组合优化问题，避免了传统优化算法的设计及其迭代效率低运算复杂度高等特点。此类方法能够学习问题本身的属性从而提升计算效率（例如传统的优化算法需要针对每个实例进行从头迭代计算，而机器学习算法可以通过训练的方式学习问题的共性特征从而直接将训练的模型进行部署测试 (offline -> online)）。再借助神经网络的并行计算能力，模型能够在极短的时间内给出优化方案。

因此，该方法的优势是经过预训练 (pre-training) 的模型求解速度非常快、时间复杂度低的特点，适合一些需要进行实时优化的场景，如滴滴就将该方法用于在线打车调度平台。

文章 [2] 分析了所提出的 End2end 框架在求解路径问题时无论在训练 (training) 还是在测试（testing/inference）阶段都具有线性 (O(N)) 运行时间复杂度，能够非常快速的给出一个次优解，相比于启发式算法和精确算法都有一定优势，在运行时间和求解精度上有一定的 trade-off。

此类方法的难点是如何把一个复杂的优化问题建模为马尔科夫决策过程 (Markov Decision Process, MDP) 包括对环境的建模，对动作、状态、收益函数的定义。其核心问题是需要解决模型的泛化性能 (generalization ability)，通常训练需要大量数据，如果训练数据的分布与应用场景的数据分布偏差很大就会存在较大的分布偏移 (Distribution shift)，对于该问题作者感觉可以借鉴 pre-training -> fine-tuning 的思路。

笔者硕士期间的工作主要是围绕这类方法进行的（对 routing problem & scheduling problem 的研究, 下面有详细介绍及源码），对于泛化问题的处理主要考虑的是对训练得到的模型进行 Ensemble（即保存每个 epoch 的参数测试时取效果最好的模型，借助算力可以忽略运算时间的消耗）。

1.2 Learning meaningful properties of optimization problems

1.3 Machine learning alongside optimization algorithms

第二类和第三类都属于借助 ML 方法辅助运筹优化算法进行求解，如在解决一些精确算法中的子问题（分支定界算法中挑选 variable 的问题）。或者结合元启发式算法 (meta-heuristics)，如在 local search 类算法中的邻域搜索算法，可以采用 ML 方法来挑选邻域结构。此外，动态调度类问题也常用到这类方法，如采用 ML 方法在每个动态调度决策点挑选合适的调度规则。

该类方法利用 ML 方法的学习表征能力帮助运筹优化算法进行决策，其底层任然属于传统优化算法的运行方式，不过结合 ML 方法可以提升搜索效率等。其优化结果的质量通常能够得到保障，但该方法的运算效率与端到端的 ML 方法不在同一量级。

▲ 图3 The combinatorial optimization algorithm repeatedly queries thesame ML model to make decisions.

End-to-end ML for CO文献总结

第一篇该方向的论文是 Google 的 Vinyals 大神提出的 Pointer Network，该网络改编自 NLP 领域的 Sequence-to-sequence 模型，由于 S2S 模型是基于一个固定的词库进行输出，即输入的维度与输出不对等（e.g., 输入 10 个词我是基于一个固定的词库（可能是一万个）进行采样输出），对应于组合优化问题需要输出维度随着输入维度改变（e.g., 对于一个 TSP 问题，给定不同客户节点数量我需要输出对应数量的序列）。

该论文基于这样的思路完成了 S2S -> PN 的改编，大体思路就是用一个encoder (i.e., MLP/RNN/CNN/GNN/Transformer etc.) 对输入 (node) 进行 embedding 得到高维的 embedding vectors（隐变量），decoder（i.e., attention-based RNN/Transformer/MLP etc.）。

基于该隐变量进行解码（一顿操作再过一个 softmax 得到与输入维度相同的一个概率分布（即对应 RL 中的 policy）），然后基于该 policy 进行策略解码，可以是 random sampling、greedy、beam search 或者是后面提出的 active search 等等。

后续的文章将强化学习与 Pointer network 进行结合->有作者认为大多数组合优化问题不存在时序信息因此将 PN 中的 RNN 替换为 CNN（RNN 不能并行计算，CNN 可以并行计算效率更高）->KOOL 将 Transformer 结合 RL 用于求解组合优化问题->大量 GNN 的结合。

相关文章链接大家可以看其他回答的内容。

现在模型算法改不动了，大家好像又转向第 2、3 种范式了，如今年 ICLR 的一篇工作 [3]；近期有篇 arxiv 的文章关于 RL for branching 的研究 [4] 也很有意思，作者认为以往采用模仿学习 (imitation learning, IL) 即行为克隆的方法来学习 branch and bound 的过程耗费人力物力（需要质量较高的专家轨迹），因此作者将 branching 挑选 variable 的的过程建模为 MDP，从而学到较优的 policy 完成这一过程。

用深度强化学习求解组合优化问题

这是我们近期发表的关于使用深度强化学习解决组合优化问题（routing problem、scheduling problem）相关的文章。

论文标题：

Solve routing problems with a residual edge-graph attention neural network

论文链接：

https://www.sciencedirect.com/science/article/abs/pii/S092523122200978X

代码链接：

https://github.com/leikun-starting/DRL-and-graph-neural-network-for-routing-problems

大多许多组合优化问题都基于图结构，可以很容易地通过现有的图嵌入或网络嵌入技术来建模，将图信息嵌入到连续的节点表示中。图神经网络的最新发展可以用于网络设计，因为它在信息嵌入和图拓扑的信念传播方面具有很强的能力。

这激励我们采用图模型来建立 End-to-end 的深度强化学习框架。旨在设计近似求解图组合优化问题的通用框架，该框架应用于不同的图组合优化问题只需要做细微的改动，图 1 概述了该框架的流程。TSP 和 VRP 作为两个经典的组合优化问题，已经在物流运输、遗传学、快递和调度领域得到了广泛的研究。论文以 TSP 和 VRP 为求解对象来验证所提通用框架的有效性。

一般而言，TSP 定义在一个有多个节点的图上，需要搜索节点的排列，以查找具有最短行驶距离的最优解。带容量约束的车辆路径问题 (capacitated vehicle routing problem, CVRP) 是 VRP 的一个重要变体，其要求在不违反车辆容量限制的约束下，寻找行驶距离最短的路径，并满足所有客户的需求。由于 TSP 和 CVRP 的 NP-hard 性质，即使在二维欧几里得的情况下也很难找到最优解。一般来说，这样的 NP-hard 问题可以表示为图上的顺序决策任务，因为它具有高度结构化的性质。

▲ 图4 所提出框架求解TSP的流程

本文设计的框架中，首先将问题的图表示（如 TSP 的节点坐标）输入到模型中，然后采用 GNN 对原始特征进行编码。在解码过程中，通过注意力机制预测未选择节点的概率。通过搜索策略基于该概率分布进行节点选择，如贪婪搜索或采样的解码策略。本文的编码器是对 GAT 的改编，改编版本考虑了图结构中的边信息和层之间的残差连接。

本章将所设计的编码器网络称为残差-边-图注意力网络 (residual edge graph attention network, RE-GAT)。除了对节点的原始状态进行编码外，RE-GAT 还对边的信息进行编码更新。边的特征可以为学习策略提供与优化目标相关的更多的直接信息（如加权距离）。路径优化问题的目标是在相应的约束条件下寻找最短的加权路径，因为边提供的权重信息（本章选择图中节点之间的距离）不由节点提供。

此外，同时输入节点和边缘信息有利于挖掘不同节点之间空间邻接关系的特征。本文的解码器是基于 Transformer 模型设计的。训练算法使用近端策略优化算法 (proximal policy optimization, PPO) 和改进的 REINFORCE 算法。

所提出的框架无论在训练 (training) 还是在测试（testing/inference）阶段都具有线性 (O(N)) 运行时间复杂度结合神经网络的批 (batch) 处理能力，能够非常快速的给出一个次优解，相比于启发式算法和精确算法都有一定优势，在运行时间和求解精度上属于 trade-off。

具体方法实现和实验结论请参考原文链接。

论文标题：

A Multi-action Deep Reinforcement Learning Framework for Flexible Job-shop Scheduling Problem

论文链接：

https://www.sciencedirect.com/science/article/abs/pii/S0957417422010624

代码链接：

https://github.com/leikun-starting/End-to-end-DRL-for-FJSP

https://github.com/leikun-starting/Dispatching-rules-for-FJSP

柔性作业车间调度问题作为典型的 NP-hard 组合优化问题，目前其求解方法主要分为两类：精确算法和近似算法。基于数学规划的精确算法可以在整个解空间中搜索以找到最优解，但这些方法由于其 NP-hard 特性难以在合理的时间内解决大规模调度问题。因此，越来越多的近似方法（包括启发式、元启发式和机器学习技术）用于求解大规模调度问题。

通常，近似方法可以在计算时间和调度结果的质量之间实现良好的折中，特别是群体智能（swarm intelligence, SI）和进化算法（evolutionary algorithm, EA），如遗传算法、粒子群算法、蚁群算法、人工蜂群算法等。

尽管与精确算法相比，SI 和 EA 可以在合理的时间内解决 FJSP，但这些方法并不能直接应用于求解产线实时运行需求下的大规模资源调度问题。基于优先级的启发式调度规则被广泛地应用于实时调度系统，例如考虑动态事件的调度问题。调度规则通常具有较低的计算复杂度，并且比数学编程和元启发式算法更容易实现。

通常，用于解决 FJSP 的调度规则可以分为两个基本类别：工件选择规则和机器选择规则。这些规则的设计和组合旨在最小化调度目标，例如平均完工时间、平均延误、最大延误。然而，有效的调度规则通常需要大量的领域专业知识和反复试验，并且不能保证求解质量。

近年来，深度强化学习 (deep reinforcement learning, DRL) 已广泛地应用于求解组合优化问题，为解决具有共同特征的调度问题提供了一种思路。然而，目前的工作主要专注于其他类型的组合优化问题，例如旅行商问题和车辆路径问题，对于更为复杂的调度问题如 FJSP 研究较少。

通常，常规的强化学习仅适用于单个动作的决策问题。其中，强化学习智能体与环境交互的方式为：智能体首先从环境中获取状态并根据该状态选择动作，然后获得奖励并转移到下一个状态。然而，在 FJSP 中面临着工序的排序任务和机器的指派任务，即该问题是一个具有多动作空间的决策问题，这意味着常规的强化学习不能直接应用于 FJSP。

图 5 构建了 FJSP 的多动作空间的层级结构。在该层级结构中，强化学习智能体首先从工序动作空间中选择一个工序动作，然后从机器动作空间中选择一个机器动作。

▲ 图5 FJSP的层级动作空间结构示意图

本文首先将柔性作业车间调度过程描述为多动作强化学习任务，并进一步将该任务定义为一个多马可夫决策过程 (Multi-Markov Decision Process)。在此基础上，提出了一种新的基于 GNN 的多指针图网络（multi-pointer graph network, MPGN，如图 6 所示）用于编码嵌入 FJSP 的析取图 (Disjunctive Graph) 作为局部状态，注：析取图作为调度过程中的局部状态提供了调度过程中的全局信息包含数值和结构信息，如工序优先级约束、调度后的工序在每台机器的加工顺序、每个工序的兼容机器集合以及兼容机器的加工时间等。

▲ 图6 MPGN wolkflow

该网络适用于 FJSP、列车调度问题等多动作组合优化问题（结构如图 7 所示）。此外，为训练该网络结构设计基于 actor-critic 风格的多近端策略优化算法 (multi-proximal policy optimization algorithm, multi-PPO) 来训练所提出的 MPGN。

具体实现细节及实验结论请参考原文链接。

此外，我们近期还投稿了使用分层强化学习（Hierarchical Reinforcement Learning）端到端地求解动态调度问题的文章，后续也会开源代码，大家感兴趣可以持续关注下。

欢迎关注 github, 后期会上传 RL to optimize （scheduling and routing problem）及 Offline RL 的代码：

https://github.com/leikun-starting