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:

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

Older versions:

Push2:

Push1 (Lisp implementation of Push and PushGP):

Related projects:


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.