背景

我们现实生活中存在许多组合优化问题，比如生产调度问题和旅行商问题。计算机科学中也存在着大量定义在图上的组合优化问题，如最大独立集（maximum independent set）和最小顶点覆盖（minimal vertex cover）问题等；在统计物理领域中也存在一种自旋玻璃模型，需要我们在指定的图结构上找到最优的粒子自旋状态组合，使得系统的基态能量最低；在网络科学中更是有许多图上的组合优化问题，比如作为社团划分的重要评价指标，模块度的优化是非常重要的。这些图上的组合优化问题需要我们在满足某些约束的情况下找到图上的最大或最小的子图。通常这类问题属于NP难或者NP完备的，可行解的数量随着网络的大小指数增长，因此无法通过穷举搜索或枚举法求解。

对于这类组合优化问题，有很多经典的通用算法能够求解。坐标下降法（Coordinate descent）是一种能够解决优化问题的经典算法，它可以通过坐标方向或坐标超平面进行一维搜索从而实现优化；粒子群优化算法（Particle swarm optimization）是一种基于种群的通用算法，它通过模仿自然界中大量生物个体的信息交流共享来解决优化问题，有较强的通用性和随机性；同样源于仿生的还有Holland提出的遗传算法（Genetic algorithm），它通过将解空间编码、引入选择和交叉变异等操作，从而模仿生物遗传过程中基因和染色体的变化，是一种非常经典且通用的算法；在物理和复杂系统领域也存在着许多优化算法，典型的有模拟退火算法（Simulated annealing）和极值优化算法（Extremal optimization），模拟退火算法来源于固体退火原理，是一种基于概率的算法，先将固体加温至充分高，再让其逐渐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小；极值优化算法源于复杂系统自组织临界的思想，算法从优化问题内部变量之间的联系出发，将问题本身作为一个演化的复杂系统，变量之间的相似性构成了变量之问比较、竞争、交流的条件，变量在局部寻优的过程中，驱动整个系统向最优解运动。

然而这些算法都存在一些弊端。一是它们都没有能够很好地利用系统的梯度信息，二是它们大都需要领域知识作为启发式信息，三是它们的时间复杂度较大，对于系统规模要求较高。因此这些经典的通用算法在解决图上的组合优化问题时通常难有很好的表现。

方法

得益于机器学习和深度学习领域的快速发展，很多更为先进的技术手段能够被用于解决图上的组合优化问题。基于计算图和张量计算的自动微分技术使得梯度下降优化能够快速、自动完成，从而使得基于梯度的优化算法更具竞争力。针对组合优化问题离散的性质，强化学习领域提出了以REINFORCE为代表的梯度估计算法，能够很好的解决可导性的问题。而近些年提出的Gumbel-softmax技术通过将采样过程可微化，使得梯度能够完整地反向传播从而实现优化。我们的算法框架正是基于自动微分技术和Gumbel-softmax技术。

我们首先初始化一组可学习参数，通过Sigmoid或Softmax函数转化为采样概率，然后使用Gumbel-softmax技术进行可微分的采样，并计算优化目标函数，最后使用误差方向传播算法和自动微分技术来更新可学习参数，从而实现整个优化过程。我们的框架可以并行地在GPU上运行，我们同时初始化若干组可学习参数作为一个种群，并同时进行上述计算步骤，在完成优化后，我们选择最小（或最大）的目标函数值及对应的可行解。

在上述并行化框架的基础上，我们引入演化计算从而更充分地利用种群优势。不同于优化结束后直接选取最优解，我们在优化过程中就周期性地进行个体信息交互和竞争，用种群中适应度最高的若干个体替换最差的若干个体，从而实现种群的定向演化。

为了避免算法陷入局部最优，我们还引入了遗传算法中的选择交叉变异算子，在每次梯度下降算法完成收敛后，对种群进行一次遗传进化操作，并再次运行梯度下降优化使之收敛，从而提升了种群的多样性并有效地使种群跳出局部最优。

创新点

1. 首次将Gumbel-softmax可微分采样技术应用于图上的组合优化问题，使得一系列NP难和NP完备问题有了新的解决思路。

2. 我们的框架充分利用了深度学习领域的自动微分技术，而又不需要大量数据进行模型的训练，对数据量和启发性的领域知识几乎没有要求。

3. 在并行化的框架中引入了演化计算，从而充分利用种群优势，提高解的多样性，尽可能避免陷入局部最优。

未来的研究方向

1. 尝试解决更为困难的排列优化问题（TSP等），可能涉及的技术如Gumbel-Sinkhorn。

2. 现有的工作都是对网络节点状态进行优化，未来会尝试一些网络结构的优化。

3. 尝试融合更多通用优化算法（如EO）