【源头活水】图上如何学习组合优化算法

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

作者：知乎—养生的控制人

地址：https://www.zhihu.com/people/yilan-zhong-shan-xiao-29-98

文章地址：https://arxiv.org/abs/1704.01665

快捷下载：本公众号后台回复【paper67】下载本论文

对于组合优化（通常是NP难）问题，主要的求解思路有：

• 精确算法（穷举、分支定界法）
• 近似算法
• 启发式算法

本文提出了一种纯机器学习的方法，即直接用机器学习得到最终的解，核心部分有两块：

• 图嵌入网络（structure2vec）
• Q-learning

图定义与问题描述

有权图

，

表示边

的权重。

最小顶点覆盖问题：找到节点的一个子集

使得每条边都被覆盖。

最大切问题：找到节点的额一个子集

使得切集

最大化，其中

是边集，且满足一端节点属于

，另一端节点属于

。

旅行商问题：给定二维空间的点集，找到一条总权重最小的路径，其中对应的图就是以这些点作为节点的全连接图（边的权重代表点之间的距离），一条完整的路径需要遍历图上的每一个节点一次。

贪婪算法

组合优化问题的解的生成模式是按序贯的方式：每次通过最大化评价函数从候选节点集合

中选择新的节点添加到部分解

最终得到一个完整的解。

对于给定图，定义binary决策变量向量

，其中每个维度

对应图中的一个节点，如果节点属于

，则

。

引入几个符号定义：

辅助函数

：将部分解映射到一个满足问题约束的组合结构

目标函数

：衡量部分解的质量

贪婪算法添加节点的方式：

其中选择出来的节点添加到列表的最后。

问题设计

• MVC：无需辅助函数，损失函数为

，终止准则为判断所有边是否覆盖。

• MAXCUT：辅助函数将

分为两个集合，

和补集

，并维护一个切集

目标函数为

，不需要终止准则。

• TSP：帮助函数用于维护一条路径。目标函数为：

终止条件是当

。

图嵌入

利用structure2vec来参数化评价函数

structure2vec：给定当前的部分解

，图嵌入网络Structure2vec能够给每一个节点

算出一个特征嵌入

其中

，

作用于输入的每一个元素。

进一步可以用节点（多次迭代后）的嵌入来定义评价函数

其中

，

为拼接操作。

因为节点嵌入基于图嵌入网络的参数，因此评价函数需要训练的参数有七个，作者采用强化学习的方式对这些参数进行端到端的学习。

Q-learning

强化学习建模

状态：对应这里的由节点嵌入表示的图嵌入

转移：这里的转移是确定性的，被选择的节点特征置为

动作：选择一个不属于当前状态的节点，采用节点的嵌入描述

奖励：奖励函数定义为

且满足

，因此有终止状态满足

。

控制律：

学习算法

一个episode表示一条完整的序列，一个step表示一次节点的添加。

Standard (1-step) Q-learning 最小化

其中

n-step Q-learning 解决延迟奖励的问题（the final reward of interest to the agent is only received far in the future during an episode）：

最终的算法描述：

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。