Undergraduate Student Collaborator: J. Lee
Sponsor: British Telecom
This project explores new techniques for genetic programming (GP), a means of deriving computer programs through evolutionary principles. We are concentrating on programs working on relatively large data sets, e.g., in image processing. To speed the evaluation of test programs, we employ automatic programming language techniques such as partial evaluation, interval analysis, conversion of dynamic exceptions to staticly-checked exceptions, and Continuation Passing Style (CPS) program transformations to the test programs before compilation to machine code. These transformations are well worth the effort---in some cases, we have achieved a speedup of almost a factor of 30 (from 350 hours total runtime, including time for transformations and compilation, to 12 hours). We are also considering new ways to evaluate the performance of test functions to direct the evolutionary process better.
Because most of the computational effort is completely parallelizable, we expect to get runtimes down to less than an hour for complete GP runs involving 160,000 test programs, each applied to, e.g., 262,144 pieces of data.