# Traveling Salesman Problem – Genetic Algorithm7

Posted by Will Campbell,

Will's picks this week is Traveling Salesman Problem - Genetic Algorithm by Joseph Kirk.

I stumbled upon this submission purely by accident while looking for something completely unrelated. It just goes to show that you never know what goodies you'll discover on the File Exchange. The function converges on the optimal solution to the traveling salesman problem by employing a genetic algorithm. Ok, what does that mean, exactly?

The traveling salesman has a set of cities he or she wishes to visit. The salesman wants to visit each city only once before returning to the city of embarkation. In which order should the salesman visit the cities to minimize the distance traveled? Well, if there are a handful of cities, you could probably figure this out through inspection. But what do you do when there are hundreds of cities to visit?

There are many approaches to solving this problem. In Joseph's case, he opted for a genetic algorithm. He creates a population of possible routes, determines the best route in the population, mutates the best route to get new samples in his population, and repeats the process. He accomplishes all of this with core MATLAB commands. If you're interested in additional capabilities in this arena, check out the Global Optimization Toolbox.

What I like about this submission is its simplicity and ease of use. The code is well-documented such that even a non-expert on the subject (such as me) can readily understand it and make changes as desired. It has a handy option to view the pathway's evolution; with nothing but a simple plot command, Joseph provides us with some strangely addictive animation.

I applied the function to a real-world problem by collecting latitude and longitude values for major US and Canadian cities off the web. I converted the HTML table into an Excel file, imported the data to MATLAB, and used the resultant vector as my input to the Traveling Salesman function. In order to see my results on a map, I added an extra line of code from the Mapping Toolbox:
geoshow( 'landareas.shp', 'FaceColor', 'LineWidth',2);
I inserted this line outside the main loop, which required some manipulation of the inner loop, but geoshow is the key command to get the map displayed. In the end, this was the fruit of my labor:

The proposed best route is as follows (different map projection for easier viewing):

Comments
Let us know what you think here or leave a comment for Joseph.

## 7 CommentsOldest to Newest

Saravanan Mani replied on : 1 of 7

Very nice!
I want graphical explanation.

Thanks,
Saravanan Mani
Lear Corporation

huayu dai replied on : 2 of 7

so miracle！I am a student, could you give the all process to me? thanks!

Atefeh Norouzi replied on : 3 of 7

i have need for alghorithm genetic for solve tsp with matllab .do you help me ?

Atefeh Norouzi replied on : 4 of 7

iam a student.could you give the all process to met?please

Will Campbell replied on : 5 of 7

Hi Atefeh,
I would recommend that you seek assistance at MATLAB Answers: http://www.mathworks.com/matlabcentral/answers/. Go there and clearly describe the problem you’re attempting to solve, the steps you’ve taken thus far to solve it, and the challenges you need assistance with. If you do that, you will likely get some valuable advice!

Best,
-Will

Emmanuel replied on : 6 of 7

wow, that’s great!!! I’m not a professional but I can use it easily.
I’m asking how to do that in Simulink?

wcampbell replied on : 7 of 7

Hi Emmanuel,
I suppose you could do this in Simulink, but I wouldn’t think that the tool would be ideal for the job. Simulink specializes in dynamic simulation and algorithm development. There’s no real need to simulate the system evolving with time in the case of the traveling salesman. Such an optimization is better-suited for MATLAB. Now, if you’re interested in improving the behavior of an existing Simulink model, you should check out Simulink Design Optimization.

Best!
-Will