TSP: creating an initial population of tours

[Pavan_5]

I am trying to develop the genetic algorithm to solve Traveling Saleman problem and part of my challenge is to generate random tours long enough and write a fitness function to evaluate the cost incurred for each of the random tour. I have attempted to write the following. My objective is to generate random tours from the city to city distance matrix without any repetitions in the tour. The random function should return a tour without any cities repeating twice. Please can any one help me with the logic for this problem:

class ran
{
public static void ranper(int n, Random newrand, int perm[])
{
int i,j,k;
for(i=1;i<=n;i++)
{
perm[i] = i;
}
for (i=1; i<=n; i++)
{
j = (int)(i + ran.nextDouble() * (n + 1 - i));
k = perm[i];
perm[i] = perm[j];
perm[j] = k;
}
System.out.println("A random permuation of " + n + " elements:");
for (i=1; i<=n; i++)
{
System.out.print(" " + perm[i]);
}

}

public static void main(String args[])
{
int n = 9,j,k,i;
long seed = 1;
int perm[] = new int[n+1];
Random newrand = new Random(seed);
randper(n, newrand, perm);
System.out.println();
}
}

[JamesCherrill]

Realistically, I doubt that anyone is going to spend any time trying to understand undocumented unindented code with meaningless variable names.
Maybe you could make it a bit easier?

[Tarek_2]

I'm not sure I understand what you want to do here (first of all, the code is not readable"), but what I know, your "perm" array is not a matrix.

[Pavan_5]

I am unable to modify the code. I am trying to . There is no "Edit Post" button in my question page. anyways I did manage to write better code. imagine the matrix is city to city distance and I am trying to generate random tours where each tour starts and ends at same city and visits all nodes atleast and exactly once.

public class randomshuffle {

    public static void main(String[] args) {
        int[] solutionArray = {0, 1, 2, 3, 4};
        int[] newar = new int[solutionArray.length+1];
        int i,x,y,z = solutionArray.length;
        int[][] distanceMatrix = {{0, 29, 82, 46, 68}, 
                                  {29,  0, 55, 46, 42},
                                  {82, 55,  0, 68, 46},
                                  {46 ,46, 68,  0, 82},
                                  {68, 42, 46 ,82,  0}};

   System.out.println(solutionArray.length);
        for (int j=0;j<=100;j++)
        {
            shuffleArray(solutionArray);
            for (i = 0; i <= solutionArray.length-1; i++)
            {
               /* if(i == solutionArray.length){
                    newar[i] == 999;
                }*/
                System.out.print(solutionArray[i]+ " ");
            }
            System.out.println();
            newar[0] = distanceMatrix[0][solutionArray[0]];
            for (i = 1; i < newar.length-1; i++)
            {
                if(i == solutionArray.length+1) {
                newar[i] = distanceMatrix[i-1][1];
                break;
                }

                x = solutionArray[i-1];
                y = solutionArray[i];
                newar[i] = distanceMatrix[x][y];
            }
            for(i=0;i<newar.length;i++){
                System.out.print(newar[i] + " ");
            }
            System.out.println();

            }
        }


    private static void shuffleArray(int[] ar) {

        int index;
        Random random = new Random();
        ar[0] = 0;
     //   for (int i = ar.length - 1; i > 1; i--)
        for (int i = 1;i < ar.length -1; i++)
        {
            index = random.nextInt(i + 1);
            if (index != i)
            {
                ar[index] ^= ar[i];
                ar[i] ^= ar[index];
                ar[index] ^= ar[i];
            }
        }
    }
}

[JamesCherrill]

That really is a whole lot better.
So now what exactly is the problem or question?

ps: Edit button behaviour is standard - you only have limited time to edit a post before people start responding. If there's some change that's really important (eg delete personal info posted by mistake) you can ask a moderator for help.

[Pavan_5]

Dear JamesCherill, My program above is expected to produce an output of random tours. http://en.wikipedia.org/wiki/Tournament_(graph_theory)

see the above is basically a 5 city network where distance between each city is provided as a "city-to-city distance" matrix. I need to find a shortest way to start from a city (could be any city), visit all cities exactly once and come back to where I started. This concept is called a tour (in graph theory) My program is suppose to produce random tours without repitions (meaning,a city cannot come twice in a given tour). If you run the output you will get a tour but that is not satisfying the condition that starting and ending city should be same and everyother city should be visitied only once. This is my requirement. Can you please help

[JamesCherrill]

Your code is heading in the right direction. You need to:

1. create an array with each city once: 1,2,3,4,5
2. shuffle it randomly
3. copy whatever is the first city and add it on the end, so now you have a 6 element array that starts and finishes with the same city and has all the other cities exactly once.

Code and test each step fully before moving on to the next. You can come back here if you get stuck.