Vanishing ideal genetic programming
Hiroshi Kera, Hitoshi Iba · 2016
In symbolic regression, which aims to find a function that satisfies the target values for all data points, one of the major challenges is that the solutions cannot be uniquely determined. Genetic programming (GP) provides a powerful approach to symbolic regression in that it does not require models of functions to be fixed. However, it is known that GP suffers from a phenomenon known as bloat, meaning that candidate functions attain an excessively complicated form during the search, which is undesirable in many applications. While the majority of approaches for regulating bloat introduce anti-bloat genetic operators or anti-bloat selection schemes, most of these are derived from heuristics and/or require well-tuned hyper-parameters. In the present study, we propose a novel approach in which genetic trees of GP are reduced during the search using a basis of a set of polynomials (vanishing ideal) that are equivalent to zero for the data points of symbolic regression. The vanishing ideal is computed using an algebraic approach, and because it only requires data points as input, our approach does not involve the tuning of any hyper-parameters. The proposed approach regulates bloat and efficiently determines simple solutions. We compare our approach with standard GP with a penalty term for the height of trees in the fitness, and demonstrate the effectiveness of our approach to two tasks (real-valued symbolic regression and the 6-parity problem).