Code covered by the BSD License  

Highlights from
Traveling Salesman Problem - Genetic Algorithm

4.475

4.5 | 45 ratings Rate this file 275 Downloads (last 30 days) File Size: 3.09 KB File ID: #13680
image thumbnail

Traveling Salesman Problem - Genetic Algorithm

by

 

16 Jan 2007 (Updated )

Finds a near-optimal solution to a TSP using a GA

Editor's Notes:

This file was selected as MATLAB Central Pick of the Week

| Watch this File

File Information
Description

TSP_GA Traveling Salesman Problem (TSP) Genetic Algorithm (GA)
Finds a (near) optimal solution to the TSP by setting up a GA to search for the shortest route (least distance for the salesman to travel to each city exactly once and return to the starting city)

Summary:
1. A single salesman travels to each of the cities and completes the route by returning to the city he started from
2. Each city is visited by the salesman exactly once

Input:
XY (float) is an Nx2 (or Nx3) matrix of cities
DMAT (float) is an NxN matrix of point to point distances/costs
POPSIZE (scalar integer) is the size of the population (should be divisible by 4)
NUMITER (scalar integer) is the number of desired iterations for the algorithm to run
SHOWPROG (scalar logical) shows the GA progress if true
SHOWRESULT (scalar logical) shows the GA results if true

Output:
OPTRTE (integer array) is the best route found by the algorithm
MINDIST (scalar float) is the cost of the best route

Example:
n = 50;
xy = 10*rand(n,2);
popSize = 60;
numIter = 1e4;
showProg = 1;
showResult = 1;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
[optRoute,minDist] = tsp_ga(xy,dmat,popSize,numIter,showProg,showResult);

Example:
n = 100;
phi = (sqrt(5)-1)/2;
theta = 2*pi*phi*(0:n-1);
rho = (1:n).^phi;
[x,y] = pol2cart(theta(:),rho(:));
xy = 10*([x y]-min([x;y]))/(max([x;y])-min([x;y]));
popSize = 60;
numIter = 2e4;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
[optRoute,minDist] = tsp_ga(xy,dmat,popSize,numIter,1,1);

Example:
n = 50;
xyz = 10*rand(n,3);
popSize = 60;
numIter = 1e4;
showProg = 1;
showResult = 1;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);
[optRoute,minDist] = tsp_ga(xyz,dmat,popSize,numIter,showProg,showResult);

Acknowledgements

This file inspired Multiple Traveling Salesmen Problem Genetic Algorithm, Traveling Salesman Problem Nearest Neighbor, Fixed Start Open Traveling Salesman Problem Genetic Algorithm, Fixed Endpoints Open Traveling Salesman Problem Genetic Algorithm, and Open Traveling Salesman Problem Genetic Algorithm.

Required Products MATLAB
MATLAB release MATLAB 7.12 (R2011a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (82)
04 Mar 2014 yuantao song

very good

28 Jan 2014 Joseph Kirk

@Pedro, thanks for the link. I had not seen the paper previously, but yes, it does appear to have used this code.

24 Jan 2014 Pedro p

Hello Joseph, You might already know about it, but i found a paper discussing this algorithm, I didnt find the right references to your work though:
http://www.ijsce.org/attachments/File/v3i2/B1514053213.pdf

28 Oct 2013 Joseph Kirk

@chikodragon, I do not use the crossover operator in my implementation. I don't think it is necessarily an essential component of a GA. I have implemented a handful of different versions of the GA (with various mutation/crossover operator combinations) to solve the TSP, and what I have found is that the crossover operator tends to be quite destructive (it makes large changes to a given route) and therefore rarely improves a decent solution. So my code uses 3 different mutation operators with the intent to make modifications that are more likely to improve the best solutions. (I randomly group 4 citizens at a time, take the best one of those four, and pass that one on to the next generation. I then perform 3 mutations on that best-of-four citizen and pass the mutated versions on to the next generation as well).

28 Oct 2013 chikodragon

hello mr kirk thank you very much. which parts of your coding are discussing crossover? I have not seen it. thank you for your attention.

11 Jun 2013 Fredrik

Found my answer in another revision of your file =)

11 Jun 2013 Fredrik

