Coder1994UK Coder1994UK - 1 month ago 10
Java Question

Genetic Algorithm - Partially Mapped Crossover - Java

I'm working on something quite interesting, the TSP in Genetic Algorithms, more specifically looking at Partially Mapped Crossover. For background on the code, it receives two arrays of type int which correspond to the relevant cities so for example, first and second could be 1,2,3,4,5,6,7 and 2,3,4,5,2,4,3. What happens next is I try and cross over the cities without any duplication, however when I'm executing the while loop, it doesn't seem to be able to solve my issue as it gets stuck in an infinite loop.

Essentially, I'm baffled as to why it would get stuck in a loop when eventually it should just cross Over the city and get rid of all the duplicates, but for some reason I'm forever stuck in the while!

Background of code:
SIZE = size of cities in array, parent one and parent two contain random cities of size SIZE.

Any help would be greatly aprechiated!

private int[][] partiallyMappedCrossover(int first, int second){
//Used to return an array of type int
int[][] tempArray = new int[2][SIZE];
//Used to represent the selected individuals
ArrayList<Integer> parentOne = new ArrayList<Integer>();
ArrayList<Integer> parentTwo = new ArrayList<Integer>();
ArrayList<Integer> parentOneExchange = new ArrayList<Integer>();
ArrayList<Integer> parentTwoExchange = new ArrayList<Integer>();
//Used to generate crossOverPoints
ArrayList<Integer> crossOverPoints = new ArrayList<Integer>();
crossOverPoints.add(random.nextInt(SIZE));
crossOverPoints.add(random.nextInt(SIZE));
Collections.sort(crossOverPoints);
//Used for checking the parents contents
int currentCity = 0;
int arrayIndex = 0;
int newCity = 0;

//Assign the contents of the selected parents to my parentArrays
for(int i = 0; i < SIZE; i++){
parentOne.add(population[first][i]);
parentTwo.add(population[second][i]);
}
//used to gather cities from tours and swap between randomly selected crossoverpoints
for(int k = crossOverPoints.get(0) ; k < crossOverPoints.get(1) ; k++){
//declare ints to store the city value
int a = parentOne.get(k);
int b = parentTwo.get(k);
//excahnge cities between the two crossOverPoints
parentOneExchange.add(b);
parentTwoExchange.add(a);
}

for(int i = 0; i < crossOverPoints.get(0); i++){
//get the first city from the parentOne
currentCity = parentOne.get(i);
//Check the cities
if(parentOneExchange.contains(currentCity)){
//If it does contain the city, give one the index from the exchange
arrayIndex = parentOneExchange.indexOf(currentCity);
// get the city where we have a repitition
newCity = parentTwo.get(arrayIndex);
//if the new city is also a duplicated one, do another check
while(parentOneExchange.contains(newCity)){
// get the index of the city to replace the repeated city
arrayIndex = parentOneExchange.indexOf(newCity);
// get the city that is intended to replace the repeated city
newCity = parentTwo.get(arrayIndex);
}
//replace the duplicated city with the new city
parentOne.set(i,newCity);
}
currentCity = parentTwo.get(i);
if(parentTwoExchange.contains(currentCity)){
//If it does contain the city, give one the index from the exchange
arrayIndex = parentTwoExchange.indexOf(currentCity);
// get the city where we have a repitition
newCity = parentOne.get(arrayIndex);
//if the new city is also a duplicated one, do another check
while(parentTwoExchange.contains(newCity)){
// get the index of the city to replace the repeated city
arrayIndex = parentTwoExchange.indexOf(newCity);
// get the city that is intended to replace the repeated city
newCity = parentOne.get(arrayIndex);
}
//replace the duplicated city with the new city
parentTwo.set(i,newCity);
}
}

//loop the second crosschange
for(int i = crossOverPoints.get(1); i < SIZE; i++){
//get the first city from the parentOne
currentCity = parentOne.get(i);
//Check the cities
if(parentOneExchange.contains(currentCity)){
//If it does contain the city, give one the index from the exchange
arrayIndex = parentOneExchange.indexOf(currentCity);
// get the city where we have a repitition
newCity = parentTwo.get(arrayIndex);
//if the new city is also a duplicated one, do another check
while(parentOneExchange.contains(newCity)){
// get the index of the city to replace the repeated city
arrayIndex = parentOneExchange.indexOf(newCity);
// get the city that is intended to replace the repeated city
newCity = parentTwo.get(arrayIndex);
}
//replace the duplicated city with the new city
parentOne.set(i,newCity);
}
currentCity = parentTwo.get(i);
if(parentTwoExchange.contains(currentCity)){
//If it does contain the city, give one the index from the exchange
arrayIndex = parentTwoExchange.indexOf(currentCity);
// get the city where we have a repitition
newCity = parentOne.get(arrayIndex);
//if the new city is also a duplicated one, do another check
while(parentTwoExchange.contains(newCity)){
// get the index of the city to replace the repeated city
arrayIndex = parentTwoExchange.indexOf(newCity);
// get the city that is intended to replace the repeated city
newCity = parentOne.get(arrayIndex);
}
//replace the duplicated city with the new city
parentTwo.set(i,newCity);
}
}
//Assign the new offspring to the temp array for return
for(int i = 0; i<SIZE; i++){
tempArray[0][i] = parentOne.get(i);
tempArray[1][i] = parentTwo.get(i);
}
//return the contents of my tempArray
return tempArray;
}

Answer

Reading code to find errors like this is notoriously difficult and laborious. There are lots of easier ways you can find these types of errors. I'll give you four to consider (in my personal rough order of preference):

  1. Split the various operations in your method into separate methods then write unit tests for each of those methods making sure they do exactly what you expect before moving onto the next. Once they are all working then you write a method that uses them all. Debugging a small method is much easier than debugging a large one.

  2. Add assert statements that check that the conditions that you expect to be true actually are true. I'll give an example of that below.

  3. An interactive debugger can find why your loop is not completing. That way you can see exactly what values the variables have at each point in your loop.

  4. Add log statements to record interim values as the method progresses. This allows you to ensure expected conditions are met as the algorithm progresses.

Looking at one of your while loops:

while(parentOneExchange.contains(newCity)){
    // get the index of the city to replace the repeated city
    arrayIndex = parentOneExchange.indexOf(newCity);
    // get the city that is intended to replace the repeated city
    newCity = parentTwo.get(arrayIndex);
}

This will infinitely loop any time parentTwo.get returns a city that has been previously encountered. I expect that's what's happening due to a logic error earlier in the code. You could add an assertion to ensure that's not the case:

List<Integer> previous = new ArrayList<>();
while(parentOneExchange.contains(newCity)){
    assert !previous.contains(newCity): previous;
    previous.add(newCity);
    arrayIndex = parentOneExchange.indexOf(newCity);
    newCity = parentTwo.get(arrayIndex);
}

When this assertion fails you can see the list of previously visited cities and try to understand why it is looping.

Comments