cs.NENov 12, 2026

TSGP-2: On the Non-Linearity of Symbolic Regression Problems and How to Exploit It with Model-based Semantic Genetic Programming

Authors: Philipp Anthes, Alina Geiger, Martin Briesch, Franz Rothlauf

Organizations: Johannes Gutenberg University, Mainz, Germany

Abstract

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

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 7, 2026

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

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.
Jun 30, 2026

Evaluation of Population Initialization Methods for Genetic Programming-based Symbolic Regression

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.
Apr 19, 2026

On the Generalization Bounds of Symbolic Regression with Genetic Programming

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.