Teller and Veloso have previously reported success using the MBPR paradigm in GP with representations that are not tree-structured [Teller and Veloso1996, Teller and Veloso1995]. While this past research is a good justification for careful investigations into the actual effectiveness of MBPR in alternate program representations, we will mention here a few persuasive reasons for the use of MBPR in non-standard program response situations.
The first non-standard response situation that is becoming increasingly common in the GP field is to have a single program return more than one value. Having separate trees that evolve together is one solution to this problem, but this is really a group of programs that share a fitness measure, not a single program with multiple outputs (e.g., [Langdon1995]). A simple way to achieve this effect is to use MBPR and use multiple memory locations for the multiple return values. For example, if we want our programs to return three values, we can treat Memory[0], Memory[1], and Memory[2] as these three values upon program completion.
A second non-standard response situation is one in which the programs must report a value periodically while running continuously or in which the programs may run for a long or infinite amount of time while the answer is required after a fixed or at least limited amount of time. In such cases, there is no way to force the programs to output a value from some special function node (e.g., the root node of a tree) when desired. If the MBPR paradigm is used, the value of Memory[0], for example, can be polled as needed without interruption of the program or concern for its state.
A third circumstance is one in which the representation itself is not isomorphic to a tree-structured representation. In such cases, as long as memory is being used, the MBPR paradigm is trivial to implement. Conversely, if an RPBR strategy is to be used, then you have to pick a special unit of the program to treat as the answer and have some reassurance that that unit will be activated within the time constraints of the problem. In the MBPR method, the program becomes responsible, not for returning a best value, but for updating its memory with its best guess.
The three reasons just outlined, and others, clearly show MBPR to be more flexible than RPBR. Thus, only a high computational overhead should prevent the use of the MBPR paradigm.