Genetic Algorithm - Partially Mapped Crossover - Java

Question

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 1

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.