解决图组合优化问题的方法、装置、电子设备及存储介质

摘要

本发明涉及一种解决图组合优化问题的方法、装置、电子设备及存储介质。本发明所述的解决图组合优化问题的方法包括：获取真实数据对应的实例图，生成所述实例图对应的图数据结构；将所述图数据结构输入到图神经网络中进行编码处理，得到所述图数据结构的每个节点的特征向量；用所述每个节点的特征向量定义用来进行强化学习训练的Q函数，得到Q函数的参数化表示；迭代执行使用经过强化学习训练的Q函数计算各节点的Q值，根据所述各节点的Q值对所述图信息进行状态更新；直至状态更新后的图信息是否达到终止条件，输出当前图信息为最优解。本发明所述的解决图组合优化问题的方法，提高了对经验的采样率，加快了Q函数的学习。

说明书

技术领域

本发明涉及深度学习技术领域，特别是涉及一种解决图组合优化问题的方法、装置、电子设备及存储介质。

背景技术

最近，机器学习算法领域取得了重大进展，它们已迅速成为科学家工具箱中用于研究的工具之一。特别是强化学习领域，已经使得电脑在Atrai和GO游戏中超过了人类玩家的水平，而且完全不需要人的指导。在组合优化问题的研究邻域，随着问题的规模的不断扩大以及对求解速度的要求越来越高，像精确算法以及近似算法这类传统的运筹算法面临着很大的计算压力。

组合优化问题即在离散决策空间内进行决策变量的最优选择，这与强化学习的“动作选择”有非常相似的特征。正因此，利用深度神经网络自动的对图像的特征进行学习，代替了人类手工进行算法设计，深度强化学习根据当前的环境、问题状态做出动作选择，并根据动作的反馈不断调整自身的策略，从而达到设定的目标。目前基于DRL(DeepReinforcement Learning)的组合优化方法主要分为基于DRL的端到端算法和基于DRL的局部搜索改进算法两大类，其中端到端算法主要包括基于Pointer network的端到端方法和基于图神经网络的端到端方法两类，端到端的方法具有求解速度快、泛化能力强的优势，但是解的最优性在大规模问题上很难被保证；局部搜索改进类算法在一定程度上还依赖于手工制作的启发式算法来获得更好的优化效果。在构造图组合优化问题的解这个过程中，主要是通过逐步添加节点来构造解，当节点数过大且奖励稀疏、中间步骤的奖励函数难以定义的时候，对强化学习算法的收敛性是个很大的考验。强化学习作用于图组合优化问题需要有良好的问题表示能力，由于图的状态和节点的上下文非常复杂，较难描述，并且可能会需要用到图的全局/局部度的分布、到标记节点的距离等特性，这些信息都直接影响到神经网络能否更好地理解当前要解决的问题。

发明内容

基于此，本发明的目的在于，提供一种解决图组合优化问题的方法、装置、电子设备及存储介质，本发明所述的解决图组合优化问题的方法，提高了对经验的采样率，加快了Q函数的学习。

第一方面，本发明提供一种解决图组合优化问题的方法，包括以下步骤：

获取真实数据对应的实例图，并根据所述真实数据，生成所述实例图对应的图数据结构；

将所述图数据结构输入到图神经网络中进行编码处理，得到所述图数据结构的每个节点的特征向量，所述每个节点的特征向量组成所述图数据结构对应的图信息；

用所述每个节点的特征向量定义用来进行强化学习训练的Q函数，得到Q函数的参数化表示；

使用经过强化学习训练的Q函数计算各节点的Q值，根据所述各节点的Q值对所述图信息进行状态更新；

判断状态更新后的图信息是否达到终止条件；

如果达到终止条件，输出当前图信息为最优解；

如果未达到终止条件，迭代执行状态更新和判断步骤，直至达到终止条件。

进一步地，所述图神经网络为Graphmer；

所述Graphmer图神经网络用于通过Aggregate和combine部分生成节点特征向量：

其中，x

所述Graphmer图神经网络还用于通过非线性激活函数更新节点特征向量。

