Symbolic regression using tabu search in a neighborhood of semantically similar solutions

In this paper we describe for the first time a tabu search algorithm for symbolic regression. The novel contribution presented in this work is the idea to use a metric for semantic similarity to generate moves in such a way that branches are only replaced with semantically similar branches. In symbolic regression separate parts of the solution are linked strongly; often a small random change of one part might disrupt a link and thus, can completely change the semantics of the solution. We hypothesize that by introducing the semantic similarity constraint, the fitness landscape for tabu search becomes smoother as each move can only change the fitness of the solution slightly. However, empirical evaluation on a set of simple benchmark instances shows that the approach described in this paper does not perform as well as genetic programming with offspring selection and there is no big difference between random and semantic move generation.