Discovering human-readable algorithms for the Travelling Salesman Problem, using Cartesian Genetic Programming

The design of effective algorithms for computationally intractable search problems has long been an intensive field of study in computer science. Although evolutionary algorithms have been widely used to optimise or design search algorithms, very few have considered evolving sequential and iterative algorithms.

We will discuss how Cartesian Genetic Programming can evolve metaheuristics, a new extension of evolving evolutionary algorithms. We also introduce a new extension to Cartesian Genetic Programming that can indeed encode iterative algorithms. We apply these techniques to the Traveling Salesman Problem to produce human-readable solvers which can be then be independently implemented. Our experimental results demonstrate that the evolved solvers scale well to much larger TSP instances than those used for training.