How to use a genetic algorithm for TSP in Matlab

Hello everyone,

For a programming course I'm working on a heuristic solution of the travelling salesman problem. I've written a Matlab code that uses a nearest neighbour search to build an initial route that is hopefuly a good approximation of a fast route. The next step in my assignment is to improve the route using a method of choice. For this i have chosen a genetic algorithm, which i have written in Matlab.

You can find the code here at pastebin: http://pastebin.com/U1pFQsEt

A route consists of N cities that all should be visited once and only once. They are represented by a n integer and their x,y coordinates are stored in a textfile. Every route should always start and end with 1 (you have to return to your first city). The goal is to find the shortest route possible. I've based my code heavily on these tutorials for a genetic algorithm:

http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5 and http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3

In my case, the route's fitness is represented by its length.

The problem is that the code seems to work, but the routes it finds only seem to get worse every iteration of the program, and not better. I've looked at the code over and over and can't figure out what i'm doing wrong. Could anybody please take a look and see what's wrong? Many thanks in advance.

Kind regards,

Joris

Answer 1

[Matt J]

Why not use the TSP genetic algorithms already available on the FEX

http://www.mathworks.com/matlabcentral/fileexchange/index?utf8=%E2%9C%93&term=traveling+salesman+Joseph+Kirk

Alternatively, you could compare the code there with yours to get an idea of what's wrong.

[Joris]

Well, of course i'm supposed to write my own code for this course ;) But these should give me a good idea yes, thank you.