The objective of this project is to develop improved genetic programming techniques
and to apply these techniques to difficult, unsolved computational problems. Of particular
interest in this project are problems involving control and adaptation of multiple
agents in heterogeneous, dynamic environments.
Genetic programming is a computational search method based on the biological concepts
of fitness-proportionate reproduction, mutation, and recombination. The proposed
improvements to genetic programming techniques are intended to broaden the range
of problems to which genetic programming can be applied, including problems with
multiple data types and complex control requirements. A further goal is to decrease
the need for expert configuration of genetic programming systems; ideally the system
will "configure itself" as part of its evolutionary process.
Early genetic programming systems forced users to restrict all operations to a single data type to ensure the semantic validity of programs undergoing recombination and mutation. More recently, "strongly typed" genetic programming systems have been developed that relax this restriction, allowing the generation of programs that manipulate a diverse set of data types. Multi-type genetic programming, as developed in the current project, builds on the stack-based genetic programming paradigm, in which all intermediate values are stored on a global stack. In multi-type genetic programming this concept is extended to use multiple stacks, one for each data type that may be important in the application environment. For example, one can use independent stacks for integers, symbols, strings, URLs, HTML tags, DAML tags, and so on. For each stack there is a set of primitive stack-manipulation operators (push, pop, swap, etc.) and higher-level functions that take any number of arguments of any of the types can be included in the function set.
In addition to providing for flexible use of multiple data types, itself critical for complex application areas, multi-type genetic programming directly supports the automatic and flexible evolution of subroutines, control structures, and adaptive genetic operators (evolved alternatives to crossover, point mutation, etc.). This is accomplished through the use of additional data types (and corresponding stacks and functions) such as CODE, and CHILD. These data types and their associated functions allow an evolved program to explicitly manipulate code that can be used to implement automatically defined functions or automatically defined macros without prior knowledge about the number or type of modules required and without the complexity of architecture-altering operations. In addition, these mechanisms can be used to allow programs to construct their own offspring, bringing the mechanisms of genetic variation and recombination under evolutionary control. This elegantly generalizes a wide range of adaptive mutation and crossover techniques and largely transfers the responsibility for reproductive strategies from the user (via global, human-set parameters) to the system itself (via natural selection operating on the programs themselves).
The cumulative effect of these innovations will be that the user will be able to specify a diverse set of primitives and related data types while simultaneously specifying little in the way of system parameters.
The improved genetic programming system will be tested on problems from several areas including the control of agents in complex environments and quantum computation. In addition, the improved genetic programming system should have applications to computational problems in almost any quantitative field (including all of those to which genetic programming has been previously applied).
Note: This project was initiated in February, 2001 (later than the other projects
in the program).
Ported the PushGP and Pushpop genetic programming systems (as documented in the GECCO-2001 paper "Autoconstructive Evolution: Push, PushGP, and Pushpop) to a 16-node Beowulf-style cluster. Results in at least 16x speedup (possibly more by allowing for runs that use the entire cluster with sub-populations).
Obtained preliminary data confirming the general utility of PushGP on standard genetic programming test problems. Began systematic benchmarking and application to previously unsolved problems.
Developed, in conjunction with the MIT/BBN group, detailed plans for applying PushGP/Pushpop to MIT/BBN traffic agent simulators and airlift scenario simulators currently under development. Plans also specify incorporation of MIT/BBN Elementary Adaptive Modules into PushGP/Pushpop. Initial steps of these plans are now being taken.
Developed a new and particularly challenging test environment for automatically programmed agents, documented in the GECCO-2001 "late-breaking" paper "Virtual Quidditch: A Challenge Problem for Automatically Programmed Software Agents."
Apply PushGP/Pushpop genetic programming systems to difficult, unsolved problems
in several areas (e.g. integer sequence induction, quantum computation) as described
in the project proposal.
Integrate PushGP/Pushpop genetic programming systems with MIT/BBN agent simulators and/or additional agent simulators.
Produce initial evolved agents and compare evolved and hand-crafted agent designs and performance.
Integrate MIT/BBN Elementary Adaptive Modules (EAMs) into the PushGP/Pushpop genetic programming systems.
Assess utility of components made available to evolution, including EAMs and other components.
The Push interpreter and the PushGP and Pushpop genetic programming systems will
be made available by the PI (Lee Spector, firstname.lastname@example.org). These systems
require a Common Lisp programming environment (on any platform). Current results
are being disseminated at the GECCO-2001 conference/proceedings and are being prepared
for journal submission. The PI is also planning to attend the next DARPA QUIST program
meeting for possible dissemination of quantum computing applications work.