Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization

• URL: http://arxiv.org/abs/2506.09404v1
• Date: Wed, 11 Jun 2025 05:17:30 GMT
• Title: Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization
• Authors: Shengda Gu, Kai Li, Junliang Xing, Yifan Zhang, Jian Cheng,
• Abstract summary: We propose the Evolutionary Augmentation Mechanism (EAM) to synergize the learning efficiency of DRL with the global search power of GAs.<n>EAM operates by generating solutions from a learned policy and refining them through domain-specific genetic operations such as crossover and mutation.<n>EAM can be seamlessly integrated with state-of-the-art DRL solvers such as the Attention Model, POMO, and SymNCO.
• Score: 25.633698252033756
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization problems are notoriously challenging due to their discrete structure and exponentially large solution space. Recent advances in deep reinforcement learning (DRL) have enabled the learning heuristics directly from data. However, DRL methods often suffer from limited exploration and susceptibility to local optima. On the other hand, evolutionary algorithms such as Genetic Algorithms (GAs) exhibit strong global exploration capabilities but are typically sample inefficient and computationally intensive. In this work, we propose the Evolutionary Augmentation Mechanism (EAM), a general and plug-and-play framework that synergizes the learning efficiency of DRL with the global search power of GAs. EAM operates by generating solutions from a learned policy and refining them through domain-specific genetic operations such as crossover and mutation. These evolved solutions are then selectively reinjected into the policy training loop, thereby enhancing exploration and accelerating convergence. We further provide a theoretical analysis that establishes an upper bound on the KL divergence between the evolved solution distribution and the policy distribution, ensuring stable and effective policy updates. EAM is model-agnostic and can be seamlessly integrated with state-of-the-art DRL solvers such as the Attention Model, POMO, and SymNCO. Extensive results on benchmark problems (e.g., TSP, CVRP, PCTSP, and OP) demonstrate that EAM significantly improves both solution quality and training efficiency over competitive baselines.

Related papers

• Leveraging Genetic Algorithms for Efficient Demonstration Generation in Real-World Reinforcement Learning Environments [0.8602553195689513]
  Reinforcement Learning (RL) has demonstrated significant potential in certain real-world industrial applications.<n>This study investigates the utilization of Genetic Algorithms (GAs) as a mechanism for improving RL performance.<n>We propose a novel approach in which GA-generated expert demonstrations are used to enhance policy learning.
  arXiv  Detail & Related papers  (2025-07-01T14:04:17Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Evolutionary Policy Optimization [47.30139909878251]
  On-policy reinforcement learning (RL) algorithms are widely used for their strong performance and training stability, but they struggle to scale with larger batch sizes.<n>We propose Evolutionary Policy Optimization (EPO), a hybrid that combines the scalability and diversity of EAs with the performance and stability of policy gradients.
  arXiv  Detail & Related papers  (2025-03-24T18:08:54Z)
• Genetic Algorithm enhanced by Deep Reinforcement Learning in parent selection mechanism and mutation : Minimizing makespan in permutation flow shop scheduling problems [0.18846515534317265]
  The proposed RL+GA method was specifically tested on the flow shop scheduling problem (FSP) The hybrid algorithm incorporates neural networks (NN) and uses the off-policy method Q-learning. Results of the study highlight the effectiveness of the RL+GA approach in improving the performance of the primitive GA.
  arXiv  Detail & Related papers  (2023-11-10T08:51:42Z)
• Reinforcement Learning-assisted Evolutionary Algorithm: A Survey and Research Opportunities [63.258517066104446]
  Reinforcement learning integrated as a component in the evolutionary algorithm has demonstrated superior performance in recent years. We discuss the RL-EA integration method, the RL-assisted strategy adopted by RL-EA, and its applications according to the existing literature. In the applications of RL-EA section, we also demonstrate the excellent performance of RL-EA on several benchmarks and a range of public datasets.
  arXiv  Detail & Related papers  (2023-08-25T15:06:05Z)
• A Reinforcement Learning-assisted Genetic Programming Algorithm for Team Formation Problem Considering Person-Job Matching [70.28786574064694]
  A reinforcement learning-assisted genetic programming algorithm (RL-GP) is proposed to enhance the quality of solutions. The hyper-heuristic rules obtained through efficient learning can be utilized as decision-making aids when forming project teams.
  arXiv  Detail & Related papers  (2023-04-08T14:32:12Z)
• Evolving Populations of Diverse RL Agents with MAP-Elites [1.5575376673936223]
  We introduce a flexible framework that allows the use of any Reinforcement Learning (RL) algorithm instead of just policies. We demonstrate the benefits brought about by our framework through extensive numerical experiments on a number of robotics control problems.
  arXiv  Detail & Related papers  (2023-03-09T19:05:45Z)
• Direct Mutation and Crossover in Genetic Algorithms Applied to Reinforcement Learning Tasks [0.9137554315375919]
  This paper will focus on applying neuroevolution using a simple genetic algorithm (GA) to find the weights of a neural network that produce optimally behaving agents. We present two novel modifications that improve the data efficiency and speed of convergence when compared to the initial implementation.
  arXiv  Detail & Related papers  (2022-01-13T07:19:28Z)
• Deceive D: Adaptive Pseudo Augmentation for GAN Training with Limited Data [125.7135706352493]
  Generative adversarial networks (GANs) typically require ample data for training in order to synthesize high-fidelity images. Recent studies have shown that training GANs with limited data remains formidable due to discriminator overfitting. This paper introduces a novel strategy called Adaptive Pseudo Augmentation (APA) to encourage healthy competition between the generator and the discriminator.
  arXiv  Detail & Related papers  (2021-11-12T18:13:45Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  Reinforcement learning (RL) has been widely investigated and shown to be a promising solution for decision-making and optimal control processes. We propose an adaptive ADMM (asI-ADMM) algorithm and apply it to decentralized RL with edge-computing-empowered IIoT networks. Experiment results show that our proposed algorithms outperform the state of the art in terms of communication costs and scalability, and can well adapt to complex IoT environments.
  arXiv  Detail & Related papers  (2021-06-30T16:49:07Z)
• Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning [56.17667147101263]
  In real-world tasks, reinforcement learning agents encounter situations that are not present during training time. To ensure reliable performance, the RL agents need to exhibit robustness against worst-case situations. We propose the Robust Hallucinated Upper-Confidence RL (RH-UCRL) algorithm to provably solve this problem.
  arXiv  Detail & Related papers  (2021-03-18T16:50:17Z)

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.