|
|
题目：【NeurIPS21】机器学习遇上运筹优化，助力企业降本增效：一种双层优化方法
【插入sjtuThinklab公众号名片，之后由管理员加上去】
【开头一句话引入】本文介绍被NeurIPS21接收的新工作。我们提出了一种结合机器学习和传统运筹优化算法的框架，提升现有运筹方法的性能，助力企业在AI时代的降本增效。论文和代码链接在文末提供。
论文题目：A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
作者信息：汪润中*，华志刚，刘赣，张嘉逸*，严骏驰*，奇峰，杨爽，周俊，杨小康*（*上海交通大学，蚂蚁集团）
背景：运筹优化问题及其应用
运筹帷幄，决胜千里。运筹优化（Operations Research）作为数学、计算机科学、管理学的交叉学科，起源于二战中的空战规划，如今广泛应用在企业的生产、运营、物流环节，通过 计算机算法指导和辅助人类管理者进行决策。在本文中，我们可以将运筹优化（粗略地）理解为，通过求解一个数学规划问题，在满足约束的条件下，最小化完成某件事所花费的成本。本文所关注的组合优化（Combinatorial Optimization）是运筹优化的一个重要分支，组合优化问题的离散特性为问题求解引入了特别的挑战。在计算机科学的视角下，我们关心一个问题能否在有限时间内精确求解，而组合优化的一大挑战是多数问题具有NP-难复杂度，即目前的计算机无法在多项式时间内精确求解。例如，对于1000个任务节点的计算调度问题，最先进的商用求解器甚至无法在24小时内给出一个可行解。因此，科学家和工程师在过去开发了贪心算法（greedy algorithms）、启发式算法（heuristic algorithms）、分支定界（branch-and-bound）等求解方法，能够在有限的决策时间内返回一个尽可能好的规划结果。值得注意的是，上述算法均诞生于这轮AI大爆发之前，在AI时代，如何将最新的机器学习技术应用在运筹和组合优化，在学术界和工业界正在受到越来越多的关注。特别地，“深度学习三驾马车”之一，图灵奖得主Yoshua Bengio教授曾在2019年撰写第一作者综述论文Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon，总结和展望了机器学习在组合优化的应用。在芯片设计等“卡脖子”领域，基于机器学习的组合优化方法很可能成为将来的基础性技术（敬请关注我们另一篇NeurIPS21论文：On Joint Learning for Solving Placement and Routing in Chip Design）。在这篇NeurIPS21论文中，我们提出了一种将最新的机器学习技术（强化学习、图神经网络）与传统优化算法结合的框架，弥补了现有机器学习框架难收敛、模型容量要求高的缺陷，在3个真实的组合优化问题上显著地提升了传统算法的求解性能。本项目获得科技创新2030-“新一代人工智能”重大项目：《组合优化问题的机器学习求解》（项目编号：2020AAA0107600）的支持。
机器学习、传统算法融合的双层优化框架
本文提出了一种机器学习、传统算法融合的双层优化框架。在介绍提出的算法框架之前，我们先讨论现有的机器学习处理组合优化问题的框架。
目前主流的利用机器学习算法处理组合问题的框架如上图所示，通过一个图学习模型构建和发掘组合问题中的特征，搭建策略网络和价值网络，通过强化学习算法进行探索和学习。现有的机器学习模型的学习目标可以由如下公式总结：
其中$f(\cdot)$是目标函数，$\mathbf{x}$是决策变量，$\mathcal{G}$是问题的图结构，例如路径规划问题中两点之间的距离。$\quad h_i(\mathbf{x}, \mathcal{G}) \leq 0, \text{for}\ i = 1 ... I$代表约束条件，例如在路径规划中，车辆需要在经过每个点后返回原点。目前现有的机器学习方法对该公式的处理方法如下：
通过序列化的决策过程，使得强化学习智能体能够总结、学习到问题求解的方法。然而，在实际情况下，随着问题规模以及决策变量规模的增大，决策序列的长度显著增大。这将带来强化学习中著名挑战之一——稀疏奖励（sparse reward）——进而使得训练过程不稳定、难收敛。此外，上述形式暗含一个假设，即需要足够的模型容量以学习从$\mathcal{G}$到$\mathbf{x}$的映射。同期的其他研究表明，这一假设是不可能实现的，并且目前的机器学习方法会引入额外的泛化性问题（见链接）。
在本论文中，我们提出了一种基于双层优化形式的学习框架，将最先进的机器学习算法和经典的优化方法有机融合。我们提出的学习目标可以写作如下形式：
这是一个经典的双层优化（bi-level optimization）形式。其中，$\mathcal{G}^\prime$和$\mathbf{x}^\prime$分别是上层、下层的优化目标，$f(\mathbf{x}^\prime|\mathcal{G})$是上层优化的目标函数，$f(\mathbf{x}^\prime|\mathcal{G}^\prime)$是下层优化的目标函数，$H(\cdot),h(\cdot)$代表约束条件。与原公式对比，上式额外引入了$\mathcal{G}^\prime$，即“优化”后的图结构。在论文中，我们将强化学习的优化目标从决策变量$\mathbf{x}$改为图结构$\mathcal{G}$。我们要求对于新得到的图结构$\mathcal{G}^\prime$，其解空间一定是原问题$\mathcal{G}$上解空间的子集，以此保证$\mathbf{x}^\prime$在原问题上一定是可行的。对于上层优化问题，我们采用强化学习输出优化后的图结构$\mathcal{G}^\prime$，同时通过限制动作空间确保$\mathcal{G}^\prime$满足约束；对于下层优化问题，我们采用传统的算法（例如贪心算法、启发式算法）进行求解。
我们提出的机器学习、经典优化算法融合框架可以总结为以下的框图，在现有框架中有机地嵌入了一个经典优化算法模块，同时通过一系列算法设计保证了约束条件得到保留：
任务I：计算任务调度
我们对计算任务调度问题的描述如下：给定一系列计算任务，其中不同的计算任务之间存在先后依赖关系（例如，先洗手、后吃饭），其依赖关系可以被有向无环图（Directed Acyclic Graph, DAG）表示。因此，该任务也被称为有向无环图调度问题（DAG scheduling problem）。该问题的示意图和强化学习动作空间的定义如下所示：
在该问题中，我们对比了集群任务调度中三种常用算法，并且基于关键路径算法（Critical Path）构造了我们的强化学习模型PPO-BiHyb。我们同时对比了单层强化学习方法PPO-Single，随机搜索的双层优化算法Random-BiHyb。其中我们提出的算法PPO-BiHyb获得了约10%的性能提升。
任务II：图编辑距离
图编辑距离（Graph Edit Distance）是图学习领域一种常用的相似度度量，图编辑距离通过计算从图1编辑到图2需要的最少代价，衡量图1和图2之间的相似程度。然而，找到图1、图2之间最小代价的编辑方法是一个NP难的问题，求解并不容易。该问题的示意图和强化学习动作空间的定义如下所示：
在该问题中，我们考虑了四种常见的启发式算法：匈牙利近似算法（Hungarian）、随机游走算法（RRWM）、基于匈牙利预测的搜索算法（Hungarian-Search）、整数投影不动点算法（IPFP），并且基于IPFP算法构造了我们的强化学习模型PPO-BiHyb。我们同时对比了单层强化学习方法PPO-Single，随机搜索的双层优化算法Random-BiHyb。其中我们提出的算法PPO-BiHyb获得了约20%的性能提升。
任务III：汉密尔顿回路
汉密尔顿回路问题（Hamiltonian Cycle Problem）类似于著名数学家欧拉提出的“戈尼斯堡七桥问题”：能否在不重复经过任何一座桥的前提下，走完戈尼斯堡的七座桥并回到原地？七桥问题最终被证明是不可行的，而判断一个图上是否存在上述回路，即汉密尔顿回路，是一个NP完全的问题。该问题的示意图和强化学习动作空间的定义如下所示：
在该问题中，我们考虑了常见的贪心算法——最近邻算法和最远插入算法，同时比较了目前路径规划问题最强求解算法LKH3。基于高效率设定下的LKH3-fast，我们构造了强化学习模型PPO-BiHyb。我们同时对比了单层强化学习方法PPO-Single，随机搜索的双层优化算法Random-BiHyb。其中我们提出的算法PPO-BiHyb在找到的回路长度方面与高精度设定下的LKH3-accu性能相当，同时在测试数据集中找到了更多的回路。需要注意的是，部分最新的论文通过刻意的超参数调整让LKH3的效率显著降低，而我们的实验中为LKH3采取了更合理的超参数设定。
未来展望与总结
机器学习模型和经典的运筹算法融合是一个具有潜力、方兴未艾的研究方向。机器学习模型拥有自适应、数据驱动的特点，能够根据特定业务数据分布提升算法性能；经典的运筹算法通常具有时间复杂度、最坏情况近似程度的理论保证，因此在理论上会比纯粹的机器学习模型更加鲁棒和稳定。因此，本文提出的有机结合方法有望形成运筹优化、机器学习研究和应用中的新范式。此外，组合问题本身是许多机器学习、数据挖掘、运筹问题的基础，除去本文研究的三种组合问题，本方法在其他问题和算法上同样具有潜力。我们欢迎来自不同领域专家学者的知识交流和思维碰撞，以期能够提升您当前模型的精度和效果。此外，学术界近期已经注意到组合优化模型的稳定性问题，基于本文提出的双层优化框架，发掘和提升求解算法的鲁棒性可能另一个有前景的研究方向。欢迎来信咨询：runzhong.wang AT sjtu DOT edu DOT cn；抄送：yanjunchi AT sjtu DOT edu DOT cn
论文链接：https://arxiv.org/pdf/2106.04927.pdf
代码链接：https://github.com/Thinklab-SJTU/PPO-BiHyb |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2022-2-21 12:04
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