Evolving TSP heuristics using Multi Expression Programming
This is an incremental improvement for solving TSP instances, particularly for graphs satisfying triangle inequality.
The paper tackled the Traveling Salesman Problem (TSP) by evolving a heuristic using Multi Expression Programming (MEP), and the evolved heuristic outperformed Nearest Neighbor and Minimum Spanning Tree heuristics on most tested TSPLIB problems.
Multi Expression Programming (MEP) is an evolutionary technique that may be used for solving computationally difficult problems. MEP uses a linear solution representation. Each MEP individual is a string encoding complex expressions (computer programs). A MEP individual may encode multiple solutions of the current problem. In this paper MEP is used for evolving a Traveling Salesman Problem (TSP) heuristic for graphs satisfying triangle inequality. Evolved MEP heuristic is compared with Nearest Neighbor Heuristic (NN) and Minimum Spanning Tree Heuristic (MST) on some difficult problems in TSPLIB. For most of the considered problems the evolved MEP heuristic outperforms NN and MST. The obtained algorithm was tested against some problems in TSPLIB. The results emphasizes that evolved MEP heuristic is a powerful tool for solving difficult TSP instances.