基于学习的运筹优化算法进展与发展趋势（二）：主要的学习策略和方法

1. 运筹优化算法的学习思想来源

实际的OR应用中，一旦方案固定和实际部署，很少改变问题的结构和类型，变化的只是输入数据，问题结构是固定的。上述特点启发优化学者借鉴机器学习的思路研究输入和输出的之间的映射关系。但运筹优化学者更多的是倾向这种输入输出关系是白盒的而非黑箱。

相关链接可参考https://www.interpretable.ai/

目前除了成熟的凸优化算法理论（因为可以保证全局收敛性，因此算法的参数跟收敛速度的关系已经分析得很清楚），其它优化领域问题的算法（本质上都是NP类问题或涉及到搜索策略的算法）都涉及到算法的参数调参和问题适配。另外，现有启发式算法对算法设计者有较高要求，他们既要掌握各种算法的设计技巧，又要具有足够的领域知识。传统做法是针对某一问题设计一种专门算法，并在一组测试实例上进行评价（包括最好结果、平均结果、解的方差等）。因此，在算法特性研究基础之上，学术界在尝试研究算法泛化的机制和策略。

优化算法的最优参数和策略组合依赖于问题结构、数据分布和算法自身结构特点，因此基于数据驱动和特征工程的机器学习算法成为优化算法参数和策略调优的一个必经之路。基于学习的优化算法有如下特点：

·         传统的优化算法参数和策略是预先固定的，基于学习的优化算法则是基于问题特征和算法结构特点训练得到合适的参数和策略；

·         传统的优化算法参数和策略是基于人工经验设定，一次确定，到处适用；基于学习的运筹优化算法则强调基于数据分布自适应调整。

·         基于学习的运筹优化算法，借鉴了机器学习的学习过程，分两个阶段：训练和推理。其中算法的推理就是传统运筹优化算法计算过程，而训练则是结合数据进行参数和策略学习的过程。

Bengio的学习分类方法

基于Bengio的分类方法（2018 Machine Learning for Combinatorial Optimization a Methodological Tour d'Horizon），针对运筹优化算法，目前有如下三种学习策略：

Ø  端到端学习（End to end learning）：通过机器学习直接输出优化问题的最优解。

Ø  基于问题特征的学习（Learning meaningful properties of optimization problems）：通过学习问题特征来输出适合该问题的运筹算法参数和策略。

Ø  完全融合的学习（Machine learning alongside optimization algorithms）：基于机器学习学习指导每次迭代过程策略及其算法参数。

2.1 端到端学习（End to end learning）

在线和离线的学习流程可以简化如下：

本质上就是根据输入参数映射得到解，即

参数和变量的关系如下：

整体的求解思想如下：

以库存管理问题为例：

但实际上参数空间是无限的，而实际使用的策略是有限的，如何保证采样的策略使得求解质量维持在一定质量水平，Dimitris Bertsimas提出了如下策略：

采样策略如下：

可以有如下理论为保证：

此类方法应用于如下几个场景，从数值实验结果来看，效果不错。

还有一类结合深度神经网络的方法，具体有如下：

（1）Pointer Network

•       Pointer Networks 也是一种seq2seq模型。他在attention mechanism的基础上做了改进，克服了seq2seq模型中“输出严重依赖输入”的问题。

•       传统的seq2seq模型是无法解决输出序列的词汇表会随着输入序列长度的改变而改变的问题的。在某些任务中，输入严格依赖于输入，或者说输出只能从输入中选择。

在解决TSP问题，可以seq2seq的模型，TSP 旅行商问题的输入和输出长度是相同的，都是城市的个数，只是排序顺序不一样。

（2）Attention Model

   构建输入来说：对一每一个问题实例s来说，s内包括n个结点（nodes，第i个结点的特征xi,对于TSP，是坐标，然后xi之间是全连通的。这一个实例s就可以当做一个图形（Graph）作为输入。也就是如下面这样，直接把这幅图当做输入，只不过这10个结点的信息是以坐标为特征的。

   作为输入比将节点作为序列输入更好，因为它消除了对输入中给出城市的顺序的依赖性，只要它们的图形坐标位置不变。也就是说，无论我们如何对节点进行排列，只要给定的图不变，那么输出就不会变，这是与序列方法相比的优势所在。

整体策略如下：

1.     将图形作为输入，实际上比节点作为序列输入更好，消除了对输入中给出城市的顺序的依赖性，只要它们的图形坐标位置不变。