Hi Joseph, I was wondering how I can specify a home point, if I start a TSP search mid journey. Using your previously explained method, it also sets this point as start, but I only want it as stop. Any tricks to do this?
Example:
I have computed a path, and something happends midway so I have to compute a new path, but this time [0 0 0] is not start location, only stop, and [30 90 5] is start =)

25 May 2013 Fredrik

Hi Mr. Kirk, I was wondering if you have any documentation (i.e scientific report/article) on your work demonstrated here. I have successfully implemented part of your code in my masters thesis project, involving cognitive control of quadrocopters, and would like to refer to your work as much as possible.

24 May 2013 Victor  
24 May 2013 Joseph Kirk

Victor, the population size is part of the GA configuration - it has nothing to do with the TSP in general...

24 May 2013 Victor

Hello Joseph.

I am missing something. Could you please explain, what is the relationship between popSize variable and the TSP problem?

22 May 2013 Joseph Kirk

Fredrik, the "showResult" flag does precisely that.

21 May 2013 Fredrik

Is there any easy way of displaying ONLY the best solution as output, after the iterations are done, instead of the changing optRoute?

20 May 2013 Fredrik

Thanks a lot Joseph, I have also managed to implement your script with some modifications in simulink, where I get a set of waypoints as input =)

13 May 2013 Joseph Kirk

Fredrik,
In the standard formulation of the TSP, the optimal solution can start at any city. If you want to force the solution to start at a specific city, you can manipulate the output as follows:

Supposing that you have requested "optRoute" as an output and that you want the solution to start at the first city, you can type the following into the Command Window:

>> index = find(optRoute == 1);
>> finalRoute = optRoute([index:end 1:index-1])

13 May 2013 Mathias

thank you

10 May 2013 Fredrik

Hi I was wondering, how can I set an initial starting point/stop points? when I run the algorithm for mywaypoints, the starting position becomes the 6th visited city, but that is where I start, so ofcourse I want that to be the initial position.

27 Mar 2013 asma

very helpfull

27 Mar 2013 asma  
26 Feb 2013 Joseph Kirk

Yuan, try this one:
http://www.mathworks.com/matlabcentral/fileexchange/21198

26 Feb 2013 Yuan

I find your next Open Traveling Salsman Solution, and it works as well good. Nice job :)

26 Feb 2013 Yuan

Excuse me Joseph, can you explain a bit how to use it if I don't want a return loop? I mean only from a starting point towards an unknown end but with smallest distance. Thank you in advance.

17 Jan 2013 Newmat

@ Joseph Kirk
Thank you so much!! This really helped me!

@all
I have 230 nodes. Is it usual for the ga-algorithm that it takes about 30000 Iterations to find a good path?

17 Jan 2013 Joseph Kirk

Newmat, that is because the code is a function. The stuff that happens inside is essentially a black box as far as the stuff outside is concerned. Certain variables are passed as output if you request them (see examples) but if you really need the internal variables, I suggest adding a line at the end of the function that saves the variables to a .mat file. [i.e. add the line: "save('TSPvariables.mat')" without the quotes after the last line of code in the function]

16 Jan 2013 Newmat

What do I have to change inside the script to keep all variables? When the script has finished, you can't check any variables anymore. For example, if I type in Matlab's command line "xy" (to get the values of xy) the variable is not defined anymore. It is like if the clear-command has been executed.
Does anybody know? It is very important!
Thank you!

05 Nov 2012 Emmanuel Luevano

Hi, Is it posible to convert this m file into c code using the emlc function?

20 Oct 2012 Emmanuel Luevano

@Joseph Hi, Is there a way to use it in SIMULINK?

12 Dec 2011 Mojeeb

thanks!

12 Dec 2011 Erdal Bizkevelci  
07 Dec 2011 Tristan Ursell

A simple to understand implementation, and can be easily modified :)

04 Dec 2011 UNIMAS

hi joseph..may i know where is the fitness function inside your program?

03 Dec 2011 UNIMAS_sk

please send me modified file if you can to angelgurl_aireen@yahoo.com

03 Dec 2011 UNIMAS_sk

