MBPR: Tree Representations

In the previous two sections, we showed three things about the MBPR paradigm:

• For the boolean 5 parity problem, MBPR works well, but much of its advantage was because of the introduction of memory.

• For the iterative lawn-mower problem, a problem that already required memory, MBPR was neutral with respect to computational effort.

• For the regression problems, problems that by their nature (homogeneity of function set) are unlikely to benefit from memory, MBPR was very expensive. Even when WRITE-ANSWER was used instead of indexed memory, the computational effort increase was always at least a factor of 2.

The explanation for MBPR's performance on the 5-parity problem is relatively simple. There is a large amount of redundancy in the parity problems that can be exploited through a technique like ADFs [Koza1992]. Since ADFs were not used, the introduction of memory served the same purpose. Values can be stored once in memory and then retrieved in several different places.

The performance improvement observed when using MBPR on the 5-parity problem provides evidence that the vertical node interference is more harmful for the 5-parity problem than is sibling coordination interference. Given that the runs with indexed memory (RPBR-M) differ only from the MBPR runs only in that the representation in the RPBR-M runs allows more vertical node interference, the improvement when using MBPR must be due to that difference.

Another way of understanding the success of MBPR on the 5 parity problem is by investigating its function set. In the 5-Parity problem, all four of the functions allow intron subtrees to form if the other subtree always returns a one or a zero. For example, if a subtree to an AND always returns a 0, the result of the other subtree is ignored. Since the 5-Parity is a boolean problem, constant values of 0 or 1 occur quite often. In contrast, in the regression problem, only a return value of 0 (out of infinitely many possible values) can cause a TIMES to have an intron subtree. Because it is relatively easy to make intron subtrees in the Boolean problem, vertical node interference is much more of a problem than is sibling coordination interference. This explains the success of MBPR on this problem

In the lawn-mower problem, it seems to be that the vertical node interference and the sibling coordination interference are approximately equal; moving from RPBR to MBPR does not make a significant difference. We suggest that this approximate equality of the two interference measures exists because memory is already being used in the RPBR lawn-mower problem. As shown in section 4, the moderate increase in computational effort was caused by contention over use of the Memory[0] when a dedicated memory cell is not provided. The lawn-mower problem uses memory in a very different way than does the 5-Parity boolean problem. The lawn-mower must use memory to communicate with itself on a later time step, whereas the 5-Parity problem only uses memory to pass values around. Using memory simulates ADFs for the 5-Parity problem, but not for the lawn-mower problem. This point may help to explain some of the difference between MBPR's effect on the 5-Parity and lawn-mower problems. Memory[0] could be a point of contention in either case (possibly more so in the 5-Parity problem when there are only 2 cells). However, these different memory requirements may change the dynamics of memory use in ways that we do not yet fully understand.

Most of the results shown in section 5 used WRITE-ANSWER instead of full indexed memory in a effort to disentangle the issues. One of the aspects of this data that we can not yet fully explain is why WRITE-ANSWER, even when it is not used for MBPR, causes such a noticeable jump in computational effort. Section 7.2 gives a plausible explanation for the underlying cause.