Enhancing Graph Reconstruction: Uniting Dual-Level Graph Structure With Graph Reinforcement Learning.

Abstract

A combinatorial optimization problem is typically regarded as a 1-D sorting problem in most existing research. The representation ignores some information about the problem because of dimension compression. When applying reinforcement learning (RL) to this problem, convolutional neural networks (CNNs) used in conventional RL cannot directly extract the connection information between two elements in the feature matrix. A typical class of combinatorial optimization problems, the job shop scheduling problem (JSSP), is used in this article as an example. Considering the limitations in previous research, this article reexamines the task from the perspective of graph reconstruction and proposes a graph RL (GRL) method that combines a double deep Q-network (DDQN) and graph attention network (GAT) to achieve breakthroughs beyond the constraints of CNN performance. Moreover, a dual-level graph representation structure is constructed to comprehensively learn the features of scheduling information and overcome the difficulty of learning dynamic graphs. Experiments show that the quality of the obtained solution and generalization performance are both improved compared with models based on original deep RL (DRL) algorithms.