MBPR: Tree Representations

The following two definitions will be useful in discussing the relative merits of the RPBR and MBPR paradigms.

Vertical Node Interference

is the blocking of a subtree result by one of its ancestors. This phenomena is aggravated by representations in which there is an non-uniform distribution of control among the nodes. The tree representation is such a representation. The tree representation provides an inverse exponential distribution of control among the nodes as a function of depth. The root controls the return value of all N nodes. If the root has arity A then each of its children has, on average, control over nodes.

Sibling Coordination Interference

is the blocking of a subtree's result by a node that is not an ancestor. This is the search difficulty brought about by representations in which nodes that are not hierarchically related (e.g., ancestor-descendant relation) to each other can still affect each other's results through side-effects. The ant problem representation in [Koza1992] suffers from this. In fact, any representation that includes memory usage (e.g., indexed memory) potentially suffers from this effect.

The argument for MBPR in the tree-structured GP representation follows. If a program has some portion of it that computes an accurate or perfect answer, it must (independent of the representation and response collection method) rely on the rest of the program not to interfere with that answer until the environment collects it. For example, in tree-GP using RPBR, if a subtree computes a good answer, it must depend on the path from the root of that subtree to the root of the tree to be non-destructive. This is the vertical node interference problem mentioned in the previous section.

Clearly, MBPR suffers from an analogous problem. If a program is allowed to update its ``answer'' memory cell in any part of its program, then clearly a ``destructive'' program fragment can overwrite a correct answer that the ``good'' part of the program had already written to the ``answer'' location in memory. This is the sibling coordination interference problem.

Because the MBPR approach is largely (although not entirely) position independent, it seems to have a natural advantage over RPBR. A response collection policy is position independent to the extent that a subtree that computes ``the answer'' for a given individual can be moved without affecting the subtree's ability to produce ``the answer'' in the new individual. In the MBPR paradigm, a subtree that includes a WRITE to the answer cell in memory can be moved to a new individual program and that subtree will still be able to store its value into the answer cell in memory. Obviously, the high degree of vertical node interference means no such guarantee can be made when RPBR is used. MBPR is not entirely position independent in the sense that while a transplanted subtree can compute an answer and store it in Memory[0], that value could later be overwritten by another subtree.

To believe that the MBPR paradigm will be better than RPBR paradigm for a particular problem, we must believe that searching with high sibling coordination interference will be easier than searching with high vertical node interference. It would seem that the a priori argument for MBPR is that, in the worst case, any tree that is a solution in RPBR space, by adding a WRITE to the top, becomes a solution in the MBPR space. Even if there are other WRITEs to the answer location in the tree, this root node, since it is last, cannot be overwritten. It seems that this ``capping'' procedure would be simple to evolve if it were necessary. However, the side-effects of introns introduced by memory (sibling coordination interference) complicates this analysis.

All these reasons contribute to our belief that MBPR is a more flexible strategy for program response collection. Now, experiments will help us to understand when, if ever, the costs associated with MBPR outweigh the arguments for using it.