Introduction

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⁡\sin, log⁡\log, …) and leaves are constants or input variables. A formula like x2+2x−3x^2 + 2x - 3 becomes a tree with ++ at the root, ×\times and xx 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.

Evolve a Formula

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.

<!-- Top bar shows the best formula found so far -->
<div class="top-bar">
  <span class="label">Best formula:</span>
  <span id="best-formula" class="formula">—</span>
</div>
<canvas id="chart" width="480" height="200"></canvas>
<div class="stats-row">
  <span>Generation: <strong id="gen-num">0</strong></span>
  <span>Best fitness: <strong id="best-fit">0.000</strong></span>
  <span>Population: <strong id="pop-sz">20</strong></span>
</div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Base styles for the GP demo */
* { 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; }

/* Genetic Programming demo — evolves expression trees to fit a target curve */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Target function: 0.5*x^2 - x + 1 (a simple parabola) */
const TARGET_FN = x => 0.5 * x * x - x + 1;
const XS = Array.from({ length: 20 }, (_, i) => -2 + i * 0.2);
const YS = XS.map(TARGET_FN);

/* GP grammar: operators, variables, constants, and tree parameters */
const OPS = ['+', '-', '*'];
const VARS = ['x'];
const CONSTS = [0.5, 1, 2];
const MAX_DEPTH = 4;
const POP_SIZE = 20;
const GENERATIONS = 80;
const CROSSOVER_RATE = 0.8;
const MUTATION_RATE = 0.15;

/* Generate a random expression tree of given depth */
function randInt(n) { return Math.floor(Math.random() * n); }
function randEl(arr) { return arr[randInt(arr.length)]; }

function genTree(depth) {
  if (depth === 0 || (depth < MAX_DEPTH && Math.random() < 0.35)) {
    /* Leaf node: variable or constant */
    return Math.random() < 0.6 ? { t: 'var', v: 'x' } : { t: 'num', v: randEl(CONSTS) };
  }
  return { t: 'op', v: randEl(OPS), l: genTree(depth - 1), r: genTree(depth - 1) };
}

function evalTree(node, x) {
  if (node.t === 'var') return x;
  if (node.t === 'num') return node.v;
  const l = evalTree(node.l, x);
  const r = evalTree(node.r, x);
  if (node.v === '+') return l + r;
  if (node.v === '-') return l - r;
  /* Default operator is multiplication */
  return l * r;
}

function treeToStr(node) {
  if (node.t === 'var') return node.v;
  if (node.t === 'num') return String(node.v);
  return `(${treeToStr(node.l)} ${node.v} ${treeToStr(node.r)})`;
}

/* Fitness = 1/(1+SSE), ranges from 0 (terrible) to 1 (perfect) */
function fitness(tree) {
  let sse = 0;
  for (let i = 0; i < XS.length; i++) {
    const pred = evalTree(tree, XS[i]);
    if (!isFinite(pred)) return 0;
    sse += (pred - YS[i]) ** 2;
  }
  return 1 / (1 + sse);
}

/* Deep-clone a tree for safe mutation */
function cloneTree(node) {
  if (node.t !== 'op') return { ...node };
  return { t: 'op', v: node.v, l: cloneTree(node.l), r: cloneTree(node.r) };
}

/* Collect all nodes with their paths for crossover/mutation */
function collectNodes(node, path = []) {
  const result = [{ node, path }];
  if (node.t === 'op') {
    result.push(...collectNodes(node.l, [...path, 'l']));
    result.push(...collectNodes(node.r, [...path, 'r']));
  }
  return result;
}

function getAt(root, path) {
  let n = root;
  for (const d of path) n = n[d];
  return n;
}
function setAt(root, path, val) {
  if (path.length === 0) return val;
  const copy = cloneTree(root);
  let n = copy;
  for (let i = 0; i < path.length - 1; i++) n = n[path[i]];
  n[path[path.length - 1]] = val;
  return copy;
}

/* Crossover: replace a random subtree in a with a subtree from b */
function crossover(a, b) {
  const nodesA = collectNodes(a);
  const nodesB = collectNodes(b);
  const { path: pa } = randEl(nodesA);
  const { node: nb } = randEl(nodesB);
  return setAt(a, pa, cloneTree(nb));
}

/* Mutation: replace a random subtree with a freshly generated one */
function mutate(tree) {
  const nodes = collectNodes(tree);
  const { path } = randEl(nodes);
  return setAt(tree, path, genTree(2));
}

/* Tournament selection: pick the best of k random individuals */
function tournament(pop, fits, k = 3) {
  let best = randInt(pop.length);
  for (let i = 1; i < k; i++) {
    const c = randInt(pop.length);
    if (fits[c] > fits[best]) best = c;
  }
  return pop[best];
}

/* GP state */
let population = [];
let fits = [];
let generation = 0;
let bestTree = null;
let bestFit = 0;
let running = false;
let timer = null;

