基于改进的指针网络深度强化学习算法求解旅行商问题

Improved Deep Reinforcement Learning Algorithm Based on Pointer Network for Traveling Salesman Problem

旅行商问题是组合优化问题中的经典问题,而深度强化学习的发展为该类问题的求解提供了新思路。在基于指针网络的深度强化学习算法求解旅行商问题中,策略网络和价值网络的编码器都采用了复杂的长短期记忆网络结构,这在求解大规模旅行商问题时会造成训练时间过长的现象。鉴于输入节点间位置顺序的无关性,本文对指针网络中编码器的循环神经网络进行了修改,将策略网络和价值网络编码器中的长短期记忆网络都替换为一维卷积神经网络,最终提出了一种改进的基于指针网络的深度强化学习算法,其在相同求解问题规模上所需要的训练时间比原模型减少12%~15%,实验结果充分验证了本文改进算法的有效性。

Traveling salesman problem is a classic problem in combinatorial optimization.The development of deep reinforcement learning provides a new way to solve this problem.In the deep reinforcement learning algorithm based on the pointer network for the traveling salesman problem,the encoders of the strategy network and the value network both employ the complex long short-term memory network structure,which leads a long training time to the large-scale traveling salesman problem.Considering the independence of the position order among the input nodes,this paper modifies the recurrent neural network of the encoder in the pointer network and replaces the long short-term memory network of encoders in the strategy network and the value network with the one-dimensional convolutional neural network.An improved deep reinforcement learning algorithm based on the pointer network is proposed,which reduces the training time by 12%to 15%compared with the original model on the same scale of resolving the problem.The experimental results verify the effectiveness of the improved algorithm.