Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems

• URL: http://arxiv.org/abs/2501.04072v1
• Date: Tue, 07 Jan 2025 16:45:41 GMT
• Title: Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems
• Authors: Long Wang, Jiongzhi Zheng, Zhengda Xiong, Kun He,
• Abstract summary: Lin-Kernighan-Helsguan (LKH) is a classic local search algorithm for the Traveling Salesman Problem (TSP)<n>LKH introduces an $alpha$-value to replace the traditional distance metric for evaluating the edge quality.<n>We propose a novel way to extract backbone information during the TSP local search process, which is dynamic and can be updated once a local optimal solution is found.
• Score: 9.035853156510507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Lin-Kernighan-Helsguan (LKH) heuristic is a classic local search algorithm for the Traveling Salesman Problem (TSP). LKH introduces an $\alpha$-value to replace the traditional distance metric for evaluating the edge quality, which leads to a significant improvement. However, we observe that the $\alpha$-value does not make full use of the historical information during the search, and single guiding information often makes LKH hard to escape from some local optima. To address the above issues, we propose a novel way to extract backbone information during the TSP local search process, which is dynamic and can be updated once a local optimal solution is found. We further propose to combine backbone information, $\alpha$-value, and distance to evaluate the edge quality so as to guide the search. Moreover, we abstract their different combinations to arms in a multi-armed bandit (MAB) and use an MAB model to help the algorithm select an appropriate evaluation metric dynamically. Both the backbone information and MAB can provide diverse guiding information and learn from the search history to suggest the best metric. We apply our methods to LKH and LKH-3, which is an extension version of LKH that can be used to solve about 40 variant problems of TSP and Vehicle Routing Problem (VRP). Extensive experiments show the excellent performance and generalization capability of our proposed method, significantly improving LKH for TSP and LKH-3 for two representative TSP and VRP variants, the Colored TSP (CTSP) and Capacitated VRP with Time Windows (CVRPTW).

Related papers

• Distilling a Small Utility-Based Passage Selector to Enhance Retrieval-Augmented Generation [77.07879255360342]
  Retrieval-augmented generation (RAG) enhances large language models (LLMs) by incorporating retrieved information.<n>In RAG, the emphasis has shifted to utility, which considers the usefulness of passages for generating accurate answers.<n>Our approach focuses on utility-based selection rather than ranking, enabling dynamic passage selection tailored to specific queries without the need for fixed thresholds.<n>Our experiments demonstrate that utility-based selection provides a flexible and cost-effective solution for RAG, significantly reducing computational costs while improving answer quality.
  arXiv  Detail & Related papers  (2025-07-25T09:32:29Z)
• Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems [13.620917861669607]
  We introduce a bandit-based method for the Lin-Kernighan-Helsgaun (LKH) algorithm for the Traveling Salesman Problem (TSP)<n>We incorporate multi-armed bandit models to dynamically select the most suitable candidate edges in each iteration, enabling LKH to make smarter choices and lead to improved solutions.
  arXiv  Detail & Related papers  (2025-05-21T06:11:00Z)
• Detecting Knowledge Boundary of Vision Large Language Models by Sampling-Based Inference [78.08901120841833]
  We propose a method to detect the knowledge boundary of Visual Large Language Models (VLLMs) We show that our method successfully depicts a VLLM's knowledge boundary based on which we are able to reduce indiscriminate retrieval while maintaining or improving the performance.
  arXiv  Detail & Related papers  (2025-02-25T09:32:08Z)
• Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices [13.68761797358598]
  We study the dynamic pricing problem with knapsack, addressing the challenge of balancing exploration and exploitation under resource constraints. We introduce three algorithms tailored to different informational settings: a Boundary Attracted Re-solve Method for full information, an online learning algorithm for scenarios with no prior information, and an estimate-then-select re-solve algorithm that leverages machine-learned informed prices with known upper bound of estimation errors.
  arXiv  Detail & Related papers  (2025-01-24T00:46:52Z)
• Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning [29.551883712536295]
  Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution.<n>We propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy.
  arXiv  Detail & Related papers  (2025-01-01T16:08:40Z)
