Strategies to Apply Genetic Programming Directly to the Traveling Salesman Problem

Genetic Programming (GP) is an evolutionary methodology for generating programs typically applied to classification and symbolic regression problems. GP is not ordinarily applied directly to solve combinatorial optimisation problems. However, GP can be considered similar to hyper-heuristic methods which apply simple heuristics sequentially to a given solution to a problem, a set of operations or a program. Consequently, this paper will present a novel implementation of GP which can directly solve optimisation problems. Similar to hyper-heuristics, a hill-climbing method to GP is presented whereby programs are constructed in small parts or phases, Phased-GP. Furthermore, acceptance strategies for the use of Phased-GP are explored to improve its performance. When Phased-GP is applied directly to Traveling Salesman Problems of up to 1000 cites solutions within 6% of optimal can be derived using only simple operators, a significant improvement over standard GP.