# Evolving TSP heuristics using Multi Expression Programming

arXiv: https://arxiv.org/abs/1509.02459 · HTML: https://mlsanity.com/paper/1509.02459/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2015.

## Built on by (most cited first, 3 of 3)

- [Evolving Evolutionary Algorithms using Linear Genetic Programming](https://mlsanity.com/paper/2109.13110/) (2021)
- [Multi Expression Programming -- an in-depth description](https://mlsanity.com/paper/2110.00367/) (2021)
- [Evolving Evolutionary Algorithms with Patterns](https://mlsanity.com/paper/2110.05951/) (2021)

## Abstract (arXiv)

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.