• Exploring Knowledge Boundaries in Large Language Models for Retrieval Judgment [56.87031484108484]
  Large Language Models (LLMs) are increasingly recognized for their practical applications. Retrieval-Augmented Generation (RAG) tackles this challenge and has shown a significant impact on LLMs. By minimizing retrieval requests that yield neutral or harmful results, we can effectively reduce both time and computational costs.
  arXiv  Detail & Related papers  (2024-11-09T15:12:28Z)
• Rethinking Optimal Transport in Offline Reinforcement Learning [64.56896902186126]
  In offline reinforcement learning, the data is provided by various experts and some of them can be sub-optimal. To extract an efficient policy, it is necessary to emphstitch the best behaviors from the dataset. We present an algorithm that aims to find a policy that maps states to a emphpartial distribution of the best expert actions for each given state.
  arXiv  Detail & Related papers  (2024-10-17T22:36:43Z)
• Research on Travel Route Planing Problems Based on Greedy Algorithm [0.0]
  Route planning problem based on the greedy algorithm represents a method of identifying the optimal or near-optimal route between a given start point and end point. In this paper, the PCA method is employed initially to downscale the city evaluation indexes, extract the key principal components, and then downscale the data. A route planning algorithm is proposed and optimised based on the greedy algorithm, which provides personalised route customisation according to the different needs of tourists.
  arXiv  Detail & Related papers  (2024-10-17T05:17:01Z)
• CAGES: Cost-Aware Gradient Entropy Search for Efficient Local Multi-Fidelity Bayesian Optimization [0.0]
  We propose a novel algorithm, Cost-Aware Gradient Entropy Search (CAGES), for local BO of multi-fidelity black-box functions. We demonstrate CAGES can achieve significant performance improvements compared to other state-of-the-art methods on a variety of synthetic and benchmark RL problems.
  arXiv  Detail & Related papers  (2024-05-13T14:00:02Z)
• Multimodal Learned Sparse Retrieval with Probabilistic Expansion Control [66.78146440275093]
  Learned retrieval (LSR) is a family of neural methods that encode queries and documents into sparse lexical vectors. We explore the application of LSR to the multi-modal domain, with a focus on text-image retrieval. Current approaches like LexLIP and STAIR require complex multi-step training on massive datasets. Our proposed approach efficiently transforms dense vectors from a frozen dense model into sparse lexical vectors.
  arXiv  Detail & Related papers  (2024-02-27T14:21:56Z)
• Hint-before-Solving Prompting: Guiding LLMs to Effectively Utilize Encoded Knowledge [85.17343729885003]
  We introduce Hint-before-Solving Prompting (HSP), which guides the model to generate hints for solving the problem. HSP can effectively improve the accuracy of reasoning tasks. We build the HSPMATH dataset based on HSP and fine-tuned Llemma-7B, reaching 64.3 accuracy.
  arXiv  Detail & Related papers  (2024-02-22T05:58:03Z)
• Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems [17.564543997481508]
  The Lin-Kernighan-Helsgaun (LKH) algorithm is one of the state-of-the-art local search algorithms for the Traveling Salesman Problem (TSP) LKH and LKH-3 associate a candidate set to each city to improve the algorithm efficiency, and have two different methods, called $alpha$-measure and POPMUSIC, to decide the candidate sets. In this work, we first propose a Variable Strategy Reinforced LKH (VSR-LKH) algorithm, which incorporates three reinforcement learning methods (Q-learning, Sarsa, and Monte Carlo)
  arXiv  Detail & Related papers  (2022-07-08T13:03:29Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Information Directed Reward Learning for Reinforcement Learning [64.33774245655401]
  We learn a model of the reward function that allows standard RL algorithms to achieve high expected return with as few expert queries as possible. In contrast to prior active reward learning methods designed for specific types of queries, IDRL naturally accommodates different query types. We support our findings with extensive evaluations in multiple environments and with different types of queries.
  arXiv  Detail & Related papers  (2021-02-24T18:46:42Z)
• Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem [12.851149098610096]
  We propose a variable strategy reinforced approach, denoted as VSR-LKH. It combines three reinforcement learning methods (Q-learning, Sarsa and Monte Carlo) with the well-known TSP algorithm, called Lin-Kernighan-Helsgaun (LKH) VSR-LKH replaces the inflexible operation in LKH, and lets the program learn to make choice at each search step by reinforcement learning.
  arXiv  Detail & Related papers  (2020-12-08T14:58:36Z)

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.