Genetic Programming: Evolving Computer Programs

An analyst building a fraud-scoring rule for a UPI payments app has a labelled dataset: transaction amount, account age, time-since-last-transaction, and a 0/1 fraud flag. A neural network can fit this in minutes, but the bank's compliance team will not approve a black box for autoflagging accounts: they need a rule an auditor can read, like (amount / avg_monthly_spend) > 4 AND account_age < 30. Nobody knows this rule in advance; it has to be discovered from the data. A genetic algorithm cannot help directly, because a GA evolves a fixed-length vector of numbers; it needs someone to already have decided the formula's shape and leave only its coefficients open. What the analyst actually needs is a search over the space of expressions themselves: over which variables to combine, with which operators, in which order. That search, evolving the structure of a program and not just its parameters, is genetic programming (GP), introduced by John Koza in Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, 1992).

From parameter vectors to executable trees

Every evolutionary algorithm needs three things: a representation, a fitness function, and variation operators (selection, crossover, mutation) that act on that representation. A genetic algorithm's representation is a chromosome of fixed length (a bit string or a real-valued vector), so crossover is trivial: cut both parents at the same locus and splice. Genetic programming keeps that same evolutionary loop but changes the representation to something that can vary in size and shape: a syntax tree that is an executable program.

A GP tree is built from two sets fixed in advance by the designer:

• Function set F (internal nodes): operators with a defined arity, e.g. {+, -, *, /}, each taking two children.
• Terminal set T (leaf nodes): variables (x), constants, or zero-argument functions (a random-number generator, a sensor read).

Koza names two conditions these sets must jointly satisfy. Sufficiency: F and T together must be expressive enough to represent an actual solution: you cannot evolve a quadratic from a function set containing only addition. Closure: every function in F must accept, as any of its inputs, whatever type any other function or terminal in the set can produce, without crashing. This sounds abstract but has a concrete, famous consequence: ordinary division is not closed, because x/0 throws an exception, and an evolving population will sooner or later generate a subtree that evaluates its denominator to zero. Koza's fix, used in essentially every GP system since, is protected division: define / so that it returns a fixed value (commonly 1) whenever the denominator is zero, instead of raising an error. Closure is a GP-specific engineering concern with no GA analogue, because a GA's chromosome positions are just numbers; they cannot throw a runtime exception.

A tree is a program: to run it, evaluate it bottom-up (postorder): evaluate the children of a node, then apply the node's operator to their values. The tree (+ (* x x) 1), read in prefix (Polish) notation, computes x² + 1. Population members are initialised at random tree shapes and depths. Koza's recommended scheme, ramped half-and-half, mixes trees generated by two methods (full, where every branch is grown to the maximum depth, and grow, where branches can terminate early at any depth) across a range of depth limits, so the starting population is not structurally uniform.

The evolutionary loop

The loop itself is standard evolutionary computation, with two operators that are genuinely different because the representation is a tree rather than a string:

1. Evaluate. Run each program in the population on a set of fitness cases (input/output pairs it should reproduce) and score it: typically sum of squared error for a regression task, or number of test cases passed for a program-repair task.
2. Select. Build a mating pool biased toward low-error (high-fitness) individuals. Tournament selection is the GP-standard method: draw k individuals uniformly at random from the population, and the one with the best fitness among them wins a slot in the mating pool. Repeat until the pool is full.
3. Vary.
   • Subtree crossover: pick two parents from the mating pool, pick a random node in each (Koza biases this 90% toward internal/function nodes and 10% toward leaves, since swapping a lone terminal rarely changes much), and swap the two subtrees rooted there. This produces two children in one operation and, unlike GA crossover, the children can be a different size and shape than either parent.
   • Subtree mutation: pick a random node in one parent and replace the subtree rooted there with a freshly grown random subtree; this is how genuinely new material re-enters a converging population.
   • Point mutation: replace a single node's label with another of the same arity (e.g. + ↔ -, or terminal x ↔ a constant) without touching the tree's shape.
4. Replace the old population with the new one (often keeping the single best individual unchanged, a practice called elitism, since without it a perfect solution found by luck in one generation can be lost by the next) and repeat until a fitness threshold or generation budget is reached.

Worked example: evolving x² + 1 by hand

Target program (unknown to the algorithm): f(x) = x² + 1. Fitness cases: x = 0, 1, 2, 3, giving target outputs y = 1, 2, 5, 10. Function set F = {+, *}; terminal set T = {x, 1}. Fitness = sum of squared error (SSE) over the four cases; lower is better, and 0 is a perfect fit.

Generation 0, four random individuals, written in prefix notation:

A = (* x x)         >> values at x=0,1,2,3: 0, 1, 4, 9
B = (+ x 1)          >> values: 1, 2, 3, 4
C = (+ x x)          >> values: 0, 2, 4, 6
D = (* x 1)          >> values: 0, 1, 2, 3

SSE against target [1, 2, 5, 10]:

