Using my own distribution matrix in the TSP Algorithm used in tsp_ga (found in the file exch)?

[EDIT: 20110602 02:26 CDT - reformat - WDR]

I'm not sure how I would input my score matrix--->

Name: scorematrix size: 145x145 Class: Double

Here is the input section of the code---->

nargs = 6;
for k = nargin:nargs-1
    switch k
        case 0
            xy = 10*rand(50,2);
        case 1
            N = size(xy,1);
            a = meshgrid(1:N);
            dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);
        case 2
            pop_size = 100;
        case 3
            num_iter = 1e4;
        case 4
            show_prog = 1;
        case 5
            show_res = 1;
        otherwise
    end
end

These are the author's definition of the parameters----->

Input:
%     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
%     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
%

I am stumped on how to get my matrix into the calculation, I would appreciate any help.

Thank you

Answer 1

[Walter Roberson]

Just make sure that you pass at least two parameters to the routine, with the second one being your distance matrix.

[Adam Quintero]

It looks like I need to pass the distance matrix to the dmat line, I am unclear as to where in the code I can specify this.

case 1

N = size(xy,1);

a = meshgrid(1:N);

-----> dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);

Also, would another parameter be the number of sequences?

[Walter Roberson]

What the code is doing is providing default values if you did *not* pass in the corresponding variable. If you _did_ pass in the corresponding variable then what you passed in would be used. So in your case,

tsp_ga(CityLocations, YourDistanceMatrix, NumberOfSequences)

I am not certain, though, that "population size" and "number of sequences" are the same. I think there might be a clash of terminology.

Answer 2

[Chijioke]

Hi

I am encountering the same challenge. Do I define the XY matrix (NX2) by any arbitrary set of points (values). I took out the Dmat and replaced it with my cost matrix.

Thanks

[Adam Quintero]

It is my understanding that the XY values are just labels for each point on the distance matrix. For example, if the distance matrix is 10x10, the XY matrix should consist of two vectors with the whole numbers 1-10.

I am curious to know how you are applying this algorithm. I am using it to objectively rate MSA's by calculating the probability that the alignment being studied results from random mutation or coincidence. The locations are DNA sequences and the distances are in PAM 50, which simulates the accumulation of random mutations over time ("units" of evolutionary distance).

[Chijioke]

I am actually applying the algorithm to the traveling salesman problem. I am optimizing the transit in a rural area. I need it to design a transit system in a little county in South Carolina.

Which is the correct format for XY?

XY {1 2 3 4....10; 1 2 3 4.....10}

XY {1 1; 2 2; 3 3; 4 4;......10 10}

Concerning the straight line in the distance matrix plot. How about inputting a large figure or cost from point 1 to 1 instead of 0 (zero). And what did you do to prevent the algorithm from reading the 0 (zeros) from a point to itself?

If you don't mind, I would like to see how you modified the code (or pass your

distance matrix to the dmat line, as well as any changes you made). I tried

Q = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);

where Q is my distance matrix. replacing all other dmat points in the code with Q. Still getting the straight line. Really appreciate your help here.

Thanks

Answer 3

[Adam Quintero]

thank you, I now see how to properly input my data. I have a question about the xy format, the author states that it is an Nx2 matrix of the city locations. I created this matrix:

 1        1
 2        2
to 145   to 145

my distance matrix (dmat) is a 145x145 matrix with the distances for:

    1    2    3  etc
______________________
1 | 0    28   11
  |
2 | 6     0    77
  | 
3 | 13    44   0
  |
etc

This format produces a straight line with -1 slope from (1,145) to (145,1)

Am I formatting these wrong, I am stuck on this one. Help appreciated. Thank you

[Adam Quintero]

how can I remove the diagonal of zeros, because I think the algorithm is finding the least cost path to be zero...

[Walter Roberson]

0 for the distance of a point to itself should be correct.

I was thinking there was a problem with your XY, but I see by looking at the code that XY is only used for plotting the progress or showing the result and is not used in the distance calculation.

Are you sure you want your distance matrix to be so asymmetric? Why would it cost 6 to go from 2 to 1, but 28 to go from 1 to 2? I know that there could be one-way roads, but the difference would seldom be that much.

It appears to me by reading the code that it supposes point to point links between every pair of cities, and that the way to work around that would be to use inf as the distance between any two points for which there is no direct route. I would think that should be done liberally if one wishes to simulate roads instead of air travel.