Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2107.06870v1
• Date: Fri, 9 Jul 2021 07:36:12 GMT
• Title: Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem
• Authors: Jiongzhi Zheng and Menglei Chen and Jialun Zhong and Kun He
• Abstract summary: 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.
• Score: 4.92025078254413
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 (LKH) local search heuristic. With the help of the proposed hybrid mechanism, the genetic evolution of EAX-GA and the local search of LKH can boost each other's performance. And the reinforcement learning technique based on Q-learning further promotes the hybrid genetic algorithm. Experimental results on 138 well-known and widely used TSP benchmarks, with the number of cities ranging from 1,000 to 85,900, demonstrate the excellent performance of the proposed method.

Related papers

• Sequential, Parallel and Consecutive Hybrid Evolutionary-Swarm Optimization Metaheuristics [43.05659890525653]
  This paper explores hybrid evolutionary-swarm metaheuristics that combine the features of PSO and GA in a sequential, parallel and consecutive manner.<n>The experimental results demonstrate that the hybrid approaches achieve superior convergence and consistency.<n>The paper introduces a novel consecutive hybrid PSO-GA evolutionary algorithm that ensures continuity between PSO and GA steps through explicit information transfer mechanisms.
  arXiv  Detail & Related papers  (2025-08-01T00:23:36Z)
• Genetic Algorithm with Innovative Chromosome Patterns in the Breeding Process [0.0]
  Genetic Algorithm with Border Trades (GAB) is a novel modification of the standard genetic algorithm that enhances exploration by incorporating new chromosome patterns in the breeding process.<n>GAB achieves up to 8x higher fitness and 10x faster convergence on complex job scheduling problems compared to standard Genetic Algorithms.
  arXiv  Detail & Related papers  (2025-01-30T07:35:43Z)
• Image Classification Method using Dynamic Quantum Inspired Genetic Algorithm [0.0]
  D-QIGA introduces adaptive mechanisms and a lengthening chromosome strategy to avoid local optima and improve optimization. Tested on benchmark and real-world problems, it significantly outperforms traditional Genetic Algorithms, achieving over 99.99% classification accuracy compared to GA's 95%.
  arXiv  Detail & Related papers  (2025-01-20T13:18:13Z)
• Evolutionary Approach to S-box Generation: Optimizing Nonlinear Substitutions in Symmetric Ciphers [19.65010496906351]
  This study explores the application of genetic algorithms in generating highly nonlinear substitution boxes (S-boxes) for symmetric key cryptography. We present a novel implementation that combines a genetic algorithm with the Walsh-Hadamard Spectrum (WHS) cost function to produce 8x8 S-boxes with a nonlinearity of 104. Our approach achieves performance parity with the best-known methods, requiring an average of 49,399 iterations with a 100% success rate.
  arXiv  Detail & Related papers  (2024-07-03T21:15:24Z)
• Tree Search-Based Evolutionary Bandits for Protein Sequence Optimization [44.356888079704156]
  Protein engineering is a daunting task due to the vast sequence space of any given protein. Protein engineering is typically conducted through an iterative process of adding mutations to the wild-type or lead sequences. We propose a tree search-based bandit learning method, which expands a tree starting from the initial sequence with the guidance of a bandit machine learning model.
  arXiv  Detail & Related papers  (2024-01-08T06:33:27Z)
• Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
  Genetic Algorithms (GAs) are known for their efficiency in solving optimization problems. This paper proposes a new metaheuristic algorithm called the Genetic Engineering Algorithm (GEA) that draws inspiration from genetic engineering concepts.
  arXiv  Detail & Related papers  (2023-09-28T13:05:30Z)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulate is an evolutionary optimization algorithm and software package for global optimization. We provide an MPI-based implementation of our algorithm, which features variants of selection, mutation, crossover, and migration. We find that Propulate is up to three orders of magnitude faster without sacrificing solution accuracy.
  arXiv  Detail & Related papers  (2023-01-20T18:17:34Z)
• A Genetic Quantum Annealing Algorithm [0.0]
  A genetic algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. We present an algorithm which enhances the classical GA with input from quantum annealers.
  arXiv  Detail & Related papers  (2022-09-15T16:59:55Z)
• 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)
• Hybrid Random Features [60.116392415715275]
  We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) HRFs automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest.
  arXiv  Detail & Related papers  (2021-10-08T20:22:59Z)
• Hybrid Henry Gas Solubility Optimization Algorithm with Dynamic Cluster-to-Algorithm Mapping for Search-based Software Engineering Problems [1.0323063834827413]
  This paper discusses a new variant of the Henry Gas Solubility Optimization (HGSO) Algorithm, called Hybrid HGSO (HHGSO) Unlike its predecessor, HHGSO allows multiple clusters serving different individual meta-heuristic algorithms to coexist within the same population. Exploiting the dynamic cluster-to-algorithm mapping via penalized and reward model with adaptive switching factor, HHGSO offers a novel approach for meta-heuristic hybridization.
  arXiv  Detail & Related papers  (2021-05-31T12:42:15Z)
• 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)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

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.