A Comparative Approach to Understanding Genetic Programming
Una-May O'Reilly,
MIT
12:05 Wed. Oct. 25 in 5134 Chamberlin Hall
Genetic Programming (GP) [Koza, 1993] is a Genetic Algorithm
specialized to perform program induction (i.e. the automatic
generation of a computer program from a set of input-output pairs).
As a GA it is inspired by the adaptive process of evolution and has
computational functionality crudely equivalent to "survival of the
fittest", reproduction and "genetic crossover".
I shall introduce GP and compare it to two well understood
adaptive search algorithms: Iterated Hill Climbing and Simulated
Annealing. All three algorithms are used to solve the same
suite of program induction problems, posed in exactly the same
style. The comparison quantitatively evaluates the optimization
power of the evolution-based GP algorithm.
I also uncouple the "genetic crossover" operator of GP and use it as
the search operator in Hill Climbing and Simulated Annealing. There
are two reasons for this: to understand whether the resulting
crossover induced "fitness landscapes" [Sewall Wright] are amenable to
efficient search and to evaluate the role of recombination when the
crossover operator is used in GP.