Evolutionary Programming Representations

In tree-based GP, programs are expression trees: internal nodes are operators and leaves are terminals. In untyped GP, any subtree can replace any other — the only constraint is arity. In typed GP, every node has a return type and typed argument slots, so crossover and mutation must preserve type correctness. Typed GP admits richer function sets (conditionals, loops, predicates) but constrains which operator applications are legal.

Click any node to select it. In typed mode, compatible crossover targets light up with a green ring; incompatible nodes dim. Use ✦ Suggest Nodes to auto-pick a valid pair.

Type System

Genetic Operator

Preset Expressions Selecting a preset loads it into A — current A slides into B

Parent A

—

Parent B

—

Num — arithmetic ops, x, y, 1, 2

Bool — comparisons, and/or, T, F

Control — if, while (Bool,Num)→Num

Green ring = compatible target · Dimmed = incompatible type

Node Palette — select a node, then click below to replace it

Controls

Status

—

Offspring

Offspring 1

Apply an operator above to see offspring

Offspring 2

—

In linear genetic programming, programs are sequences of instructions for a register machine. Many instruction formats are possible — a common choice for illustration is Rd = Ra op Rb, used here. A backward dataflow analysis starting from the output register (R0) identifies which instructions actually contribute to the result — these are effective instructions. The rest are structural introns: they execute but their results are overwritten before ever reaching R0. Introns act as a buffer — crossover landing in intron code produces a behaviorally neutral offspring.

R0 = output · R1–R3 = working registers · x and y = read-only registers (inputs)
Click a row to place a cut point after it (orange line). Click again to remove it.

Preset Programs

Parent Tape A

Parent Tape B

Crossover Mode

Controls

Status

—

Offspring Tapes

Offspring 1

Apply an operator to see offspring

Offspring 2

—

Evolutionary Programming (Fogel, 1962) traditionally evolves finite-state machines for sequence prediction tasks. Unlike GP, an FSM's behavior only becomes legible by watching it consume input symbols — the meaning is distributed across the transition function, not readable from structure alone. EP uses mutation only (no crossover): operators structurally modify the FSM one step at a time.

Gold border = initial state · Double ring = output 1 · Orange fill = current state during execution · Each state outputs its label (0 or 1) when visited.

Preset FSMs

FSM Graph

Mutation Operators

Mutation history appears here…

Execute on Input Sequence

Input

Output

These three paradigms use fundamentally different program representations — not merely syntactic variants. The representation shapes which operators are natural, what problem domains fit, and what evolutionary dynamics emerge. Use the tabs above to explore each representation interactively; use this table as a reference when comparing them.

Representation Properties

Property	🌳 Tree GP	📼 Linear GP	🔄 EP / FSM
Program structure	Hierarchical expression tree	Flat instruction sequence	Directed labeled graph
Closure / validity	Automatic — any well-typed tree is a valid program	Automatic — any instruction sequence is executable	Automatic — any complete transition function is valid
Primary operator	Subtree crossover	Segment crossover (1-pt, 2-pt)	Mutation only — no crossover
Introns / neutral variation	Semantic introns via non-executed branches (requires control flow nodes)	Structural introns via overwritten registers — explicit, analyzable via backward dataflow	No direct analogue; neutral mutations via output-preserving state changes
Bloat tendency	High — subtree crossover biased toward larger trees	Moderate — tape grows via non-homologous crossover; introns buffer effective code	Controlled via explicit add/remove state operators
Reading the program	Human-readable as an expression or parse tree	Readable instruction-by-instruction; behavior requires execution to verify	Structure visible in graph; behavior only apparent by running on input sequences
Natural problem domain	Symbolic regression, classification, program synthesis	Symbolic regression, embedded / real-time systems	Sequence prediction, automata learning, control policies
Variable-length programs	Yes — tree depth unbounded; bloat control needed	Yes — tape length varies; length bias depends on crossover mode	Yes — number of states varies via add/remove operators
Type safety	Optional — untyped GP allows any subtree swap; typed GP enforces argument types	Not applicable — all registers hold the same type	Not applicable — transitions are symbol-indexed, not typed
Crossover analogue	Subtree swap between two parent trees	Segment swap between two parent tapes	None — EP is mutation-only by design
Key historical reference	Koza (1992)	Brameier & Banzhaf (2007)	Fogel, Owens & Walsh (1966)