Decoupling Numerical and Structural Parameters: An Empirical Study on Adaptive Genetic Algorithms via Deep Reinforcement Learning for the Large-Scale TSP

Hongyu Wang; Yuhan Jing; Yibing Shi; Enjin Zhou; Haotian Zhang; Jialong Shi

cs.NEMar 21, 2026

Decoupling Numerical and Structural Parameters: An Empirical Study on Adaptive Genetic Algorithms via Deep Reinforcement Learning for the Large-Scale TSP

Authors: Hongyu Wang, Yuhan Jing, Yibing Shi, Enjin Zhou, Haotian Zhang, Jialong Shi

Organizations: School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China · School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an, China · Frontier Institute of Science and Technology, Xi’an Jiaotong University, Xi’an, China

Abstract

Proper parameter configuration is a prerequisite for the success of Evolutionary Algorithms (EAs). While various adaptive strategies have been proposed, it remains an open question whether all control dimensions contribute equally to algorithmic scalability. To investigate this, we categorize control variables into numerical parameters (e.g., crossover and mutation rates) and structural parameters (e.g., population size and operator switching), hypothesizing that they play distinct roles. This paper presents an empirical study utilizing a dual-level Deep Reinforcement Learning (DRL) framework to decouple and analyze the impact of these two dimensions on the Traveling Salesman Problem (TSP). We employ a Recurrent PPO agent to dynamically regulate these parameters, treating the DRL model as a probe to reveal evolutionary dynamics. Experimental results confirm the effectiveness of this approach: the learned policies outperform static baselines, reducing the optimality gap by approximately 45% on the largest tested instance (rl5915). Building on this validated framework, our ablation analysis reveals a fundamental insight: while numerical tuning offers local refinement, structural plasticity is the decisive factor in preventing stagnation and facilitating escape from local optima. These findings suggest that future automated algorithm design should prioritize dynamic structural reconfiguration over fine-grained probability adjustment. To facilitate reproducibility, the source code is available at https://github.com/StarDream1314/DRLGA-TSP

Figures & tables

Fig. 1 : A Dual-level Adaptive Control Architecture

Fig. 2 : The Upper Controller and The Lower Worker

Fig. 5 : Examples of TSP Instances Generated by the TSP Generator Pool

Instance	Optimality Gap (%)		Inference Time (s)
Instance	Static GA	DRLGA (Ours)	Static GA	DRLGA (Ours)
fl1577	9.10	4.44	$\approx$ 183	$\approx$ 347
u2152	13.50	4.57	$\approx$ 426	$\approx$ 869
pcb3038	11.53	4.89	$\approx$ 746	$\approx$ 1606
fnl4461	9.84	6.60	$\approx$ 1,807	$\approx$ 3903
rl5915	19.19	10.48	$\approx$ 2,821	$\approx$ 6,240

TABLE I : Performance Comparison

Panel of Figure 8 — Fig. 7 : Analysis of lin318 Instance

Dataset	Experiment	Gap (%)
Dataset	Experiment	Mean	Std	Min	Max
kroA100	Fixed CR (0.8)	0.07	0.02	0.06	0.12
	Fixed MR (0.2)	0.08	0.03	0.06	0.12
	Fixed Op (2-Opt)	0.18	0.06	0.12	0.28
	Fixed Pop (500)	0.08	0.03	0.06	0.12
	Full DRLGA (Ours)	0.08	0.03	0.06	0.12

TABLE II : Ablation Study

Evolutionary Optimization

Evolutionary optimization searches for strong solutions through population-based variation, selection, and adaptation.

See all 293 papers

Discovering Interpretable Multi-Parameter Control Policies for Evolutionary Algorithms Using Deep Reinforcement Learning
Jun 8, 2026Tai Nguyen, Phong Le, Carola Doerr +1Evolutionary Optimization Deep Q-Learning
University of St Andrews, St Andrews, United Kingdom · Sorbonne Universit´e, CNRS, LIP6, Paris, France
Learning to Orchestrate Evolutionary Search: Progression-Aware Deep Reinforcement Learning for Dynamic DE-CMA-ES Coordination in Optimization and Structural Model Updating
Oct 8, 2026Lechen Li, Rongye Shi, Wanhuan ZhouEvolutionary Optimization Model Calibration
State Key Laboratory of Internet of Things for Smart City, University of Macau, Macau 519000, China · College of Water Conservancy and Hydropower Engineering, Hohai University, Nanjing 210098, China · School of Artificial Intelligence, Beihang University, Beijing 100191, China
Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search
Mar 7, 2026Shaohua Yu, Tianyu Chen, Linyan Liu +1Automated Heuristic Design Large Neighborhood Search
School of Intelligent Science and Technology, Nanjing University of Science and Technology, Nanjing 210094, China · School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China · Université Paris-Saclay, CentraleSupélec, Laboratoire Génie Industriel, 91190, Gif-sur-Yvette, France +1

Jun 8, 2026J/K move · Enter open · S save

Discovering Interpretable Multi-Parameter Control Policies for Evolutionary Algorithms Using Deep Reinforcement Learning

Tai Nguyen, Phong Le, Carola Doerr, Nguyen Dang

University of St Andrews, St Andrews, United Kingdom · Sorbonne Universit´e, CNRS, LIP6, Paris, France

Evolutionary Optimization Deep Q-Learning Policy Learning

Open paper AskPDF arXiv

While deep Reinforcement Learning (deep-RL) has been increasingly applied to parameter control in evolutionary algorithms, rigorous theoretical analysis of parameter control remains largely restricted to single-parameter settings, owing to the difficulty of deriving effective, interpretable multi-parameter policies amenable to formal study. We demonstrate how deep-RL can be leveraged to overcome this barrier, using the (1+(

λ

λ

))-genetic algorithm optimizing OneMax, one of the few problems where a super-constant speedup of dynamic control has been formally proven, as a representative case study. We first show that standard approaches struggle to converge in this multi-parameter setting, and introduce algorithm-agnostic enhancements targeting action-space decomposition, reward shifting, and long-horizon discounting. With these in place, we compare common deep-RL methods and find that Double Deep Q-Networks uniquely avoid the policy collapse observed in Proximal Policy Optimization, yielding trajectories suitable for downstream analysis. Crucially, we move beyond the ``black-box'' nature of neural networks by distilling the learned behaviors into a transparent, symbolic control policy. This resulting policy does not only offer interpretability for future theoretical analysis but also yields exceptional performance, consistently outperforming existing baselines across a wide range of problem sizes.

Abstract

Evolutionary Optimization

Explore similar work

Discovering Interpretable Multi-Parameter Control Policies for Evolutionary Algorithms Using Deep Reinforcement Learning

Learning to Orchestrate Evolutionary Search: Progression-Aware Deep Reinforcement Learning for Dynamic DE-CMA-ES Coordination in Optimization and Structural Model Updating

Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search