next up previous
Next: Discussion Up: Experiments Previous: Static Programs

Halting Programs


As this chapter has described, PADO does not have to require that a MAIN program halt in order for that program to have non-zero fitness. By using a time-threshold and an anytime extraction procedure (e.g., answer = MEMORY[0]), we do not have to require that programs find an answer, know that they are done, and transition to their stop node. Indeed, when no self-halting criterion is enforced, by generation 100 only about 1% of the programs transition to their stop node even once during a particular execution. So, there does not appear to be a selective advantage to stopping and being restarted during a run. The reason the stop node exists in the MAIN programs is that an experimental version of PADO is beginning to use MAIN programs (as well as ADF programs) in the Library. This requires that MAIN programs be able to relinquish control.

Figure 3.6: Percent of the Population that halts when recombination is applied

As an experiment, however, we pressured programs to halt by assigning zero fitness to programs that had not self-halted by the time-threshold. This situation presents an interesting problem to the recombination operators: the fitness of an individual will drop to zero if recombination causes the new program to no longer halt. In figure 3.6 we see that the SMART operators are able to significantly reduce the percentage of newly created programs that never halt. While this is not always of direct fitness advantage it is, in this experiment, another indication of the SMART operators' flexibility to respond to demands of the environment. The important thing to notice is that an interesting operator ``sub-task'' was partly solved here through the co-evolution of recombination programs.

Eric Teller
Tue Oct 29 17:04:55 EST 1996