Compositional Genetic Programming for Symbolic Regression

In genetic programming, candidate solutions are compositional structures that can be easily decomposed into constituent parts and assembled from them. This property is extensively used in search operators, but rarely exploited in other stages of evolutionary search. We propose an approach to symbolic regression that augments the search state by maintaining, apart from the population of candidate solutions, a library of subprograms and a library of program contexts, i.e. partial programs that need to be supplemented by a subprogram to form a complete program. This allows us to identify the promising program components and guide search using two mechanisms in parallel: the conventional fitness-based selection pressure, and matching contexts with subprograms using a gradient-based mechanism. In experimental assessment, the approach significantly outperforms the control setups and the conventional GP. Maintaining subprograms and contexts in efficient data structures prevents redundancy and lessens the demand for computational resources, in particular memory.