Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 36 ยท Genetic Programming

Symbolic Regression with Genetic Programming

Discover a formula from data with genetic programming. Build a full symbolic regression GP with tournament selection, depth limits and parsimony pressure in Python.

Ordinary regression fits the numbers in a formula you picked in advance: y = a*x + b. Symbolic regression also searches for the formula itself. You give it data, and it returns an expression such as x*x + x - 3 that explains the data. Because the output is a readable formula, it is popular in science, where people want a law, not just a prediction. It is the classic application of genetic programming.

In this lesson you build a complete symbolic regression GP, in about 90 lines, and use it to rediscover a hidden formula.

The setup

  • Data: 40 points sampled from a secret function, y = x^3 - 2x + 1, on x in [-2, 2].
  • Functions: +, -, *, protected /.
  • Terminals: x and small integer constants.
  • Fitness: mean squared error (lower is better), plus a parsimony penalty 0.001 * size.
  • Selection: tournament of size 5.
  • Variation: subtree crossover (85 percent), subtree mutation (15 percent), a depth limit of 8 and elitism.
flowchart LR
    D["Data (x, y)"] --> F["Evaluate each tree: MSE + size penalty"]
    P["Population of trees"] --> F
    F --> T["Tournament selection"]
    T --> V["Subtree crossover / mutation"]
    V --> L{"Depth limit OK?"}
    L -- yes --> N["New population + elite"]
    L -- no --> K["Keep parent instead"]
    N --> F

Children deeper than the limit are replaced by one of their parents, which stops runaway growth.

Python A complete symbolic regression GP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The run is seeded, so you get the same result each time. With the seed above, the final program reaches an MSE of essentially zero, but it is a bloated, algebraically tangled version of x^3 - 2x + 1 (it contains pieces such as x / x). Change the seed or the data and compare: some seeds give a compact formula, others a close but messier one. That is normal: run GP several times and keep the best.

Reading the output

  • The MSE falls fast in the first generations (finding a cubic-like shape) and then slowly as constants and structure are polished.
  • The size column shows parsimony pressure at work. Without the penalty, programs would keep growing as the error shrinks.
  • The printed program often contains redundant pieces such as (x - x). You can simplify it afterwards with algebra (for example with SymPy, offline) because the evolved tree is just an expression.

Ephemeral random constants

Real constants such as 3.14 cannot come from a tiny set like {1, 2, 3} unless the program builds them by arithmetic. GP therefore usually includes ephemeral random constants (ERCs): a terminal that draws a random number when the tree is created and keeps it fixed from then on. Mutation can later nudge these numbers, and many modern systems add a numeric optimizer (such as least squares) to tune constants inside each tree.

Generalization: do not memorize the data

A flexible formula can fit noise. To avoid fooling yourself:

  • Hold out a validation set of points the GP never trains on and report the error there.
  • Prefer small formulas: the parsimony penalty helps.
  • Compare against simple baselines such as a polynomial fit of the same size.
Python Overfitting check: train on noisy data, test on clean data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same lesson applies to GP trees: size is capacity, and capacity beyond what the data supports hurts. That is the reason for parsimony pressure.

Beyond regression

Symbolic regression is one use of GP. Others include evolving classifiers (a tree that outputs "yes" or "no"), control programs (a robot controller as an expression), feature construction (new input features for another model) and hyper-heuristics (programs that decide which heuristic to run). Libraries such as gplearn, DEAP and PySR package the ideas here, with faster evaluation and richer function sets.

Common mistakes

  • Fitting without a validation set. A low training error says nothing about the truth.
  • Penalty too large. The population collapses to a constant or to x. Start with a tiny penalty.
  • Population too small. Symbolic search is hard; use hundreds or thousands of individuals.
  • Trusting a single run. Repeat with different seeds.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does symbolic regression search for that ordinary regression does not?

    Ordinary regression only fits coefficients of a chosen form.
  2. 2. What is parsimony pressure?

    It discourages bloat by making large programs pay a cost.
  3. 3. Why is a validation set important in symbolic regression?

    Training error alone cannot reveal overfitting.
  4. 4. What is an ephemeral random constant?

    ERCs give GP a supply of real-valued constants.

Summary

  • Symbolic regression evolves a formula that fits data; GP trees are the individuals.
  • Fitness combines error with a size penalty; depth limits control bloat.
  • Tournament selection, subtree crossover and mutation drive the search.
  • Ephemeral constants and constant tuning supply real numbers.
  • Always validate on unseen data and run several seeds.

Next: Tuning GA Parameters