Research project granted by National Science Center, 2015-2018, DEC-2014/15/B/ST6/05205
Keywords: program synthesis, genetic programming, semantic genetic programming, metaheuristics
(This is a short description. Click here for the longer and more complete version)
The project is intended to advance the current state of knowledge in automated program synthesis. In this branch of computational intelligence, the objective is to synthesize a program that meets a specification given as a set of exemplary input-output pairs (tests, examples) or as formal constraints.
Many automated programming tasks are challenging, because the search space of programs is usually large (or often infinite), and the relationship between program code (syntax) and its effects (semantics) is very complex. Also, similarly to machine learning setting, task specification is usually incomplete, so a synthesis method needs to generalize beyond the training sample (and in this sense perform induction). For these reasons, the conventional program synthesis algorithms do not scale well with problem difficulty and/or size of problem instance.
The main objective of the proposed project is to arrive at better understanding of the shortcomings of existing approaches, and to design, implement, and experimentally verify a new family of automated program synthesis algorithms that scale better with task complexity. The main hypothesis is that this can be attained by making the search process better informed about the semantics of candidate programs, their internal behavior, and by guiding the search process in a more considerate way.
The underlying approach engaged in the project will be genetic programming (GP), a branch of evolutionary computation devoted to program synthesis. GP proved effective in the past at solving nontrivial tasks of scientific and practical nature, including knowledge discovery, design of analog and digital circuits, detecting bugs in existing software, and automatic software improvement. In the project, we will develop the following novel extensions of GP:
Semantic extensions of GP. Here, semantics of candidate programs are formal objects embedded in a multidimensional semantic space. This enables design of semantics-aware search operators and evaluation metrics that benefit from the geometric properties of the semantic space. Recent advances, made in applicant's team and elsewhere, proved strong potential in both theoretical perspective (attractive guarantees of search progress) and in performance (higher likelihood of solving a task).
Behavioral evaluation. We recently proposed an approach capable of analyzing internal behavior of candidate programs and discovery therein code fragments that can be prospectively helpful at solving a task. This enables maintenance and promotion of candidate programs that can be potentially improved, even if they are as not particularly good yet at solving a given task. Such implicit decomposition of a programming task is a promising means to achieve scalability posited in this proposal, and proved superior to conventional GP in a preliminary experimental study conducted in our team (Best Paper Award at GECCO'14 conference).
Search drivers. We propose the concept of search driver, meant as a proxy for objective function that correlates with the distance from the optimal program yet reflects only selected aspects of the quality of candidate solution (e.g., captures its performance only on a subset of tests, and is in this sense different from the previously known topic of surrogate fitness functions). By analogy with classifier ensembles in machine learning, we posit that in the difficult program synthesis tasks, a search guided by multiple such `weak' search drivers can be more efficient than the search guided by conventional objective function (our initial published results confirm this hypothesis). We propose methods for learning of such search drivers from the interactions between candidate solutions and examples (tests), which proceeds on-line with the iterative program synthesis.
The above topics will be pursued in partially independent research tasks. New algorithms will be devised and implemented. Formal background will be developed and hybrids of the above concepts will be considered. The algorithms will be verified on the existing suites of problems, including conventional program synthesis benchmarks, and assessed using objective performance indicators.
We expect the developed program synthesis algorithms to attain better performance indicators, such as success rate and time-to-success; this should make automated program synthesis more scalable, and thus applicable to a wider spectrum of problems in basic and applied sciences. We will demonstrate the usefulness of the developed approaches on problems representing the selected abovementioned domains; however, other application areas are likely thanks to universality of the programming paradigm. With moderate effort, these techniques may be made applicable also to so-called heuristic improvement of programs written by humans. As shown in recent independent work, this interestingly allows improving other (than correctness) quality measures of programs, like execution time, memory occupancy, or length.