Graph Convolutional Neural Networks with AM-Actor-Critic for Minimum Vertex Cover Problem

At present, deep reinforcement learning (DRL) methods are mostly used to solve the problems in Euclidean space. Typical evaluation environment of algorithm performance includes Atari pixel game with image as input, or single inverted pendulum system with specific data input shape, etc. However, most of the practical problems exist in non-Euclidean space, and the features of topological data need to be extracted. In this paper, a new framework combining DRL and graph neural network (GNN) is proposed, which aims to reduce the over-estimation problem, and obtain better performance results than before in solving NP-hard problems. NP-hard problem is a problem with high time complexity. The proposed method is used to solve a typical NP-hard problem named the Minimum Vertex Cover problem (MVC) and is compared with the common Actor-Critic-GNN_(AC-GNN) method, a heuristic strategy and a random strategy, the proposed algorithm has the best performance. At the same time, the experiment also show the superiority of our new method in generalization ability, which is a feature that the previous DRL methods do not have.