4.41667

4.4 | 26 ratings Rate this file 580 downloads (last 30 days) File Size: 2.94 KB File ID: #13680

Traveling Salesman Problem - Genetic Algorithm

by Joseph Kirk

 

16 Jan 2007 (Updated 02 Jun 2009)

Code covered by BSD License  

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

Download Now | 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
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)
Zip File Content  
Other Files license.txt,
tsp_ga.m
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (31)
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.

17 Jan 2007 shahin masti  
17 Jan 2007 John A

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

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.

04 Apr 2007 rana salem  
10 May 2007 Michael Kleder

Very useful. Well written. Really nice job.

20 May 2007 kazim akbulut  
22 May 2007 Husnul Hidayat

Thank u

01 Jun 2007 semra buyukkapu

thank you so much..

05 Jun 2007 nader khadher

tsp+ga+code source

11 Nov 2007 Yongguk Kim

thx

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.

13 Dec 2007 faigh mohamad rahimy

hi.tankas

23 Jan 2008 tom wiechet  
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

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

01 Mar 2008 beh mal  
11 Mar 2008 Antoine S

Great. Very useful. Thx.

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.

03 Aug 2008 reza ghanbari

good

18 Sep 2008 Felipe Padilla  
25 Sep 2008 Sandip Vijay  
26 Sep 2008 Naresh Kolla

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

03 Nov 2008 hudmem ira

thanks nice written

14 Nov 2008 Mahdieh

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

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

04 Mar 2009 xu jinpeng

very good!
thanks

07 Apr 2009 dokuzyuzseksen yuzseksen

thankss..

02 Jun 2009 Thierry Dalon

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

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.

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

Please login to add a comment or rating.
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 Sep 2008

updated help notes, description

02 Jun 2009

Added 3D capability.

Tag Activity for this File
Tag Applied By Date/Time
optimization Joseph Kirk 22 Oct 2008 08:57:10
traveling salesman problem Joseph Kirk 22 Oct 2008 08:57:10
tsp Joseph Kirk 22 Oct 2008 08:57:10
genetic algorithm Joseph Kirk 22 Oct 2008 08:57:10
ga Joseph Kirk 22 Oct 2008 08:57:10
 

MATLAB Central Terms of Use

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Terms prior to use.

Contact us at files@mathworks.com