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

Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity
Apr 19, 2026Claude Carlet, Marko Čupić, Marko Ðurasevic +3Monotonicity Genetic Algorithms
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
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
Jun 14, 2026Duc-Cuong Dang, Roman Kalkreuth, Andre OprisGenetic Algorithms Runtime
University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany
Guiding Multi-Objective Genetic Programming with Description Length Improves Symbolic Regression Solutions
May 21, 2026Gabriel Kronberger, Fabricio Olivetti de Franca, Deaglan J. Bartlett +2Symbolic Regression Genetic Algorithms
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

Apr 19, 2026, cs.NEJ/K move · Enter open · S save

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

Claude Carlet, Marko Čupić, Marko Ðurasevic, Domagoj Jakobovic+2

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

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