遺伝的アルゴリズム - 部分的にマップされたクロスオーバー - Java

Question

私は非常に興味深い、遺伝的アルゴリズムのTSP、特に部分的にマッピングされたクロスオーバーを調べています。コードのバックグラウンドについては、関連する都市に対応するint型の2つの配列を受け取ります。たとえば、1,2,3,4,5,6,7および2,3,4,5、 2,4,3。次に何が起こるかは、重複することなく都市を越えようとしていますが、whileループを実行すると、無限ループに陥っても問題は解決できないようです。

最終的に都市を越えてすべての重複を取り除く必要があるときに、なぜそれがループに詰まってしまうのか、私はいつも困惑しています。

コードの背景 SIZE =配列内の都市のサイズ、親1と親2にサイズ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

このようなエラーを見つけるためのコードを読むことは、非常に困難で面倒です。これらのタイプのエラーを簡単に見つける方法はたくさんあります。私は（好みの私の個人的なラフな順序で）検討することあなたに4をあげる：

1. スプリットをあなたの方法で様々な操作を別の方法に、彼らは正確に何をすべきかを確認し、それらの各メソッドのためのユニットテストを書きますあなたは次へ進む前に期待しています。彼らがすべて働いたら、それらをすべて使用するメソッドを作成します。小さなメソッドをデバッグするのは、大きなメソッドをデバッグするよりはるかに簡単です。

2. assertステートメントを追加して、実際に真となる条件が真であることを確認します。私は下の例を挙げます。

3. ループが完了していない理由を対話型デバッガが検出できます。こうすることで、ループ内の各ポイントで変数にどのような値が含まれているかを正確に確認できます。

4. メソッドの進行に合わせて暫定値を記録するためのログステートメントを追加します。これにより、アルゴリズムの進行に合わせて期待される条件が満たされるようにすることができます。あなたの中の一つを見てみると

ループ：

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を無限になり、以前に遭遇した街を返します。私は、コードの前の論理エラーのために起こっていることを期待しています。あなたはそれがケースではありません確実にするためのアサーションを追加することができます。

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

この主張は、あなたが以前に訪れた都市のリストを表示し、それがループしている理由を理解しようとすることができないとき。