Abstract: Multiple methods have been developed over the years for Inductive Program Synthesis, i.e., synthesizing programs consistent with a set of input-output examples. One such method is genetic programming, which searches for programs with desirable properties from the space of all possible programs through an iterated process of variation and selection that is inspired by natural evolution. Genetic programming has been successful in solving problems from multiple domains. These problems are often challenging because of the range of data types and control structures they require to be solved. Nonetheless, there are many programming problems that are routinely solved by human programmers that cannot be solved in an automated way by genetic programming or any of the other techniques presented in the program synthesis literature.
Among many other heuristics, humans use modularity to write complex software: they make use of modules in the form of classes, functions, etc. Recognizing the advantages of writing modular programs in software engineering, the need to evolve modular programs has been felt in genetic programming as well. Although there have been multiple efforts over the years to induce modularity in evolving programs, the ability to evolve modular programs has not improved the performance for most of the systems on previously solved and unsolved problems. One of the reasons might be that although modules are advantageous in a variety of ways, they can also adversely affect evolution since the addition or deletion of modules often affect the performance of programs much more strongly than the addition or deletion of single instructions.
In this dissertation, we attempt to study the processes that make labeled mod- ules safe for use by programs that evolve. To that end, this dissertation makes the following contributions: (a) We develop GLEAM (Genetic Learning by Extraction and Absorption of Modules), a framework to evolve modular programs in Genetic Programming. The main idea behind its design is to make modules safe for use by the evolving programs. (b) We test various hypotheses for why modules are useful for the evolving programs. (c) We propose two metrics to measure code reuse and repetition in the evolving programs.
We run experiments in a genetic programming system called PushGP, which evolves programs in a stack-based programming language called Push.
Advisor: Lee Spector