|
|
Multi-type, Self-adaptive Genetic Programming for Complex ApplicationsA 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 |
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.
Principal Investigator: Lee Spector (lspector@hampshire.edu)
Research Assistant: Jon Klein (jklein@artificial.com)
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
The Hampshire College Cluster Computing Facility.
Additional SwarmEvolve documentation and movies (or older Quicktime movie (10MB) showing evolved, goal-directed swarms).
Selected PI meeting/workshop presentations:
- August, 2001: PDF
- October, 2002: PDF, PowerPoint
- February, 2003: Keynote (Apple, Stuffed), PDF, PowerPoint
- August, 2004: PDF
DARPA Technical Reports:
- April, 2001
- July, 2001
- October, 2001
- January, 2002
- April, 2002
- July, 2002
- October, 2002
- April, 2003
- July, 2003
- October, 2003
- August, 2004 (items for on-line form, cumulative quarterly reports)
- Final report (December , 2004)
PSUM Technical Report information (July, 2001)