Grammar-Guided Genetic Programming

In unconstrained GP, the search space is vast as there are many syntactically valid but irrelevant or meaningless programs. We can narrow this down by using a formal grammar to define the set of admissible programs:

$$\mathcal{P}=\{\text{programs derivable from grammar }G\}$$

Examples:

$$\begin{array}{r}⟨\text{expr}⟩\to ⟨\text{expr}⟩+⟨\text{expr}⟩|⟨\text{expr}⟩\cdot ⟨\text{expr}⟩|\times \left|1\right|\sin (⟨\text{expr}⟩)\end{array}$$

• $⟨\text{expr}⟩$ is non-terminal
• $x,1$ are terminals
• rules specify legal constructions

Basically, we start with $⟨\text{expr}⟩$, choose one of the right-hand side options, and replace the selected non-terminal. We then repeat this until only terminals remain. This means that first options create larger structures, while last options terminate expansion. Generation alternates between expansion and stopping.