遗传算法 - 部分映射交叉 - Java

Question

我正在研究一些非常有趣的东西，遗传算法中的 TSP，更具体地说是研究部分映射交叉。对于代码的背景，它接收两个对应于相关城市的 int 类型数组，例如，first 和 second 可以是 1,2,3,4,5,6,7 和 2,3,4,5， 2,4,3。接下来会发生什么，我尝试不重复地穿越城市，但是当我执行 while 循环时，它似乎无法解决我的问题，因为它陷入了无限循环。

从本质上讲，我很困惑为什么它最终应该穿过城市并摆脱所有重复项时会陷入循环，但由于某种原因我永远陷入困境!

代码背景： SIZE = 数组中城市的大小，父一和父二包含大小为 SIZE 的随机城市。

任何帮助将不胜感激！

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

阅读代码以查找此类错误是出了名的困难和费力。有许多更简单的方法可以找到这些类型的错误。我会给你四个考虑（按照我个人的大致偏好顺序）：

将方法中的各种操作拆分为单独的方法，然后为每个方法编写单元测试，确保它们完全按照您的预期进行，然后再进行下一个。一旦它们都正常工作，您就可以编写一个使用它们的方法。调试小方法比调试大方法容易得多。
添加 assert 语句来检查您期望为真的条件是否真的为真。我将在下面举一个例子。
交互式调试器可以找到您的循环未完成的原因。这样您就可以准确地看到变量在循环中每个点的值。
添加日志语句以在方法进行时记录临时值。这使您可以确保在算法进行时满足预期条件。

查看您的 while 循环之一：

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);
}

这将在任何时候无限循环 parentTwo.get returns 一个以前遇到过的城市。我希望这是由于代码前面的逻辑错误而发生的事情。您可以添加断言以确保不是这种情况：

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);
}

当此断言失败时，您可以查看之前访问过的城市列表，并尝试理解它循环的原因。

遗传算法 - 部分映射交叉 - Java

Genetic Algorithm - Partially Mapped Crossover - Java

java

arrays

sorting

while-loop

genetic-algorithm