Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2304.09407v1
• Date: Wed, 19 Apr 2023 03:48:32 GMT
• Title: Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem
• Authors: Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, Jiang Bian
• Abstract summary: Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics. Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency. We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
• Score: 67.32731657297377
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Traveling Salesman Problem (TSP), as a classic routing optimization problem originally arising in the domain of transportation and logistics, has become a critical task in broader domains, such as manufacturing and biology. Recently, Deep Reinforcement Learning (DRL) has been increasingly employed to solve TSP due to its high inference efficiency. Nevertheless, most of existing end-to-end DRL algorithms only perform well on small TSP instances and can hardly generalize to large scale because of the drastically soaring memory consumption and computation time along with the enlarging problem scale. In this paper, we propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer. Particularly, Pointerformer adopts both reversible residual network in the encoder and multi-pointer network in the decoder to effectively contain memory consumption of the encoder-decoder architecture. To further improve the performance of TSP solutions, Pointerformer employs both a feature augmentation method to explore the symmetries of TSP at both training and inference stages as well as an enhanced context embedding approach to include more comprehensive context information in the query. Extensive experiments on a randomly generated benchmark and a public benchmark have shown that, while achieving comparative results on most small-scale TSP instances as SOTA DRL approaches do, Pointerformer can also well generalize to large-scale TSPs.

Related papers

• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  The traveling purchaser problem (TPP) is an important optimization problem with broad applications. We propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately. By introducing a meta-learning strategy, the policy network can be trained stably on large-sized TPP instances.
  arXiv  Detail & Related papers  (2024-04-03T05:32:10Z)
• Less Is More - On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP [8.317022421446639]
  We propose a data preprocessing method that allows the encoders to focus on the most relevant parts of the Traveling Salesman Problem (TSP) instances only. We show that for GNNs appropriate sparsification and ensembles of different sparsification levels lead to substantial performance increases of the overall architecture.
  arXiv  Detail & Related papers  (2024-03-25T20:16:16Z)
• Stop Regressing: Training Value Functions via Classification for Scalable Deep RL [109.44370201929246]
  We show that training value functions with categorical cross-entropy improves performance and scalability in a variety of domains. These include: single-task RL on Atari 2600 games with SoftMoEs, multi-task RL on Atari with large-scale ResNets, robotic manipulation with Q-transformers, playing Chess without search, and a language-agent Wordle task with high-capacity Transformers.
  arXiv  Detail & Related papers  (2024-03-06T18:55:47Z)
• RegFormer: An Efficient Projection-Aware Transformer Network for Large-Scale Point Cloud Registration [73.69415797389195]
  We propose an end-to-end transformer network (RegFormer) for large-scale point cloud alignment. Specifically, a projection-aware hierarchical transformer is proposed to capture long-range dependencies and filter outliers. Our transformer has linear complexity, which guarantees high efficiency even for large-scale scenes.
  arXiv  Detail & Related papers  (2023-03-22T08:47:37Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  Image super-resolution (SR) has witnessed extensive neural network designs from CNN to transformer architectures. This work investigates the potential of network pruning for super-resolution iteration to take advantage of off-the-shelf network designs and reduce the underlying computational overhead. We propose a novel Iterative Soft Shrinkage-Percentage (ISS-P) method by optimizing the sparse structure of a randomly network at each and tweaking unimportant weights with a small amount proportional to the magnitude scale on-the-fly.
  arXiv  Detail & Related papers  (2023-03-16T21:06:13Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• Improving Generalization of Deep Reinforcement Learning-based TSP Solvers [19.29028564568974]
  We propose a novel approach named MAGIC that includes a deep learning architecture and a DRL training method. Our architecture, which integrates a multilayer perceptron, a graph neural network, and an attention model, defines a policy that sequentially generates a traveling salesman solution. Our training method includes several innovations: (1) we interleave DRL policy updates with local search (using a new local search technique), (2) we use a novel simple baseline, and (3) we apply gradient learning.
  arXiv  Detail & Related papers  (2021-10-06T15:16:19Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  The Travelling Salesman Problem (TSP) is a classical optimisation problem. Deep learning has been successfully extended to meta-learning, where previous solving efforts assist in learning how to optimise future instances. This paper introduces a new learning-based approach to solve a variety of different and common TSP problems.
  arXiv  Detail & Related papers  (2020-10-23T07:37:16Z)
• OverNet: Lightweight Multi-Scale Super-Resolution with Overscaling Network [3.6683231417848283]
  We introduce OverNet, a deep but lightweight convolutional network to solve SISR at arbitrary scale factors with a single model. We show that our network outperforms previous state-of-the-art results in standard benchmarks while using fewer parameters than previous approaches.
  arXiv  Detail & Related papers  (2020-08-05T22:10:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.