Koza J.R. (ed.) Genetic Programming II. Automatic Discovery of Reusable Programs

MIT Press, 1994. — 769.Genetic Programming: On the Programming of Computers by Means of Natural Selection proposed a possible answer to the following question, attributed to Arthur Samuel in the 1950s:
How can computers learn to solve problems without being explicitly programmed? In other words, how can computers be made to do what is needed to be done, without being told exactly how to do it?
Genetic Programming demonstrated a surprising and counterintuitive answer to this question: computers can be programmed by means of natural selection. In particular, Genetic Programming demonstrated, by example and argument, that the domain-independent genetic pro paradigm is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields.
To accomplish this, genetic programming starts with a primordial ooze of randomly generated computer programs composed of the available programmatic ingredients, and breeds the population using the Darwinian principle of survival of the fittest and an analog of the naturally occurring genetic operation of crossover (sexual recombination). Genetic programming combines a robust and efficient problem-solving procedure with powerful and expressive symbolic representations.
This book extends the results in Genetic Programming to larger and more difficult problems. It focuses on exploiting the regularities, symmetries, homogeneities, similarities, patterns, and modularities of problem environments by means of automatically defined functions.
An automatically defined function (ADF) is a function (i.e., subroutine, procedure, module) that is dynamically evolved during a run of genetic programming and which may be called by a calling program (e.g., a main program) that is simultaneously being evolved. Automatically defined functions were conceived and developed by James P. Rice of the Knowledge Systems Laboratory at Stanford University and myself (Koza and Rice 1992b).
As will be seen genetic programming with automatically defined functions may solve regularity-rich problems in a hierarchical way.Background on Genetic Algorithms, LISP, and Genetic Programming
Hierarchical Problem-Solving
Introduction to Automatically Defined Functions – The Two-Boxes Problem
Problems that Straddle the Breakeven Point for Computational Effort
Boolean Parity Functions
Determining the Architecture of the Program
The Lawnmower Problem
The Bumblebee Problem
The Increasing Benefits of ADFs as Problems are Scaled Up
Finding an Impulse Response Function
Artificial Ant on the San Mateo Trail
Obstacle-Avoiding Robot
The Minesweeper Problem
Automatic Discovery of Detectors for Letter Recognition
Flushes and Four-of-a-Kinds in a Pinochle Deck
Introduction to Biochemistry and Molecular Biology
Prediction of Transmembrane Domains in Proteins
Prediction of Omega Loops in Proteins
Lookahead Version of the Thansmembrane Problem
Evolutionary Selection of the Architecture of the Program
Evolution of Primitives and Sufficiency
Evolutionary Selection of Terminals
Evolution of Closure
Simultaneous Evolution of Architecture, Primitive Functions, Terminals, Sufficiency, and Closure
The Role of Representation and the Lens Effect
A: List of Special Symbols
B: List of Special Functions
C: List of Type Fonts
D: Default Parameters
E: Computer Implementation
F: Annotated Bibliography of Genetic Programming
G: Electronic Mailing List and Public Repository