浅谈组合优化问题求解中的机器学习方法

DomDomm · 发表于 2022-11-14 21:51

导读：机器学习方法求解组合优化问题领域在 2015 年以来，取得很大的进展，机器学习 ML+组合优化 CO（简称 ML+CO）发展主要有两条主线，一条是监督学习路线，另外一条是强化学习路线。我们的目标是设计求解组合优化问题的机器学习算法框架，适用多个组合优化问题。
今天的介绍会围绕下面四点展开：

组合优化问题
机器学习方法
求解组合优化的机器学习算法
未来研究方向

<hr/>分享嘉宾｜蔡庆琼南开大学计算机学院副教授
编辑整理｜松烨深圳博瑜科技
出品平台｜DataFunSummit
<hr/>01/组合优化问题

组合优化问题（Combinatorial Optimization Problem，COP）是一类在离散状态下求极值的最优化问题，组合优化问题有非常多的实际应用:通讯网络、芯片设计、飞行路线调度、数据中心管理等。

其中 TSP 问题是大家比较熟知的一个组合优化问题，如有一个售货员，从北京出发，经过下图当中所有的城市而且只能通过一次，最后回到北京，要选择一个合适的城市序列，使得走的路程之和或总花费最少。

1. 组合优化问题数学模型

组合优化问题其实属于离散优化的问题，我们可以写成如下的数学模型：

例如 TSP 问题，给定一个完全图 G，顶点集 V(G)={0,1....n-1}, 边权重ω：E(G)-> Q,我们要从 0、1 到 n-1 所有置换当中挑出一个置换，使得这个置换相邻两个顶点之间的权重之和是最小的。我们可以抽象成如下数学模型：

2. 组合优化问题分类

根据计算复杂性理论，有 P 问题、NP 问题、NP-complete（NPC）问题，NP-hard问题四类，它们的定义分别为：

P 问题：可以用确定性算法在多项式时间内解决的问题
NP 问题：可以在多项式时间内验证是否正确的问题
NPC 问题：它是一个 NP 问题，同时所有的 NP 问题都能在多项式时间内约化到它。（注意，如果这种问题存在多项式时间的算法，那么所有 NP 问题都是多项式时间可解的，即 P=NP）
NP-hard 问题：所有 NP 都能在多项式内约化到它，但它不一定是一个 NP 问题。

少数组合优化问题是 P 问题，如最小生成树，最短路。大多数组合优化问题没有精确的多项式时间算法，许多组合优化问题是 NP-hard 的，如旅行售货商问题 TSP、最小顶点覆盖问题 MVC 等。

3. 组合优化领域一些基本问题

我们普遍认为 NPC 问题是比较难解的，一般没有多项式时间的精确算法。为了让大家更好理解，我们介绍背包问题、旅行商问题、车辆路径问题、最小顶点覆盖、最大独立集等组合优化的一些基本问题。

背包问题（Knapsack Problem，KP）

有一个背包和若干个物品，每个物品都有一定的重量和价值，我们往背包里装物品，保证不超过背包的容量，并且装在背包里的物品价值最大。

旅行商问题（Travelling Salesman Problem，TSP）

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

车辆路径问题（Vehicular Routing Problem，VRP）

一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

最小顶点覆盖（Minimum Vetex Coer,MVC）

顶点覆盖（Vertex Cover）是无向图 G=(V,E) 的一个顶点子集 S,使得图 G 中的任意一条边都至少存在一个顶点属于该顶点子集 S。最小顶点覆盖问题（Minimum Vertex Cover）的目标是找出包含顶点个数最少的一个顶点覆盖。

最大独立集（Maximal Independent Set，MIS）

独立集是图 G 的顶点子集，使得其中任意两个顶点之间都没有边相联。任意有关图中团的性质都能很自然地转述成独立集的性质。一般而言，寻找图的最大团是 NP 困难的，从而寻找图的最大独立集也是 NP 困难的。但是，对于二部图的情形，存在多项式时间算法找出图中的最大独立集。

上述的组合优化问题其实都是 NPC 类问题，那么求解 NPC 问题有精准算法、近似算法、启发式算法传统方法，传统方法的优缺点如下：

三种传统算法都有各自的优点，同时面临着一些共性的挑战，主要有三个方面的挑战：

为一个组合优化问题设计的算法一般很难用来求解其他组合优化问题。
对于问题的每一个实例，都要从头运行算法，迭代很多次求出解，对实例稍作修改时，也需要重新运行算法。
现实中新出现的问题规模和复杂度都越来越大，只依靠人工设计算法越来越困难。

4. 机器学习ML+组合优化 CO

近几年的机器学习和深度学习在各个领域大放异彩，我们想设计求解组合优化问题的机器学习算法框架来解决传统算法面临的三大挑战。我们分析机器学习应用在组合优化的几大优势：

机器学习算法可以从大量的数据或经历中自动学习规律和经验，来得到问题的近似解，而人工算法需要利用领域的专业知识及数学直觉，并经历很多试错和调试的过程。
机器学习算法有可能挖掘人工算法很难发现的有用性质
机器学习算法可以适用于多个组合优化问题，如 S2V-DQN 可以解决 TSP、MVC、MaxCut。而传统算法一般只针对一个组合优化问题，很难推广到其他组合优化问题。

