Reinforced Linear Genetic Programming

Urmzd Mukhammadnaim

cs.NEJan 7, 2026

Reinforced Linear Genetic Programming

Authors: Urmzd Mukhammadnaim

Organizations: Dalhousie University Halifax, Nova Scotia

Abstract

Linear Genetic Programming (LGP) is a powerful technique that allows for a variety of problems to be solved using a linear representation of programs. However, there still exists some limitations to the technique, such as the need for humans to explicitly map registers to actions. This thesis proposes a novel approach that uses Q-Learning on top of LGP, Reinforced Linear Genetic Programming (RLGP) to learn the optimal register-action assignments. In doing so, we introduce a new framework "linear-gp" written in memory-safe Rust that allows for extensive experimentation for future works.

Figures & tables

Property	Type	Value Range
default_fitness	float	-
population_size	int	[0,)
gap	float	(0, 1.)
mutation_percent	float	[0, 1.0]
crossover_percent	float	[0, 1.0]
n_generations	int	[0,)

Table 3.1 : Hyperparameters

Panel of Figure 3 — Figure 3.1 : Performance comparison of different genetic programming methods on iris dataset (1/2)

Panel of Figure 4 — Figure 4.1 : Comparison of RLGP vs LGP Performance on Cart Pole

Generation	Max	Mean	Median	Min
0	197.6150	48.2211	8.0180	3.3220
1	198.6100	82.5966	58.6020	4.1180
2	199.6040	135.8412	149.9540	4.1400
3	200.1010	163.9173	180.0105	4.4240
4	200.1010	176.6355	189.1775	5.2090
5	200.1010	180.8190	192.1495	4.8770

Table 4.1 : LGP Cart Pole Aggregated Results

Generation	Max	Mean	Median	Min
0	209.1090	52.2117	7.2245	4.1240
1	211.0950	96.6963	87.9155	4.5420
2	211.5910	157.7400	172.4700	17.6940
3	211.0930	188.2812	190.5340	48.7950
4	211.5870	198.0718	200.6880	95.9330
5	211.5870	201.7260	205.1595	68.1670

Table 4.2 : RLGP Cart Pole Aggregated Results

Generation	Max	Mean	Median	Min
0	-147.2600	-198.8564	-200.0000	-200.0000
1	-140.7800	-198.0396	-200.0000	-200.0000
2	-135.9000	-196.7488	-200.0000	-200.0000
3	-136.2400	-194.4066	-200.0000	-200.0000
4	-130.4800	-191.1292	-200.0000	-200.0000
5	-122.5800	-186.1694	-198.1600	-200.0000

Table 4.3 : LGP Mountain Car Aggregated Results

Generation	Max	Mean	Median	Min
0	-159.3520	-199.2556	-200.0000	-200.0000
1	-148.2350	-198.4004	-200.0000	-200.0000
2	-129.8430	-197.0150	-200.0000	-200.0000
3	-125.7290	-195.3591	-200.0000	-200.0000
4	-124.0570	-192.3421	-200.0000	-200.0000
5	-121.1780	-187.7516	-199.4060	-200.0000

Table 4.4 : RLGP Mountain Car Aggregated Results

Genetic Programming

Genetic programming evolves programs and expression trees to discover models, heuristics, and algorithms for complex tasks.

See all 54 papers

Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
Oct 1, 2026Jinhwan Sul, Alex Oshin, Evangelos A. TheodorouPrimal-Dual Optimization Reinforcement Learning
Georgia Institute of Technology, USA
AGAR: a reinforcement learning substrate for LLM program evolution
Oct 6, 2026Haoran Li, Zengle Ge, Xiaomin Yuan +11LLM-Based Program Synthesis RL for Code Generation
University of the Chinese Academy of Sciences · Baidu · Tsinghua University +2
RLGT: A reinforcement learning framework for extremal graph theory
Feb 19, 2026Ivan Damnjanović, Uroš Milivojević, Irena Đorđević +1Reinforcement Learning RL for Combinatorial Optimization
Faculty of Electronic Engineering, University of Niš, Aleksandra Medvedeva 4, Niš, 18104, Serbia · Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Glagoljaška 8, Koper, 6000, Slovenia · College of Integrative Studies, Abdullah Al Salem University, Firdous Street, Block 3, Khaldiya, 72303, Kuwait

Oct 1, 2026J/K move · Enter open · S save

Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

Jinhwan Sul, Alex Oshin, Evangelos A. Theodorou

Georgia Institute of Technology, USA

Primal-Dual Optimization Reinforcement Learning Linear Programming Accelerated Gradient Methods

Open paper AskPDF arXiv

Primal-dual hybrid gradient (PDHG) methods solve large-scale linear programs (LPs) using GPU-friendly matrix-vector products and projections, but their practical performance depends on coordinating algorithm parameters, acceleration, and restarts. We introduce GALLOP, which uses reinforcement learning to jointly learn continuous algorithm parameters and discrete restart decisions without differentiating through the solver. Its generalized accelerated PDHG update combines separate primal and dual extrapolation, history corrections, and restart anchoring with independently adjustable coefficients. We train a dimension-agnostic feedback policy using a groupwise proximal policy optimization objective that clips likelihood ratios separately for different control groups and excludes inactive acceleration controls on restart transitions. We evaluate GALLOP on six LP families and a public item-placement benchmark. On the main evaluation settings across the six families, GALLOP reduces iteration counts by factors of

1.9

5.6

and achieves up to a

16.0\times

speedup in algorithm wall-clock time over MPAX. With one policy trained per family, the learned policies generalize without retraining to within-family LPs

3\times

400\times

larger than the largest training instances, including Transport LPs with

10.24

million variables.

Abstract

Genetic Programming

Explore similar work

Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

AGAR: a reinforcement learning substrate for LLM program evolution

RLGT: A reinforcement learning framework for extremal graph theory