A: (1-0)² + (2-1)² + (5-4)² + (10-9)²  = 1+1+1+1  = 4
B: (1-1)² + (2-2)² + (5-3)² + (10-4)² = 0+0+4+36 = 40
C: (1-0)² + (2-2)² + (5-4)² + (10-6)² = 1+0+1+16 = 18
D: (1-0)² + (2-1)² + (5-2)² + (10-3)² = 1+1+9+49 = 60

Rank by fitness: A(4) is best, then C(18), then B(40), then D(60). Run two size-2 tournaments to fill the mating pool: draw {A, D} → A wins (4 < 60); draw {B, D} → B wins (40 < 60). Parents for crossover: A and B. Note that B is the second-worst individual in the population, selected only because it happened to be paired against the single worst one. This is normal tournament selection, not a mistake: it lets moderately-fit individuals through, which matters because a low-fitness tree can still carry a valuable sub-structure inside it, exactly what happens next.

Crossover point in A: the root (the entire subtree (* x x)). Crossover point in B: the left leaf, x. Swap the two selected subtrees:

Child 1 = B with its left leaf x replaced by A's donated subtree (* x x)
        = (+ (* x x) 1)                    >> values: 1, 2, 5, 10  → SSE = 0

Child 2 = A with its root subtree (* x x) replaced by B's donated leaf x
        = x                                 >> values: 0, 1, 2, 3  → SSE = 60

One crossover event, applied to the same pair of parents, produced an exact solution and, simultaneously, one of the worst individuals possible in this population. Child 1 folded A's correct x² structure into B's +1 shell and landed exactly on the target; Child 2 lost that structure entirely and degenerated to the bare terminal x (structurally identical to D, and indeed scores the same SSE, 60, as an independent check that the arithmetic is consistent). This is the mechanism the diagram below traces.

The claim can be checked by running it rather than trusting the hand arithmetic:

def evaluate(node, x):
    if node == 'x':
        return x
    if isinstance(node, (int, float)):
        return node
    op, left, right = node
    l, r = evaluate(left, x), evaluate(right, x)
    if op == '+': return l + r
    if op == '-': return l - r
    if op == '*': return l * r
    if op == '/': return l / r if r != 0 else 1   # protected division

target = {0: 1, 1: 2, 2: 5, 3: 10}

population = {
    'A':       ('*', 'x', 'x'),
    'B':       ('+', 'x', 1),
    'C':       ('+', 'x', 'x'),
    'D':       ('*', 'x', 1),
    'Child1':  ('+', ('*', 'x', 'x'), 1),
    'Child2':  'x',
}

for name, tree in population.items():
    sse = sum((evaluate(tree, xv) - y) ** 2 for xv, y in target.items())
    print(name, sse)

# Output:
# A 4
# B 40
# C 18
# D 60
# Child1 0
# Child2 60

The printed values match the hand-derived SSEs exactly, including the coincidence that Child 2 and D, structurally the same one-node tree x, score identically.

The mechanism, diagrammed

Misconception check: "GP is just a GA that happens to hold code"

Because the name shares the word "genetic," students commonly assume genetic programming is a genetic algorithm with the chromosome relabelled as source code: same fixed-length encoding, same single-point crossover, just interpreted differently at the end. That is wrong in a way that matters for both correctness and exam answers. A GA chromosome has a fixed number of loci fixed before the run starts; GP individuals vary in size and shape across the entire run, and the population's average tree size typically grows generation over generation (a phenomenon called bloat: trees accumulate inert sub-structure, or "introns," that computes something and then gets discarded, e.g. (* x (- 1 1)) multiplied by zero and added to nothing, contributing zero to fitness while still costing evaluation time and memory). GA crossover cuts both parents at the same locus by definition, because the loci mean the same thing in every individual; GP crossover picks an independent random node in each parent, because there is no shared coordinate system between two trees of different shapes; the worked example's crossover points (A's root, B's left leaf) were chosen independently and needed no correspondence between them. And GP's function set carries the closure requirement (protected division, type-safe combination) that a GA's numeric loci never need, because a GA chromosome cannot throw a runtime exception the way an evolved expression tree can. Two practical mitigations for bloat that follow directly from this difference: parsimony pressure, which adds a penalty proportional to tree size into the fitness function so equally-fit smaller programs are preferred, and a hard maximum-depth limit enforced at every crossover and mutation, rejecting or truncating any offspring that would exceed it.

Real evolved programs, not just formulas