@Joseph thanks for ur explanation, i now start to understand what u try to do. now, u used mutation as an operators to generate new generations. i believe it is possible if we want to modify the operators in ur sourcecode to use crossover instead of mutation. I am curios as to compares the result of using mutation and crossover operators. i'm trying to do this but keep on failing since i'm new to MATLAB coding. If u can, could u please show me the modified version for the crossover operators?

02 Dec 2011 nur lydia

thank for the above explanation,however when i study your previous program there are different in both coding. could you explain the different ...thanks you

02 Dec 2011 Joseph Kirk

@John, click on the "Download All" button at the upper right of this page to download the files.

@Derek, no, but I save the score of the best solution as the function runs. You could modify the file so this variable gets passed as an output.

@Unimas, a potential TSP solution is scored by the length of the route, which we are trying to minimize. I am NOT calculating "fitness" in the traditional sense (as a score between 0 and 1, with 1 being the best) but rather scoring various solutions relative to each other and selecting the shorter routes.

30 Nov 2011 UNIMAS_sk

great one! i need to ask though, if i were to modified this file, how do i change the fitness functions and its value? i am not even sure what fitness function that u used in the sourcecode since i'm so new to this. the selection method and operators too -_- it would be great if someone can explain that to me. i am also in fuzzy state of how this fitness criteria results are evaluated

28 Nov 2011 Derek O'Connor

Has anybody tested the quality vs numIters of this function?

That is, minDist/optDist as numIters increases.

26 Nov 2011 JOHN ROBINSON

Good job ! How do i download the file ?

11 Nov 2011 Joseph Kirk

Thierry/Mark, no particular reason except that I originally developed only a small number of files (just the standard TSP and standard MTSP) and it seemed to make sense at the time to submit them separately. Then the list kept growing as more and more people asked me for variations. So they were submitted over a relatively long span of time, but when I update them, the changes show up all at once and hindsight makes it apparent that submitting a single "toolbox" might have made more sense. (But now external sites link to some of the files, so I hesitate to remove them and form a toolbox).

Tero, did you have any success with the modified file I emailed to you?

08 Nov 2011 Tero Tuohioja

Hello Joseph, without knowing this problem well, can I have 1/TSP easily.. meaning I want the longest possible route

07 Nov 2011 Mark Shore

Hello Joseph. Just out of curiosity, is there a reason you submitted 11 different variants on this problem as separate files rather than one zipped file containing all of them, with descriptions, or (admittedly more work) a single function allowing the different options to be called?

14 Oct 2011 Joseph Kirk

Will, yes, there is a very good reason. Let me explain. "Distance" is a rather intuitive but perhaps misleading term. For example, you may want to provide my function with geographic coordinates (Latitude/Longitude). However, such a coordinate system is not Cartesian. Therefore, relying on my calculation of the distances may be tenuous at best. In this case, it may be more appropriate to compute "great circle distance" values or something similar to determine the actual distance between each point. I could also envision users wishing to compute the distance along roads, for example, rather than straight-line distances. There are any number of other reasons not to use the simple Euclidean distance that is the default for my function. Thus, perhaps it would be more accurate to think of this input as a "cost" matrix rather than a distance matrix. My function attempts to minimize the cost of the TSP path. And I deemed it appropriate to allow users to provide their own inputs in whatever cost/distance form they would like to choose.

13 Oct 2011 Will Campbell

Great stuff. I'm curious, is there a particular reason that you pass dmat as an input? Couldn't it always be calculated within the function itself?

21 Aug 2011 Sam

who could tell me about the selection method that has been used in this program.

10 Aug 2011 nikhil  
09 Jul 2011 Avinash

very useful.

22 Jun 2011 Abdullah Y?lmaz  
05 May 2011 Joseph Kirk

tim: POP_SIZE must be divisible by 4 because of the way good solutions in the current population are propagated to the next iteration.

(I randomly group 4 citizens at a time, take the best one of those four, and pass it on to the next generation. I then perform 3 different mutations on that best-of-four citizen and pass the mutated versions on to the next generation).

04 May 2011 tim

can someone please tell me why POP_SIZE must be divisible by 4? Please! thank you!

27 Oct 2010 Masoud Allahkarami

thanks!

10 Dec 2009 Srinivas Raparthi

Great. Very useful. Thx.

30 Oct 2009 Joseph Kirk

