一种基于图神经网络的改进邻域搜索算法

Improved neighborhood search algorithm based on graph neural network

近年来图神经网络与深度强化学习的发展为组合优化问题的求解提供了新的方法。当前此类方法大多未考虑到算法参数学习问题,为解决该问题,基于图注意力网络设计了一种智能优化模型。该模型对大量问题数据进行学习,自动构建邻域搜索算子与序列破坏终止符,并使用强化学习训练模型参数。在标准算例集上测试模型并进行三组不同实验。实验结果表明,该模型学习出的邻域搜索算子具备较强的寻优能力和收敛性,同时显著降低了训练占用显存。该模型能够在较短时间内求解包含数百节点的CVRP问题,并具有一定的扩展潜力。

In recent years,the development of graph neural network(GNN)and deep reinforcement learning provides new methods to solve combinatorial optimization problems.Currently,most of these methods do not consider the problem of algorithm parameter learning.This paper developed an intelligent optimization model based on graph attention networks to solve this problem.The model automatically learned neighborhood search operators and destructive sequence terminators according to a significant amount of problem data,and trained model parameters based on reinforcement learning.This article used standard examples to test the model and conducted three different groups of experiments.The experimental results show that the learned neighborhood search operator has a remarkable ability to optimize and converge,while significantly reducing the training memory occupation.It can solve CVRP problems containing hundreds of nodes in a short time and has the potential for expansion.