2.     修改版的Transformer的结构（也就是不用positional encoding 部分）。

3.     RL基于greedy rollout baseline，损失函数就是现在网络生成的策略的总路程长（TSP总路程）L(π)和基线值b（s）的里程差值，可理解为当前策略和基线策略的差距。

（3）Graph Neural Network

整体思路如下：

具体策略如下：

1.     将问题的状态表示为图形，基于神经网络构建解决方案。在构建过程的每次迭代中，网络观察当前图形，并选择要添加到解决方案的节点，之后根据该选择更新图形，并且重复该过程直到获得完整的解决方案。

2.     structure2vec图嵌入网络来寻找评价函数的方案（因为手动设计一个合理的评价函数在复杂问题中是不现实的）。

3.     RL： n-step Q-learning。

这一算法的关键在于找到问题对应的评价函数Q。我们说一个评价函数Q*是最优的，当且仅当对任意一个问题具例，这个函数都能在此贪心算法下为我们找出最优解。通常情况下，寻找最优的评价函数这一任务本身就是NP难题，因此我们往往需要近似找出一个评价函数Q。解决这类问题的传统贪心算法需要算法设计人手动给出一个Q，（比如在最大割问题中，这个Q可以是节点的邻居数），而手动设计一个合理的评价函数在复杂问题中是不现实的。因此，这篇论文提出了用图嵌入寻找评价函数的方案。

目前来看，效果不错：

 

（4）Graphs + DRL

•       对象：最小顶点覆盖（MVC）和最大覆盖问题（MCP）

•       用流行的贪婪算法来训练神经网络嵌入图形，并预测每一阶段要选择的下一个节点，然后用DQN算法对其进行进一步的训练。

（5）GCN + TSP

整体策略：

1.     基于GCN对TSP问题建模，基于监督学习训练GCN网络。

2.     结合Beam Search对GCN网络进行寻优。

3.     文献的结果优于先前基于Pointer Network的结果；采样效率高于RL。

 

简要总结一下：

n  End2end Learning 常见的几类方法：

Ø  核心思想：将组合优化看成序列决策问题。

ü  利用RNN作为基本单元，利用Seq2seq的框架直接做多对多的求解。

ü  转换为MDP，采用强化学习框架（定义关键几个要素：state，action，reward，termination），用policy gradient来调优，reward对应优化问题。

Ø  Pointer Network + Deep Learning (Vinyals 2015)

Ø  Pointer Network + Reinforcement Learning (Bello 2016)

Ø  Attention Model + Reinforcement Learning (Nazari 2018)

Ø  Transformer + Reinforcement Learning (Kool 2019)

Ø  GCN + Reinforcement Learning (Mittal 2019)

Ø  GCN + Beam search (Joshi 2019)，较为特殊，类似第二种。

Ø  Hyper-heuristic + Reinforcement Learning (Choong 2018)

n  E2E Learning针对OR的优缺点：

Ø  训练复杂，推理简单，是云上服务的理想模式。

Ø  目前E2E Learning的方法大部分解决的是图论类的组合优化，其它的组合优化涉及较少，初步原因可能是没有合适的神经网络结构对这类问题进行建模；组合优化问题的复杂程度是NP难的，训练的样本空间能否表示近乎无穷的解空间，理论上还未知。

Ø  从OR角度来看，组合优化问题自身有很多好的问题结构特点，基于这些问题特点设计的启发式算法效率非常高，目前基于机器学习的方法没有对此类问题做更多研究，可能是由于OR自身门槛较高，难以理解。

Ø  目前看到的E2E Learning方法都是针对非常简单的组合优化问题，但约束稍微复杂一点，例如VRP问题里面的带周期约束如何在神经网络上进行建模，是个很有挑战的问题，但对于元启发式算法来讲，只是一个编码策略问题。

Ø  有些优化问题的参数随着条件或时间会有一定的变化，目前方法暂时没有考虑。

2.2基于问题特征的学习（Learning meaningful properties of optimization problems）

（1）Learning when to use a decomposition

Dantzig–Wolfe decomposition，Dantzig–Wolfe算法解决特殊的线性规划问题，它是George Dantzig和Phil Wolfe在1960年建立起来和并得到发展，依靠Delayed Column Generation算法改进为了解决大规模线性规划问题。在重复使用单纯形法(Simplex Algorithm)解决大多数的线性规划问题，发现很多的列(变量)是多余的，基于这样的事实，提出主要问题包含最少的活动列(基本矩阵basis)，然后使用子问题去生成列(变量)填入基本矩阵来改进目标函数。