Alex, my code is a slight deviation from the "standard" genetic algorithm, but it has all the essential components of a GA (abstract representation of possible solutions, individual fitness evaluation, a population of potential solutions, and a method of propagating good solutions and forming new, potentially better, solutions).

There IS selection AND elitism, actually, but you are right about crossover. I don't think it is necessarily an essential component of a GA. I have implemented a handful of different versions of the GA (with various mutation/crossover operator combinations) to solve the TSP, and what I have found is that the crossover operator tends to be quite destructive (it makes large changes to a given route) and therefore rarely improves a decent solution. So my code uses 3 different mutation operators with the intent to make modifications that are more likely to improve the best solutions. (I randomly group 4 citizens at a time, take the best one of those four, and pass it on to the next generation. I then perform the 3 mutations on that best-of-four citizen and pass the mutated versions on to the next generation).

29 Oct 2009 Alex Ter-Sarkissov

Great implementation, fast and furious, but...where is a genetic algorithm? There's no crossover, no selection, no elitism. It's more of a population-based hill climbing/simulated annealing, I guess.

02 Jun 2009 Thierry Dalon

How about making a TSP Toolbox with all your TSP contributions? (around 15)!

07 Apr 2009 dokuzyuzseksen yuzseksen

thankss..

04 Mar 2009 xu jinpeng

very good!
thanks

26 Dec 2008 shaima A.I

so good ..
and very useful
but it would be better if you explain the graphical result

thanks so much

14 Nov 2008 Mahdieh

this was awesome, nice job
though for 1000 points, took very long ...

03 Nov 2008 hudmem ira

thanks nice written

26 Sep 2008 Naresh Kolla

This would be better if it is extended by taking some more conditions

25 Sep 2008 Sandip Vijay  
18 Sep 2008 Felipe Padilla  
03 Aug 2008 reza ghanbari

good

01 Apr 2008 me me

i need a guide on to use distance between cities instead of coordinates.do u have any idea?u can email me if possible.

11 Mar 2008 Antoine S

Great. Very useful. Thx.

01 Mar 2008 beh mal  
12 Feb 2008 Fernando Castro

Your program is very good. Congratulation. I will need to do something close to your program, but I will use the distances between the cities, and not the coordinates.
Do you have something to help me?
You can email-me, if possible.
Thanks a lot.
Regards

12 Feb 2008 Fernando Castro

Very good. Congratulation.
I'm need to somethind very close to your program, but I will use the distance between the cities, and not the coordinates.
Do you have something to help me?
You can send it to my email:
thanks

23 Jan 2008 tom wiechet  
13 Dec 2007 faigh mohamad rahimy

hi.tankas

14 Nov 2007 Dimitri Shvorob

Just to clarify: the author does not use Direct Search and Genetic Algorithm toolbox, but codes up a GA routine from scratch.

11 Nov 2007 Yongguk Kim

thx

05 Jun 2007 nader khadher

tsp+ga+code source

01 Jun 2007 semra buyukkapu

thank you so much..

22 May 2007 Husnul Hidayat

Thank u

20 May 2007 kazim akbulut  
10 May 2007 Michael Kleder

Very useful. Well written. Really nice job.

04 Apr 2007 rana salem  
17 Jan 2007 John D'Errico

I tested the options, they are now operative. So John A may have downloaded it before the new version was installed. It runs much faster with no plot updates too.

17 Jan 2007 John A

m file does not appear to support Options listed in description.

17 Jan 2007 shahin masti  
16 Jan 2007 John D'Errico

Nicely written. Good help. Nice graphics for the solution. But think about it - this is not actually a really useful tool. Its mainly a nice demo. A true tool that could be used to solve a TSP would allow the user to turn off the graphics.

I'd happily raise my rating to a 5 if the author provided a switch to turn off the graphics (as nice as they are.) If there are any parameters that will allow a user to improve the result for specific problems, they too should be controllable, with documentation as to what they do.

Updates
17 Jan 2007

Included options to turn off plots and change the parameters of the GA

22 May 2007

Vectorized distance matrix calculation.

25 Aug 2008

Added distance matrix as input, reworked GA operators

02 Jun 2009

Added 3D capability.

07 Nov 2011

Minor cosmetic updates.

Contact us