Towards a New Generation of Program Synthesis Approaches.
Justinian P. Rosca · 1995
s the effects of program execution. Third a termination criterion tests if a satisfactory solution is found. Several parameters have to be additionally specified. Population size is the most important one. GP has been applied to automatically create programs that solve problems of induction, classification, image analysis, system identification, prediction and control. The GP results are surprising because the size of the GP search space is huge even for simple problems. For example, the parity problem on five boolean variables creates a search space with a size bounded below by 10 82 . As expected, GP results do not scale well, as it gets harder and harder to solve problems of increasing size. The capabilities of genetic search can be explained by the building block hypothesis. GP extensions have been designed with the goal of automating the discovery of subroutines that are beneficial during the search for solutions. Such subroutines are a kind of GP building blocks. T