从交通优化、信息传播优化、用户网络分析，组合优化这一传统计算问题在日常应用中无处不在。然而，这类问题往往是NP难题（NP-hard），并需要大量的专业知识和试错来解决。在许多实际生活的应用中，相似的组合优化问题一次又一次的出现，而每次面对具有相同形式、但数据不同的问题，却需要大量人力一遍又一遍的设计新的算法方案。在机器学习席卷各个行业的同时，我们不禁想问：组合优化这一传统的应用数学问题是否也会有新的自动化的解决方法呢？

后台回复“图论”获取宋乐教授论文Learning Combinatorial optimisation Algorithms over Graphs原文等资源。

基于图论的组合优化问题：被重复解决的老大难题

广告商如何在资源有限的情况下投放广告，使得广告信息在投放用户的相互传播后抵达尽可能多的人群？货运公司如何合理安排送货路线来提高送货效率？在社交网站的聚类分析中，我们如何根据每个用户的差异指数将用户分为两个用户组，从而最大化两个组之间的差异指数？

以上这些常见的问题都可以被归类为基于图论的组合优化问题（combinatorial optimization problems over graphs），这三个问题分别对应为最小顶点覆盖问题（minimum vertex cover, MVC）、最大割问题（maximum cut, MAXCUT）、巡回售货员问题（graph travelling salesman problem, GTSP）。从交通优化、信息传播优化到用户网络分析，这一类问题在日常应用中无处不在。然而，这类问题往往是NP难题（NP-hard），并需要大量的专业知识和试错来解决。在许多实际生活的应用中，相似的组合优化问题一次又一次的出现，而每次面对具有相同形式、仅仅是数据不同的问题，我们却需要一遍又一遍的设计新的算法方案。在机器学习席卷各个行业的同时，我们不禁想问：组合优化这一传统的应用数学问题是否也会有新的自动化的解决方法呢？

今年三月，一篇题为Learning Combinatorial optimisation Algorithms over Graphs的论文对这个问题提出了最新看法。这篇论文运用了强化学习（reinforcement learning）和一个叫structure2vec的图嵌入（graph embedding）方法，提出了解决这一类问题的一种“元算法”，即学习算法的算法——通过这一类算法，同一类的基于图论的组合优化问题将不再需要被逐一解决。这一“元算法”的提出对基于图论的组合优化问题这一领域的研究有着开创性的建设作用。

近日，大数据文摘有幸邀请到这篇论文的作者之一——来自佐治亚理工计算机学院的宋乐教授，进行了一次专访。宋乐教授目前是佐治亚理工大学机器学习中心的associate director,领导机器学习的研究试验室，其主要研究领域为大规模机器学习，图嵌入，以及机器学习跨学科领域研究（如社交网络分析、神经科学等）。在这篇论文中，他之前的多个研究成果也得到了进一步的应用。

传统解决方案的瓶颈

首先，宋乐教授为我们介绍了解决这类组合优化问题的传统方法和它们各自的缺点。

第一种，精准算法。精准算法往往通过穷举或是基于整数规划的分支界限算法寻找问题的最优解，因此，这类算法无法被应用到数据规模较大的组合优化问题上。

第二种，近似算法。我们可以通过多项式时间的算法来近似最优解。现有的这类算法可被用来解决数据规模较大的组合优化问题，然而它们的最坏情况保证往往不尽如人意。另外，有部分问题是无法被近似解决的。

第三种，启发式搜索。启发式搜索指那些快速有效但缺乏理论支撑的算法。现有的这类算法的设计需要大量的专业知识和试错，因此无法被广泛使用。

除此之外，这三类解决方案都忽略了实际优化问题的一个共性。

相似的组合优化问题一次又一次的出现，他们具有相同形式，而区别仅仅是数据的不同。换句话说，在许多应用中，每个问题的目标函数和限制都可以被当成是从某个概率分布中取出的样本。

算法总览：基于图嵌入和强化学习的贪心算法

和大多数近似算法和启发式搜索类似，这篇论文所提出的名为Structure2Vec Deep Q-learning的新算法也是一种贪心算法（greedy algorithm），也就是说，此算法基于最大化某个“评价函数”（evaluation function）的目标，逐步添加节点的方法得到问题的解。具体算法如下，数学符号的具体含义课参见原论文。