Java Collections - Shuffle repeats items

Question

Right, I'm doing a GA algorithm for a college project, but as I was doing the Crossover, I noticed my individual length was changed, when it should have been 100.

I am creating an ArrayList of 100 City objects (it's a version of the Travelling Salesman), and creating a path of 100 Id numbers from it and passing it into a String[]. The ids go from 0 to 99. However, when I use the Collections class to shuffle, it is shuffling them, but it's also duplicated entries. Here's the code.

Random r = new Random(seed);
for (int i = 0; i < popSize; i++){ // popSize is population size which is 100 normally
    Collections.shuffle(baseInd, r); //baseInd is the ArrayList of 100 City objects
    for (int ii = 0; ii < baseInd.size(); ii++){
        indPath[ii] += String.valueOf(baseInd.get(ii).getID() + "."); // This is getting the current baseInd and outputting the ID to a String.
    }
    indDist[i] = Double.toString(calculateDistance(baseInd)); //method to calculate the distance from start to end on a individual.

}

This is current sample output (I'll only post the first 3 as it's long winded) and I've bolded one or two repeats. There may be more but one is too many!

0: 60+74+94+39+13+76+42+60+59+27+3+19+13+44+90+33+3+84+94+66+26+15+30+65+75+37+82+86+97+60+54+10+72+22+87+59+68+82+58+33+94+13+70+58+54+31+93+25+91+10+94+14+89+73+39+67+12+41+99+46+28+62+32+96+37+46+9+81+33+36+42+77+1+21+39+61+41+81+23+73+42+13+66+35+51+64+2+11+96+87+75+24+50+8+86+52+32+35+73+77+ Distance: 13781+834427040787

1: 2+89+43+7+58+32+71+44+96+63+2+57+12+34+53+43+94+14+97+18+91+40+18+86+46+70+46+46+46+98+50+0+45+44+94+34+17+89+72+1+9+99+40+97+88+3+12+38+5+41+2+26+74+96+33+33+29+16+74+18+10+13+96+12+16+76+77+2+0+89+18+36+88+56+35+33+28+88+35+86+61+98+99+66+31+90+23+86+45+74+2+88+80+84+19+33+81+23+90+37+ Distance: 14157+066270019255

2: 69+13+20+68+8+80+58+26+57+1+45+73+83+13+32+58+10+17+76+25+99+29+28+31+68+95+88+91+19+22+86+97+75+64+1+49+19+88+55+96+3+62+23+45+31+63+39+52+70+70+35+2+86+49+34+49+7+2+72+37+37+81+46+23+82+7+35+65+74+64+80+43+48+3+5+46+35+30+94+55+47+45+79+83+58+40+95+94+98+84+28+94+61+87+1+40+83+55+18+74+ Distance: 13178+332276530997

}

I am ensuring that the baseInd contains only one occurance of 0 to 99.

for (int a = 0; a < baseInd.size(); a++){
    System.out.print(baseInd.get(a).getID() + "+");
}

It's definitely seems (maybe!) to be the shuffle that is causing it. Any ideas?

--- More Code ----

This is the method that creates the City objects. It reads from a .csv file. I'm not concerned with this as the above code prints out 0 to 99 before any shuffle.

public static ArrayList<City> createBaseInd(ArrayList<City> baseInd){

            BufferedReader reader;
            try {
                reader = new BufferedReader(new FileReader("towns.csv"));
        String line;
        String[] lines;

        while ((line = reader.readLine()) != null)
        {
            lines = line.split(",");
            baseInd.add(new City(lines[0], Double.parseDouble(lines[1]), Double.parseDouble(lines[2]), Integer.parseInt(lines[3]))); //Struct is Name, X Co Ord, Y Co Ord, ID
        }
        reader.close();
    } catch (IOException e) {
        System.out.println("file not found");
                e.printStackTrace();
            }

        return baseInd;
}

---

There's nothing else I can really add that relevant to the problem as the issue occurs after the baseInd is created and the output isn't edited (via mutation or crossover) at this point of the output yet.

Answer 1

You should change your indexing in the inner loop from

indPath[ii] += String.valueOf(baseInd.get(ii).getID() + ".");

to

indPath[i] += String.valueOf(baseInd.get(ii).getID() + ".");

Let's look at a simple example where popSize is 2 and the shuffle results in [1, 2] twice:

After the first iteration of the outer loop, you have

indPath[0] => 1.
indPath[1] => 2.

After the second iteration of the outer loop, you have

indPath[0] => 1.1.
indPath[1] => 2.2.

Both paths contain duplicates.

Answer 2

For the uninitiated GA == genetic algorithms.

Utilizing the shuffle for any of the standard GA operations is incorrect. With crossover you have two parents, you find an index, and switch those parts of the index. If what is included is your crossover method, it is just plain wrong. It needs to look something Like this:

public TwoParents crossOver(ArrayList<> parentA, ArrayList<> parentB) {

  TwoParents toReturn = new TwoParents();  //This holds the new parent A and B.

  int index = r.nextInt(parentA.size());  //The crossover point

  //This is the copying part
  for(int i = 0;i<index;i++) {
    toReturn.parentA.add(parentA[i]);
    toReturn.parentB.add(parentB[i]);
  }

  //Now we crossover
  for(int i = index;i<parentA.size();i++) {
    toReturn.parentA.add(parentB[i]);
    toReturn.parentB.add(parentA[i]);
  }

  //return both parents
  return toReturn;
}

It is an interesting application, but if you have to visit all cities, then mutation is not an applicable operator.