2 Representation and Operator Conflicts

Section 3.2 described issues in the representation and operator that increase problem difficulty. Intuitively, exchanging subtrees between two syntax trees (representing computer programs) during recombination, regardless of tree shape or content, would seem unlikely to preserve the semantic meaning of the exchanged subtrees. Thus, it is not too surprising that subtree crossover has been shown to perform similarly to mutation variants [Angeline, 1997,Luke and Spector, 1998,O'Reilly and Oppacher, 1996]. However, because the population only represents a portion of the search space at one time, could the population make the search more robust against landscape roughness issues by avoiding particular regions of the search space? If the population can encourage the search toward regions of the search space that minimise internal conflicts between the representation and operator, it would be able to `smooth' the search landscape.

Homology attempts to address some of the problems with the representation and operator. Intuitively, recombination should modify similar content with similar context in parents, thereby preserving the semantics of exchanged genetic material. In this way, solutions may be iteratively and incrementally built. Homology can be achieved by using operators that search for semantically similar subtrees. Platel et al. (2003) defined a homologous crossover for a linear genetic programming representation. Their results showed that homology reduced code growth and produced far more neutral events than a standard crossover operator. While neither method produced many ``Advantageous'' events, the number of destructive events were more numerous using standard crossover. Smaller solution sizes with mixed improvement of quality were seen in other studies using homologous operators [D'haeseleer, 1994,Langdon, 2000b,Poli and Langdon, 1998a,Nordin et al., 1999].

The concept of homology could also be implemented with a population that consist of similar trees. In this case, operators are more likely to pick subtrees from semantically similar areas as probability of selection will apply similarly to the homogeneous population. That is, less genetically diverse, or homologous, populations may, among other things, improve the chance of preserving semantics during recombination.

As noted in [Langdon, 2000b], a potential drawback of homologous crossover is the slow growth in size of the population. If the initial population is of the wrong structure, e.g. trees much smaller than optimal size, then homologous crossover will approach this rate slowly. Standard crossover might better obtain the ideal size, but its ability to improve solution quality or maintain the size is debatable and problem dependent. Additionally, homologous operators introduce or preserve similarities in the population, which could counter the possible benefits of diversity preservation. However, a converged population, while possibly improving search, can also limit the ability to avoid local optima.