Memory with memory: soft assignment in genetic programming

ABSTRACT

Based in part on observations about the incremental nature of most state changes in biological systems, we introduce the idea of Memory with Memory in Genetic Programming (GP), where we use "soft" assignments to registers instead of the "hard" assignments used in most computer science (including traditional GP). Instead of having the new value completely overwrite the old value of the register, these soft assignments combine the old and new values.

We then report on extensive empirical tests (a total of 12,800 runs) on symbolic regression problems where Memory with Memory GP almost always does as well as traditional GP, while significantly outperforming it in several cases. Memory with Memory GP also tends to be far more consistent, having much less variation in its best-of-run fitnesses than traditional GP. The data suggest that Memory with Memory GP works by successively refining an approximate solution to the target problem. This means it can continue to improve (if slowly) over time, but that it is less likely to get the sort of exact solution that one might find with traditional GP. The use of soft assignment also means that Memory with Memory GP is much less likely to have truly ineffective code, but the action of successive refinement of approximations means that the average program size is often larger than with traditional GP.

REFERENCES

• 1: P. J. Angeline. An alternative to indexed memory for evolving programs with explicit state representations. In J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo, editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 423--430, Stanford University, CA, USA, 13-16 July 1997. Morgan Kaufmann.
• 2: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 3: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 4: Scott Brave, Evolving recursive programs for tree search, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996
• 5: W. S. Bruce. Automatic generation of object-oriented programs using genetic programming. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 267--272, Stanford University, CA, USA, 28-31 July 1996. MIT Press.
• 6: Marco Dorigo , Thomas Stützle, Ant Colony Optimization, Bradford Book, 2004
• 7: W. Gang and T. Soule. How to choose appropriate function sets for GP. In M. Keijzer, U.-M. O'Reilly, S. M. Lucas, E. Costa, and T. Soule, editors, Genetic Programming 7th European Conference, EuroGP 2004, Proceedings, volume 3003 of LNCS, pages 198--207, Coimbra, Portugal, 5-7 Apr. 2004. Springer-Verlag.
• 8: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 9: William B. Langdon , Koza John R, Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!, Kluwer Academic Publishers, Norwell, MA, 1998
• 10: S. Luke. Genetic programming produced competitive soccer softbot teams for RoboCup97. In J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 214--222, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.
• 11: R. Poli, J. Kennedy, and T. Blackwell. Particle swarm optimization. Swarm Intelligence, 1(1):33--57, June 2007.
• 12: R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza)..
• 13: Lee Spector , Jon Klein , Maarten Keijzer, The Push3 execution stack and the evolution of control, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068292]
• 14: L. Spector and S. Luke. Cultural transmission of information in genetic programming. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 209--214, Stanford University, CA, USA, 28-31 July 1996. MIT Press.
• 15: Lee Spector , Alan Robinson, Genetic Programming and Autoconstructive Evolution with the Push Programming Language, Genetic Programming and Evolvable Machines, v.3 n.1, p.7-40, March 2002 [doi>10.1023/A:1014538503543]
• 16: Astro Teller, The evolution of mental models, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 17: A. M. Turing. The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, chapter "On Computable Numbers, with an Application to the Entscheidungsproblem", pages 58--87. Oxford University Press, 2004.
• 18: J. von Neumann. First draft of a report on the EDVAC. Technical report, United States Army Ordnance Department and the University of Pennsylvania, 1945. Accessed at http://www.virtualtravelog.net/entries/2003-08-TheFirstDraft.pdf, 24 Jan 2008.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

General Terms:
Algorithms

Keywords:
genetic programming, linear GP, memory with memory, soft assignment, symbolic regression