A Dynamic Hybrid Model with Generalization Performance to Solve Large-Scale TSP
Traveling salesman problem(TSP)is a typical problem in combinatorial optimization,and the relevance of solving the TSP is significant.Using deep re-inforcement learning(DRL)models to automatically design learning algorithms has become a recent research hotspot as DRL is widely used in industry.In order to en-hance the generalization ability of the DRL model on the large-scale TSP,this paper proposes a hybrid model of dynamic graph convolutional network to encode and spa-tial attention mechanism to decode for tackling the large-scale TSP.Dynamic graph convolution module can dynamically encode node information so as to efficiently up-date the hidden layer state of each node.Spatial attention facilitates capturing the global connections between nodes,and then calculating and extracting key features by weighting all local features.Experimental results show that our model outperforms the previous DRL model for optimization when generalizing the training strategy of TSP50 to TSP250/500/750/1000,and the test results on the standard dataset of TSPlib also show the improvement of the model for optimization performance.
万方数据
维普
