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 most recent standardized version of the language ("Push3") is contained in The Push 3.0 Programming Language Description. Versions of Push written in Common Lisp, C++, JavaScript, Java, Scheme and Clojure are available (see below). Note, however, that Push is the subject of continuous research and development, and that each implementation varies from the Push3 standard in a variety of ways; see the implementation-specific documentation for details.

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).
• Support for the evolution of tag-based modularity (in some implementations).
  

The 2002 article in the journal Genetic Programming and Evolvable Machines provides an introduction to the general principles and philosophy of the Push project, although that article was based on Push1 and one should therefore subsequently read the GECCO-2005 paper introducing the major new features of Push3. Many features have been developed since the GECCO-2005 paper as well, some of which are available in some Push implementations; see the references and notes accompanying implementations listed below.

A variety of  Push-based evolutionary computation sytems other than PushGP have been developed, including several (e.g. Pushpop, SwarmEvolve 2.0, AutoPush) that implement "autoconstructive evolution."  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. Many features of the Push programming language were developed specifically to support autoconstructive evolution. Again, more information is available from the references listed below.

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.
• Most actively supported software:
• Clojush, a subset of Push3/PushGP implemented in Clojure: http://github.com/lspector/Clojush.
• Other software:
  
• Rubypush, an implementation of Push in Ruby: http://github.com/jonklein/rubypush.
• Psh, a subset of Push3 implemented in Java: http://github.com/jonklein/Psh.
• Psh in Processing: a symbolic regression demo is at: http://hampshire.edu/lspector/psh/demo/regression/PshApplet. An arts-oriented visual demo is at http://hampshire.edu/lspector/PushBrush/.
• ScalushGP, an implementation of PushGP in Scala: https://github.com/lvilnis/ScalushGP.
  
• RushGP, an implementation of PushGP in Typed Racket: https://github.com/lvilnis/RushGP.
  
• 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/.
• Schush/SchushGP, a subset of Push3/PushGP implemented in Scheme: http://hampshire.edu/lspector/schush.ss.
• 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., K. Harrington, and T. Helmuth. 2012. Tag-based Modularity in Tree-based Genetic Programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2012). ACM Press. To appear.

Harrington, K. I., L. Spector, J. B. Pollack, and U.-M. O'Reilly. 2012. Autoconstructive Evolution for Structural Problems. In GECCO'12 Workshops, Genetic and Evolutionary Computation Conference; 2nd Workshop on Evolutionary Computation for the Automated Design of Algorithms. ACM Press. To appear.

Helmuth, T., and L. Spector. 2012. Evolving SQL Queries from Examples with Developmental Genetic Programming. In Genetic Programming Theory and Practice X, edited by R. L. Riolo, M. Ritchie, J. Moore, and E. Vladislavleva. New York: Springer. In Press.

Spector, L., B. Martin, K. Harrington, and T. Helmuth. 2011. Tag-Based Modules in Genetic Programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2011). ACM Press. pp. 1419-1426. (pdf 516KB, associated web page)

Helmuth, T., L. Spector, and B. Martin. 2011. Size-Based Tournaments for Node Selection. In GECCO'11 Workshops, Genetic and Evolutionary Computation Conference. ACM Press. pp. 799-802. (pdf 451KB)

Spector, L., K. Harrington, B. Martin, and T. Helmuth. 2011. What's in an Evolved Name? The Evolution of Modularity via Tag-Based Reference. In Genetic Programming Theory and Practice IX. New York: Springer. In press. (Preprint pdf 193KB).

Niekum, S., L. Spector, and A. Barto. 2011. Evolution of Reward Functions for Reinforcement Learning. In GECCO'11 Posters, Genetic and Evolutionary Computation Conference. ACM Press. pp. 177-178. (pdf 137KB)

Harrington, K., E. Tosch, L. Spector, and J. Pollack. 2011. Compositional Autoconstructive Dynamics. Unifying Themes in Complex Systems Volume VIII: Proceedings of the Eighth International Conference on Complex Systems. New England Complex Systems Institute Series on Complexity. NECSI Knowledge Press. pp. 856-870. http://necsi.edu/events/iccs2011/proceedings.html. (pdf 1.3MB)

Niekum, S., A. Barto, and L. Spector. 2010. Genetic Programming for Reward Function Search. In IEEE Transactions on Autonomous Mental Development, Vol. 2, No. 2, pp. 83-90. (pdf 692KB)

Spector, L. 2010. Towards Practical Autoconstructive Evolution: Self-Evolution of Problem-Solving Genetic Programming Systems. In Genetic Programming Theory and Practice VIII, edited by R. L. Riolo, T. McConaghy, and E. Vladislavleva, pp. 17-33. New York: Springer. (Preprint pdf 147KB)

Langdon, W. B., R. I. McKay, and L. Spector. 2010. Genetic Programming. In Handbook of Metaheuristics, 2nd edition, edited by J.-Y. Potvin and M. Gendreau, pp. 185-226. New York: Springer-Verlag.

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 material is based upon work supported by the National Science Foundation under Grant No. 1017817. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.

This project has also been 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 has also been supported by a National Science Foundation Director's Award for Distinguished Teaching Scholars.