Evolutionary Computing with Push Project Documentation and Code Lee Spector (lspector@hampshire.edu) School of Cognitive Science Hampshire College

Introduction

Push is a programming language designed for evolutionary computation, to be used as the programming language within which evolving programs are expressed. A concise introduction to the newest version of the language ("Push3") is contained in The Push 3.0 Programming Language Description, which also serves as a language reference. Versions of Push written in Lisp, C++, JavaScript, Java, and Scheme are available (see below).

PushGP is a genetic programming system that evolves programs in the Push programming language. PushGP has been used for a variety of applications, ranging from intelligent agent design to automatic quantum computer programming. Features include:

• Multiple data types without constraints on code generation or manipulation.
• Arbitrary modularity without constraints on code generation or manipulation.
• Evolved module architecture with no extra machinery.
• Support for explicit, arbitrary recursion.
• Support for ontogenetic "development" of code as it runs, via code-manipulation instructions.
• Automatic program simplification (in some implementations).
  

The best introduction to the Push project is probably the 2002 article in the journal Genetic Programming and Evolvable Machines, although that article was based on Push1 and one should therefore subsequently read the GECCO paper introducing the major new features of Push3.

A variety of  Push-based evolutionary computation sytems other than PushGP have been developed, including:

• Pushpop is an "autoconstructive evolution" system that also evolves Push programs. In an autoconstructive evolution system the evolving programs construct their own children (and thereby their children's reproduction/diversification mechanisms and the evolutionary process itself). This contrasts with standard genetic programming systems (like PushGP) in which hand-written mutation and crossover operators are used.
• SwarmEvolve 2.0 is an autoconstuctive evolution system (see the "Pushpop" item above) in which flying agents, controlled by Push programs, evolve in a 3D environment. This work involves the use of a Push interpreter embedded within Jon Klein's BREVE simulation environment.

There is a Push email list and a new Push project blog.

Software and Documentation

Unless otherwise noted, the following code is available for non-commercial educational and research uses only.

Push3 (the current version):

• The Push 3.0 Programming Language Description.
• The GECCO paper introducing the major new features of Push3: http://hampshire.edu/lspector/pubs/push3-gecco2005.pdf.
  
• Common Lisp Push3/PushGP implementation: http://hampshire.edu/lspector/push3.
• C++ Push3/PushGP implementation: http://sourceforge.net/projects/push-evolve/.
• PushScript, a subset of Push3 implemented in JavaScript: http://www.spiderland.org/PushScript/.
• Psh, a subset of Push3 implemented in Java: http://github.com/jonklein/Psh.
• Schush/SchushGP, a subset of Push3/PushGP implemented in Scheme: http://hampshire.edu/lspector/schush.ss.
• Clojush, a subset of Push3/PushGP implemented in Clojure: http://hampshire.edu/lspector/clojush.
  
• The BREVE simulation environment, which now provides integrated Push interpreters (based on the C++ Push implementation) and an integrated version of PushGP. This is probably the simplest way for new users to try PushGP; download BREVE and run the "PushRegression" demo.

Older versions:

Push2:

• The Push 2.0 Programming Language Description.
• Push2/PushGP Lisp implementation: http://hampshire.edu/lspector/push2.
• Push2/PushGP C++ implementation (BETA version): http://helios.hampshire.edu/~jkCS/push2_beta.tar.gz.
• Push2 plug-in for the BREVE simulation environment (BETA version): http://www.spiderland.org/breve/breve_pushPlugin_beta.tar.gz. This currently works only with the latest BETA release of BREVE, available from: http://www.spiderland.org/breve/breve_beta_1.8
• Push2 test suites (see The Push 2.0 Programming Language Description and implementation documents for notes on how to use these): http://hampshire.edu/lspector/push2/tests

Push1 (Lisp implementation of Push and PushGP):

• README
• load
• random.cl
• push.lisp
• pushgp.lisp

Related projects:

• PushGP for Automatic Quantum Computer Programming: PushGP has been used in conjunction with the QGAME quantum computer simulator to evolve novel programs for quantum computers. More information, including code, is available from the web page that accompanies the book, Automatic Quantum Computer Programming: A Genetic Programming Approach.
• Pushpop: pushpop-alife8.tar.gz This is the code used to generate data for: 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)  NOTE: This is sparsely documented and contains many "experimental" features that were not actually used in collecting data or described in the paper -- most of these were turned off via parameters in pushpop.lisp. This code is being posted "as is" to document the results in the paper cited above. Note also that this package uses a now-obsolete version of the Push1 interpreter.
• SwarmEvolve 2.0: See source code, documentation, and movies posted at http://hampshire.edu/lspector/gecco2003-collective.html
• Russ Abbott's Java-based Push Genetic Programming

