Representation and Structural Difficulty in Genetic
Programming
IEEE Transactions on Evolutionary Computation, 10 (2):
157--166 (April 2006)DOI: doi:10.1109/TEVC.2006.871252
Abstract
Standard tree-based genetic programming suffers from a
structural difficulty problem in that it is unable to
search effectively for solutions requiring very full or
very narrow trees. This deficiency has been variously
explained as a consequence of restrictions imposed by
the tree structure or as a result of the numerical
distribution of tree shapes. We show that by using a
different tree-based representation and local
(insertion and deletion) structural modification
operators, that this problem can be almost eliminated
even with trivial (stochastic hill-climbing) search
methods, thus eliminating the above explanations. We
argue, instead, that structural difficulty is a
consequence of the large step size of the operators in
standard genetic programming, which is itself a
consequence of the fixed-arity property embodied in its
representation.