一种双层优化方法
引言:
论文题目:A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
Abstract/Background
组合优化 (CO) 以其NP-hard性质为特征，一直是一个具有挑战性的研究课题。当前，用于组合优化的机器学习 (MLCO) 已成为热门研究主题，但是大多数现有的MLCO方法都通过直接学习端到端解决方案来将CO视为单层优化，由于CO的高度复杂性，很难扩大规模，并且主要受ML模型容量的限制。在本文中，我们提出了一种混合方法来结合两个世界的优点，其中使用上层学习方法开发了一个双层框架来优化图 (例如添加，删除或修改图中的边)，与优化图上的低级启发式算法进行融合求解。这种双层方法简化了对原始硬CO的学习，并可以有效地减轻对模型容量的需求。对几个流行的CO问题 (例如有向无环图调度，图编辑距离和哈密顿循环问题) 的实验和结果表明，它比手动设计的启发式方法和单层学习方法有效。
本文解决的问题在实际中的例子:
例如计算任务的调度问题，在调度问题中需合理安排计算资源及数据中的CPU的核数指派到合适的任务，实现最大效率的完成，优化目标是最小化完成所有任务的时间；
图学习或机器学习中常用到的，图编辑距离，图学习中常用的图之间的距离度量，它通过衡量从图1到图2之间最短的编辑路径所对应的最小的编辑代价来衡量两张图的相似程度，也是一个NP-hard的优化问题，目标为最小化图上的编辑代价；或汉密尔顿回路问题以及著名的欧拉七桥问题等。
当前的研究方法:Single-Level Optimization
当前方法
当前关于此类问题的研究方法都可被总结为Single-Level optimization的优化形式,如下式:寻找合适的x以最小化函数f.式中的x为决策变量,f(x)为目标函数,s.t.为约束条件.
$$\min _{\mathbf{x}} f(\mathbf{x} \mid \mathcal{G}) \quad s.t. \quad h_i(\mathbf{x}, \mathcal{G}) \leq 0, for\ i=1 \ldots I$$
当前主流思路是直接使用强化学习对其进行端到端的学习,由于问题本身单独为NP-hard问题,因此大部分问题得不到最优解,无法进行端到端的训练.在RL框架下,决策变量会被一系列的决策替代,目标函数对应RL中的reward,约束条件通过限制RL的agent动作的范围来实现.
在使用强化学习直接处理规模较大的问题时,由于动作序列变长,导致动作空间增大,最终导致稀疏奖励(sparse reward),使得RL比较难以学到有用的信息,而且在默认的求解过程中,框架暗含的假设为:模型存在直接从G(graph)学习到x(solution)的能力–>学习端到端的映射.这为模型的容量设计带来了挑战,也就意味着需要为特定的问题,特定的数据分布去设计不同的模型结构才能实现如此大的模型容量.为了解决上述问题,传统的解决方法(no-learning)通过修改问题本身的结构来辅助问题的求解.例如在求解整数规划问题时使用割平面法(cutting planes)为求解整数规划问题添加额外的约束,来辅助问题能够得到更好更快的解决.
对当前研究方法的优化
本文发现,在计算任务调度的过程中,通过修改原先数据有向无环图的结构,比如加两条边,同样一个算法能够在两种修改条件下获得不一样的结果.原来21s完成的任务现在16s就能完成.通过这个思路,可以实现对问题求解的优化.
Our Formulation: Bi-Level Optimization
基于以上观察和思路，本文提出了一个双层优化（Bi-Level）方法，其核心引入一个新的变量称为优化过的图结构G’，基于G’给出双层优化的形式，如图3所示。图中上方红色框内表示上层优化部分（Upper-Level Optimization），蓝色框内表示下层优化部分（Lower-Level Optimization）。其中上层优化目标为G’，下层优化目标为一个决策变量与单层优化形式类似。可以发现目标函数及约束条件都是相对于G’。而对于上层优化，通过优化后的G’来实现对最终目标函数值在原先图中G目标函数值的优化。
基于上述框架，本文提出了一个强化学习-传统算法融合的方法如图4所示。针对输入的图结构，首先调用一个传统算法可以求出一个解，在此基础上，加入ReNet Attention GNN 组成的强化学习模型进行决策，该模型在图上预测图如何修改的概率，图中红色的深浅代表了不同的预测概率。
基于预测概率，进行决策，对图的结构进行修改。基于新的图结构，再次调用传统算法得到新的解，继续调用RL修改图结构，不断循环。图中蓝色为用来做决策的上层算法，通过PPO进行学习。下层黄色表示传统求解算法。蓝色G’表示上层优化需解决的问题，黄色X’表示下层优化需要处理的内容。由于采用强化学习进行学习，总目标函数会作为回馈函数来指导搜索与学习。
该方法的伪代码如下:
假设:图G的最优解X*可以通过修改G来获得.通过引入以下的主张去验证该假设的可行性:
Proposition.我们将从图g修改的所有图的集合定义为$\mathbb G$,并且$\mathbb X$是图g的所有可行解的集合.如果启发式算法是一个从$\mathbb G$到$\mathbb X$的超射(surjection),对图g和他的最优解x*,应该存在g*$\in \mathbb G$,使得x*成为求解g*的启发式算法的输出.
Proof.由超射的定义可知, 因为x* $\in X$,因此必须至少存在一个图G*$\in G$使得X*是通过求解g*的启发式算法的输出.
在进行完理论上的分析之后,本文基于假设内容原先图上的最优解x*可以通过不断修改图结构来得到.由于直接证明难度较大,因此添加一定限制条件, 如图6所示,但必须注意的是寻找最优的修改过的图这个问题本身也是一个NP-hard问题,本文通过理论上的分析证明优化图结构本身是可行的,同时可启发通过该方向开发性能更强更有用的算法.
在三个问题上使用该算法实现可以发现该框架的通用性,该方法在三个问题都维持了比较general的特性,如图7所示:
实验部分
To be continued…