Multi-type, Self-adaptive Genetic Programming for Complex Applications

A project supported by the Defense Advanced Research Project Agency (DARPA) and the Air Force Research Laboratory (AFRL)

DARPA Program: Agent-Based Computing, Taskable Agent Software Toolkit (TASK)

Principal Investigator: Lee Spector (lspector@hampshire.edu), School of Cognitive Science, Hampshire College



Project Goals and Background

The aim 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 in heterogeneous, dynamic environments.

Genetic programming is a computational search method based on the biological concepts of fitness-proportionate reproduction, mutation, and recombination; it has been developed and applied by hundreds of researchers and is the primary topic of an annual international conference, a journal, and at least fifteen books. It has been applied to a wide range of problems including electrical circuit design, financial market prediction, natural language processing, and software engineering. In a genetic programming system software evolves from a primordial soup of instructions and data. By specifying an appropriate definition of "fitness" a user can leverage the evolutionary process of genetic programming to produce solutions to computational problems, in some cases rivaling or exceeding the performance of human engineers and scientists. By virtue of their similarities to natural evolutionary processes, genetic programming systems can also be used to explore hypotheses about biological evolution.

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. The methods by which such self-configuration will be achieved borrow heavily from evolutionary biology and it is also hoped that the system, considered as an "artificial life" model, will provide data that can inform the interdisciplinary study of evolutionary processes.

The improved genetic programming system will be tested on problems from several areas including the control of agents in complex environments and quantum computation (a recent research area at the intersection of computer science and quantum mechanics). Some of these problems, if solved, may have substantial practical applications. 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). In the long term important results of this type of research may derive from insights that genetic programming and artificial life systems provide about the nature of evolution and about the ways in which nature's algorithms can be harnessed to solve human problems.

Personnel

Principal Investigator: Lee Spector (lspector@hampshire.edu)

Research Assistant: Jon Klein (jklein@artificial.com)

Publications

Spector, L., J. Klein, C. Perry, and M. Feinstein. To appear. Emergence of Collective Behavior in Evolving Populations of Flying Agents. In Genetic Programming and Evolvable Machines.

Spector, L., C. Perry, J. Klein, and M. Keijzer. 2004. Push 3.0 Programming Language Description. http://hampshire.edu/lspector/push3-description.html.

Spector, L., J. Klein, and C. Perry. 2004. Tags and the Evolution of Cooperation in Complex Environments. In Proceedings of the AAAI 2004 Symposium on Artificial Multiagent Learning. Melno Park, CA: AAAI Press. (pdf: 140KB)

Crawford-Marks, R., L. Spector, and J. Klein. 2004. Virtual Witches and Warlocks: A Quidditch Simulator and Quidditch-Playing Teams Coevolved via Genetic Programming. In Late-Breaking Papers of GECCO-2004, the Genetic and Evolutionary Computation Conference. Published by the International Society for Genetic and Evolutionary Computation. (pdf 308KB, Raphael's page on the project, additional movies).

Spector, L., J. Klein, C. Perry, and M. Feinstein. 2003. Emergence of Collective Behavior in Evolving Populations of Flying Agents. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003). Springer-Verlag. pp. 61-73. Winner, Best Paper Award (AAAA Track). (associated web page, including link to full text)

Spector, L. 2003. An Essay Concerning Human Understanding of Genetic Programming. In Genetic Programming: Theory and Practice, edited by R.L Riolo and W. Worzel, pp. 11-24. Boston, MA: Kluwer Academic Publishers.

Spector, L., and H.J. Bernstein. 2002. Communication Capacities of Some Quantum Gates, Discovered in Part through Genetic Programming. In J.H. Shapiro and O. Hirota, Eds., Proceedings of the Sixth International Conference on Quantum Communication, Measurement, and Computing (QCMC). Princeton, NJ: Rinton Press. (prepress version with additional figures: pdf 1.2MB)

Spector, L. 2002. Adaptive populations of endogenously diversifying Pushpop organisms are reliably diverse. In R. K. Standish, M. A. Bedau, and H. A. Abbass (eds.), Proceedings of Artificial Life VIII, the 8th International Conference on the Simulation and Synthesis of Living Systems, pp. 142-145. Cambridge, MA: The MIT Press. (pdf 488KB)

Spector, L., and J. Klein. 2002. Evolutionary Dynamics Discovered via Visualization in the BREVE Simulation Environment. In Bilotta et al. (eds), Workshop Proceedings of the 8th International Conference on the Simulation and Synthesis of Living Systems, pp. 163-170. Sydney, Australia: University of New South Wales. (associated web page, including link to full text)

Spector, L., and A. Robinson. 2002. Multi-type, Self-adaptive Genetic Programming as an Agent Creation Tool. In Proceedings of the Workshop on Evolutionary Computation for Multi-Agent Systems, ECOMAS-2002, International Society for Genetic and Evolutionary Computation. (pdf 527KB)

Robinson, A., and L. Spector. 2002. Using Genetic Programming with Multiple Data Types and Automatic Modularization to Evolve Decentralized and Coordinated Navigation in Multi-Agent Systems. In Late-Breaking Papers of GECCO-2002, the Genetic and Evolutionary Computation Conference. Published by the International Society for Genetic and Evolutionary Computation. (pdf 33KB)

Spector, L., and A. Robinson. 2002. Genetic Programming and Autoconstructive Evolution with the Push Programming Language. In Genetic Programming and Evolvable Machines, Vol. 3, No. 1, pp. 7-40. (pdf 216KB)

Crawford-Marks, R., and L. Spector. 2002. Size Control via Size Fair Genetic Operators in the PushGP Genetic Programming System. In W. B. Langdon, E. Cantu-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska (editors), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2002, pp. 733-739. San Francisco, CA: Morgan Kaufmann Publishers. (pdf 586KB)

Spector, L. 2002. Hierarchy Helps it Work That Way. In Philosophical Psychology, Vol. 15, No. 2 (June, 2002), pp. 109-117.

Spector, L. 2001. Autoconstructive Evolution: Push, PushGP, and Pushpop. In Spector, L., E. Goodman, A. Wu, W.B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, 137-146. San Francisco, CA: Morgan Kaufmann Publishers. (pdf 547KB).

Spector, L., R. Moore, and A. Robinson. 2001. Virtual Quidditch: A Challenge Problem for Automatically Programmed Software Agents. In E.D. Goodman, editor, Late-Breaking Papers of GECCO-2001, the Genetic and Evolutionary Computation Conference. Published by the International Society for Genetic and Evolutionary Computation. (pdf 244KB).

Barnum, H., H.J. Bernstein, and L. Spector. 2000. Quantum circuits for OR and AND of ORs. Journal of Physics A: Mathematical and General, Vol. 33 No. 45 (17 November 2000), pp. 8047-8057. (postscript 436KB, pdf 156KB)

Additional Related Publications

Software

Facilities

The Hampshire College Cluster Computing Facility.

Additional Information

Additional SwarmEvolve documentation and movies (or older Quicktime movie (10MB) showing evolved, goal-directed swarms).

Selected PI meeting/workshop presentations:

DARPA Technical Reports:

PSUM Technical Report information (July, 2001)

DARPA Quad Chart (July, 2001)

DARPA Quad Chart (July, 2004)