version 1.3.0.0 (9.62 KB) by
Joseph Kirk

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

**Editor's Note:** This file was selected as MATLAB Central Pick of the Week

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:

USERCONFIG (structure) with zero or more of the following fields:

- XY (float) is an Nx2 matrix of city locations, where N is the number 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

- SHOWWAITBAR (scalar logical) shows a waitbar if true

Input Notes:

1. Rather than passing in a structure containing these fields, any/all of

these inputs can be passed in as parameter/value pairs in any order instead.

2. Field/parameter names are case insensitive but must match exactly otherwise.

Output:

RESULTSTRUCT (structure) with the following fields:

(in addition to a record of the algorithm configuration)

- OPTROUTE (integer array) is the best route found by the algorithm

- MINDIST (scalar float) is the cost of the best route

Usage:

tsp_ga

-or-

tsp_ga(userConfig)

-or-

resultStruct = tsp_ga;

-or-

resultStruct = tsp_ga(userConfig);

-or-

[...] = tsp_ga('Param1',Value1,'Param2',Value2, ...);

Example:

% Let the function create an example problem to solve

tsp_ga;

Example:

% Request the output structure from the solver

resultStruct = tsp_ga;

Example:

% Pass a random set of user-defined XY points to the solver

userConfig = struct('xy',10*rand(50,2));

resultStruct = tsp_ga(userConfig);

Example:

% Pass a more interesting set of XY points to the solver

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]));

userConfig = struct('xy',xy);

resultStruct = tsp_ga(userConfig);

Example:

% Pass a random set of 3D (XYZ) points to the solver

xyz = 10*rand(50,3);

userConfig = struct('xy',xyz);

resultStruct = tsp_ga(userConfig);

Example:

% Change the defaults for GA population size and number of iterations

userConfig = struct('popSize',200,'numIter',1e4);

resultStruct = tsp_ga(userConfig);

Example:

% Turn off the plots but show a waitbar

userConfig = struct('showProg',false,'showResult',false,'showWaitbar',true);

resultStruct = tsp_ga(userConfig);

Joseph Kirk (2021). Traveling Salesman Problem - Genetic Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/13680-traveling-salesman-problem-genetic-algorithm), MATLAB Central File Exchange. Retrieved .

Created with
R2014a

Compatible with any release

- Mathematics and Optimization > Global Optimization Toolbox > Genetic Algorithm >
- Mathematics and Optimization > Global Optimization Toolbox > Particle Swarm >
- AI, Data Science, and Statistics > Statistics and Machine Learning Toolbox > Cluster Analysis > Nearest Neighbors >
- MATLAB > Mathematics > Graph and Network Algorithms > Shortest Path > Traveling Salesman (TSP) >
- Mathematics and Optimization > Optimization Toolbox > Linear Programming and Mixed-Integer Linear Programming > Solver-Based Linear Programming >

**Inspired:**
Multiple Traveling Salesmen Problem - Genetic Algorithm, Open Traveling Salesman Problem - Genetic Algorithm, Fixed Endpoints Open Traveling Salesman Problem - Genetic Algorithm, Fixed Start Open Traveling Salesman Problem - Genetic Algorithm, Traveling Salesman Problem - Nearest Neighbor

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Shamine MoganathanJoseph Kirk@Rafaela, you can just pass a cost matrix in for the distance matrix input.

Rafaela MachadoHow could I change the code to add a cost restriction, with a costs matrix, besides the distance matrix?

Thuzar Myint@DearJoseph,

Thank you very much.

Wishing you good health and good luck

Joseph Kirk@Thuzar, I'm not sure -- I think your equation refers to a detection process where there are true & false positives & negatives. I do not see how that concept applies to the TSP, because the TSP is not a detection process. If you have any specific questions about my code, I'd be happy to answer them, but I do not see how this is relevant.

Thuzar Myint@Dear Joseph,

I have studied the formula for computing accuracy as follow.

Accuracy=(TP +TN)/(TP+TN+FP+FN)

I want to know TP and TN that are used for computing the accuracy of travelling salesman problem .

I think that (TP+TN+FP+FN)is the total number of cities .

I do not know (TP +TN)

Please, explain me detail.

Please, let me learn from you.

Thuzar MyintDear Joseph,

I have studied the formula for computing accuracy as follow.

Accuracy=(TP +TN)/(TP+TN+FP+FN)

I want to know TP and TN that are used for computing the accuracy of travelling salesman problem .

I think that (TP+TN+FP+FN)is the total number of cities .

I do not know (TP +TN)

Please, explain me detail.

Please, let me learn from you.

Thuzar MyintDear Joseph,

I have studied the formula for computing accuracy as follow.

Accuracy=(TP +TN)/(TP+TN+FP+FN)

I want to know TP and TN that are used for computing the accuracy of travelling salesman problem .

I think that (TP+TN+FP+FN)is the total number of cities .

I do not know (TP +TN)

Please, explain me detail.

Please, let me learn from you.

Thuzar MyintDearJoseph,

Thank you very much.

Wishing you good health and good luck

Thuzar MyintJoseph Kirk@Thuzar, the algorithm already uses a form of tournament selection because, at each iteration, it randomly groups solutions into sets of 4 and selects the best of those 4 to propagate forward, and the 3 lesser solutions are discarded.

Thuzar MyintDear Joseph ,

Please help me.

I want to use tournament selection in your code.How can I modify your code if I use tournament selection in your code.Please, please help me.

Nour BS@Joseph, Now it's clear for me, thank you !

Joseph Kirk@Nour, the current-best-solution plot is only updated when a shorter path has been found, so at the end, the iteration number in the title is not the total number of iterations, but the last one that produced a better solution

Nour BS@Joseph, So why for each execution, the code stops at a different iteration (e.g if the number of cities is 100 and I run the code 3 times, I had 3 different iteration numbers: 6851 - 6976 - 6860) however the nomber of iterations NUMITER=10000 ?

Thuzar MyintDear Joseph,

Thank you very much.Really thank you very much.

May God bless you

Wishing you good health

and good luck

🙏🙏🙏🙏🙏

Joseph Kirk@Thuzar, see https://github.com/rubikscubeguy/matlab-tsp-ga/blob/master/GA-Mutation-Descriptions.pdf

Thuzar MyintHi I know that flip mutation is used to convert 0 to 1 or 1to 0 but i do not understant your flip mutation .Therefore ,I want to know flip mutation you used.

Please ,explain detail

Thank you very much

Joseph Kirk@Nour, the stop condition is the number of iterations

Nour BSWhat is the stop condition in this code?

Dejan Trifunovicvimal rGreat code, But my problem requires path should always start from city 1 and end in city 1.

could you please help me.

li qiangDear Joseph Kirk, Is there no reproduction operator, no crossover in the program, only mutation?

Dong HeKhalil ZbissGreat code, Thank you very much.

Robert LeeSANYAM JAINJoseph Kirk@Suleyman, if you read the help notes, you will see descriptions of the expected input types. Based on the error you were getting, it appears you attempted to provide a "table" as one of the inputs, which is not supported.

Joseph Kirk@Griffin, it sounds like you may want to try my "Fixed Endpoints Open Traveling Salesman Problem - Genetic Algorithm" variation

https://www.mathworks.com/matlabcentral/fileexchange/21197

Griffin KivitzHi Joseph, great code! Is it possible to alter the code so that the first and last cities in the route are specified with xy coordinates? The final route would not be a loop. How would I do this?

Thanks

