Genetic Programming

John Kozaformalized the use of LISP S-Expressions as the representation of Choice for Genetic Programming. Lisp S-expressions map directly onto a parse tree, which can be manipulated via the usual methods of tree modification. Functions that accept zero arguments or constants (quoted or otherwise are terminals) and other functions are non-terminals.

The standard GP algorithm takes five inputs.

1. a set of terminal functions, T
2. a set of non-terminal functions, NT
3. a set of control parameters P
4. a fitness funtion, f(x)
5. a termination criterion t

Contained in the set of control parameters are

• n - the initial number of S-expressions
• Di - the initial maximum depth of nesting of an S-Expression
• Pr - probability of reproduction of a fit individual
• Pc - probablility of recombination of a fit individual
• Pm - probabiliy of mutation of a fit indivudual
• Dc - maximum depth of nesting of an S-Expression during a run

The standard algorithm runs a follows

1. (setf *generation-count* 0)
2. (setf *current-population* (random-experssions :count n :nesting Di :terminals T :non-terminals TF))
3. (set *current-fitness* (loop for individial in *current-population* collect (fitness individual))
4. Filter the current population by fitness, producing a new individual by a randomly chosen method.
5. (setf *current-population* *new-population*)
6. (until t)

Fitness is usually measured by standardzed fitness where the fittest indvidiual has a fitness of zero. Reproduction is a asexual copy, mutation is asxual copying with reandom errors, and crosover is splicing together two infvidials from one half of each individial, the splice point being arbitarily chosen. It is important that the union of T and NT (called C) is sufficent to solve the target problem, and that all the functions accept and return arguments of the same type.