Page 62 - 49A Field Guide to Genetic Programming

48 6 Modular, Grammatical and Developmental Tree-based GP

taken from parts of fit GP trees. Special mutation operations allowed the
GP population to share code by referring to the same code within the li-
brary. Subsequently, Angeline suggested that the scheme’s advantages lay
in allowing GP individuals to access far more code than they actually “held”
within themselves, rather than principally in developing more modular code.
Rosca and Ballard (1996a) used a similar scheme, but were able to use much
more information from the fitness function to guide the selection of the code
to be inserted into the library and its subsequent use by members of the GP
population. Olsson (1999, 1995) later developed an abstraction operator for
use in his ADATE system, where sub-functions (anonymous lambda expres-
sions) were automatically extracted. Unlike Angeline’s library approach,
Olsson’s modules remained attached to the individual they were extracted
from.
Koza’s automatically defined functions (ADFs) (Koza, 1994) remain the
most widely used method of evolving reusable components and have been
used successfully in a variety of settings. Basic ADFs (covered in Sec-
tion 6.1.1) use a fixed architecture specified in advance by the user. Koza
later extended this using architecture altering operations (Section 6.1.2),
which allow the architecture to evolve along with the programs.

6.1.1 Automatically Defined Functions

Human programmers organise sequences of repeated steps into reusable com-
ponents such as subroutines, functions and classes. They then repeatedly
invoke these components, typically with different inputs. Reuse eliminates
the need to “reinvent the wheel” every time a particular sequence of steps
is needed. Reuse also makes it possible to exploit a problem’s modularities,
symmetries and regularities (thereby potentially accelerate the problem-
solving process). This can be taken further, as programmers typically or-
ganise these components into hierarchies in which top level components call
lower level ones, which call still lower levels, etc. Koza’s ADFs provide a
mechanism by which the evolutionary process can evolve these kinds of po-
tentially reusable components. We will review the basic concepts here, but
ADFs are discussed in great detail in (Koza, 1994).
When ADFs are used, a program consists of multiple components. These
typically consist of one or more function-defining branches (i.e., ADFs), as
well as one or more main result-producing branches (the RPB), as illustrated
in the example in Figure 6.1. The RPB is the “main” program that is
executed when the individual is evaluated. It can, however, call the ADFs,
which can in turn potentially call each other. A single ADF may be called
multiple times by the same RPB, or by a combination of the RPB and other
ADFs, allowing the logic that evolution has assembled in that ADF to be
re-used in different contexts.