Genetic Programming

Ordinary programming starts with a human who understands the problem, designs an algorithm, and writes code. Genetic programming flips that order: you describe what a good program looks like, and then let a population of candidate programs fight for survival — the fittest survive, reproduce, and gradually improve.

The idea was developed into a full method by John Koza in his 1992 book Genetic Programming. The key insight is to represent programs as expression trees — branching structures where inner nodes are operations ($+$, $-$, $\times$, $\div$, $\sin$, $\log$, …) and leaves are constants or input variables. A formula like $x^2 + 2x - 3$ becomes a tree with $+$ at the root, $\times$ and $x$ as children of the left branch, and so on.

Once programs are trees, Darwin's toolkit applies directly:

• Selection: prefer trees whose output fits the target data better (lower error = higher fitness).
• Crossover: swap a random subtree from one parent into another, mixing "genetic material."
• Mutation: replace a random subtree with a freshly generated one, adding new building blocks.

Over hundreds of generations a population of random trees converges on formulas that would have been hard to design by hand — and sometimes discovers ones that surprise even the researchers.

Genetic programming lives in the broader family of evolutionary computation, and it shares deep roots with the search problems studied in P vs NP: finding the best tree in a vast search space is, in general, intractable.

The demo below runs a miniature genetic programming loop in your browser. A small population of expression trees tries to match a hidden target curve. Each generation, the fittest trees are selected, crossed over, and mutated to produce the next population.

<!-- {{c_layout_comment}} -->
<div class="top-bar">
  <span class="label">{{lbl_best_formula}}</span>
  <span id="best-formula" class="formula">—</span>
</div>
<canvas id="chart" width="480" height="200"></canvas>
<div class="stats-row">
  <span>{{lbl_generation}} <strong id="gen-num">0</strong></span>
  <span>{{lbl_best_fitness}} <strong id="best-fit">0.000</strong></span>
  <span>{{lbl_pop_size}} <strong id="pop-sz">20</strong></span>
</div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_base_styles}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px 0; }
.top-bar { display: flex; align-items: baseline; gap: .4rem; margin-bottom: .4rem; flex-wrap: wrap; }
.label { font-size: .8rem; color: #555; white-space: nowrap; }
.formula { font: 600 .85rem ui-monospace, monospace; color: #1d3557; word-break: break-all; }
canvas { display: block; width: 100%; max-width: 480px; border: 1px solid #d0d7de; border-radius: 8px; }
.stats-row { display: flex; gap: 1.2rem; flex-wrap: wrap; margin: .5rem 0 .2rem; font-size: .85rem; color: #444; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Watch the best fitness climb toward 1.0 and the best formula printed at the top. You will rarely recover the exact target — but the evolved expression often gets surprisingly close. Notice how early generations are wild and noisy, then converge as good sub-trees spread through the population.

Genetic programming looks like magic, but the underlying search is genuinely hard:

• Exponential search space. With $n$ distinct symbols (operators + variables + constants), the number of expression trees of depth $d$ grows at least as fast as $n^{2^d - 1}$. For any non-trivial grammar and depth, exhaustive search is completely out of reach.
• No gradient. Unlike neural network training, there is no continuous loss surface to follow downhill. The space of trees is discrete, and small structural changes can completely alter a program's output.
• Bloat. Programs tend to grow across generations — useless subtrees ("introns") accumulate without hurting fitness, wasting computation and obscuring the meaningful parts. Controlling tree size is an active research challenge.
• No optimality guarantee. GP is a heuristic. It can get stuck in local optima, or never find the target even if it exists. A run that looks converged may be sitting on a fitness plateau far from the global best.
• Symbolic regression is PSPACE-hard. Even finding a program that exactly fits a finite dataset can be undecidable in general, and approximation guarantees are elusive.

Despite all this, GP routinely finds surprisingly good solutions on real problems — because evolution is an excellent explorer of structured search spaces, and real-world fitness landscapes are rarely random.

Genetic programming has produced genuine surprises across many domains:

• Symbolic regression: given a table of measurements, GP can discover the closed-form equation that generated the data — a task that has rediscovered physical laws from experimental data alone (see AI Feynman, 2019).
• Antenna design: NASA's 2006 ST5 satellite carried an antenna whose shape was evolved by a GP system — the first artificially evolved hardware deployed in space.
• Automated feature engineering: GP-based tools such as gplearn evolve transformations of raw features before feeding them to classifiers, often beating hand-crafted features.
• Trading strategies and scheduling: financial firms and logistics companies use GP to evolve rule sets that would be difficult to design manually.
• Drug discovery and chemistry: GP explores molecular formula space, evolving candidate structures that match desired binding or reaction properties.

The common thread: whenever the right form of the solution is unknown and the search space is too large for exhaustive exploration, genetic programming is a compelling option — and it produces interpretable symbolic expressions rather than black-box weights.

Genetic programming turns the act of writing code inside-out: instead of designing a solution, you design a competition, and let programs fight for survival until the fittest formula emerges. The approach has no guarantee of finding the best answer, and the search space it explores is astronomically large — but evolution is an astonishingly good navigator.

More than a practical tool, GP is a reminder that computation and biology share a deep logic. The same principles that shaped multicellular life can shape expressions trees: variation, selection, inheritance. And sometimes the programs that emerge — like Koza's rediscoveries of circuit designs and physical laws — are things no human programmer would have written.

If you want to explore further, follow the thread into evolutionary computation and the question of how hard search really is via P vs NP.