http://hampshire.edu/lspector/darpa-selfadapt.html
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, lspector@hampshire.edu). 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.