Model-based variation operators such as the one used in Transformer Semantic Genetic Programming (TSGP) are affected by possible biases of their training data. TSGP is trained, in particular, on programs generated by Genetic Programming (GP) runs on linear target functions, which leads to a bias toward linear offspring. This bias can hinder search performance on problems that require non-linear solutions. This work has two goals: first, it investigates the linearity of standard test problems such as the Feynman and real-world benchmark problems. While most of the structure of real-world problems can be well approximated by linear structures, the Feynman problems exhibit varying levels of non-linear structure. Thus, a proper variation operator of a search method should be able to create both types of programs, linear as well as non-linear ones. Motivated by this observation, we propose TSGP-2, which follows the functionality of TSGP but uses as training data programs from GP runs on both linear and non-linear target functions. As a result, the training data includes a lower share of programs that behave linearly (the share drops from 83% to 37%). With a higher share of non-linear structures, TSGP-2 outperforms TSGP on problems with non-linear structure, while performing similarly on linear problems. In addition, TSGP-2 is less biased toward linear offspring and is able to propose a higher number of meaningful non-linear offspring earlier during search, which coincides with better solutions. The findings underscore the importance of training data for a learned variation operator and emphasize that the biases of search operators should be aligned with the problems they are applied to.
Figures & tables
Figure 1. Each plot shows the output of an example function on standardized inputs together with the least-squares linear fit. λ is the adjusted R2 of that fit. Each column shows two examples of one syntactic class. Constant and linear functions always have λ=1 . Although the non-linear examples differ only in their constants, the example functions in the bottom row behave more linearly (higher λ ). As in the experiments, division and power are protected and return 1 for undefined results (Table 2 ).
Problem
Ground truth
d
n
λ
RNN2
RNN2−λ
Feynman equations
I_8_14
(x2−x1)2+(y2−y1)2
4
10,000
0.00
1.00
1.00
III_17_37
β(1+αcosθ)
3
10,000
0.13
1.00
0.87
I_50_26
x1(cosωt+αcos2ωt)
4
10,000
0.34
1.00
0.66
II_13_17
2I/(4πϵc2r)
4
10,000
0.47
1.00
0.53
II_2_42
κ(T2−T1)A/d
5
10,000
0.60
1.00
0.40
Table 1. The synthetic and real-world benchmark problems, ordered by their exploitable non-linearity RNN2−λ . d is the dimensionality and n the number of samples. λ and RNN2 are the held-out R2 of a linear model and of a neural network fitted to the target.
Figure 2. Share of linearity level among 100,000 sampled training programs of TSGP (left) and TSGP-2 (right).
Parameter
Value
Population size
100
Generations
100
Initialization
Ramped half-and-half, depth [2,5]
Selection
Tournament, size 5
Primitive set
{x1,…,xd,ERC,+,−,×,%,pow}
ERC
[−0.5,0.5] , step size 0.1
Table 2. Parameters of the searches. % and pow are protected operators, which return 1 for undefined results.
Problem
Standard GP (a)
TSGP (b)
TSGP-2 (c)
Feynman equations
I_8_14
0.774 (0.096)
a 0.696 (0.122)
a 0.633 (0.223)
III_17_37
0.578 (0.187)
0.500 (0.135)
0.488 (0.336)
I_50_26
0.803 (0.037)
0.793 (0.020)
0.792 (0.022)
II_13_17
0.543 (0.263)
a 0.470 (0.111)
a 0.484 (0.114)
II_2_42
0.622 (0.178)
a 0.402 (0.214)
a 0.326 (0.173)
Table 3. Median test RMSE of the solutions over 30 runs, with the interquartile range over the runs in parentheses. Lower is better and the best method per problem is bold. For each problem, superscripts indicate all other methods that are significantly worse (Mann-Whitney per problem and Wilcoxon signed-rank over the per-problem ranks; both are Holm-corrected). Problems are ordered as in Table 1 , from the highest exploitable non-linearity to the lowest.
Figure 3. Training error (top) and linearity λ (bottom) of the best program over the run, for the Feynman (left) and real-world problems (right); we show the median over runs and problems. Bands are bootstrap intervals over problems.
Figure 4. Percentage of offspring that belong to a linearity level over the number of generations. Results are for all offspring (solid) and selected offspring (dashed) and for Feynman (top) and real-world problems (bottom). If a dashed line is above the corresponding solid one, selection favors solutions of this linearity level. If it is below, selection disfavors it, indicating low fitness.
Figure 5. Change in linearity Δλ from parent to offspring, per linearity level of the parent and operator. Bars left of zero lower λ , bars right of zero raise it, and the shade indicates ∣Δλ∣ . The right panel shows the share of offspring with unchanged λ . All operators vary the same 40,000 parents from test pairs held out from the TSGP and TSGP-2 training data.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6. Training error of the best program over the run on each Feynman problem. Lines are medians over the 30 runs, bands the interquartile range.
Figure 7. Training error of the best program over the run on each real-world problem. Lines are medians over the 30 runs, bands the interquartile range.
Figure 8. Linearity λ of the best program over the run on each Feynman problem. Lines are medians over the 30 runs, bands the interquartile range.
Figure 9. Linearity λ of the best program over the run on each real-world problem. Lines are medians over the 30 runs, bands the interquartile range.
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.
Nam H. Le
Vermont Complexity Center University of Vermont Burlington, VT 05405
We analyze the effect of optimizing the initial population of genetic programming (GP) for symbolic regression (SR) on the accuracy and complexity of solutions. We compare three well-established random initialization methods as well as initialization with small optimized solutions from exhaustive symbolic regression (ESR) using a GP/SR implementation which is based on the multi-objective evolutionary algorithm NSGA-II. We compare the final Pareto fronts found with each initialization method on twelve synthetic problems of varying complexity and one real-world dataset. We find no significant differences in accuracy or model complexity among the initialization methods. The initial advantage of initialization with ESR disappears after only a few generations. Our results show that, given similar diversity in the initial population, the effect of the initialization method in GP-based symbolic regression on the final Pareto front is negligible.
Lukas Kammerer, Gabriel Kronberger, Deaglan J. Bartlett +3
Heuristic and Evolutionary Algorithms Laboratory, University of Applied Sciences Upper Austria, Hagenberg, Austria · Astrophysics, University of Oxford, Oxford, UK · Institute of Cosmology & Gravitation, University of Portsmouth, Portsmouth, UK
Symbolic regression (SR) with genetic programming (GP) aims to discover interpretable mathematical expressions directly from data. Despite its strong empirical success, the theoretical understanding of why GP-based SR generalizes beyond the training data remains limited. In this work, we provide a learning-theoretic analysis of SR models represented as expression trees. We derive a generalization bound for GP-style SR under constraints on tree size, depth, and learnable constants. Our result decomposes the generalization gap into two interpretable components: a structure-selection term, reflecting the combinatorial complexity of choosing an expression-tree structure, and a constant-fitting term, capturing the complexity of optimizing numerical constants within a fixed structure. This decomposition provides a theoretical perspective on several widely used practices in GP, including parsimony pressure, depth limits, numerically stable operators, and interval arithmetic. In particular, our analysis shows how structural restrictions reduce hypothesis-class growth while stability mechanisms control the sensitivity of predictions to parameter perturbations. By linking these practical design choices to explicit complexity terms in the generalization bound, our work offers a principled explanation for commonly observed empirical behaviors in GP-based SR and contributes towards a more rigorous understanding of its generalization properties.
Masahiro Nomura, Ryoki Hamano, Isao Ono
Institute of Science Tokyo, Yokohama, Japan · CyberAgent, Shibuya, Japan