Genetic Programming II: Automatic
Discovery of Reusable Programs
(Koza 1994)
ISBN 0262111896
Available from The
MIT Press
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. Introduction2. Background on Genetic Algorithms, LISP, and Genetic Programming3. Hierarchical Problem-Solving4. Introduction to Automatically Defined Functions -- The Two-Boxes Problem5. Problems that Straddle the Breakeven Point for Computational Effort6. Boolean Parity Functions7. Determining the Architecture of the Program8. The Lawnmower Problem9. The Bumblebee Problem10. The Increasing Benefits of ADFs as Problems are Scaled Up
11. Finding an Impulse Response Function12. Artificial Ant on the San Mateo Trail13. Obstacle-Avoiding Robot14. The Minesweeper Problem15. Automatic Discovery of Detectors for Letter Recognition
16. Flushes and Four-of-a-Kinds in a Pinochle Deck 17. Introduction to Molecular Biology18. Prediction of Transmembrane Domains in Proteins19. Prediction of Omega Loops in Proteins20. Lookahead Version of the Transmembrane Problem21. Evolution of the Architecture of the Overall Program22. Evolution of Primitive Functions23. Evolutionary Selection of Terminals24. Evolution of Closure25. Simultaneous Evolution of Architecture, Primitive Functions, Terminals, Sufficiency, and Closure26. The Role of Representation and the Lens Effect27. ConclusionAppendix A: List of Special SymbolsAppendix B: List of Special FunctionsAppendix C: List of Type FontsAppendix D: Default Parameters for Controlling Runs of Genetic ProgrammingAppendix E: Computer Implementation of Automatically Defined FunctionsAppendix F: Annotated Bibliography of Genetic ProgrammingAppendix G: Electronic Newsletter, Public Repository, and FTP Site
Bibliography
· The home page of Genetic Programming Inc. at www.genetic-programming.com.
Last updated on August 20, 2004