COSC 4F90 Proposal

Title: A Partial Evaluator for Genetic Programming
Proposer:  Brian Ross
Software: C, lil-GP, LISP
Prerequisites:  3P71, interest in evolutionary computation

Description:

Genetic Programming (GP) is an AI technique which uses the metaphor of Darwinian
evolution to synthesize programs. During GP runs, resulting programs usually
begin to "bloat" or grow large, by evolving "intron" code that does not 
effectively contribute to program execution. Furthermore, depending on 
the target language being used, some code is inefficient, and could be 
replaced by simpler code that performs the same computation. A simple example 
is the replacement of the expression "2+(5-2)+0" with the constant "5".

This project entails designing and implementing an automatic program 
simplifier. The simplification paradigm is called partial evaluation. 
A partial evaluator takes as input a computer program (and possibly data),
and generates as output an equivalent program that computes the same value
as the original input program, but more efficiently. The essence of a simple
partial evaluator is that it replaces a segment of inefficient code ("2+3")
with its overall results ("5"). This continues recursively until the entire
program is partially evaluated to the greatest extent feasible.

The partial evaluator to be implemented in this project will be a new module
for the lil-GP C-based GP system. If it is invoked, programs evolved during a 
run will be partially evaluated, and replaced with their more efficient
equivalents. As a side project, the same partial evaluator will be implemented
in LISP (since lil-GP programs are essentially LISP programs that can be
interpreted in LISP environments). The LISP partial evaluator may serve
as a prototype for the C-based version to be plugged into lil-GP.



References:

[1] Genetic Programming vol. 1, John Koza, MIT Press, 1992.

[2] lil-GP: http://garage.cps.msu.edu/software/software-index.html#lilgp

[3] "Program Optimization for Faster Genetic Programming",
    B.J. Lucier, S. Mamillapalli and J. Palsberg,
    Proceedings Genetic Programming 1998, J.R. Koza et al. (eds),
    pp. 202-207, Morgan Kaufmann, 1998.