问题的选取特征如下：

n  Features:

•       Instance statistics

•       Decomposition based statistics

•       Adjacencies

•       Detector indicator feature

（2）Learning a Classification of Mixed-Integer Quadratic Programming Problems.

Linearizing a convex MIQP has its benefits and inconveniences.

ü  cutting plane techniques are more complete, and the algorithmic framework is overall more mature.

ü  But requires adding potentially many variables and constraints

（4）Automated Algorithm Selection Survey and Perspectives

（5）Automated Algorithm Selection Survey and Perspectives

n  Algorithm Configuration

•       Strength: find a single configuration with strong performance for a given cost metric.

•       Weakness: for heterogeneous instance sets, there is often no configuration that performs great for all instances.

n  Algorithm Selection

•       Strength: works well for heterogeneous instance sets due to per-instance selection.

•       Weakness: in standard algorithm selection, the set of algorithms P to choose from typically only contains a few relatively uncorrelated candidate algorithms.

n  Putting the two together [Kadioglu et al, 2010; Xu et al, 2010]

•       Use algorithm configuration to determine useful configurations.

•       Use algorithm selection to select from them based on instance characteristics.

2.3完全融合的学习（Machine learning alongside optimization algorithms）

(1) Learning to Branch in Mixed Integer Programming

n  核心思想：

Ø  PC-based strategy 依赖于人的经验和技巧，因此可以通过ML结合数据来学习这些规则和技巧。

n  策略：

Ø  收集SB过程中的的特征和标签

Ø  构造一个代理函数模拟SB，基于学习排序的方法学习

Ø  将学习到的排序函数用于分支策略。

n  数据：

n  标签：

Ø  A label is a value assigned to each variable in Ci, such that better variables w.r.t. to the SB score have larger labels.

Ø  The SB score is a sort of “gold standard” for scoring variables, hence labels based on such a score are a good target for learning.

p  Note：Summary of experimental results. “Unsolved instances” are counts, “Num. nodes” and “Total time” (in seconds) are shifted geometric means over instances with shifts 10 and 1, respectively. Lower is better, and the best value in each row among PC, SB+PC and SB+ML is in bold.

p  The C API of IBM ILOG CPLEX 12.6.1 is adopted to implement various strategies using control callbacks, in single-thread mode.

p  CPLEX-D is the strategy that branches on the variable chosen by the solver with its default variable selection rule (as set by CPX PARAM VARSEL);

p  SB+ML is on par with CPLEX-D in terms of overall wins, with fewer absolute win.

(2) Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction

n  How to get Label?

ü  Obtaining optimal solutions for medium or large scale MIP instances can be very time-consuming or even an impossible task.

ü  Identifying stable and unstable variables in solutions. This is motivated by the observation that solution values of the majority of binary decision variables remain unchanged across a series of different feasible solutions.

ü  Although obtaining optimal solutions might be a difficult task, the stable variables can be viewed as an easy-to-predict part in the (near) optimal solutions.

ü  To generate a sequence of solutions to an instance, we use the proximity search method.

Remark: The solver finds a good solution quickly on the left tree, and goes to the right tree to get the optimal solution, and finally prove optimality by exploring the remaining nodes on both sides.

(3) Learning to Optimize

The reinforcement learning method we use is guided policy search (GPS) (Levine et al., 2015), which is a policy search method designed for searching over large classes of expressive non-linear policies in continuous state and action spaces.

(5) Learning to learn by gradient descent by gradient descent

3. 基于学习的方法面临的挑战

n  解的可行性挑战。

Ø  End2End Learning的方法最大挑战就是可行性问题，尤其在组合优化问题里面，有时寻找可行解自身就是一个NP难问题。

n  建模的挑战。

Ø  视觉或NLP领域，有着已经很成熟的建模方法和策略，但针对组合优化问题，目前还没有较好的指导建模方法和对应的模型。

Ø  目前发现针对图网络类的组合优化问题，基于图神经网络的建模方法效果不错。

n  规模扩增的挑战。

Ø  限于计算能力或数据采集手段，训练的很多问题规模都是中小规模的，针对大规模问题，性能下降比较明显。

Ø  从组合优化算法角度来看，规模增大，寻优的复杂度是指数级增长的，所以解空间也是指数级增长的，样本的增加速度与规模增长相比可以忽略不计，导致样本代表性非常有限。

