Search Comments and Ratings

go

   
Date File Comment by Comment Rating
06 Nov 2014 Advanced Dijkstra's Minimum Path Algorithm calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm Author: Joseph Kirk Joseph Kirk

Remove the edge connections in the adjacency matrix for any nodes that are inside the "keep out" area prior to running the shortest path algorithm:

A(in,:) = 0;
A(:,in) = 0;

08 Oct 2014 Advanced Dijkstra's Minimum Path Algorithm calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm Author: Joseph Kirk Joseph Kirk

Vishal, in your case, you could provide the inputs as follows:

C = zeros(4);
C(1,2) = 10;
C(1,3) = 20;
C(2,4) = 30;
C(3,4) = 40;
A = logical(C);
[cost,path] = dijkstra(A,C,1,4)

And the output you would get is:

cost =
40
path =
1 2 4

26 May 2014 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk Joseph Kirk

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

30 Apr 2014 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk Joseph Kirk

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

27 Apr 2014 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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.

31 Mar 2014 Dijkstra's Shortest Path Algorithm calculates the shortest path and distance between two nodes on a map Author: Joseph Kirk Joseph Kirk

@Tyler, my other version can:
http://www.mathworks.com/matlabcentral/fileexchange/20025-advanced-dijkstras-minimum-path-algorithm

19 Feb 2014 Fixed Start/End Point Multiple Traveling Salesmen Problem - Genetic Algorithm Finds a near-optimal solution to a variation of the M-TSP with fixed endpoints using a GA Author: Joseph Kirk Joseph Kirk

@sukanya, why don't you just download the file? And a rating of 1 when you apparently haven't even used the code seems a little premature, no?

28 Jan 2014 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk Joseph Kirk

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

03 Jan 2014 Fixed Start/End Point Multiple Traveling Salesmen Problem - Genetic Algorithm Finds a near-optimal solution to a variation of the M-TSP with fixed endpoints using a GA Author: Joseph Kirk Joseph Kirk

@Pedro, yes the notes are in error. They will be fixed shortly.

21 Dec 2013 Advanced Dijkstra's Minimum Path Algorithm calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm Author: Joseph Kirk Joseph Kirk

@Dee, I am not sure what you are asking. There are several examples provided in the help notes (the comment section) that you can run from the Command Window to help you get started.

09 Dec 2013 Traveling Salesman Problem - Nearest Neighbor Finds a near-optimal solution to a TSP using Nearest Neighbor (NN) Author: Joseph Kirk Joseph Kirk

@Julien, it is already generalized (other than the figure displays, which you can turn off). Regardless of the dimensionality, the cost/distance matrix will be NxN, and it is this matrix that the algorithm operates on. So the algorithm really is agnostic to the number of dimensions.

28 Oct 2013 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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).

24 May 2013 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk Joseph Kirk

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

22 May 2013 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk Joseph Kirk

Fredrik, the "showResult" flag does precisely that.

13 May 2013 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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])

26 Feb 2013 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk Joseph Kirk

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

17 Jan 2013 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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]

27 Sep 2012 Advanced Dijkstra's Minimum Path Algorithm calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm Author: Joseph Kirk Joseph Kirk

Denny, could you email me with the specific inputs you used?

04 Apr 2012 Advanced Dijkstra's Minimum Path Algorithm calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm Author: Joseph Kirk Joseph Kirk

@David, this is not a bug in my implementation as much as a limitation of Dijkstra's Algorithm in general. You may have better luck looking for an algorithm that returns the k-best shortest paths.

27 Mar 2012 Multiple Traveling Salesmen Problem - Genetic Algorithm Finds a near-optimal solution to a M-TSP using a GA Author: Joseph Kirk Joseph Kirk

Abdullah, try this one:
http://www.mathworks.com/matlabcentral/fileexchange/21299

12 Dec 2011 Vivid Colormap creates a personalized, vivid colormap Author: Joseph Kirk Joseph Kirk

@Jiro, as per your suggestion, I made a modification to the file. Now the inputs are interpretted in order from low-to-high in accordance with the standard colormap convention.

09 Dec 2011 Vivid Colormap creates a personalized, vivid colormap Author: Joseph Kirk Joseph Kirk

@Jiro, thank you. In regards to your example, it is not a bug if it was intentional. :o) I thought it was more intuitive to input colors top-to-bottom so that if inputs are provided in a "rainbow order", users would not have to think about the color sequence in reverse. For example:
>> colormap(vivid('royg'));
would have red on top and green on the bottom, which I thought made more sense than:
>> colormap(vivid('gyor'))

However, if you do not like this feature, you can replace line 136 with the following:
>> rgb = repmat(reshape(clrs,1,nc,3),ns,1);
...where I just removed the call to flipud.

02 Dec 2011 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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.

11 Nov 2011 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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?

02 Nov 2011 Plot a Directed Graph plots a directed graph represented by an adjacency matrix and xy points Author: Joseph Kirk Joseph Kirk

Kong,
1. Not sure what you mean by this. There is a '.' Marker used for the nodes.
2. Read the help notes. Rather than using arrows, a different line style is used to represent directed/undirected edges.

14 Oct 2011 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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.

05 May 2011 Multiple Traveling Salesmen Problem - Genetic Algorithm Finds a near-optimal solution to a M-TSP using a GA Author: Joseph Kirk Joseph Kirk

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

(I randomly group 8 citizens at a time, take the best one of those eight, and pass it on to the next generation. I then perform 3 different mutations on that best-of-four citizen: flip, swap, and slide. I make copies of the best-of-four and three mutated versions and mix up the length of the salesmen routes for each. The seven modified solutions are then passed on to the next generation).

05 May 2011 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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).

28 Apr 2010 multiWaitbar( label, varargin ) A new "shiny" progress-bar with multiple bars in a single window, time-estimates and more. Author: Ben Tordoff Joseph Kirk

This is *exactly* what I was looking for! I wanted a waitbar that could get called by various functions (so that I could have an "overall progress" bar along with progress updates for various subroutines) without having to pass handles around everywhere. This does all that and more... I'm really impressed (and glad I checked the File Exchange before attempting my own version). Rate it a 6!

14 Apr 2010 Variable Precision Integer Arithmetic Arithmetic with integers of fully arbitrary size. Arrays and vectors of vpi numbers are supported. Author: John D'Errico Joseph Kirk

This is quite possibly the best submission I have downloaded from the File Exchange. Great work John!

09 Mar 2010 SHADOWPLOT Add a shadow to an existing surface plot. Author: Michelle Hirsch Joseph Kirk

line 79: if length(axis==4)

I don't think this achieves the intended purpose. (axis==4) will evaluate to a logical array of either 4 or 6 elements. length(axis==4) will thus equal 4 or 6, so the if-statement will always execute.

It should be: if length(ax)==4
This will execute the if-statement if the axis view is 2D, but not if the view is already 3D.

25 Nov 2009 DSPLOT - downsampled plot This function creates a downsampled plot to improve the speed of exploration (zoom, pan) Author: Jiro Doke Joseph Kirk

This is an excellent function to have. Good work. Have you considered writing code to do something similar for other plotting functions such as IMAGESC for example?

30 Oct 2009 Traveling Salesman Problem - Genetic Algorithm Finds a near-optimal solution to a TSP using a GA Author: Joseph Kirk 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).

Contact us