Page 63 - 49A Field Guide to Genetic Programming

6.1 Evolving Modular and Hierarchical Structures 49

ROOT

ADF1 ADF2 RPB

Figure 6.1: Example of program structure with two automatically-defined
functions (ADF1 and ADF2) and one result-producing branch (RPB).

Consider, for example, the following individual consisting of a result-
producing branch and a single ADF:

RPB : ADF(ADF(ADF(x))) (6.1)
ADF : arg0 × arg0 (6.2)
The ADF (Equation 6.2) is simply the squaring function, but by combining
this multiple times in the RPB (Equation 6.1) this individual computes x 8
in a highly compact fashion.
It is important to not be fooled by a tidy example like this. ADFs
evolved in real applications are typically complex and can be very difficult
to understand. Further, simply including ADFs provides no guarantee of
modular re-use. As is discussed in Chapter 13, there are no silver bullets.
It may be that the RPB never calls an ADF or only calls it once. It is also
common for an ADF to not actually encapsulate any significant logic. For
example, an ADF might be as simple as a single terminal, in which case it
is essentially just providing a new name for that terminal.
In Koza’s approach, each ADF is attached (as a branch) to a specific indi-
vidual in the population. This is in contrast to both Angeline’s and Rosca’s
systems mentioned above, both of which have general pools of modules or
components which are shared across the population. Sometimes recursion
is allowed in ADFs, but this frequently leads to infinite computations. Typ-
ically, recursion is prevented by imposing an order on the ADFs within an
individual and by restricting calls so that ADF i can only call ADF j if i < j.
In the presence of ADFs, recombination operators are typically con-
strained to respect the larger structure. That is, during crossover, a subtree