n  数据生成的挑战。

Ø  组合优化问题的特点决定了样本采样的速度跟不上规模的增长，如何选取代表性样本是个挑战。

1.    发展趋势

n  Learning meaningful properties of optimization problems (LMPOP)是个实用或可行的方向。

ü  运筹优化算法自身研究已经很多年，有着很多成熟的方法和理论，End2end学习方法直接替代现有方法，目前看过于激进。另外还面临比较大的问题是可解释的问题。

ü  由于NP难属性问题，现有使用的方法基本都是近似算法（基于启发式或元启发式算法），因此算法的参数是基于数据特征来经验设定，这方面可以通过学习的方式（融合一些专家的经验），将数据特征、算法特征融合起来，给出不同问题的不同算法参数和策略，目前看更加高效。

n  超参优化与半黑箱优化的融合。

ü  超参优化是基于学习的方法主要工具，但目前都是假设问题是黑箱，然而，实际问题中，很多算法结构是可以确定的，只是无法确定参数取值和相关策略。如何结合这些算法结构信息，进行超参优化，是个非常有意义的方向。

n  面向运筹优化的通用学习系统的开发和优化。

ü  当前面向运筹优化，尤其组合优化的，都是针对经典类的问题，针对实际问题目前较少，如何从数据获取到最终实用算法输出，目前相关的系统暂时没看到，遇到的都是针对机器学习场景。

【参考文献】

[1].   2015 Metaheuristics—the metaphor exposed

[2].   2017 A history of Metaheuristic

[3].   2009 Meta-heuristic - From design to implementation

[4].   2013 组合优化问题的特化与泛化算法设计

[5].   2017 超启发算法研究进展综述

[6].   2011 超启发算法， 跨领域的问题求解模式

[7].   2018 Hyper-heuristics

[8].   2020 Hyper-Parameter Optimization A Review of Algorithms and Applications

[9].   2018 Machine Learning for Combinatorial Optimization a Methodological Tour d'Horizon

[10]. 2015 Pointer Networks

[11]. 2017 Neural Combinatorial Optimization with Reinforcement Learning

[12]. 2019 Learning Combinatorial Optimization Algorithms over Graphs

[13]. 2019 Attention, Learn to Solve Routing Problems

[14]. 2019 An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

[15]. 2018 Automatic design of hyper-heuristic based on reinforcement learning

[16]. 2017 Learning When to Use a Decomposition

[17]. 2018 Learning a Classification of Mixed-Integer Quadratic Programming Problems

[18]. 2014 Automatic Dantzig–Wolfe reformulation of mixed integer programs

[19]. 2010 Experiments with a generic Dantzig-Wolfe decomposition for integer programs

[20]. 2018 Learning a Classification of Mixed-Integer Quadratic Programming Problems.

[21]. 2019 The Voice of Optimization

[22]. 2019 Online Mixed-Integer Optimization in Milliseconds

[23]. 2018 Automated Algorithm Selection Survey and Perspectives

[24]. 2019 Algorithm Configuration - Learning in the Space of Algorithm Designs (slide)

[25]. 2010 ISAC – Instance-Specific Algorithm Configuration

[26]. 2010 Hydra Automatically Configuring Algorithms for Portfolio-Based Selection

[27]. 2016 Learning to Branch in Mixed Integer Programming

[28]. 2019 Learning to Branch in MILP Solvers (slide)

[29]. 2014 Learning to Search in Branch-and-Bound Algorithms

[30]. 2016 Learning to Optimize

[31]. 2017 Reinforcement Learning for Learning Rate Control

[32]. 2017 Learning to Optimize Neural Nets

[33]. 2016 Learning to learn by gradient descent by gradient descent

[34]. https://www.zhihu.com/question/43610101

[35]. http://www.ams.jhu.edu/~wcook12/dl/index.html

[36]. https://zhuanlan.zhihu.com/p/96634714

[37]. https://baijiahao.baidu.com/s?id=1569650026866896&wfr=spider&for=pc

[38]. http://www.ams.jhu.edu/~wcook12/dl/index.html

[39]. http://ml.informatik.uni-freiburg.de/~hutter/ICML19_AC.pdf

[40]. https://blog.csdn.net/wangkaidehao/article/details/103376715

[41]. https://blog.csdn.net/senius/article/details/84483329

[42]. 2019 从数值最优化方法到学习最优化方法