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

Improved neighborhood search algorithm based on graph neural network

作　　者：伍康 夏维[1,2] 王子源 Wu Kang;Xia Wei;Wang Ziyuan(School of Management,Hefei University of Technology,Hefei 230009,China;Key Laboratory of Process Optimization&Intelligent Decision-Making,Ministry of Education,Hefei University of Technology,Hefei 230009,China)

机构地区：[1]合肥工业大学管理学院,合肥230009 [2]合肥工业大学过程优化与智能决策教育部重点实验室,合肥230009

出　　处：《计算机应用研究》2024年第5期1402-1408,共7页Application Research of Computers

基　　金：国家自然科学基金资助项目(72271074)。

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

关 键 词：组合优化 CVRP 邻域搜索 图注意力网络 深度强化学习 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]