Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 36 ยท Genetic Programming

Genetic Programming: Evolving Programs

Learn genetic programming (GP): evolve programs as expression trees. Build trees, evaluate them, apply subtree crossover and mutation, and run a tiny GP in Python.

A genetic algorithm evolves a list of numbers. Genetic programming (GP) evolves a program. Instead of asking "which parameters work best?", GP asks "which formula, rule or procedure works best?". The individuals are programs, represented as trees, and the fitness is how well each program does its job. John Koza made GP famous in the early 1990s; it has since produced circuit designs, trading rules, symbolic formulas that rediscover physical laws and many compact classifiers.

The big idea is that nearly everything from the rest of this course still applies: a population, fitness, selection, crossover, mutation. Only the representation and the operators change.

Programs as trees

A mathematical expression is naturally a tree. x * x + 3 looks like this:

flowchart TD
    P["+"] --> M["*"]
    P --> C["3"]
    M --> X1["x"]
    M --> X2["x"]

Internal nodes are functions (operators); leaves are terminals (variables and constants).

GP needs two sets, chosen by you:

  • The function set: the operations a program may use, for example +, -, *, / (and maybe sin, exp, if).
  • The terminal set: the inputs and constants, for example x and numbers like 1 and 2.

Together they define the search space: every tree you can build from them. A designer who picks poor sets makes the problem impossible, so choose sets that could plausibly contain the answer.

Closure: every tree must run

GP requires closure: any function must accept any value that any other function or terminal could produce. Division is the classic problem, because x / 0 crashes. The standard fix is protected division, which returns a safe value (often 1) when the divisor is near 0. Do the same for log and sqrt.

Representing trees in Python

The simplest representation is a nested tuple: ("+", ("*", "x", "x"), 3). A leaf is a string (variable) or a number (constant). Evaluating is a short recursive function, and by using NumPy arrays for x you evaluate the tree on all data points at once.

Python Build, evaluate and print expression trees

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.

Initializing the population

Koza's ramped half-and-half is the standard recipe. Half the trees are built with the full method (every branch reaches the maximum depth), half with the grow method (branches may stop early). The maximum depth is ramped, for example from 2 to 6, so the first population contains small and large trees of different shapes.

Genetic operators on trees

Subtree crossover

Pick a random node in each of two parents and swap the subtrees rooted there. Both children are always valid programs, whatever nodes were chosen. This is the main GP operator.

Subtree mutation

Pick a random node and replace its subtree with a freshly generated random tree. Variants include point mutation (change one node's function or constant, keeping the shape) and hoist mutation (replace the tree with one of its own subtrees, to shrink it).

Reproduction

Copy an individual unchanged, usually the best few (elitism).

Python Subtree crossover and mutation in action

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.

Run it a few times (the seed is fixed, so edit it) and you will see that children are always syntactically correct programs, with parts of both parents.

Fitness in GP

Fitness measures how well the program's output matches the target on a set of fitness cases: for symbolic regression, the mean squared error over data points; for a classifier, the error rate; for a game-playing agent, the score it earns. Because evaluating a tree on many cases is expensive, GP often evaluates on a small sample or uses vectorized operations.

Bloat

GP has a notorious problem: programs tend to grow bigger and bigger without getting better, filling up with useless branches (introns) such as (x - x) or (x * 1). This is called bloat. It slows evaluation and hurts generalization. Common remedies:

  • A depth limit (Koza used 17): reject children deeper than the limit.
  • Parsimony pressure: subtract a small penalty proportional to the program size from fitness.
  • Tournament on size: when two programs tie, prefer the smaller.

The next lesson builds a complete GP that uses depth limits and parsimony pressure.

The GP loop

  1. Create a population of random trees (ramped half-and-half).
  2. Evaluate fitness for each tree.
  3. Select parents (usually tournament selection).
  4. Apply crossover (about 90 percent), mutation (about 5 to 10 percent) and reproduction.
  5. Repeat until a good enough program appears or the generations run out.

This is identical to the GA loop you already know. That is the beauty of the idea.

Common mistakes

  • A function set without closure. One unprotected division can poison a whole run with inf and nan.
  • No size control. Without limits, trees explode to thousands of nodes in a few dozen generations.
  • Too small a terminal set. If the variable is missing from the terminals, no program can use it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In genetic programming, what is an individual?

    GP evolves programs, commonly as expression trees.
  2. 2. What is the closure property?

    Closure lets crossover swap any subtrees safely. Protected division is a typical way to get it.
  3. 3. What does subtree crossover do?

    Children are built from parts of both parents and are always valid programs.
  4. 4. Which of these helps against bloat?

    Both reduce the growth of useless code.

Summary

  • GP evolves programs; trees have functions inside and terminals at the leaves.
  • You choose the function set and the terminal set, and they must satisfy closure.
  • Ramped half-and-half initialization mixes shapes and depths.
  • Subtree crossover and mutation always produce valid programs.
  • Bloat is controlled with depth limits and parsimony pressure.

Next: Symbolic Regression with GP