Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve

Nam H. Le

cs.NEOct 7, 2026

Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve

Authors: Nam H. Le

Organizations: Vermont Complexity Center University of Vermont Burlington, VT 05405

Abstract

Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output. A substantial line of work instead makes the program an input to a separate learner, so fitness measures the learner's output rather than the program's. Which learner to attach matters, with no account of what decides it. What makes a target hard for genetic programming is how much nonlinearity the program must build by composing primitives; whatever nonlinearity the learner supplies, the program need not. The quantity to measure is therefore how much of a target's nonlinearity a learner can take over, though on continuous benchmarks it can only be estimated. Here we show that how much the program must still build is decided by which learner is attached, and is measurable on the programs themselves. Moving to Boolean domains, where a target's nonlinearity is exactly its Fourier degree, we tune that degree from one to six with everything else fixed. Conditioned on success, a linear learner forces the evolved program to the target's degree exactly, at one through six without exception over thirty runs per setting, while tree ensembles succeed with far simpler programs and four times as often. This gives the field two things: a learner can be chosen from a target's structure instead of its reputation for difficulty, and the degree of the evolved program is a diagnostic free to compute during any run. Our control target has lower degree than the parity problems yet gains nothing from a nonlinear learner, while targets reducible to a simple statistic gain a great deal. The latter comes with a warning: evolution internalises what the learner supplies in only four of sixty-three conditions, and grows more dependent on it in forty-four, so the more capable the learner, the less of the model is legible in the program.

Figures & tables

Figure 1: The two arrangements, with $\mathbf{x}$ an input, $y$ its target, $g$ the evolved program and $f$ the downstream learner. Only the second row is studied here. The learner is refitted for every candidate in every generation and its fitted parameters are discarded, so nothing it learns is inherited. Everything in the evolutionary loop is held fixed across conditions; only $f$ changes.

Figure 2: Order of nonlinearity of the benchmark targets. (a) The Fourier spectrum of each Boolean target. Parity puts its entire spectrum at one degree, which is what makes $k$ a dial; the multiplexer spreads its spectrum over degrees one to three. (b) The same quantity for the two continuous targets, read off the error curve of the best polynomial fit. Nguyen-11 is exact at degree two, but for Nguyen-8 the order is two at $\varepsilon=10^{-2}$ , eight at $\varepsilon=10^{-4}$ and undefined at $10^{-6}$ , so on a continuous domain the answer is partly a choice.

Figure 3: Illustration of Proposition 2 . The target $\mathrm{PAR}_{4}$ is plotted against the value of the evolved program; points are jittered so that coincident inputs are visible. An affine learner can only draw a straight line here. Left: a program of order $1$ , on which the affine learner is useless and a four-piece learner is exact. Right: a program of order $4$ , on which the affine learner is exact because the program has already done the work. The affine learner never changes the order of what reaches it; it only decides whether the order the program supplies is enough.

Target	Order	Linear	Tree	Forest	Boosting
$\mathrm{PAR}_{2}$	2	$-0.061$	1.000	1.000	1.000
$\mathrm{PAR}_{4}$	4	$-0.015$	1.000	1.000	1.000
$\mathrm{PAR}_{6}$	6	$-0.004$	1.000	1.000	1.000
$\mathrm{PAR}_{8}$	8	$-0.057$	0.948	0.948	0.948
$\mathrm{MUX}_{6}$	3	0.233	0.211	0.213	0.211

Table 1: Held out

R^{2}

when the order-

1

representation is supplied and only the downstream learner is fitted. The linear column is at chance for every order above one, which is Proposition 2 in numerical form.

Target	Order	Linear	Tree	Forest	Boosting	MLP
$\mathrm{PAR}_{2}$	2	0.377	0.849	1.000	0.994	1.000
$\mathrm{PAR}_{3}$	3	0.378	0.840	0.996	0.891	1.000
$\mathrm{PAR}_{4}$	4	0.383	0.630	0.712	0.227	0.995
$\mathrm{PAR}_{5}$	5	0.388	0.469	0.273	0.238	0.819
$\mathrm{PAR}_{6}$	6	0.390	0.369	0.112	0.221	0.716