机器学习方法求解组合优化问题最早可追溯到 1980 年，有学者利用 Hopfield神经网络来求解组合优化问题，近五六年 ML+CO 方面得到很大的发展，有监督学习和强化学习两条发展主线，发展的具体情况如下：

--
02/机器学习方法

用机器学习方法解决组合优化问题，我们需要用一些机器学习的基本方法，包含注意力机制、图神经网路、强化学习。分别简单介绍这些基本的方法：

1. 注意力机制

2. 图神经网络

3. （深度）强化学习

--
03/求解组合优化的机器学习算法

采用机器学习算法求解组合优化问题，有两种模式：端到端和与运筹算法相结合。
一种是端到端，输入一个组合优化问题，通过机器学习算法直接给出结果。具有求解速度快，泛化能力强的优势，但解的最优性很难保证。

另一种是与传统的运筹算法相结合，有一个总体的运筹算法，在其中某一些步骤利用机器学习算法来辅助做决策。比如我们把机器学习方法与分支定解法相结合，在选择分支节点和分支变量时，利用机器学习方法做决策。这种方法具有较好的优化效果，但求解速度远不及端到端方法。

接下来我们主要关注端到端的模式。

1. 基于注意力机制

2015 年 Vinyals 等人在 NeurlPS 上发表一篇文章《Pointer Network》，基于 Attention 机制提出指针网络模型。提出算法A1，算法如下：

算法 A1 采用监督式学习训练网络，优点是泛法能力强，求解速度快，缺点是解的质量不会超过样本的解的质量，事先构造训练样本费时。
基于算法 A1 的缺点，2017 年 Bello 等人在 ICLR 发表文章《Neural combinatorial optimization with reinforcement》提出算法 A2，采用强化学习方法训练 Pointer Network 模型，他们将每个问题实现视为一个训练样本，将问题的目标函数作为 Reward，采用 REINFORCE 强化学习算法进行训练，并引入 Critic 网络作为 Baseline 以降低训练方差。
算法 A1 只处理了 50 个点的 TSP 问题，算法 A2 处理了 100 个点的 TSP 问题，这个问题还没有结束，在 2019 年 Kool 等人在 ICLR 发表《Attention，learn to solve routing problems》文章，提出算法 A3。

算法 A3 也采用强化学习来训练，设计了一种 Rollout Baseline 来代替 Critic 神经网络，在之前训练过程中得到的所有策略模型里，选择在测试集中表现最好的模型作为极限策略，将利用该基线策略对状态 S 求解得到的目标函数值作为 b(s)，如果当前策略比历史最优策略的表现好，则进行正向激励，从而对当前策略进行评价和参数更新。

三种算法的实验结果如下图，注意下面所列的时间并没有包含训练时间，只包含推断时间。算法 A3 比算法 A1、算法 A2 都好，已经非常接近求解器的效果。

2. 基于图神经网络

2018年 Li 等人在 NeurlPS 发表文章《Combinatorial optimization with graph convolutional networks and guided tree search》提出算法 B1。

2017 年 Dai 等人在 NeurlPS 发表文章《Learning combinatorial optimization algorithms over graphs》提出算法 B2。

上图是 S2V-DQN 求解 MVC 问题时，对一个实例的求解可视化。刚开始没有选点，从第1 点、第 2 点、第 3 点依次选择下来，发现不仅要挑选度数大的点去覆盖尽可能多的边，而且要使得剩下图的连通性比较好。机器学习方法发现这个选点策略的效果更好。
通过介绍上述的机器学习算法，总结组合优化要用的机器学习算法：

--
04/未来研究方向

1. 进一步提升模型的效果，包括解的质量，求解时间，泛化能力

Attention 机制与 GNN 更好地结合；
机器学习算法与传统的运筹算法更好地结合；
开发更适合的强化学习策略

2. 求解更复杂的问题

多目标，多约束，动态变化的组合优化问题

3. 模型的可解释性

--
05/问答环节

Q：强化学习的策略如何选择呢？
A：目前没有一个明确的说法，刚才我在讲的过程当中大家应该也能看到，各个学习策略都有用到。所以，还是具体问题具体分析，可以都试一下，哪个效果好，就用哪个。
今天的分享就到这里，谢谢大家。
<hr/>分享嘉宾

蔡庆琼｜南开大学计算机学院副教授
2011年于南京师范大学获得数学学士学位，2016年于南开大学获得应用数学博士学位，现为南开大学计算机学院副教授，主要研究方向为图机器学习、图论与组合优化，主持过国家自然科学基金、天津市自然科学基金等多个项目，入选了天津市131创新型人才第三层次。
<hr/>DataFun新媒体矩阵

<hr/>关于DataFun

专注于大数据、人工智能技术应用的分享与交流。发起于2017年，在北京、上海、深圳、杭州等城市举办超过100+线下和100+线上沙龙、论坛及峰会，已邀请超过2000位专家和学者参与分享。其公众号 DataFunTalk 累计生产原创文章800+，百万+阅读，15万+精准粉丝。

		自动登录	找回密码
密码			立即注册

浅谈组合优化问题求解中的机器学习方法

本帖子中包含更多资源