2 Relevance to Other Domains

The Tree-String problem is similar to the Royal Tree problem [Punch et al., 1996] where an objective is a predefined structure. However, the Royal Tree problem gives maximum credit to full trees with specific functions and terminals at specific depths in a hierarchical fitness function. An extension of the Royal Tree [Platel et al., 2003] is also related where an objective is matching contiguous symbols in a string in the context of a linear representation. The structural aspect of the Tree-String problem is also similar to the Lid problem [Daida et al., 2003b] where a structure at a pre-defined depth and size is the objective. However, the Lid problem is concerned with structure and does not consider the effects of content or context that are present in other problem domains.

With respect to other problem domains, the following characteristics are relevant:

• The string objective is likely to contain a high level of deception, similar to the Ant problem, as described earlier and found in [Langdon and Poli, 2002]. For example, the string objective function can assign the same fitness to very different strings that share the same length of matching subsequence with the target string. In the following two trees, both contain the string ``ABC'' (found by a depth-first traversal):
  
  $$\Tree [.A [.B [.C D A ] A ] A ] \Tree [.A [.A [.A A B ] C ] D ]$$
  
  
  If the complete target string is ``ABCDDDDDD'', then both trees have a fitness of (9-4) by matching the subsequence ``ABCD''. The two trees, however, achieve the same fitness in very different ways.

  Figure 7.2: A binary tree of depth 10 is realised on a circular lattice on the left and the target tree in the Tree-String problem of 63 nodes on the right. The root nodes lies at the center of the lattice. Note that the scale was increased in the right figure.

  

• The tree objective function is likely to have less deception and be amenable to a hill-climbing search. A genetic programming approach that mimics the target tree construction method should be very effective. A hill-climbing method that encouraged the slow growth of an tree should work well in minimising the tree objective. Whether the reasons are similar, the Parity problem is also amenable to hill-climbing type methods, which often out-performs genetic programming, described in Chapter 5 and in [O'Reilly and Oppacher, 1994,Juels and Wattenberg, 1995].

• Lastly, the combined objectives of string and structure will probably create a content and context conflict similar to the regression domain [Daida et al., 2001]. Moving mathematical functions expressed on subtrees is likely to change the way the content applies toward fitness in a new context. Similarly, a subtree is likely to contribute very differently when the context is not preserved in a similar shaped offspring, even one with similar content. For example, in the Tree-String problem, inserting a subtree into an existing tree is likely to effect any sequence matching the target string. This is due to the fact that the string is obtained by a depth-first traversal.

Given these properties of the Tree-String problem and the similarities to other common domains, the problem appears to be representative of the general class of problems to which genetic programming is typically applied. Of course, additional analysis is required to verify these speculated properties and behaviours of the Tree-String problem.