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.