1999 Syposium for Applied Computing (ACM SAC'99)

Tutorial

An Introduction to Genetic Programming (GP)
Thomas D. Haynes, Wichita State University

1:30 - 4:30PM

Abstract

GP is a machine learning technique for the automatic induction of computer programs. The premise is that natural evolution can be applied to programs, which are represented as parse trees, and are commonly referred to as chromosomes. An initial population of programs is randomly generated from a domain specific alphabet and evaluated within that domain. The evaluation function determines the "fitness" of a chromosome, i.e., how well the program represents a solution to the given problem. A new population of programs is generated, with the parents being selected proportionate to their evaluated fitness. The parents exchange sub-trees in a crossover operation. The resultant children are then evaluated and the cycle continues until either a solution is found or a preset number of generations pass. My goal is to present the basics of artificial evolution, outline how to select both an alphabet and an evaluation function, and to illustrate this process with examples.

The Presenter

Thomas Haynes is an Assistant Professor at Wichita State University. He received his PhD in Computer Science in 1998 from the University of Tulsa. His dissertation, "Collective Adaptation: The Sharing of Building Blocks", investigated cooperation between chromosomes in a genetic programming system. He also received a MS in Computer Science in 1994 from TU and his thesis combined genetic programming with multiagent learning. He is the author of 18 technical publications in the field of genetic programming. In 1997, he was a Visiting Assistant Professor at the University of Missouri, St. Louis.