function initPop() {
  population = Array.from({ length: POP_SIZE }, () => genTree(MAX_DEPTH));
  fits = population.map(fitness);
  generation = 0;
  bestTree = null;
  bestFit = 0;
  updateBest();
}

function updateBest() {
  for (let i = 0; i < population.length; i++) {
    if (fits[i] > bestFit) { bestFit = fits[i]; bestTree = population[i]; }
  }
}

/* Run one generation: select, crossover, mutate */
function step() {
  const next = [];
  const nextFits = [];
  for (let i = 0; i < POP_SIZE; i++) {
    let child = cloneTree(tournament(population, fits));
    if (Math.random() < CROSSOVER_RATE) {
      const other = tournament(population, fits);
      child = crossover(child, other);
    }
    if (Math.random() < MUTATION_RATE) child = mutate(child);
    next.push(child);
    nextFits.push(fitness(child));
  }
  population = next;
  fits = nextFits;
  generation++;
  updateBest();
}

/* Draw the chart with target (blue) and best (red) curves */
const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');
const W = 480, H = 200;

function drawChart() {
  ctx.clearRect(0, 0, W, H);
  const xMin = -2, xMax = 2, yMin = -1, yMax = 4;
  const toX = x => ((x - xMin) / (xMax - xMin)) * (W - 40) + 20;
  const toY = y => H - 20 - ((y - yMin) / (yMax - yMin)) * (H - 40);

  /* Draw grid lines */
  ctx.strokeStyle = '#e0e0e0'; ctx.lineWidth = 1;
  for (let gx = xMin; gx <= xMax; gx++) {
    ctx.beginPath(); ctx.moveTo(toX(gx), 10); ctx.lineTo(toX(gx), H - 20); ctx.stroke();
  }
  ctx.beginPath(); ctx.moveTo(20, toY(0)); ctx.lineTo(W - 20, toY(0)); ctx.stroke();

  /* Draw the target curve in blue */
  ctx.strokeStyle = '#aac4dd'; ctx.lineWidth = 2;
  ctx.beginPath();
  XS.forEach((x, i) => { i === 0 ? ctx.moveTo(toX(x), toY(YS[i])) : ctx.lineTo(toX(x), toY(YS[i])); });
  ctx.stroke();

  /* Draw the best evolved curve in red */
  if (bestTree) {
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2;
    ctx.beginPath();
    let first = true;
    for (let xi = 0; xi <= 80; xi++) {
      const x = xMin + xi * (xMax - xMin) / 80;
      const y = evalTree(bestTree, x);
      if (!isFinite(y) || y < yMin - 5 || y > yMax + 5) { first = true; continue; }
      first ? ctx.moveTo(toX(x), toY(y)) : ctx.lineTo(toX(x), toY(y));
      first = false;
    }
    ctx.stroke();
  }
}

function updateUI() {
  document.getElementById('gen-num').textContent = generation;
  document.getElementById('best-fit').textContent = bestFit.toFixed(3);
  document.getElementById('pop-sz').textContent = POP_SIZE;
  document.getElementById('best-formula').textContent = bestTree ? treeToStr(bestTree) : '—';
  drawChart();

  const statusEl = document.getElementById('status');
  if (bestFit >= 0.98) {
    statusEl.textContent = i18nFmt('Converged at generation %gen% — great fit!', { gen: generation });
    statusEl.className = 'status ok';
    stopRun();
  } else if (generation >= GENERATIONS) {
    statusEl.textContent = i18nFmt('Stopped at generation %gen% — best fitness %fit%', { gen: generation, fit: bestFit.toFixed(3) });
    statusEl.className = 'status info';
    stopRun();
  } else if (generation > 0) {
    statusEl.textContent = i18nFmt('Generation %gen% — evolving...', { gen: generation });
    statusEl.className = 'status info';
  } else {
    statusEl.textContent = 'Press Run or Step to start evolving.';
    statusEl.className = 'status';
  }
}

function stopRun() {
  running = false;
  clearInterval(timer);
  document.getElementById('btn-run').textContent = 'Run';
  document.getElementById('btn-step').disabled = false;
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (generation < GENERATIONS && bestFit < 0.98) { step(); updateUI(); }
});

document.getElementById('btn-run').addEventListener('click', () => {
  if (running) {
    stopRun();
  } else {
    running = true;
    document.getElementById('btn-run').textContent = 'Pause';
    document.getElementById('btn-step').disabled = true;
    timer = setInterval(() => {
      if (generation < GENERATIONS && bestFit < 0.98) { step(); updateUI(); }
      else stopRun();
    }, 60);
  }
});

document.getElementById('btn-reset').addEventListener('click', () => {
  stopRun();
  initPop();
  updateUI();
});

initPop();
updateUI();
Result
Console

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.

The Real Complexity

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

  • Exponential search space. With nn distinct symbols (operators + variables + constants), the number of expression trees of depth dd grows at least as fast as n2d−1n^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/genetic-programming/Content licensed under CC BY-NC 4.0.