  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.
