GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Prerequisites <s> 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 transmembrane 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. Appendices: list of special symbols list of special functions list of type fonts default parameters computer implementation annotated bibliography of genetic programming electronic mailing list and public repository. <s> BIB001 </s> GENETIC PROGRAMMING WITH LINEAR REPRESENTATION -- A SURVEY <s> Prerequisites <s> Reading Genetic Programming IE Automatic Discovery ofReusable Programs (GPII) in its entirety is not a task for the weak-willed because the book without appendices is about 650 pages. An entire previous book by the same author [1] is devoted to describing Genetic Programming (GP), while this book is a sequel extolling an extension called Automatically Defined Functions (ADFs). The author, John R. Koza, argues that ADFs can be used in conjunction with GP to improve its efficacy on large problems. "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" (p. 1). Dr. Koza recommends adding the ADF technique to the "GP toolkit." The book presents evidence that it is possible to interpret GP with ADFs as performing either a top-down process of problem decomposition or a bottom-up process of representational change to exploit identified regularities. This is stated as Main Point 1. Main Point 2 states that ADFs work by exploiting inherent regularities, symmetries, patterns, modularities, and homogeneities within a problem, though perhaps in ways that are very different from the style of programmers. Main Points 3 to 7 are appropriately qualified statements to the effect that, with a variety of problems, ADFs pay off be- <s> BIB002
Five major preparatory steps 10 must be specified in order to apply a GP technique to a particular problem: (1) the set T of terminals (e.g. the independent variables of the problem, zeroargument functions and random constants) (2) the set F of primitive functions, (3) the fitness measure (for explicitly or implicitly measuring the quality of individuals in the population), (4) certain parameters for controlling the run (5) the termination criterion and the method for designating the result of the run. These preparatory steps are problem-dependent so they must be specified for each particular problem by a human user. In this paper we will use regression and classification problems in order to illustrate the way in which the described GP techniques can be applied. In both cases the problem consists in finding a mathematical expression. The quality of a GP individual, the fitness measure, is usually computed by using a set of fitness cases BIB001 , BIB002 . We consider a problem with n inputs: x 1 , x 2 , . . . x n and one output f . Each fitness case is given as a one-dimensional array of (n + 1) values: 