Table 2: Held out accuracy of learners applied directly to the raw inputs, with no evolved representation, mean over ten splits. Chance is

0.5

Target	Ord	$n$	$p$	$n$	$n$	$n$	$p$	$n$	$p$	$n$	$p$
		GP		LR	Ridge	Tree		Forest		Boosting
$\mathrm{PAR}_{1}$	1	30	–	30	30	30	–	30	–	30	–
$\mathrm{PAR}_{2}$	2	30	–	30	30	30	–	30	–	30	–
$\mathrm{PAR}_{3}$	3	13	$8\!\times\!10^{-6}$	29	28	30	1.0	30	1.0	30	1.0
$\mathrm{PAR}_{4}$	4	2	0.0009	14	13	28	0.0001	30	$2\!\times\!10^{-6}$	28	0.0001
$\mathrm{PAR}_{5}$	5	0	0.005	8	7	24	$7\!\times\!10^{-5}$	25	$2\!\times\!10^{-5}$	21	0.002

Table 3: Number of runs out of thirty classifying every held out row correctly.

p

values are Fisher’s exact test against LaSER-LR, the GP column included. Dashes mark comparisons where both conditions are exact on all runs.

Figure 4: Reliability and generalisation against the order of nonlinearity of the target.

Target	Order	GP	LR	Ridge	Tree	Forest	Boosting	MLP
$\mathrm{PAR}_{1}$	1	1	1	1	1	1	3	1
$\mathrm{PAR}_{2}$	2	2	2	2	1	1	2	2
$\mathrm{PAR}_{3}$	3	0	3	3	2	2	3	3
$\mathrm{PAR}_{4}$	4	0	4	4	2	2	2	4
$\mathrm{PAR}_{5}$	5	0	5	5	2	3	3	4
$\mathrm{PAR}_{6}$	6	0	6	6	3	3	3	6

Table 4: Median order of nonlinearity of the evolved representation

g

, over successful runs. A dash means no run succeeded. The linear variants lie on the diagonal at every order without a single exception; the tree based learners hold at two or three.

Figure 5: (a) Order of nonlinearity of the evolved representation among successful runs; the grey band is the diagonal. (b) How often that representation is found.

Target	Method	Test MSE	Succ. %	Order of $g$	vs LaSER-LR
Nguyen-11	GP	0.00000	100	2
(order 2)	LaSER-LR	0.00000	100	2
	LaSER-Tree	0.00001	100	2	$p<10^{-8}$ , LR better
	LaSER-RF	0.00001	100	6	$p<10^{-8}$ , LR better
	LaSER-GB	0.00003	100	3	$p<10^{-8}$ , LR better
	LaSER-MLP	0.00003	100	2	$p<10^{-8}$ , LR better

Table 5: Continuous targets, thirty runs each.

p

values are Wilcoxon signed-rank tests against LaSER-LR on test MSE.

Figure 6: Innate (dashed) and learned (solid) accuracy of the best individual, mean over thirty runs; the shaded area is what lifetime learning contributes.

Figure 7: Accuracy contributed by lifetime learning, over generations.

Target	GP	LR	Ridge	Tree	Forest	Boosting	MLP
$\mathrm{PAR}_{1}$	100.0	3.3	0.0	26.7	26.7	0.0	0.0
$\mathrm{PAR}_{2}$	100.0	3.3	0.0	13.3	13.3	0.0	3.3
$\mathrm{PAR}_{3}$	43.3	6.7	0.0	10.0	13.3	0.0	3.3
$\mathrm{PAR}_{4}$	6.7	10.0	0.0	3.3	3.3	0.0	6.7
$\mathrm{PAR}_{5}$	0.0	0.0	0.0	0.0	0.0	0.0	0.0
$\mathrm{PAR}_{6}$	0.0	3.3	0.0	0.0	0.0	0.0	3.3

