# Why do all nodes in a GP tree need to be the same type?

Context: I'm a complete beginner to evolutionary algorithms and genetic algorithms and programming. I'm currently taking a course about genetic algorithms and genetic programming.

One of the concepts introduced in the course is "closure," the idea that - with an expression tree representing a genetic program that we're evolving - all nodes in the tree need to be the same type. As a practical example, the lecturer mentions that implementing greater_than(a, b) for two integers a and b can't return a boolean like true or false (it can return, say, 0 and 1 instead).

What he didn't explain is why the entire tree needs to match in all operators. It seems to me that this requirement would result in the entire tree (representing your evolved program) being composed of nodes that all return the same type (say, integer).

• – nbro
Jan 23, 2021 at 15:13

In tree-based genetic programming (TGP), you have a tree that represents a program or a function. The nodes in this tree are functions, while the edges represent the interactions between these functions. The leaves of this tree are the inputs (or random numbers) that you pass to this function. The incoming edges into a node represent the inputs, while the outgoing edges represent the output of the associated function.

So, for example, consider the following function

\begin{align} f(x) &= \sin(x^2) \\ &= \sin(y) \tag{1}\label{1}, \end{align} where $$y = g(x)$$ (note that this is just a change of variable in order to illustrate the corresponding tree more clearly below!).

The function $$f$$ will be represented by the following tree

sin(y)
|
g(x)
|
x


So, how do we read this diagram? Essentially, we read it from the bottom-up. So, $$x$$ is first passed to $$y = g(x) = x^2$$, which then passed to $$\sin(y)$$. In this case, given that we are dealing with mathematical operations, you expect $$x$$ to be a number, because, otherwise, what would $$x^2$$ or $$\sin(x^2)$$ mean?

Let's now consider a function of 2 inputs.

\begin{align} f(x, y) &= x + y \tag{2}\label{2}, \end{align}

The corresponding tree would be

  +
/ \
x   y


In this case, you naturally expect that $$x$$ and $$y$$ are also numbers. However, this may not be actually the case. Let's say that you're evolving Python functions, then x + y is well defined even if x and y are strings, i.e. that would be a concatenation operation.

So, in this sense, we naturally expected the functions (the nodes in the tree) to get parameters/arguments with the right types, but, in some cases, more types are possible for the apparently same function.

So, in general, types don't necessarily need to be enforced! It depends on the implementation of TGP.

There's a specific approach to TGP where the idea is really to ensure type-safety, i.e. strongly-typed (tree-based) genetic programming, where functions can have a different number and type for their parameters and return values, but, in that case, only functions that are consistent with the signature of the function can be "connected" with that function in the tree.

In weakly-typed GP, the types are not checked, so you could end up evolving functions of the form $$f(x) = \sin(x)$$, where $$x$$ is a string. Of course, when you execute these programs/functions, the program may crash, but this is a different story, which you need to take care of (i.e. you need to ensure that your individuals can be evaluated), if you need this flexibility. This weakly-typed approach can also be viewed as a strongly-typed approach where all functions' parameters and return values have the same type.

DEAP, a well-known Python library for GAs and GP, provides both weakly and strongly-typed GP, so, if you are familiar with Python, you may want to start from it.

To conclude and answer your question more directly, it's not true that in TGP you need all functions to have the same type for all parameters and return values.