Suleyman Utku DAGLIHello, I was trying to use your source code but when I add my own distance matrix and XY values it gives this error and I couldn`t understand why.

Can you help me ? Thank you!

Undefined operator '+' for input arguments of type 'table'.

Error in tsp_ga (line 170)

d = d + dmat(pop(p,k-1),pop(p,k));

Distance Matrix

0 12 9 6 3 15 12 9 6 15 12 9 6 18 15 12 9 18 15 12 9 21 18 15 12

12 0 3 6 9 8 11 13 17 8 11 14 17 11 14 17 20 11 14 17 20 14 17 20 23

9 3 0 3 6 10 14 17 14 10 14 17 14 14 17 20 17 14 17 20 17 17 20 23 20

6 6 3 0 3 13 16 14 11 13 16 14 11 20 17 17 14 17 20 17 14 19 23 20 17

3 9 6 3 0 17 14 11 8 17 14 11 8 20 17 14 11 20 17 14 11 24 21 18 15

15 8 10 13 17 0 3 6 9 1 3 6 9 8 11 14 17 8 11 14 17 11 14 17 20

12 11 14 16 14 3 0 3 6 3 1 3 6 11 14 17 20 11 14 17 20 14 17 20 23

9 13 17 14 11 6 3 0 3 6 3 1 3 15 17 15 12 15 17 15 12 17 20 17 14

6 17 14 11 8 9 6 3 0 9 6 3 1 17 14 11 8 17 14 11 8 20 17 14 11

15 8 10 13 17 1 3 6 9 0 3 6 9 8 11 14 17 8 11 14 17 11 14 17 20

12 11 14 16 14 3 1 3 6 3 0 3 6 11 14 11 8 11 14 17 14 14 17 20 17

9 14 17 14 11 6 3 1 3 6 3 0 3 14 17 14 11 14 17 14 11 17 20 17 14

6 17 14 11 8 9 6 3 1 9 6 3 0 17 14 11 8 17 14 11 8 20 17 14 11

18 11 14 17 20 8 11 15 17 8 11 14 17 0 3 6 9 1 3 6 9 8 11 14 17

15 14 17 20 17 11 14 17 14 11 14 17 14 3 0 3 6 3 1 3 6 11 14 17 14

12 17 20 17 14 14 17 15 11 14 11 14 11 6 3 0 3 6 3 1 3 14 17 14 11

9 20 17 14 11 17 20 12 8 17 8 11 8 9 6 3 0 9 6 3 1 17 14 11 8

18 11 14 17 20 8 11 15 17 8 11 14 17 1 3 6 9 0 3 6 9 8 11 14 17

15 14 17 20 17 11 14 17 14 11 14 17 14 3 1 3 6 3 0 3 6 11 14 17 14

12 17 20 17 14 14 17 15 11 14 17 14 11 6 3 1 3 6 3 0 3 14 17 14 11

9 20 17 14 11 17 20 12 8 17 14 11 8 9 6 3 1 9 6 3 0 17 14 11 8

21 14 17 19 24 11 14 17 20 11 14 17 20 8 11 14 17 8 11 14 17 0 3 6 9

18 17 20 23 21 14 17 20 17 14 17 20 17 11 14 17 14 11 14 17 14 3 0 3 6

15 20 23 20 18 17 20 17 14 17 20 17 14 14 17 14 11 14 17 14 11 6 3 0 3

12 17 20 17 15 20 23 14 11 20 17 14 11 17 14 11 8 17 14 11 8 9 6 3 0

XY values

0 0

12 2

9 2

6 2

3 2

12 3

9 3

6 3

3 3

12 5

9 5

6 5

3 5

12 6

9 6

6 6

3 6

12 8

9 8

6 8

3 8

12 9

9 9

6 9

3 9

sahar zarJoseph Kirk@Venky, there are a few lines that would have to be changed -- send me an email if this is still something you need.

Venky SuriyanarayananThanks a lot for sharing this..!! Where do I make the change in the code if I want to find the Longest path instead of Shortest path?

Sajad MajDear Joseph, I’m asking about the source you relied on to program this method,

I’m waiting for reply,Thank you for your cooperation Dear Joseph

Irving LopezKaia MacapagalCan we also consider other constraints? Aside from distance and the identified household to be evacuated? How do we input that in your code? Thank you.

rene estemberHI! We have data of household coordinates (longitude and latitude) in a certain barangay in the Philippines. Barangay a community where households reside. How can we input these data in you TSP_GA code. We also have data on the vulnerability index of each household. This represents the priority of household in case evacuation during typhoon happens. So we intend to use the TSP. Hope help us on this.

Thank you.

Rene

David FrancoPerfect!

David Franco5wenbinSupachan TraitruengsakulSupachan TraitruengsakulNICE CODE! Thanks!

osama bushnaqAlexandre RibeiroIznaDear Joseph, this is a really good work. I wish to speak with you concerning the codes. Can you email me plz?

Helena LeppäkoskiJoseph Kirk@Tahsin, yes, you are welcome to use the code in a project. And the output of the function is a structure containing a field named "optRoute" which is the order of the cities for the shortest tour found.

Tahsin Alam KhanHi, I have a problem: how can I make the results graph display the optimal route between city locations and label the cities on the points of the graph. I can see it has found the shortest distance but I am having trouble finding the optimal route between the locations. Here are my values:

defaultConfig.xy = 10*rand(5,2);

defaultConfig.dmat = [0 6.95 6.10 12.21 10.65; 6.95 0 9.2 15.93 10.46; 6.1 9.2 0 16.3 18.39; 12.21 15.93 16.3 0 9.00; 10.65 10.46 18.39 9 0];

defaultConfig.popSize = 5;

Tahsin Alam KhanHi, is it ok if I use this in my project?. I will cite you as you have said in a previous comment:

Kirk, Joseph (2014). Traveling Salesman Problem - Genetic Algorithm, MATLAB Central File Exchange. Retrieved October 12, 2017.

Joseph Kirk@warayu, try

result = tsp_ga('xy',X)

warayu intawongsThanks Joseph, I have some problem, i try to test wit burma 14 but it has an error

>> X=[16.47 96.10;16.47 94.44;20.09 92.54;22.39 93.37;25.23 97.24;22.00 96.05;20.47 97.02;17.20 96.29;16.30 97.38;14.05 98.12;16.53 97.38;21.52 95.59;19.41 97.13;20.09 94.55]

X =

16.4700 96.1000

16.4700 94.4400

20.0900 92.5400

22.3900 93.3700

25.2300 97.2400

22.0000 96.0500

20.4700 97.0200

17.2000 96.2900

16.3000 97.3800

14.0500 98.1200

16.5300 97.3800

21.5200 95.5900

19.4100 97.1300

20.0900 94.5500

>> userConfig = struct('dmat',X)

userConfig =

dmat: [14x2 double]

>> result = tsp_ga('xy',rand(14,2),'dmat',X);

??? Error using ==> tsp_ga at 134

Invalid XY or DMAT inputs!

RenaudDear Joseph,

First Thanks a lot for sharing this code, it is really good!!!

I have couple of questions for you:

(1) I am using this code as a part in my project and will cite you in the text of the publication this way:

"we used open source genetic algorithm travelling salesperson code, tsp_ga.m, written by Joseph Kirk, and made available via http://www.mathworks.com/matlabcentral" --- Is that fine with you?

(2) I modified your code which is now part of an entire Matlab project that I plan to put on GitHub. The part with your code in GitHub will be associated with the license that goes with your code -- Is that fine with you?

(3) I would like to discuss with you why you chose to use a Genetic algorithm and not a Lin-Kernighan Heuristic approach, here is my email address: renaud.schuck@gmail.com feel free to contact me.

Many thanks,

Best,

Renaud

sheydaExcuse me, I have this problem and I download your code and read it but I can't write code for this problem.plz, help me.

x =[

0 15 20 10 5 25 36 10 30 12 15 50 40 27

15 0 30 25 14 26 20 39 51 17 9 14 45 28

20 30 0 25 14 17 57 26 16 11 9 38 27 56

10 25 25 0 26 58 14 5 10 26 35 40 22 32

5 14 14 26 0 50 11 23 36 38 37 21 25 26

25 26 17 58 50 0 23 35 42 39 21 19 7 11

36 20 57 14 11 23 0 28 29 36 28 36 28 16

10 39 26 5 23 35 28 0 15 25 35 45 20 11

10 51 16 10 36 42 29 15 0 28 39 21 8 19

12 17 11 26 38 39 36 25 28 0 23 15 38 50

15 9 9 35 37 21 28 35 39 23 0 25 10 50

50 14 38 40 21 19 36 45 21 15 25 0 28 39

40 45 27 22 25 7 28 20 8 38 10 28 0 15

27 28 56 32 26 11 16 11 19 50 50 39 15 0

];

Joseph Kirk@Cintia, something like this would be fine:

Kirk, Joseph (2014). Traveling Salesman Problem - Genetic Algorithm, MATLAB Central File Exchange. Retrieved July 20, 2017.

Cintia BarrocaHi, I used this algorithm in my project, what is the best way to give you credit?

Joseph Kirk@halime, I do not understand your question.

halime çelikHi, I want to mathworks' travel salesman problem code in Matlab 2016b. But , in mathwork site ,there is 2017 code. How can find , could you help me.

Joseph Kirk@Alexander, your code in your other comment should work just fine.

Alexander Kulikov@Joseph Kirk, Can you tell me where I'm mistaking the code entry? How can I write it correctly? Can you say please ??

Joseph Kirk@Alexander, it looks like you have your solution -- when I run your code, I get:

>> result.optRoute

[2 3 4 1 5]

with a minimum cost of 62

Vahid AnariAlexander KulikovHi, guys

help me please!!!!!

There is a traveling salesman's problem, here it is:

>> X= [0 10 25 25 10; 1 0 10 15 2; 8 9 0 20 10; 14 10 24 0 15; 10 8 25 27 0]

X=

0 10 25 25 10

1 0 10 15 2

8 9 0 20 10

14 10 24 0 15

10 8 25 27 0

>> userConfig = struct('dmat',X)

userConfig =

dmat: [5x5 double]

result = tsp_ga('xy',rand(5,2),'dmat',X);

I need to solve it with the help of a genetic algorithm in matlab.

Please, write the code! I will be very grateful !!!

Nicolas LIAwesome, thanks !

Nathan ParrishJoseph Kirk@Madina, what you seem to be describing is a *VRP*, but this code is for the *TSP* so it does not use constraints like travel time.

Madina AtwanHi, I need help with imposing some constraints. For example split the nodes into two sets depending on the type of car i need.

impose time constraint of travel time from start to end. Last minimum time from pick up point till destination. How can i do that in this code?

thank you

Madina

RobertQ leongVery helpful

Joseph Kirk@Ricardo, there is a variation for the "open" TSP here:

http://www.mathworks.com/matlabcentral/fileexchange/21196

Ricardo ReisVery nice code you made. I have a small doubt if anyone could help me, if I don't want a closed path what should I change around line 168? thanks in advance!

reza marvastiFan Zhangwonderful work！

RenaudHi,

I was just wondering why you wrote a code with a Genetic Algorithm rather then using a Lin-Kernighan Heuristic approach?

Thanks for the code!

Best,

Renaud

Joseph Kirk@Vera, you should not need to modify the code itself -- just pass different inputs that are specific to the problem you are trying to solve.

@yogita, if you have a specific question about my code, I would be happy to answer it.

cagatay odabasiVera BajicHi! First of all thank you for your code, it is amazing! I am trying to use this algorithm on Europe map, but i don't know how to modify the code, could you help?

yogita tandelhello sir

i m m.tech power system student.

sir u have any idea for genetic algorithm mppt technique for pv cell in partial shading condition

please help me sir how to generate duty cycle using genetic algorithm with fitness function of power p = v * i

please help me

Joseph Kirk@Lilly,

If your coordinates are latitude/longitude, then you should create a distance matrix for the point-to-point distances in the units you desire and pass that matrix in as the DMAT input.

If no distance matrix is provided as an input, my code assumes the inputs are in a Cartesian coordinate system and computes the pair-wise Euclidean distances. In the case of non-Cartesian systems like geographic latitude/longitude, this is undesirable, which is one of the reasons my code offers the option of passing in a pre-computed distance matrix.

LillyIf I insert a longitude and latitude as input, and the shortest distance is 2.6702, so 2.6702 stand for what ? Meaning here is it km or coordinate ?

Joseph Kirk@Tonia, I think the choice of configuration values (like POPSIZE and NUMITER) is an exercise best left to the user. There is a trade-off between computation time and solution convergence rate. If you choose a higher population size, fewer iterations should be required to converge to a near-optimal solution, but each iteration will take a little longer to process. Alternatively, you could decrease the population size and increase the number of iterations.

And POPSIZE 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 of those four, and pass that one on to the next iteration. I then perform 3 different mutations on that best-of-four citizen and replace the 3 lesser solutions in the population with the mutated versions for the next iteration).

Tonia PapadopoulouHello joseph,Thanks a lot for your code.I would like to explain me please in a problem with 100 cities what should be the number of POPSIZE and why this must be divisible by 4.I don't really understand what's the reason of : popSize = 4*ceil(popSize/4); .

Na LiThanks very much, it is helpful. I understand why you did not use crossover opration, but I am confused why there is not a mutation rate. although i think it is right, i can not convince myself. please help!

nelson alvesThank you a lot. I get it to work now! @Joseph

Joseph Kirk@nelson, the reason you are getting an error is because you are only passing the DMAT input instead of both XY and DMAT. When a DMAT is provided, the XY points are only used for plotting purposes, but I still do a consistency check to make sure they have the same number of points. If you do not have XY points for your problem, you can always pass in "dummy" values.

So in your case, you could call the function as follows:

>> result = tsp_ga('xy',rand(5,2),'dmat',X);

Joseph Kirk@Aalaa, please see some of the comments below. I do not use a crossover operator but rather 3 different mutation operators.

Aalaa MagablehThanks a lot for your response, I wont to know what is the Selection function and Crossover function used in this code and what is the

Crossover ratio.

nelson alvesPlease tell me what am I doing wrong:

This is my distance matrix for a travelers salesman problem.

>> X=[0 150 120 330 190; 150 0 50 290 150;120 50 0 240 100;330 290 240 0 140;190 150 100 140 0]

X =

0 150 120 330 190

150 0 50 290 150

120 50 0 240 100

330 290 240 0 140

190 150 100 140 0

>> userConfig = struct('dmat',X)

userConfig =

dmat: [5x5 double]

>> resultStruct = tsp_ga(userConfig)

Error using tsp_ga (line 134)

Invalid XY or DMAT inputs!

I dont know why my matrix is invalid please help me.

Joseph Kirk@Aalaa, there is an "optRoute" field in the output variable structure that stores the best route found. As for optimizing the input parameters, that is an exercise best left up to the user.

Aalaa MagablehHello Joseph thanks a lot for your code. I have apply it on 2000 cities but how i can get the order of the cities in the last route?

whats about the best number of iteration and the other GA operator you sujest me to use with pop. size 2000Thanks

Joseph Kirk@Gunjan, for a TSP with 10 cities, the route 1-2-3-4-5-6-7-8-9-10 is the same as the route 5-6-7-8-9-10-1-2-3-4, so if you have to start at city number 5, all you have to do is shift the values before the 5 in the resulting solution to the end of the list.

Regarding citations, here is a useful blog post: http://blogs.mathworks.com/community/2010/12/13/citing-file-exchange-submissions/

Gunjan IndapurkarHello Joseph your code helped a lot. I have few more question

If I have a 10 city problem and if I have to start from a predetermined city say city number 5, then how do I do it? Also I would like to refer/cite your work as much as possible, how do I do it? Thanks.

Gunjan IndapurkarHello Joseph,

My From/To distance chart has a dash '-' for diagonal elements. How do I enter this matrix in dmat command with diagonal elements set to dash ' - ' or infinity.

Thanks

Twinkle katiyar@kirk thanks sir for your reply. I am trying to implement crossover in your above code but i failed. Can you please help me to do this??

Joseph Kirk@katiyar, see some of the comments below for why I did not implement a crossover operator. There is, however, a mutation operator -- 3 of them in fact.

Twinkle katiyarga algorithm also have crossover and mutation funtion. But this code doesn't have these function?? Is there any who have ga code including crossover and mutation. please send me. I really need it.

minahi. i want to make a WSN and implement one of the intelligent routing protocols on it.for start i dont know how to simulate a WSN. would anyone help me or send me anything helpful?

thank you

Joseph Kirk@Ravisasthiri, you can pass the points into the function as inputs. Please see the numerous examples provided in the help notes.

Ravisasthiri Pnice code, its useful. but i don't know how to load data sets in this coding please help me.

MAYUR PAILWARwhat is the procedure for download????

Emre YakutHi, Dear Joseph Kirk. I have found your tsp genetic matlab code. I am studying tsp matlab code. My data set is presented to additional your information. One store and seven shop, I am trying to find which best route. How can I make the appropriate my data in your code to take into account?

I would be glad if you can help.

Best Regards.

Emre YAKUT

Osmaniye Korkut Ata University

chengzhiJoseph Kirk@Binayak, look in the help notes for examples and input/output options.

Binayak duttaThe code is amazing. The coder is a life saver. But please tell me how to specify the xy coordinates in the code as I'm a novice in matlab. Please!!!!

SvenJoseph Kirk@Sven, thanks for the suggestions. I'll look into overhauling the interface.

SvenNice work Joseph as usual. Note however a frustration: The function has reasonable defaults, but these are ONLY accessed if no subsequent inputs are given. For instance, if I want to call the function with default inputs but NOT show results (the 6th input), I can no longer use defaults for ANY of the other inputs and MUST provide them all. This is really just a frustration with the distMap matrix (I know, just a couple of lines, but I'll bet the default is being used most of the time) as the others are simple scalar inputs, but the interface design in general could do with a tweak. I suggest some logic to check each and use defaults if empty (which could be implemented without changing the function IO), or in general I find the inputParser class to be useful for this style of not-necessarily-ordered user inputs.

Oh, and I think that numStaticIter may be a useful parameter too: the user could specify the number of iterations in which - if the distance hasn't reduced - the loop kicks out to save computation time.

Joseph Kirk@Larry, the XY coordinates are only randomly created if no inputs are provided to the function. If you pass a set of XY points, the function will use them.

You can also pass in a distance matrix of point-to-point distances. If you do not provide one, my function computes the pairwise Euclidean distances. However, for latitude and longitude points, this is probably not desirable. You should create a distance matrix in the units you desire and pass that in as the second input.

LarryHi Joseph,

Can I first say that this is an amazing code and thank you so much for it's creation.

I was wondering how it would be possible to change the xy co-ordinates from being randomly selected to being set points (for example longitude and latitude).

Many thanks

yuantao songvery good

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

Pedro pHello 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

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

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

FredrikFound my answer in another revision of your file =)

FredrikHi 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 =)

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

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

VictorHello Joseph.

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

Joseph KirkFredrik, the "showResult" flag does precisely that.

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

FredrikThanks 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 =)

Joseph KirkFredrik,

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

Mathiasthank you

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

asmaasmavery helpfull

Joseph KirkYuan, try this one:

http://www.mathworks.com/matlabcentral/fileexchange/21198

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

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

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?

Joseph KirkNewmat, 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]

NewmatWhat 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!

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

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

Mojeebthanks!

Erdal BizkevelciTristan UrsellA simple to understand implementation, and can be easily modified :)

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

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

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?

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

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.

UNIMAS_skgreat 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

Derek O'ConnorHas anybody tested the quality vs numIters of this function?

That is, minDist/optDist as numIters increases.

JOHN ROBINSONGood job ! How do i download the file ?

Joseph KirkThierry/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?

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

Mark ShoreHello 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?

Joseph KirkWill, 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.

Will CampbellGreat 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?

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

nikhilAvinashvery useful.

Abdullah Y?lmazJoseph Kirktim: 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).

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

Masoud Allahkaramithanks!

Srinivas RaparthiGreat. Very useful. Thx.

Joseph KirkAlex, 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).

Alex Ter-SarkissovGreat 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.

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

dokuzyuzseksen yuzseksenthankss..

xu jinpengvery good!

thanks

shaima A.Iso good ..

and very useful

but it would be better if you explain the graphical result

thanks so much

Mahdiehthis was awesome, nice job

though for 1000 points, took very long ...

hudmem irathanks nice written

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

Sandip VijayFelipe Padillareza ghanbarigood

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

Antoine SGreat. Very useful. Thx.

beh malFernando CastroYour 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

Fernando CastroVery 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

tom wiechetfaigh mohamad rahimyhi.tankas

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

Yongguk Kimthx

nader khadhertsp+ga+code source

semra buyukkaputhank you so much..

Husnul HidayatThank u

kazim akbulutMichael KlederVery useful. Well written. Really nice job.

rana salemJohn D'ErricoI 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.

John Am file does not appear to support Options listed in description.

shahin mastiJohn D'ErricoNicely 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.