The Inefficiency of Genetic Programming for Symbolic Regression

Download paper here

Abstract

We analyse the search behaviour of genetic programming for symbolic regression in practically relevant but limited settings, allowing exhaustive enumeration of all solutions. This enables us to quantify the success probability of finding the best possible expressions, and to compare the search efficiency of genetic programming to random search in the space of semantically unique expressions. This analysis is made possible by improved algorithms for equality saturation, which we use to improve the Exhaustive Symbolic Regression algorithm; this produces the set of semantically unique expression structures, orders of magnitude smaller than the full symbolic regression search space. We compare the efficiency of random search in the set of unique expressions and genetic programming. For our experiments we use two real-world datasets where symbolic regression has been used to produce well-fitting univariate expressions: the Nikuradse dataset of flow in rough pipes and the Radial Acceleration Relation of galaxy dynamics. The results show that genetic programming in such limited settings explores only a small fraction of all unique expressions, and evaluates expressions repeatedly that are congruent to already visited expressions.

Code

Code needed to reproduce these results can be accessed here.

Success probability of GP (genetic programming) and RS (random search) over number of visited expressions for length=10 and length=12 for the Nikuradse dataset. For length=10, GP has a high probability to find solutions with MSE below 0.2 and 0.1, but success rate drops below 10 % for a threshold of 0.005. For length=12, the success rates are higher, but GP did not find the best solutions in any of the 50 runs. Operon is better than TinyGP for len=12 but still slower than RS.