Information Technology Reference
In-Depth Information
introduces genetic variation using genetic operators. Thus, the fundamental
difference between GP and GAs resides in the nature of the individuals
and, consequently, in the way in which they are reproduced with modifica-
tion to allow adaptation.
The individuals of genetic programming are usually LISP programs rep-
resented as parse trees (Figure 1.8). What is particularly interesting is that
parse trees may assume different sizes and shapes in the process of evolu-
tion. As such, populations may evolve and discover solutions of greater
complexity.
As stated previously, in GP, the genetic operators act directly on the
parse tree and, although at first sight this might appear advantageous, it
greatly limits this technique (it is impossible to make an orange tree pro-
duce mangos only by grafting and pruning). The genetic operators must be
very carefully applied so that only valid structures are formed. Consider,
for instance, crossover, the most used and often the only search operator
used in GP (Figure 1.9). In this case, selected branches are exchanged be-
tween two parent trees to create offspring. The idea behind its implementa-
tion was to exchange smaller, mathematically concise blocks in order to
evolve more complex, hierarchical solutions composed of smaller building
blocks. Effectively, GP crossover very much resembles the pruning and
a.
(-(*(-a(sqrt(*ba)))(/(/(-aa)(+bb))(sqrt(+ab))))(+ba))
b.
a
/
b
a
/
sqrt
sqrt
b
a
a
a
b
b
a
b
Figure 1.8.
A computer program in LISP
(a)
and its tree representation
(b)
. Note that
LISP operators precede their arguments, e.g., (
a
+
b
) is written as (+
ab
).
