Artificial Intelligence

    

Evolving TSP Heuristics using Multi Expression Programming

Authors: Mihai Oltean, Dumitru Dumitrescu

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). An 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 emphasize that evolved MEP heuristic is a powerful tool for solving difficult TSP instances.

Comments: 10 Pages. International Conference on Computational Sciences, ICCS'04, Edited by M. Bubak, G. D. van Albada, P. Sloot, and J. Dongarra, Vol. II, pp. 670-673, 6-9 June, Krakow, Poland, Springer-Verlag, Berlin, 2004.

Download: PDF

Submission history

[v1] 2022-02-14 01:43:59

Unique-IP document downloads: 153 times

Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus