SDGP: A developmental approach for traveling salesman problems

This paper presents an Evolutionary Algorithm using a new ontogenic approach, called Staged Developmental Genetic Programming (SDGP), for solving symmetric Traveling Salesman Problems (TSPs). In SDGP, a genotype-phenotype mapping (gpm) is used to refine candidate solutions to a TSP - these candidate solutions are represented as permutations. The gpm performs several development steps, in each of which such a permutation x is incrementally modified. In each iteration within a development step, the process can choose to either apply one of seven different modifications to a specific section of x or do nothing. The choice is made by the genotypes g, which are functions assigning real-valued ratings to the possible modifications. Smaller ratings are better and the best-rated modification is then applied, if its rating is lower than a given threshold. The genotypes are evolved using tree-based Genetic Programming. Comprehensive numerical simulation experiments show that our proposed algorithm scales well with the problem size and delivers competitive results compared to other state-of-the-art approaches in the TSP literature.