(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210394840.5 (22)申请日 2022.04.15 (71)申请人 华南师范大学 地址 528225 广东省佛山市南海区狮山 南 海软件科技园华 南师范大学软件学院 (72)发明人 杜志斌　叶家豪　黄银豪　徐英秋　 (74)专利代理 机构 广州骏思知识产权代理有限 公司 44425 专利代理师 张金龙 (51)Int.Cl. G06Q 10/04(2012.01) G06N 3/04(2006.01) G06N 3/08(2006.01) G06F 16/22(2019.01) G06F 16/23(2019.01) (54)发明名称 解决图组合优化问题的方法、 装置、 电子设 备及存储介质 (57)摘要 本发明涉及一种解决图组合优化问题的方 法、 装置、 电子设备及存储介质。 本发明所述的解 决图组合优化问题的方法包括： 获取真实数据对 应的实例图， 生成所述实例图对应的图数据结 构； 将所述图数据结构输入到图神经网络中进行 编码处理， 得到所述图数据结构的每个节点的特 征向量； 用所述每个节点的特征向量定义用来进 行强化学习训练的Q函数， 得到Q函数的参数化表 示； 迭代执行使用经过强化学习训练的Q函数计 算各节点的Q值， 根据所述各节点的Q值对所述图 信息进行状态更新； 直至状态更新后的图信息是 否达到终止条件， 输出当前图信息为最优解。 本 发明所述的解决图组合优化问题的方法， 提高了 对经验的采样率， 加快了Q 函数的学习。 权利要求书2页 说明书8页 附图3页 CN 114792162 A 2022.07.26 CN 114792162 A 1.一种解决图组合优化问题的方法， 其特 征在于， 包括以下步骤： 获取真实数据对应的实例图， 并根据所述真实数据， 生成所述实例图对应的图数据结 构； 将所述图数据 结构输入到图神经网络 中进行编码处理， 得到所述图数据 结构的每个节 点的特征向量， 所述每 个节点的特 征向量组成所述图数据结构对应的图信息； 用所述每个节点的特征向量定义用来进行强化学习训练的Q函数， 得到Q函数的参数化 表示； 使用经过强化学习训练的Q函数计算各节点的Q值， 根据所述各节点的Q值对所述图信 息进行状态更新； 判断状态更新后的图信息是否 达到终止条件； 如果达到终止条件， 输出当前图信息为 最优解； 如果未达 到终止条件， 迭代执 行状态更新和判断步骤， 直至 达到终止条件。 2.根据权利要求1所述的一种解决图组合优化问题的方法， 其特 征在于： 所述图神经网络为Graphmer； 所述Graphmer图神经网络用于通过Aggregate和combine部分生成节点特征向量： 其中， xv表示节点是否被选择， 表示邻节点N(v)的信息， {w(v,u)}u∈N(v)表示 邻边的权 重信息， Θ为模型参数； 所述Graphmer图神经网络还用于通过非线性激活函数 更新节点特 征向量。 3.根据权利要求2所述的一种解决图组合优化问题的方法， 其特 征在于： 所述Q函数的参数化表示 为Q(St,v； Θ)； 其中， St表示当前实例的状态、 v表示可选取的节点， Θ为模型参数。 4.根据权利要求3所述的一种解决图组合优化问题的方法， 其特征在于， 对所述Q函数 进行强化学习训练， 包括： 使用HER‑DQN对所述Q函数进行强化学习训练； 采用拟合Q迭代的方式更新Q函数， 采用随机梯度下降法更新Q函数中的参数Θ， 以最小 化损失函数： L oss＝(y‑Q(St,vt； Θ))2； 其中， y为DQN中目标网络的逼近函数y＝γmaxv'Q(h(St+1),v'； Θ)+r(St,vt)， γ为Q值得 折扣系数， r为从经验 池中采样得到的动作奖励函数； 训练至Loss值减少趋 于稳定， 得到训练好的Q 函数。 5.根据权利要求1所述的一种解决图组合优化问题的方法， 其特征在于， 生成所述实例 图对应的图数据结构， 包括： 当所述实例图为目标图结构， 生成所述实例图对应的布尔表达式； 当所述实例图为MVC和/或TS P问题， 生成所述实例图对应的稀疏矩阵。 6.根据权利要求5所述的一种解决图组合优化问题的方法， 其特征在于， 根据 所述各节 点的Q值对所述图信息进行状态更新， 包括： 根据Q函数计算得到每 个动作的Q 值， 基于贪心策略选取节点； 如果是求 解MVC和/或TS P问题， 则选择一个节点到最优解 点集中；权　利　要　求　书 1/2 页 2 CN 114792162 A 2如果是生成未知图结构问题， 则选择与Q 值最大的节点连接一条边。 7.根据权利要求1所述的一种解决图组合优化问题的方法， 其特征在于， 状态更新后的 图信息达到终止条件， 包括： 当前的节点 集合和/或图结构能够解决当前图组合优化问题； 和/或， 当前的节点 集合和/或图结构不能再 添加节点。 8.一种解决图组合优化问题的装置， 其特 征在于， 包括： 图数据结构生成模块， 用于获取真实数据对应的实例图， 并根据 所述真实数据， 生成所 述实例图对应的图数据结构； 编码模块， 用于将所述图数据结构输入到 图神经网络中进行编码处理， 得到所述图数 据结构的每个节点的特征向量， 所述每个节点的特征向量组成所述图数据结构对应的图信 息； Q函数定义模块， 用于用所述每个节点的特征向量定义用来进行强化学习训练的Q函 数， 得到Q 函数的参数化表示； 状态更新模块， 用于使用经过强化学习训练的Q函数计算各节点的Q值， 根据所述各节 点的Q值对所述图信息进行状态更新； 终止条件判断模块， 用于判断状态更新后的图信息是否 达到终止条件； 图信息输出模块， 用于如果达 到终止条件， 输出当前图信息为 最优解； 迭代模块， 用于如果未达到终止条件， 迭代执行状态更新和判断步骤， 直至达到终止条 件。 9.一种电子设备， 其特 征在于， 包括： 至少一个存 储器以及至少一个处 理器； 所述存储器， 用于存 储一个或多个程序； 当所述一个或多个程序被所述至少一个处理器执行， 使得所述至少一个处理器实现如 权利要求1 ‑7任一所述的一种解决图组合优化问题的方法的步骤。 10.一种计算机可读存 储介质， 其特 征在于： 所述计算机可读存储介质存储有计算机程序， 所述计算机程序被处理器执行时实现如 权利要求1 ‑7任一所述的一种解决图组合优化问题的方法的步骤。权　利　要　求　书 2/2 页 3 CN 114792162 A 3