Koza's own demonstrations in the 1992 book were symbolic-regression tasks much like the worked example, scaled up: GP rediscovering known mathematical and physical relationships (Kepler's third law among them) purely from numeric data, without being told the functional form in advance. The chapter title's phrase "evolving computer programs" is literal in a more recent and directly relevant research line: automatic program repair. Le Goues, Nguyen, Forrest, and Weimer's GenProg (IEEE Transactions on Software Engineering, 2012) applies genetic-programming search directly to a real program's abstract syntax tree: candidate patches are generated by inserting, deleting, or swapping statement-level AST subtrees copied from elsewhere in the same codebase, each candidate's fitness is scored by how many of the program's existing test cases it passes (weighted toward not breaking tests that already passed), and the population is evolved with tournament selection and crossover/mutation over these AST edits until a variant that fixes the failing test while preserving the passing ones emerges. The representation, the fitness-by-execution, and the subtree-level variation operators are exactly the GP mechanism traced above, applied to real C source files instead of a four-point regression problem.

Active recall

Attempt each question before reading its answer.

1. Why must the function set be closed, and what would happen during the run in the worked example if / (ordinary division) were added to F without protection?
2. In the worked example, suppose the crossover point chosen in Parent A had been the leaf x (not the root) while the point in Parent B stayed the left leaf x. Write out both offspring and their SSE.
3. If instead of tournament selection the algorithm used pure fitness-proportionate (roulette-wheel) selection on this population, would D = (* x 1) ever be selected as a parent? Why does this matter for maintaining diversity?
4. The target function changes to f(x) = x² + 2, with the same fitness cases x = 0,1,2,3. Recompute the target outputs, then recompute the SSE of every individual from the worked example (A, B, C, D, Child 1, Child 2) against this new target. Which individual is now fittest?
5. What is bloat, and name one operator-level and one fitness-level mitigation.

Answers

1. Closure requires every function to accept, without error, any value any other function or terminal in the set can produce. Plain division violates this because a subtree can evaluate its right operand to 0, and in a population being mutated and recombined at random, some individual eventually will (e.g. (/ x (- x x)) divides by x - x = 0 for every x). Without protection, that individual crashes fitness evaluation instead of returning a (bad) number; the standard fix is protected division, returning a fixed value such as 1 when the denominator is 0, so the tree still evaluates and simply scores poorly rather than halting the run.

2. Parent A = (* x x), crossover point now the left leaf x (donated subtree = the terminal x). Parent B unchanged, crossover point still its left leaf x. Child 1 = B with its left leaf replaced by A's donated leaf x → (+ x 1), which is exactly Parent B's own shape (a leaf swapped for an identical-looking leaf) → SSE = 40, same as B. Child 2 = A with its left leaf replaced by B's donated leaf x → (* x x), exactly Parent A's own shape → SSE = 4, same as A. When both crossover points are single terminals of the same "kind," subtree crossover degenerates to swapping a leaf for a lookalike leaf and both children are copies of their parents, a reminder that leaf-leaf crossover (the 10% case in Koza's bias) is usually unproductive, which is exactly why real GP implementations bias crossover-point selection toward internal nodes.

3. Yes: roulette-wheel selection gives every individual a selection probability proportional to its fitness, so as long as D's fitness is nonzero (it is: SSE = 60 is finite, not zero fitness under a suitably transformed fitness measure such as 1/(1+SSE)), it retains some nonzero chance of selection every generation, just a small one. This matters because D, despite being the worst individual here, is still a legitimate carrier of genetic material. The misconception-check section and question 2 both show that fitness of a whole individual is a poor predictor of the value of a specific subtree inside it; keeping low-fitness individuals in the mating pool with reduced-but-nonzero probability keeps rare useful subtrees available for future crossover rather than deleting them outright, which is the core rationale for probabilistic (rather than strictly elitist) selection.

4. New target values: x²+2 at x=0,1,2,3 → y = 2, 3, 6, 11. Recomputing SSE for every individual against this new target (tree outputs are unchanged from before; only the target column shifted by a constant +1 at every point):

A = x²:            0,1,4,9   vs 2,3,6,11 → 4+4+4+4   = 16
B = x+1:           1,2,3,4   vs 2,3,6,11 → 1+1+9+49  = 60
C = 2x:             0,2,4,6   vs 2,3,6,11 → 4+1+4+25  = 34
D = x:              0,1,2,3   vs 2,3,6,11 → 4+4+16+64 = 88
Child1 = x²+1:      1,2,5,10  vs 2,3,6,11 → 1+1+1+1   = 4
Child2 = x:         0,1,2,3   vs 2,3,6,11 → 4+4+16+64 = 88

5. Bloat is the tendency of GP trees to grow larger across generations without a matching gain in fitness, driven by accumulating inert sub-structure ("introns," e.g. a subtree multiplied by zero) that crossover cannot easily remove because deleting it risks also deleting nearby useful code. Operator-level mitigation: enforce a maximum tree depth or node count, rejecting or truncating any offspring produced by crossover or mutation that would exceed it. Fitness-level mitigation: parsimony pressure, which adds a term proportional to tree size into the fitness function (effectively a penalty for length), so that among equally accurate programs, evolution prefers the smaller one.

Think About It

Think about this: How would you explain genetic programming: evolving computer programs to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind genetic programming: evolving computer programs, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.