进一步地，所述Q函数的参数化表示为Q(S

其中，S

进一步地，对所述Q函数进行强化学习训练，包括：

使用HER-DQN对所述Q函数进行强化学习训练；

采用拟合Q迭代的方式更新Q函数，采用随机梯度下降法更新Q函数中的参数Θ，以最小化损失函数：Loss＝(y-Q(S

其中，y为DQN中目标网络的逼近函数y＝γmax

训练至Loss值减少趋于稳定，得到训练好的Q函数。

进一步地，生成所述实例图对应的图数据结构，包括：

当所述实例图为目标图结构，生成所述实例图对应的布尔表达式；

当所述实例图为MVC和/或TSP问题，生成所述实例图对应的稀疏矩阵。

进一步地，根据所述各节点的Q值对所述图信息进行状态更新，包括：

根据Q函数计算得到每个动作的Q值，基于贪心策略选取节点；

如果是求解MVC和/或TSP问题，则选择一个节点到最优解点集中；

如果是生成未知图结构问题，则选择与Q值最大的节点连接一条边。

进一步地，状态更新后的图信息达到终止条件，包括：

当前的节点集合和/或图结构能够解决当前图组合优化问题；

和/或，

当前的节点集合和/或图结构不能再添加节点。

第二方面，本发明还提供一种解决图组合优化问题的装置，包括：

图数据结构生成模块，用于获取真实数据对应的实例图，并根据所述真实数据，生成所述实例图对应的图数据结构；

编码模块，用于将所述图数据结构输入到图神经网络中进行编码处理，得到所述图数据结构的每个节点的特征向量，所述每个节点的特征向量组成所述图数据结构对应的图信息；

Q函数定义模块，用于用所述每个节点的特征向量定义用来进行强化学习训练的Q函数，得到Q函数的参数化表示；

状态更新模块，用于使用经过强化学习训练的Q函数计算各节点的Q值，根据所述各节点的Q值对所述图信息进行状态更新；

终止条件判断模块，用于判断状态更新后的图信息是否达到终止条件；

图信息输出模块，用于如果达到终止条件，输出当前图信息为最优解；

迭代模块，用于如果未达到终止条件，迭代执行状态更新和判断步骤，直至达到终止条件。

第三方面，本发明还提供一种电子设备，其特征在于，包括：

至少一个存储器以及至少一个处理器；

所述存储器，用于存储一个或多个程序；

当所述一个或多个程序被所述至少一个处理器执行，使得所述至少一个处理器实现如本发明第一方面任一所述的一种解决图组合优化问题的方法的步骤。

第四方面，本发明还提供一种计算机可读存储介质，其特征在于：

所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如本发明第一方面任一所述的一种解决图组合优化问题的方法的步骤。

本发明提供的一种解决图组合优化问题的方法、装置、电子设备及存储介质，引入了Graphmar图神经网络来更好的表示图结构。对于图数据而言，这种结构信息更加复杂、多元，例如在图上的每个节点都有不同数量的邻居节点，两个节点之间可以有多种路径，每条边上都可能包含重要的信息。如何在图结构中更准确预测出我们要选择的节点，最关键的难题是要确保模型可以正确利用这些图结构信息。针对强化学习算法在构造图组合优化问题的最优解这个过程中，agent做出的每个动作无法得到足够多的、有效的奖励，或者说直到最优解解构造完全了才得到奖励，为了应对这种稀疏奖励的情况，引入了结合了HER的DQN算法来解决在稀疏奖励的任务中，奖励函数难以设计的问题。图结构经过Graphmer图神经网络编码，其状态以及各个节点信息都被编码成可以通过迭代学习的特征向量，然后在HER-DQN强化学习加持下，通过简单地奖赏设计，在失败的经验中学习，不断地接近目标状态也就是最优解。

为了更好地理解和实施，下面结合附图详细说明本发明。

附图说明

图1为本发明提供的一种解决图组合优化问题的方法的流程示意图；

图2为本发明在一个实施例中使用的问题求解单步流程图；

图3为本发明在另一个实施例中使用的链路预测生成解的过程示意图；

图4为本发明提供的一种解决图组合优化问题的装置的结构示意图。

具体实施方式

为使本申请的目的、技术方案和优点更加清楚，下面将结合附图对本申请实施例方式作进一步地详细描述。

应当明确，所描述的实施例仅仅是本申请实施例一部分实施例，而不是全部的实施例。基于本申请实施例中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本申请实施例保护的范围。

在本申请实施例使用的术语是仅仅出于描述特定实施例的目的，而非旨在限制本申请实施例。在本申请实施例和所附权利要求书中所使用的单数形式的“一种”、“所述”和“该”也旨在包括多数形式，除非上下文清楚地表示其他含义。还应当理解，本文中使用的术语“和/或”是指并包含一个或多个相关联的列出项目的任何或所有可能组合。

下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本申请相一致的所有实施方式。相反，它们仅是如所附权利要求书中所详述的、本申请的一些方面相一致的装置和方法的例子。在本申请的描述中，需要理解的是，术语“第一”、“第二”、“第三”等仅用于区别类似的对象，而不必用于描述特定的顺序或先后次序，也不能理解为指示或暗示相对重要性。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本申请中的具体含义。

此外，在本申请的描述中，除非另有说明，“多个”是指两个或两个以上。“和/或”，描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，同时存在A和B，单独存在B这三种情况。字符“/”一般表示前后关联对象是一种“或”的关系。

针对背景技术中的问题，本申请实施例提供一种解决图组合优化问题的方法，如图1-3所示，该方法包括以下步骤：

S01：获取真实数据对应的实例图，并根据所述真实数据，生成所述实例图对应的图数据结构。

在一个优选的实施例中，将实例图G的顶点V、边E和权重w根据真实数据，生成对应的图数据结构输入图神经网络，如果是生成目标图结构，则输入布尔表达式；如果是MVC、TSP问题，则输入图的稀疏矩阵。

其中，目标图指用于说明为实现目标而采取的步骤的图表。

MVC问题指最小顶点覆盖问题(Minimum Vertex Cover,MVC)：寻找一个图的最小顶点集合的子集S，使得图中的每一条边都至少有一个端点在集合S中。

TSP问题指旅行商问题(Traveling Salesman Problem,TSP)：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

S02：将所述图数据结构输入到图神经网络中进行编码处理，得到所述图数据结构的每个节点的特征向量，所述每个节点的特征向量组成所述图数据结构对应的图信息。

在一个优选的实施例中，所述图神经网络为Graphmer。

所述Graphmer图神经网络用于通过Aggregate和combine部分生成节点特征向量：

其中，x

所述Graphmer图神经网络还用于通过非线性激活函数更新节点特征向量。在下次迭代的时候通过非线性激活函数relu更新。

S03：用所述每个节点的特征向量定义用来进行强化学习训练的Q函数，得到Q函数的参数化表示。

在一个优选的实施例中，Q函数的参数化表示为Q(S

S04：使用经过强化学习训练的Q函数计算各节点的Q值，根据所述各节点的Q值对所述图信息进行状态更新。

在一个优选的实施例中，根据Q计算得到每个动作的Q值，基于贪心的策略来选取节点，

图实例经节点选择之后，状态更新，对于MVC、TSP类问题，状态更新主要体现在所选的节点集合，也就是已经被选择了的节点不能再次被选择了，之后的状态所选节点减少；对于生成未知图结构问题，状态更新为连接边之后的图结构。

在一个优选的实施例中，使用HER-DQN对Q函数进行强化学习训练。

在强化学习的过程中，从一个节点构造成最优解的这个过程，称为一个episode，DQN中的经验池就是存储每个episode中的统计的状态、动作、奖励以及采取动作之后的状态，用一个四元组表示，而HER就是说将那些失败的episode，但是也有比较好的效果的，相当于组合优化问题的次优解，给四元组加上一个目标g，成为五元组(s

最后按照DQN强化学习，拟合Q迭代的方式更新Q函数，采用随机梯度下降法更新Q函数中的参数Θ，以最小化损失函数：Loss＝(y-Q(S

训练结束时，Loss值减少趋于稳定，即找到了当前网络能找到的最优解。

S05：判断状态更新后的图信息是否达到终止条件。

在一个优选的实施例中，状态更新后的图信息达到终止条件，包括：

当前的节点集合和/或图结构能够解决当前图组合优化问题；

和/或，

当前的节点集合和/或图结构不能再添加节点。

S06：如果达到终止条件，输出当前图信息为最优解。

如果是求解目标图结构，最优解表示为目标图结构的布尔表达式；如果是求解MVC，TSP这类问题，最优解为该图实例按顺序得到的顶点集合。

S07：如果未达到终止条件，迭代执行状态更新和判断步骤，直至达到终止条件。

更新完成之后需判断当前的节点集合，或者当前生成的图结构是否解决当前图组合优化问题或是否达到终止条件(不能再添加节点)，若都未达到，则再次进入第二步，Graphmer对状态进行迭代更新。

本申请实施例还提供一种解决图组合优化问题的装置，如图4所示，该解决图组合优化问题的装置400包括：

图数据结构生成模块401，用于获取真实数据对应的实例图，并根据所述真实数据，生成所述实例图对应的图数据结构；

编码模块402，用于将所述图数据结构输入到图神经网络中进行编码处理，得到所述图数据结构的每个节点的特征向量，所述每个节点的特征向量组成所述图数据结构对应的图信息；

Q函数定义模块403，用于用所述每个节点的特征向量定义用来进行强化学习训练的Q函数，得到Q函数的参数化表示；

状态更新模块404，用于使用经过强化学习训练的Q函数计算各节点的Q值，根据所述各节点的Q值对所述图信息进行状态更新；

终止条件判断模块405，用于判断状态更新后的图信息是否达到终止条件；

图信息输出模块406，用于如果达到终止条件，输出当前图信息为最优解；

迭代模块407，用于如果未达到终止条件，迭代执行状态更新和判断步骤，直至达到终止条件。

优选的，所述图神经网络为Graphmer；

所述Graphmer图神经网络用于通过Aggregate和combine部分生成节点特征向量：

其中，x

所述Graphmer图神经网络还用于通过非线性激活函数更新节点特征向量。

优选的，所述Q函数的参数化表示为Q(S

其中，S

优选的，对所述Q函数进行强化学习训练，包括：

使用HER-DQN对所述Q函数进行强化学习训练；

采用拟合Q迭代的方式更新Q函数，采用随机梯度下降法更新Q函数中的参数Θ，以最小化损失函数：Loss＝(y-Q(S

其中，y为DQN中目标网络的逼近函数y＝γmax

训练至Loss值减少趋于稳定，得到训练好的Q函数。

优选的，图数据结构生成模块包括：

布尔表达式生成单元，用于当所述实例图为目标图结构，生成所述实例图对应的布尔表达式；

稀疏矩阵生成单元，用于当所述实例图为MVC和/或TSP问题，生成所述实例图对应的稀疏矩阵。

优选的，状态更新模块包括：

节点选择单元，用于根据Q函数计算得到每个动作的Q值，基于贪心策略选取节点；

最优解点单元，用于如果是求解MVC和/或TSP问题，则选择一个节点到最优解点集中；

节点连接单元，用于如果是生成未知图结构问题，则选择与Q值最大的节点连接一条边。

优选的，终止条件包括：

当前的节点集合和/或图结构能够解决当前图组合优化问题；

和/或，

当前的节点集合和/或图结构不能再添加节点。

对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元。所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统，装置和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

本申请实施例还提供一种电子设备，包括：

至少一个存储器以及至少一个处理器；

所述存储器，用于存储一个或多个程序；

当所述一个或多个程序被所述至少一个处理器执行，使得所述至少一个处理器实现如前所述的一种解决图组合优化问题的方法的步骤。

对于设备实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的设备实施例仅仅是示意性的，其中所述作为分离部件说明的组件可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本公开方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。

本申请实施例还提供一种计算机可读存储介质，

所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现如前所述的一种解决图组合优化问题的方法的步骤。

计算机可用存储介质包括永久性和非永久性、可移动和非可移动媒体，可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括但不限于：相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(R AM)、只读存储器(R OM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。

本发明提供的一种解决图组合优化问题的方法、装置、电子设备及存储介质，可以通过关联跨层特征来学习更多的鉴别性特征，结合不同层特征的特性，得到更具表达能力是多尺度特征，提高分类效果。本发明提供的一种解决图组合优化问题的方法、装置、电子设备及存储介质，在多个层次特征之间的空间和通道形成依赖关系，并学习更多的区分性特征，从而获取到更具鉴别性、表述能力更好的特征，提升分类性能。本发明提出一种即插即用模块，Polarized Cross-layer Fusion Network(简称PCFN)，跨层建模空间和通道高分辨率依赖关系，比其他方法所需的复杂度更低，但达到了最先进的性能。PCFN可以在多尺度上自适应地关注各个部分，通过在CNN骨干上建立高低层特征依赖，提取高层特征语义引导下的多尺度特征，可以提取高级语义和低级详细信息，从而更好地分类和精确定位。

以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。