Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances

• URL: http://arxiv.org/abs/2012.10658v2
• Date: Wed, 24 Feb 2021 02:48:46 GMT
• Title: Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
• Authors: Zhang-Hua Fu, Kai-Bin Qiu, Hongyuan Zha
• Abstract summary: This paper tries to train a small-scale model, which could be repetitively used to build heat maps for the traveling salesman problem (TSP) Heat maps are fed into a reinforcement learning approach (Monte Carlo tree search) to guide the search of high-quality solutions. Experimental results show that, this new approach clearly outperforms the existing machine learning based TSP algorithms.
• Score: 55.64521598173897
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10,000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.

Related papers

• Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems [14.277867417951347]
  Recent advancements in solving large-scale traveling salesman problems utilize the heatmap-guided Monte Carlo tree search (MCTS) paradigm. We demonstrate that a simple baseline method can outperform complex ML approaches in heatmap generation. Our findings show the paradigm's inferiority to the LKH-3 despite the paradigm's reliance on problem-specific, hand-crafted strategies.
  arXiv  Detail & Related papers  (2024-06-02T16:11:38Z)
• Modular Learning of Deep Causal Generative Models for High-dimensional Causal Inference [5.522612010562183]
  Modular-DCM is the first algorithm that, given the causal structure, uses adversarial training to learn the network weights. We show our algorithm's convergence on the COVIDx dataset and its utility with a causal invariant prediction problem on CelebA-HQ.
  arXiv  Detail & Related papers  (2024-01-02T20:31:15Z)
• An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems [22.792870849003137]
  This work proposes a data-driven graph representation learning method for solving the Traveling Salesman Problem (TSP) A residual gated encoder is trained to learn latent edge embeddings, followed by an edge-centered decoder to output link predictions in an end-to-end manner. The experimental results demonstrate that the proposed edge-aware graph autoencoder model achieves a highly competitive performance.
  arXiv  Detail & Related papers  (2023-10-10T11:42:49Z)
• Generalizing Backpropagation for Gradient-Based Interpretability [103.2998254573497]
  We show that the gradient of a model is a special case of a more general formulation using semirings. This observation allows us to generalize the backpropagation algorithm to efficiently compute other interpretable statistics.
  arXiv  Detail & Related papers  (2023-07-06T15:19:53Z)
• Travel the Same Path: A Novel TSP Solving Strategy [0.0]
  We consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to. We demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework.
  arXiv  Detail & Related papers  (2022-10-12T03:56:37Z)
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning [132.45959478064736]
  We propose a general framework that unifies model-based and model-free reinforcement learning. We propose a novel estimation function with decomposable structural properties for optimization-based exploration. Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed.
  arXiv  Detail & Related papers  (2022-09-30T17:59:16Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)
• Model-free Representation Learning and Exploration in Low-rank MDPs [64.72023662543363]
  We present the first model-free representation learning algorithms for low rank MDPs. Key algorithmic contribution is a new minimax representation learning objective. Result can accommodate general function approximation to scale to complex environments.
  arXiv  Detail & Related papers  (2021-02-14T00:06:54Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

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.