| As simple replicators, the ramified structures or trees of GP are tied up in their own complexity. On the one hand, bigger, more complex structures become less and less flexible and, therefore, the evolution of more complex structures becomes extremely difficult as these structures cannot be fragmented into smaller, manageable sub-trees. On the other hand, the introduction of genetic variation can only be done at the tree level and, therefore, must be done carefully so that valid structures are created. For instance, the tree-specific crossover illustrated in
Figure 1 is practically the only source of genetic variation used in GP for it allows the exchanging of sub-trees and, therefore, always produces valid structures.
Fig. 1. Tree-specific crossover in genetic programming. Sub-trees in parents are selected and exchanged, forming two new daughter trees.
But the implementation of other operators, like the equivalent of the high-performing point mutation
[8], is unproductive as most mutations result in syntactically incorrect structures
(Figure 2). Obviously, the implementation of other operators such as transposition or inversion raises similar difficulties and the search space in GP remains vastly unexplored.
Fig. 2. Illustration of an hypothetical event of point mutation in genetic programming. Note that the daughter tree is an invalid structure.
|