  For theoretical analyses there are two specifics distinguishing GP from many
other areas of evolutionary computation. First, the variable size
representations, in particular yielding a possible bloat (i.e. the growth of
individuals with redundant parts). Second, the role and realization of
crossover, which is particularly central in GP due to the tree-based
representation. Whereas some theoretical work on GP has studied the effects of
bloat, crossover had a surprisingly little share in this work. We analyze a
simple crossover operator in combination with local search, where a preference
for small solutions minimizes bloat (lexicographic parsimony pressure); the
resulting algorithm is denoted Concatenation Crossover GP. For this purpose
three variants of the well-studied MAJORITY test function with large plateaus
are considered. We show that the Concatenation Crossover GP can efficiently
optimize these test functions, while local search cannot be efficient for all
three variants independent of employing bloat control.
