Method and device for solving graph combination optimization problem, electronic equipment and storage medium

Abstract

The invention relates to a method and device for solving a graph combination optimization problem, electronic equipment and a storage medium. The method for solving the graph combination optimization problem comprises the steps that an instance graph corresponding to real data is obtained, and a graph data structure corresponding to the instance graph is generated; inputting the graph data structure into a graph neural network for coding processing to obtain a feature vector of each node of the graph data structure; defining a Q function for reinforcement learning training by using the feature vector of each node to obtain a parameterized representation of the Q function; iteratively executing a Q function subjected to reinforcement learning training to calculate a Q value of each node, and performing state updating on the graph information according to the Q value of each node; and outputting the current graph information as an optimal solution until the graph information with the updated state reaches a termination condition or not. According to the method for solving the graph combination optimization problem, the sampling rate of experience is improved, and learning of the Q function is accelerated.

Description

technical field [0001] The present invention relates to the technical field of deep learning, and in particular, to a method, an apparatus, an electronic device and a storage medium for solving a graph combinatorial optimization problem. Background technique [0002] Recently, there has been significant progress in the field of machine learning algorithms, and they have quickly become one of the research tools in a scientist's toolbox. The field of reinforcement learning, in particular, has allowed computers to outperform human players in Atrai and GO games without human guidance at all. In the research neighborhood of combinatorial optimization problems, as the scale of the problem continues to expand and the requirements for solving speed become higher and higher, traditional operational research algorithms such as exact algorithms and approximate algorithms face great computational pressure. [0003] The combinatorial optimization problem is the optimal selection of deci...

AI Technical Summary

Problems solved by technology

At present, combinatorial optimization methods based on DRL (Deep Reinforcement Learning) are mainly divided into two categories: DRL-based end-to-end algorithm and DRL-based local search improvement algorithm. The end-to-end algorithm mainly includes the end-to-end method based on Pointer network and the There are two types of end-to-end methods for graph neural networks. The end-to-end method has the advantages of fast solution speed and strong generalization ability, but the optimality of the solution is difficult to be guaranteed on large-scale problems; To a certain extent, it also relies on handcrafted heuristic algorithms to obtain better optimization results

Images