next up previous
Next: Looking Inside a PADO Up: 3 Previous: Background

The Language

 

PADO (Parallel Algorithm Discovery and Orchestration) is a new learning architecture specifically designed for signal understanding. PADO's learning core is Genetic Programming. Figure 3.1 sketches the structure of a PADO program. Each program has three main components: a main program (referred to as MAIN), one or more private ADF programs [Koza 1994], and an indexed memory [Teller 1994a]. The MAIN program may call any of the private ADF programs it owns or any of the publicly available Library programs (see below). The private ADF programs may call each other, themselves, or any of the Library programs. The Library programs may, in turn, call any of the other Library programs, themselves, or any of the private ADF programs of the current PADO program. Any of these programs may access the indexed memory of the current running PADO program.

When a PADO MAIN program is run, a timer is started and the program is forcibly terminated when a pre-set time threshold is reached. This forced termination ensures that every program will halt with some answer (see section 3.3.1) in a limited amount of time.

   figure34
Figure 3.1: The general structure of a PADO program.

The indexed memory is an array of integers indexed by the integers. Each program has the ability to access any element of its memory, either to read from it (READ Index) or to write to it (WRITE NewValue Index). This memory scheme, in conjunction with loop or recursive constructs in GP has been shown to be Turing complete [Teller 1994b]. Indexed memory can be seen as the simplest memory structure that can practically support all other memory structures. Indeed, indexed memory has been successfully used to build up complex data structures and mental models of local geography [Langdon 1995, 1996; Teller 1994a].

The ADF programs (e.g., A in Figure 3.1) associated with each MAIN program are similar to standard GP ADF's (automatically defined functions). However, PADO ADF programs do not take a specific number of arguments but evolve to use what they need from the incoming argument stack (see below). In addition, they have internal loops and recursion. ADF programs evolve along with the MAIN program (as Koza does in [Koza 1994]).

The Library programs (e.g., tex2html_wrap_inline843 in Figure 3.1) are globally available programs (public ADFs) that can be executed at any time and from anywhere just like the ADF programs. But unlike the ADF programs, where each ADF may be run only during the execution of the PADO program of which it is a part, the Library programs are publicly available to the entire population. These Library programs are gathered from the ADFs of the most fit main population programs and survive through a competition for usage from highly fit main population programs. Details can be seen in [Teller and Veloso 1995a, 1995c]. While the creation, destruction, and global availability of these Library programs is different from the ``module'' concept, the maintenance of a pool of encapsulations of code is not [Angeline and Pollack 1993].





next up previous
Next: Looking Inside a PADO Up: 3 Previous: Background



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