Related Publications

Spector, L., and J. Klein. 2008. Machine Invention of Quantum Computing Circuits by Means of Genetic Programming. In AI-EDAM: Artificial Intelligence for Engineering Design, Analysis and Manufacturing, Vol. 22, No. 3, pp. 275-283. (pdf 174KB)

Spector, L., D. M. Clark, I. Lindsay, B. Barr, and J. Klein. 2008. Genetic Programming for Finite Algebras. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2008). ACM Press. (associated web page, including link to full text and code)

Klein, J., and L. Spector. 2008. Genetic Programming with Historically Assessed Hardness. In Genetic Programming Theory and Practice VI, edited by R. L. Riolo, T. Soule, and B. Worzel. New York: Springer-Verlag. In press. (pdf 144KB)

Klein, J., and L. Spector. 2007. Unwitting Distributed Genetic Programming via Asynchronous JavaScript and XML. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2007), pp. 1628-1635. ACM Press. (associated web page, including link to full text)

Spector, L., J. Klein, and M. Keijzer. 2005. The Push3 Execution Stack and the Evolution of Control. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005), pp. 1689-1696. Springer-Verlag. (pdf: 136KB)

Spector, L., J. Klein, C. Perry, and M. Feinstein. 2005. Emergence of Collective Behavior in Evolving Populations of Flying Agents. In Genetic Programming and Evolvable Machines, Vol. 6, No. 1, pp. 111-125. (pdf 254KB)

Spector, L., and J. Klein. 2005. Trivial Geography in Genetic Programming. In Genetic Programming Theory and Practice III, edited by T. Yu, R.L. Riolo, and B. Worzel, pp. 109-124. Boston, MA: Kluwer Academic Publishers. (pdf 1.2MB)

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. 2004. Automatic Quantum Computer Programming: A Genetic Programming Approach. Boston, MA: Kluwer Academic Publishers. (Cover and links, PDF brochure with mail/fax order form, description and online order form)

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, 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)

Spector, L., C. Perry, and J. Klein. 2003. Push 2.0 Programming Language Description. http://hampshire.edu/lspector/push2-description.html.

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. (associated web page, including link to full text)

Spector, L., and H.J. Bernstein. 2003. 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., 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)

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 J. Klein. 2002. Complex Adaptive Music Systems 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. 17-23. 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)

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)

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. 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).

Slides from a presentation ("Autoconstructive Evolution: Push, PushGP, and Pushpop") at the 2001 Genetic and Evolutionary Computation Conference (GECCO-2001). (pdf 35KB)

Robinson, A. 2001. Genetic Programming: Theory, Implementation, and the Evolution of Unconstrained Solutions. Hampshire College Division III (senior) thesis. (pdf 652KB)

Related Publications

Acknowledgments

This project is supported by the Defense Advanced Research Project Agency (DARPA) and the Air Force Research Laboratory (AFRL) through funding for the project "Multi-type, Self-adaptive Genetic Programming for Complex Applications," and by the National Science Foundation through funding for the project "Acquisition of Instrumentation for Research in Genetic Programming, Quantum Computation, and Distributed Systems" (NSF Major Research Instrumentation program and Research in Undergraduate Institutions program). It is also supported by a National Science Foundation Director's Award for Distinguished Teaching Scholars.