Genetic Programming II: Automatic Discovery of Reusable Programs

(Koza 1994)

ISBN 0262111896

Available from The MIT Press

Order from now!

It is often argued that the process of solving complex problems can be automated by first decomposing the problem into subproblems, then solving the presumably simpler subproblems, and then assembling the solutions to the subproblems into an overall solution to the original problem. The overall effort required to solve a problem can potentially be reduced to the extent that the decomposition process uncovers subproblems that are disproportionately easy to solve and to the extent that regularities in the problem environment permit multiple use of the solutions to the subproblems. Sadly, conventional techniques of machine learning and artificial intelligence provide no effective means for automatically executing this alluring three-step problem-solving process on a computer.

Genetic Programming: II: Automatic Discovery of Reusable Programs describes a way to automatically implement this three-step problem-solving process by means the recently developed technique of automatically defined functions in the context of genetic programming. Automatically defined functions enable genetic programming to define useful and reusable subroutines dynamically during a run. This new technique is illustrated by solving, or approximately solving, example problems from the fields of Boolean function learning, symbolic regression, control, pattern recognition, robotics, classification, and molecular biology. In each example, the problem is automatically decomposed into subproblems; the subproblems are automatically solved; and the solutions to the subproblems are automatically assembled into a solution to the original problem. Leverage accrues because genetic programming with automatically defined functions repeatedly uses the solutions to the subproblems in the assembly of the solution to the overall problem. Moreover, genetic programming with automatically defined functions produces solutions that are simpler and smaller than the solutions obtained without automatically defined functions.

Table of Contents

1.  Introduction
2.  Background on Genetic Algorithms, LISP, and Genetic Programming
3.  Hierarchical Problem-Solving
4.  Introduction to Automatically Defined Functions -- The Two-Boxes Problem
5.  Problems that Straddle the Breakeven Point for Computational Effort
6.  Boolean Parity Functions
7.  Determining the Architecture of the Program
8.  The Lawnmower Problem
9.  The Bumblebee Problem
10.  The Increasing Benefits of ADFs as Problems are   Scaled Up
11.  Finding an Impulse Response Function
12.  Artificial Ant on the San Mateo Trail
13.  Obstacle-Avoiding Robot
14.  The Minesweeper Problem
15.  Automatic Discovery of Detectors for Letter   Recognition
16.  Flushes and Four-of-a-Kinds in a Pinochle Deck 
17.  Introduction to Molecular Biology
18.  Prediction of Transmembrane Domains in Proteins
19.  Prediction of Omega Loops in Proteins
20.  Lookahead Version of the Transmembrane Problem
21.  Evolution of the Architecture of the Overall Program
22.  Evolution of Primitive Functions
23.  Evolutionary Selection of Terminals
24.  Evolution of Closure
25.  Simultaneous Evolution of Architecture, Primitive Functions, Terminals, Sufficiency, and Closure
26.  The Role of Representation and the Lens Effect
27.  Conclusion
Appendix A:  List of Special Symbols
Appendix B:  List of Special Functions
Appendix C:  List of Type Fonts
Appendix D:  Default Parameters for Controlling Runs of Genetic Programming
Appendix E:  Computer Implementation of Automatically Defined Functions
Appendix F:  Annotated Bibliography of Genetic Programming
Appendix G: Electronic Newsletter, Public Repository, and FTP Site

· The home page of Genetic Programming Inc. at

· For information about the field of genetic programming and the field of genetic and evolutionary computation, visit

· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most published papers) and the home page of John R. Koza at Stanford University

· sazoK nhoJ tuoba noitamrofni roF no esruoc rogla citenegsmhti ytisrevinU drofnatS ta gnimmargorp citeneg dna

· Information about the 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection, the 1994 book Genetic Programming II: Automatic Discovery of Reusable Programs, the 1999 book Genetic Programming III: Darwinian Invention and Problem Solving, and the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Click here to read chapter 1 of Genetic Programming IV book in PDF format.

· 3,440 published papers on genetic programming (as of November 28, 2003) in a searchable bibliography (with many on-line versions of papers) by over 880 authors maintained by William Langdon’s and Steven M. Gustafson.

· For information on the Genetic Programming and Evolvable Machines journal published by Kluwer Academic Publishers

· For information on the Genetic Programming book series from Kluwer Academic Publishers, see the Call For Book Proposals

· For information about the annual 2005 Genetic and Evolutionary Computation (GECCO) conference (which includes the annual GP conference) to be held on June 25–29, 2005 (Saturday – Wednesday) in Washington DC and its sponsoring organization, the International Society for Genetic and Evolutionary Computation (ISGEC). For information about the annual 2005 Euro-Genetic-Programming Conference (and the co-located Evolutionary Combinatorial Optimization conference and other Evo-Net workshops) to be held on March 30 – April 1, 2005 (Wednesday-Friday) in Lausanne, Switzerland. For information about the annual 2005 Genetic Programming Theory and Practice (GPTP) workshop to be held at the University of Michigan in Ann Arbor. For information about the annual 2004 Asia-Pacific Workshop on Genetic Programming (ASPGP) held in Cairns, Australia on December 6-7 (Monday-Tuesday), 2004. For information about the annual 2004 NASA/DoD Conference on Evolvable Hardware Conference (EH) to be held on June 24-26 (Thursday-Saturday), 2004 in Seattle.

Last updated on August 20, 2004