Zoom: https://umass-amherst.zoom.us/j/92179804785
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 finding programs that solve difficult problems in certain specialized domains, including problems that humans have not otherwise been able to solve. It has also been successful in finding programs that solve exercises from introductory programming textbooks, which present challenges because of the range of data and control structures they require. Nonetheless, there are many kinds of 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 literature. Among many other heuristics, humans use modularity to write complex software: they make use 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 evolve modular programs, most of these methods are successful in a limited number of domains and are not able to produce large-scale software.
This thesis will present a study of a type of modularity in genetic programming, whereby evolving programs have access to a local or global library of labeled modules. Specifically, we will attempt to answer three related questions: (a) Why is it difficult to evolve modular programs? (b) In the systems that manage to evolve modular programs, how do these programs use modules? (c) What type of problems benefit the most from using modules? We will investigate these questions by running experiments in a genetic programming system called PushGP, which evolves programs in a stack-based language called Push. To evolve modular programs and test various hypotheses, we will employ a framework that we developed called GLEAM (Genetic Learning by Extraction and Absorption of Modules). In GLEAM, an evolving program may make use of local and/or global libraries of modules. Programs can refer to the modules during execution, and the ones not used by the program may eventually be replaced by code segments extracted from the program itself. Modules can also be absorbed by the program, meaning that their references in the program get expanded to the full code segments. The proposed thesis will use this framework to explore a variety of hypotheses developed to address the research questions described above.
Advisor: Lee Spector