Genetic Programming, Live
Genetic programming evolves programs. What gets bred is the program itself rather than the settings of a program: a working formula nobody wrote, assembled out of worse ones. I've published with this one: the belt-laying search in the Factorio post is a genetic programming system, and it came out ahead of both other methods in the paper.
This is part eight of the series. So far:
- ants have foraged
- triangles have evolved
- a search has cooled its way out of bad valleys
- a swarm has chased its own best guess
- a stuck search has widened its neighbourhood until it came unstuck
- a cloud of samples has learned the shape of a valley
- a population has built its moves out of its own spread
In part two every individual was a fixed-length list of numbers: fifty triangles, ten genes each, five hundred dials for evolution to twiddle. The shape of that genome was decided by me, in advance, forever. Genetic programming throws that away. The genome is a tree of code, and the size and shape of the tree are up for grabs too. Evolution gets the structure as well as the settings.
Quick jargon guide
- Genetic programming (GP): an evolutionary algorithm whose individuals are programs (here, mathematical expressions) rather than fixed-length strings of parameters. Selection, crossover, and mutation operate on the program's tree.
- Expression tree: a program written as a tree, with operators at the branches and variables or constants at the leaves. sin(x)*(x+1.7) is a seven-node tree.
- Symbolic regression: searching for a formula that fits data, where the formula itself is the unknown, not just the coefficients of a formula you chose in advance.
- Crossover: in GP, snipping a random subtree out of one parent and grafting in a random subtree from another. Children can be bigger than both parents or smaller than either.
- Bloat: trees growing larger generation after generation without getting any fitter - famous disease of GP.
- Parsimony pressure: a fitness penalty per node, taxing big trees. The standard treatment for bloat.
- Intron: code that has no effect on a program's output, like a subtree multiplied by zero. Bloat is mostly introns.
An infinite haystack
The demo below does symbolic regression. I sample forty points from a hidden target curve, and the population's job is to find an expression that fits them. Individuals are trees built from plus, minus, times, a protected divide (dividing by nearly zero returns 1 instead of exploding), sine, cosine, the variable x, and random constants.
Fitness is mean squared error over the sample points with the lower the better. A formula that outputs infinity or NaN anywhere gets a score so bad it amounts to a death sentence.
Part two's genome was a box with five hundred dials: finite and fixed. The space of all expressions is infinite, and almost all of it is garbage. A random tree comes out like cos(x/x)*0.3-x. There's no gradient to follow and no obvious notion of "nearby".
And yet a population of these things, bred and culled, finds working programs in seconds - which is kinda crazy.
Trading subtrees
The engine is the one you already know from part two: tournament selection, crossover, mutation, and a couple of elites carried into each new generation untouched. What changes is what crossover means. With trees, crossover picks a random subtree in each parent and swaps them. It works because subtrees are meaningful units in a way that random substrings of characters never are: sin(2*x) is a working component. Evolution here is trading parts, not shuffling letters.
The starting population is grown "ramped half-and-half", a mix of bushy full trees and scraggly random ones at several depths (GP-speak for seeding the pool with variety). I also cap tree depth at eight, partly for your device's sake and partly because, as you'll see, GP will take every inch you give it.
Watch a program grow
Below, a population of formulas is evolving against the data. The dots are the samples from the hidden curve, and the green line is the best formula so far, redrawn each generation so you can watch it snap toward the data.
The node diagram is that formula's actual code: blue nodes are operators, amber leaves are x and constants. The readout underneath prints it as maths you can read. Generations tick by a few per second so the motion stays watchable.
Best error is the mean squared distance between the green curve and the dots, and the left chart plots it on a log scale, so every gridline down is ten times better. Avg size is the mean node count across the whole population: the bloat detector, and the right chart is where you watch it take off. Switching target restarts the run, because a new curve is a new fitness landscape. Expect long flat stretches in the error and then sudden cliffs, which is crossover assembling the right subtree at last.
The parsimony tax
Set parsimony to zero. Keep one eye on the average size chart. Error improves, then plateaus, while average size climbs and keeps climbing until it slams into the depth cap.
The population is now hauling around programs of a hundred-plus nodes that fit the data no better than a fifteen-node formula from fifty generations ago. This is bloat, the most famous disease of genetic programming and the reason the parsimony slider exists. Why a population would choose to bloat gets its own section below.
Now slam parsimony to maximum. The opposite catastrophe --- every node now costs more fitness than accuracy is worth, so the population collapses to tiny, dumb expressions: a bare constant, a lonely x. They fit the data terribly, but cheaply. Parsimony is a tax, and like any tax, set it too high and nobody builds anything.
Shrink the population to twenty. The run crawls or stalls. With so few trees, the pool of subtrees for crossover to trade is tiny, and once the population homogenises, mutation has to invent every new part from scratch.
And drop mutation to zero while you're at it. Same lesson as part two, sharper here: crossover can only recombine subtrees that already exist somewhere in the population. Once the interesting ones are gone, they are gone.
Bloat is evolved defensive code
Subtree crossover is destructive: graft a random subtree into a random point of a working program and you'll usually break it.
Imagine two parents of equal fitness, one lean, one padded with introns: code that computes something and then multiplies it by zero, or adds a quantity and subtracts it again. When crossover hits the padded parent, odds are it lands in the padding, and the child behaves just like its parent. When it hits the lean one, it hits something that mattered.
Padded parents therefore produce more viable children. Padding spreads. Average size marches upward while fitness stands perfectly still.
The population is evolving resistance to its own genetic operators. No line of my code rewards defensive padding: it falls out of selection pressure, the same way real genomes are stuffed with non-coding DNA and real codebases accrete dead branches nobody dares delete (you don't want to see some of the folders I don't sync to GitHub here locally...).
The trees are, in effect, growing bubble wrap to survive crossover.
Where GP turns up in practice
Symbolic regression is the flagship application and it earns its keep in science. Fit a neural network to experimental data and you get a black box that interpolates. Fit an expression tree and you get an equation a human can read and argue with.
GP-based systems have rediscovered conservation laws from raw motion-capture data, and they get used to propose compact models in physics, materials science and ecology. When you want insight rather than raw predictive power, a ten-node formula beats a million-weight network, contrary to what many machine learning specialists would say.
NASA's ST5 mission needed a small satellite antenna with an awkward radiation pattern, and an evolutionary algorithm designed one[3]. The result looks like a bent paperclip. No engineer would have drawn it, and it outperformed the conventionally designed alternative.
It flew in 2006. There is evolved hardware in space!
John Koza launched the field with his 1992 book[1] and then spent years compiling "human-competitive" results: GP runs that reinvented patented circuits and produced patentable designs of their own.
Every one of them lived in a domain with a fast, automatic, well-behaved fitness function. GP never became a general way to write software, and the field guide I recommend below[2] is refreshingly frank about why. Where a score is cheap to compute and means what you want, GP is a live option. Everywhere else, the fitness function is the really hard part.
Structure is a freedom
Part two's lesson was that the fitness function is where the meaning lives: change what you reward and you change what evolves. Give evolution control over structure as well and it will use that control in every way that pays.
It builds the subtree that fits your curve. It also builds padding to shield that subtree from your own crossover operator, and for the same reason: both help its children survive.
Zero the parsimony and watch the trees fatten in real time, then tax them back down to stumps. Sit through thirty flat generations of the error chart until it falls off a cliff, because two mediocre parents happened to be holding complementary halves of the answer.
An infinite search space, almost all of it garbage, explored by trading parts and taxing waste. It should not work anything like as well as it does.
Common questions
Is this how AI coding assistants work?
No. A modern code assistant is a large language model: it learned from an enormous corpus of human-written code and generates likely text, so it turns up to every problem with a vast prior about what programs should look like. GP turns up knowing nothing. It has never seen a maths textbook. It has a score, and it searches blind. That makes it wasteful (it rediscovers wheels constantly) and also unprejudiced: it can find designs no human would write, like that antenna. Researchers have begun combining the two, with a language model proposing programs and an evolutionary loop scoring and selecting them.
References
- Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press. ISBN 978-0262111706.
- Poli, R., Langdon, W. B., & McPhee, N. F. (2008). A Field Guide to Genetic Programming. Freely available at http://www.gp-field-guide.org.uk
- Lohn, J. D., Hornby, G. S., & Linden, D. S. (2005). An evolved antenna for deployment on NASA's Space Technology 5 mission. In Genetic Programming Theory and Practice II (pp. 301–315). Springer.