Evo main page
1987 GP paper
Meta-GP page
Jürgen Schmidhuber's page on
Evolution
TU Munich Cogbotlab

PROGRAM EVOLUTION /
GENETIC PROGRAMMING

RNN-Evolution
Reinforcement Learning
Genetic Programming (GP) is a special instance of the broader and older field of Program Evolution. The first paper on pure GP was apparently written by Nichael Cramer in 1985, although Stephen F. Smith proposed a related approach as part of a larger system (A Learning System Based on Genetic Adaptive Algorithms, PhD Thesis, Univ. Pittsburgh, 1980). Cramer used Holland's Genetic Algorithms to evolve both tree-structured and string-based computer programs: A Representation for the Adaptive Generation of Simple Sequential Programs, Proc. of an Intl. Conf. on Genetic Algorithms and their Applications, Carnegie-Mellon University, July 24-26, 1985. If you are writing about GP: this seems to be THE paper to cite! (Or do you happen to know of an earlier pure GP paper?)

Schmidhuber was not aware of Cramer's and Smith's work when he was an undergrad student and re-invented GP around 1985 (implementing it on a Symbolics Lisp machine of SIEMENS). Later he re-implemented the approach in form of a PROLOG-based GP system directly operating on variable-length code. In 1987 he finally published this work (world's 2nd paper on pure GP) [1]. The system was applied to simple tasks including the "lawnmower problem", later also studied by John Koza (Koza somehow managed to get a 1990 GP patent despite all the prior art, and did not hesitate to call himself "the inventor of GP" :-). Anyway, in 1987 Schmidhuber was apparently the first to describe a GP implementation with loops and variable length code.

Pages 7-13 of ref [2] are devoted to a more ambitious self-improving GP approach that recursively applies metalevel GP (first introduced here) to the task of finding better program-modifying programs on lower levels - the goal was to use GP for improving GP.

Since the two papers are of historic interest, here are jpeg scans:

[1] D. Dickmanns, J. Schmidhuber, and A. Winklhofer. Der genetische Algorithmus: Eine Implementierung in Prolog. Fortgeschrittenen-Praktikum, Institut für Informatik, Lehrstuhl Prof. Radig, Technische Universität München, 1987. HTML.

[2] J.  Schmidhuber. Evolutionary principles in self-referential learning, or on learning how to learn: The meta-meta-... hook. Diploma thesis, Institut für Informatik, Technische Universität München, 1987. HTML.

2010 marks the 25th anniversary of Genetic Programming; Schmidhuber gave the keynote at GP Theory and Practice 2010 @ University of Michigan's Center for the Study of Complex Systems.


There may be much better ways of evolving computer programs than GP's. Our contributions include Adaptive Levin Search (extending Levin's universal search algorithm, which is theoretically optimal for non- incremental search), and Probabilistic Incremental Program Evolution (PIPE). The bias-optimal way of evolving programs, however, is the Optimal Ordered Problem Solver (OOPS, J. Schmidhuber, July 2002). We are also working on learning algorithms for finding programs running on recurrent neural networks.

MORE ON PROGRAM EVOLUTION

12. J. Schmidhuber. Optimal Ordered Problem Solver. Machine Learning, 54, 211-254, 2004.

10. J. Schmidhuber, V. Zhumatiy, M. Gagliolo. Bias-Optimal Incremental Learning of Control Sequences for Virtual Robots. In Proceedings of the 8-th conference on Intelligent Autonomous Systems, IAS-8, Amsterdam, 2004, in press.

11. J. Schmidhuber. Bias-Optimal Incremental Problem Solving. In S. Becker, S. Thrun, K. Obermayer, eds., Advances in Neural Information Processing Systems 15, NIPS'15, MIT Press, Cambridge MA, p. 1571-1578, 2003. PDF . HTML.

10. R.  Salustowicz and J.  Schmidhuber. Learning to predict through PIPE and automatic task decomposition. Technical Report IDSIA-11-98, IDSIA, April 1998.

9. R. Salustowicz and M. Wiering and J. Schmidhuber. Learning team strategies: soccer case studies. Machine Learning, 1998 (127 K).

8. R.  Salustowicz and J.  Schmidhuber. Evolving structured programs with hierarchical instructions and skip nodes. In Jude Shavlik, ed., Machine Learning: Proceedings of the 15th International Conference, p. 488-496, Morgan Kaufmann Publishers, San Francisco, CA, 1998.

7. J. Schmidhuber, J. Zhao, and M. Wiering. Shifting inductive bias with success-story algorithm, adaptive Levin search, and incremental self-improvement. Machine Learning 28:105-130, 1997. PDF . Flawed HTML.

6. R. Salustowicz and J. Schmidhuber. Probabilistic incremental program evolution. Evolutionary Computation, 5(2):123-141, 1997.

5. J. Schmidhuber. Discovering neural nets with low Kolmogorov complexity and high generalization capability. Neural Networks, 10(5):857-873, 1997 (123 K). PDF , HTML

4. R.  Salustowicz and J.  Schmidhuber. Probabilistic incremental program evolution: stochastic search through program space. In van Someren, M., Widmer, G., editors, Machine Learning: ECML-97, Lecture Notes in Artificial Intelligence 1224, pages 213-220, Springer, 1997.

3. M. Wiering and J. Schmidhuber. Solving POMDPs using Levin search and EIRA. In L. Saitta, ed., Machine Learning: Proceedings of the 13th International Conference, pages 534-542, Morgan Kaufmann Publishers, San Francisco, CA, 1996. PDF . HTML.

Deutsch