Traveling Salesman Problem - Genetic Algorithm

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

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  
POP_SIZE (scalar integer) is the size of the population (should be divisible by 4)  
NUM_ITER (scalar integer) is the number of desired iterations for the algorithm to run  
SHOW_PROG (scalar logical) shows the GA progress if true  
SHOW_RES (scalar logical) shows the GA results if true  
 
Output:  
OPT_RTE (integer array) is the best route found by the algorithm  
MIN_DIST (scalar float) is the cost of the best route  
 
Example:  
n = 50;  
xy = 10*rand(n,2);  
a = meshgrid(1:n);  
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);  
pop_size = 60;  
num_iter = 1e4;  
show_prog = 1;  
show_res = 1;  
[opt_rte,min_dist] = tsp_ga(xy,dmat,pop_size,num_iter,show_prog,show_res);

• Acknowledgements: This submission has inspired the following:; 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, Open Traveling Salesman Problem - Genetic Algorithm
• MATLAB release: MATLAB 7.3 (R2006b)
• Other Files: license.txt, ; tsp_ga.m

[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.

[shahin masti]

 

[John A]

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

[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.

[rana salem]

 

[Michael Kleder]

Very useful. Well written. Really nice job.

[kazim akbulut]

 

[Husnul Hidayat]

Thank u

[semra buyukkapu]

thank you so much..

[nader khadher]

tsp+ga+code source

[Yongguk Kim]

thx

[Dimitri Shvorob]

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

[faigh mohamad rahimy]

hi.tankas

[tom wiechet]

 

[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

[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

[beh mal]

 

[Antoine S]

Great. Very useful. Thx.

[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.

[reza ghanbari]

good

[Felipe Padilla]

 

[Sandip Vijay]

 

[Naresh Kolla]

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

[hudmem ira]

thanks nice written

[Mahdieh]

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

[shaima A.I]

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

[xu jinpeng]

very good!  
thanks

[dokuzyuzseksen yuzseksen]

thankss..

[Thierry Dalon]

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