Table 6: Percentage of runs reaching perfect innateness, in which the evolved representation alone attains the target and the learner is redundant.

Figure 8: Continuous targets: canonical GP assimilates, every learner condition does not. $R^{2}$ floored at $-2$ for legibility.

Explore similar work

Apr 19, 2026cs.NE

Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity

Monotone Boolean functions are a structurally important class of Boolean functions, but their restricted form imposes strong limitations on achievable nonlinearity. In this paper, we investigate whether evolutionary computation can evolve monotone Boolean functions with high nonlinearity, both in the balanced and imbalanced settings. We consider three solution encodings: the standard truth table representation, a balanced truth table encoding that preserves Hamming weight, and a symbolic tree-based genetic programming representation. To guide the search toward monotone increasing functions, we introduce a non-monotonicity penalty and combine it with fitness functions targeting balancedness and nonlinearity. Experimental results are reported for dimensions from

n=5

n=14

. The results show that evolutionary search can discover monotone Boolean functions with nonlinearities clearly exceeding those of majority functions, and in several cases approaching the best currently known values for monotone functions. At the same time, the experiments reveal substantial differences between encodings: the balanced truth table encoding performs poorly for larger dimensions, while the standard truth table and genetic programming encodings remain competitive, with genetic programming becoming especially relevant in the largest tested dimensions.

Claude Carlet, Marko Čupić, Marko Ðurasevic +3

University of Paris 8, 2 rue de la liberté, 93526 Saint-Denis Cedex, France · University of Bergen, Bergen, Norway · Faculty of Electrical Engineering and Computing, University of Zagreb, Unska 3, Zagreb, Croatia +2

Monotonicity Genetic Algorithms Nonlinearity

Ask PDF

Jun 14, 2026cs.NE

Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound

O(n D^5)

for the expected number of fitness evaluations of CGP to construct a conjunction of

n

inputs using at most

D \geq n-1

binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to

O(n D^4)

. Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.

Duc-Cuong Dang, Roman Kalkreuth, Andre Opris

University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany

Genetic Algorithms Runtime

Ask PDF

May 21, 2026cs.NE

Guiding Multi-Objective Genetic Programming with Description Length Improves Symbolic Regression Solutions

Symbolic regression with genetic programming (GPSR) may suffer from overfitting and structural bloat, especially when noise is present. In this paper we evaluate description length (DL) and fractional Bayes factor (FBF) criteria as principled, data-efficient alternatives to heuristics for selecting compact expressions that generalise well. We implement DL using a Fisher-information-based parameter encoding and compare it to AIC and BIC across multiple datasets, including noisy synthetic benchmarks and real-world regression problems. We study three search/selection strategies: (i) multi-objective search for accuracy and program length followed by DL/FBF selection; (ii) multi-objective search using DL directly as an objective; and (iii) single-objective optimisation with DL/FBF as the fitness. Across datasets we find that DL/FBF post-selection improves test performance compared to AIC/BIC baseline and that BIC in combination with the same function complexity penalty from DL/FBF produces similar results. In contrast, using DL/FBF directly as a fitness function in single-objective GPSR frequently induces premature convergence to overly simple models. We conclude with practical guidance for using DL/FBF as robust model-selection tools in genetic programming workflows.

Gabriel Kronberger, Fabricio Olivetti de Franca, Deaglan J. Bartlett +2

Heuristic and Evolutionary Algorithms Laboratory University of Applied Sciences Upper Austria Softwarepark 11, 4232 Hagenberg, Austria · Center of Mathematics, Computing and Cognition Federal University of ABC Av. dos Estados 5001, Santo Andre, 09280-560, SP, Brazil · Astrophysics, University of Oxford Denys Wilkinson Building, Keble Road, Oxford, OX1 3RH, UK +1

Symbolic Regression Genetic Algorithms Model Selection Gaussian Process Pac-Bayesian Theory Rtk-Gnss

Ask PDF