next up previous
Next: Introduction to the Memory Up: A Study in Program Previous: ABSTRACT


The traditional method for extracting the response from each individual in GP was inspired by the functional programming of LISP. The most common way to get a program's response is to take the value returned by the root node. The tree whose value is taken to be the answer, especially when an individual consists of multiple trees (such as automatically defined functions (ADFs)), is usually called the Result Producing Branch (RPB). We label this traditional method Result Producing Branch Response, or RPBR. While using the return value of the RPB is the simplest thing to do, it gives exponentially decreasing importance to nodes further down the tree. In other words, nodes lower in the tree have exponentially less of an effect on the outcome in RPBR. We conjecture that this situation can increase the complexity of the search.

The genesis of this paper was the idea of a Memory-Based Program Response (MBPR) paradigm. This idea has already been suggested and found to be successful in non-tree representations (e.g., [Teller and Veloso1996, Teller and Veloso1995]). The hypothesis that this paper addresses is that the advantages of MBPR outweigh its disadvantages for many problems. This paper includes a description of the MBPR mechanism, presentation of experiments designed to test the hypothesis, and analysis of those experimental results.

Section 2 describes an alternative to RPBR. Section 3 presents a set of runs on a classic GP benchmark on which MBPR does well. Then sections 4 and 5 present two other benchmark domains for which the MBPR costs are negligible and high, respectively. The following two sections (6 and 7) describe the important effects of introns in these reported results and comment on the implications. Finally, section 8 concludes with a summary and future research directions.

Eric Teller
Tue Oct 29 16:58:50 EST 1996