Syntax Tree GP Programs

A syntax tree has functions as internal nodes and terminals as leaves. The evaluation proceeds bottom-up. This representation makes program structure explicit and easy to manipulate.

For example, for the expression $f(x,y)=x+2y$:

Symbolic expressions can be defined by two fundamental sets.

The function set $F$ is the internal computational operators. For example:

$$F=\{+,-,\times ,÷,\sin ,\cos \}$$

The terminal set $T$ is the leaves of the tree:

$$T=\{x,y,\text{constants}\}$$

All candidate programs are compositions built from $F\cup T$. The design of $F$ and $T$ strongly influences search effectiveness.

We enforce a closure requirement: every function must accept any input produced by the tree. However, random trees may generate invalid expressions, like division by zero. To deal with this, we introduce protected operators. For example:

$${÷}_p(a,b)=\{\begin{array}{ll}a/b,& \left|b\right|>ϵ\\ a,& \left|b\right|\le ϵ\end{array}$$

This ensures that output is always defined, and makes division closed over all inputs.

In the context of GP, a single individual can be written in several equivalent forms:

Each form is useful. Trees are good for visualization, prefix are good for implementation (Lisp?), and infix is good for human interpretation.

Each function in $T$ has a fixed number of children called its arity.

$$\text{arity}(+)=2,\text{arity}(\sin )=1,\text{arity}(\text{ifgt})=4$$

where $\text{ifgt}$ implements “if $a>b$, return $c$, else $d$”:

Arity determines the legal tree structure. If the function set contains mostly binary operators, subtree crossover can be disruptive, and size will grow quickly with depth. Thus, the choice of functions shapes both representation and search behavior.

With the above components, we can formally define a GP individual to be modeled as a rooted ordered tree:

$$T=(V,E,r)$$

where $V$ is the set of nodes, $E$ is the set of edges, and $r$ is the root node.

We partition the node set as:

$$V=V_F\cup V_T$$

where $V_F$ are function nodes and $V_T$ are terminal nodes. This formal view helps when reasoning about tree size and depth.

Strongly Typed Representation

Standard GP allows any subtree as long as closure holds. In strongly typed GP, nodes carry data types. For example:

• Arithmetic nodes return real values
• Logical nodes return Boolean values
• Conditional nodes combine both.

This prevents nonsensical constructions such as $\sin (\text{True})$. Typing constrains the search space but often involves semantic quality.

Automatically Defined Functions

GP can evolve reusable subprograms. Instead of a single tree, an individual may contain a main program, along with one or more auxiliary functions

Conceptually, we say:

$$\text{program}=\text{main tree}+\text{callable subtrees}$$

This promotes modularity and encourages code reuse. Repeated structure is represented more compactly.

Tree Execution

Tree execution is recursive. For $f(x,y)=x+2y$, the evaluation order is:

1. Read terminal $x$
2. Read terminal $y$
3. Compute $2y$
4. Compute $x+2y$

We can consider this more cleanly by writing it in prefix form:

$$(+x(\ast y2))$$

Let $x=3$ and $y=5$. Then:

$$(\ast y2)=5\cdot 2=10$$

and finally

$$(+x10)=3+10=13$$

Search Space

GP search spaces are huge; even shallow trees produce enormous search spaces. To see this, let $\left|F\right|=m$ and $\left|T\right|=k$. For a rough binary-tree estimate, the number of syntactic probabilities grows on the order of

$$(\left|F\right|+\left|T\right|{)}^{2d}$$

for depth $d$.

This implies that exhaustive search is impossible, and local structure matters greatly. Thus, good variation operators are crucial.

There is a distinction that we can make: semantic vs. syntactic search spaces. Two different trees can compute the same function. For example, $x+0$ and $x$. This means that GP searches in a huge syntactic space, but a smaller semantic space. This redundancy can both help and hurt search.