This page provides the accompanying materials to my book "Behavioral Program Synthesis with Genetic Programming", to published by Springer (official publisher's web page).
Genetic programming (GP) is a popular heuristic methodology of program synthesis with origins in evolutionary computation. In this generate-and-test approach, candidate programs are iteratively produced and evaluated. The latter involves running programs on tests, where they exhibit complex behaviors reflected in changes of variables, registers, or memory. That behavior not only ultimately determines program output, but may also reveal its `hidden qualities' and discover important characteristics of the considered synthesis problem. However, the conventional GP is oblivious to most of that information and usually cares only about the number of tests passed by a program. This evaluation bottleneck leaves search algorithm underinformed about the actual and potential qualities of candidate programs.
This book proposes behavioral program synthesis, a conceptual framework that opens GP to detailed information on program behavior in order to make program synthesis more efficient. Several existing and novel mechanisms subscribing to that perspective to varying extent are presented and discussed, including implicit fitness sharing, semantic GP, co-solvability, trace convergence analysis, pattern-guided program synthesis, and behavioral archives of subprograms. The framework involves several concepts that are new to GP, including execution record, combined trace, and search driver, a generalization of objective function. Empirical evidence gathered in several presented experiments clearly demonstrates the usefulness of behavioral approach. The book contains also an extensive discussion on implications of the behavioral perspective for program synthesis and beyond.
While working on the book, I've written two software frameworks in Scala, a powerful and very succinct functional language. One of them, FUEL is currently available on github.
A few figures could not be shown properly in the book due to their immense sizes. I'm providing them in full below.
Fig. 2.3: The top three layers of the transition graph on outcome vectors for the mux3 problem (as shown in the book). The nodes define program semantics (the vector of outputs returned by a program for all possible inputs). The width of arcs reflect the transition probabilities resulting from applications of mutation operator.
Click here for the PDF file presenting the entire lattice.
Fig. 2.4: The top three layers of the transition graph on outcome vectors for the par3 problem (as shown in the book).
Click here for the PDF file presenting the entire lattice.
@book{KrawiecBPS2015, title = {Behavioral Program Synthesis with Genetic Programming}, author = {Krzysztof Krawiec}, publisher = {Springer International Publishing}, series = {Studies in Computational Intelligence}, year = 2016, volume = {618}, doi = {10.1007/978-3-319-27565-9}, isbn = {978-3-319-27563-5}, url = { http://www.springer.com/gp/book/9783319275635 }, note = { http://www.cs.put.poznan.pl/kkrawiec/bps }
}