【源头活水】图上如何学习组合优化算法
“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。
作者：知乎—养生的控制人
地址：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）：
最终的算法描述：
本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。