유전자 알고리즘 - 부분 매핑 된 크로스 오버 - Java

Question

저는 유전자 알고리즘의 TSP, 특히 부분 매핑 된 크로스 오버를 흥미롭게 연구하고 있습니다. 코드에 대한 배경 정보는 관련 도시에 해당하는 int 유형의 두 배열을받습니다. 예를 들어 첫 번째와 두 번째는 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

이와 같은 오류를 찾기위한 코드 읽기는 어렵고 힘든 일입니다. 이러한 유형의 오류를 쉽게 찾을 수있는 방법이 많이 있습니다. 나는 (선호 내 개인 거친 순서대로) 고려하는 당신에게 사주지 : 별도의 방법으로 당신의 방법의 다양한 작업을 후하게 그 각각의 방법에 대한 단위 테스트를 작성

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

이 주장은 당신이 이전에 방문한 도시의 목록을 확인하고이 반복되는 이유를 이해하려고 할 수 실패합니다.