Page 71 - 49A Field Guide to Genetic Programming

6.3 Developmental Genetic Programming 57

systems, such as grammatical evolution and the various TAG-based systems,
are typically simple to initialise, and mutation and crossover need to enforce
few, if any, constraints on the new child. The work (and the bias) in these
systems is much more in the choice of the grammar, and once it has been
designed, there is often little additional work required of the practitioner or
the GP system to enforce the implied constraints.
While a constraint system may limit the search space in valuable ways
(Ratle and Sebag, 2000) and can improve performance on interesting prob-
lems (Hoai, McKay, and Essam, 2006), there is no general guarantee that
constraint systems will make the evolutionary search process easier. There
is no broad assurance that a constraint will increase the density of solu-
tions or (perhaps more importantly) approximate solutions. 2 Also, while
there are cases where constraint systems smooth the search landscape (Hoai
et al., 2006), it is also possible for constraint systems to make the search
landscape more rugged by preventing genetic operations from creating inter-
mediate forms on potentially valuable evolutionary paths. In the future, it
might be useful to extend solution density studies such as those summarised
in (Langdon and Poli, 2002) to the landscapes generated by constraint sys-
tems in order to better understand the impact of these constraints on the
underlying search spaces.
In summary, while types, grammars, and other constraint systems can
be powerful tools, all such systems carry biases. One therefore needs to be
careful to explore the biases introduced by the constraints and not simply
assume that they are beneficial.

6.3 Developmental Genetic Programming

By using appropriate terminals, functions and/or interpreters, GP can go
beyond the production of computer programs. In cellular encoding (Gruau,
1994; Gruau and Whitley, 1993; Gruau, 1994), programs are interpreted
as sequences of instructions which modify (grow) a simple initial structure
(embryo). Figure 6.4 shows part of the development of an electronic circuit. 3
Once the program has finished, the quality of the structure it has produced
is measured and this is taken to be the fitness of the program.
Naturally, for cellular encoding to work the primitives of the language
must be able to grow structures appropriate to the problem domain. Typical
instructions involve the insertion and/or sizing of components, topological

2 By “solution density” we refer to the ratio between the number of acceptable solutions
in a program search space and the size of the search space itself. This is a rough assessment
of how hard a problem is, since it gives an indication of how long random search would
take to explore the program space before finding an acceptable solution.
3
The process is easier to explain with a movie. This can be downloaded from http:
//www.genetic-programming.com/gpdevelopment.html.