Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2012.04461v6
• Date: Wed, 17 Mar 2021 08:02:11 GMT
• Title: Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem
• Authors: Jiongzhi Zheng and Kun He and Jianrong Zhou and Yan Jin and Chu-Min Li
• Abstract summary: 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.
• Score: 12.851149098610096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We address the Traveling Salesman Problem (TSP), a famous NP-hard combinatorial optimization problem. And we propose a variable strategy reinforced approach, denoted as VSR-LKH, which 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 traversal operation in LKH, and lets the program learn to make choice at each search step by reinforcement learning. Experimental results on 111 TSP benchmarks from the TSPLIB with up to 85,900 cities demonstrate the excellent performance of the proposed method.

Related papers

• 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)
• Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems [9.035853156510507]
  Lin-Kernighan-Helsguan (LKH) 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. 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.
  arXiv  Detail & Related papers  (2025-01-07T16:45:41Z)
• 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)
• 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)
• Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
  We introduce a Deep Reinforcement Learning based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search. We evaluate the proposed method on a problem with orienteering weights and time windows, as presented in an IJCAI competition. The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches.
  arXiv  Detail & Related papers  (2022-11-01T21:33:46Z)
• 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)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem [14.605192361813454]
  We present NeuroLKH, a novel algorithm that combines deep learning with the strong traditional Lin-Kernighan-Helsgaun (LKH) Specifically, we train a Sparse Graph Network (SGN) with supervised learning for edge scores and unsupervised learning for node penalties. By training one model on a wide range of problem sizes, NeuroLKH significantly outperforms LKH and generalizes well to much larger sizes.
  arXiv  Detail & Related papers  (2021-10-15T10:14:27Z)
• Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem [4.92025078254413]
  We propose a powerful Reinforced Hybrid Genetic Algorithm (RHGA) for the famous NP-hard Traveling Salesman Problem (TSP) RHGA combines reinforcement learning technique with the well-known Edge Assembly Crossover genetic algorithm (EAX-GA) and the Lin-Kernighan-Helsgaun local search. Experimental results on 138 well-known and widely used benchmarks, with the number of cities ranging from 1,000 to 85,900, demonstrate the excellent performance of the proposed method.
  arXiv  Detail & Related papers  (2021-07-09T07:36:12Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We build the connections between the theory of approximate maximum inner product search and the regret analysis of reinforcement learning.
  arXiv  Detail & Related papers  (2021-05-18T05:23:53Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  We propose a new reinforcement learning based ZO algorithm (ZO-RL) with learning the sampling policy for generating the perturbations in ZO optimization instead of using random sampling. Our results show that our ZO-RL algorithm can effectively reduce the variances of ZO gradient by learning a sampling policy, and converge faster than existing ZO algorithms in different scenarios.
  arXiv  Detail & Related papers  (2021-04-09T14:50:59Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
  Many traditional algorithms for solving optimization problems involve using hand-crafteds that sequentially construct a solution. Reinforcement learning (RL) proposes a good alternative to automate the search of theses by training an agent in a supervised or self-supervised manner.
  arXiv  Detail & Related papers  (2020-03-07T16:19:45Z)

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.