유전 알고리즘이 지역 최소치에서 수렴하는 것을 방지하는 방법은 무엇입니까?

Question

유전자 알고리즘을 사용하여 4 x 4 스도쿠 해결사를 만들려고합니다. 로컬 미니 마에 수렴하는 가치에 몇 가지 문제가 있습니다. 나는 순위가 매겨진 접근법을 사용하고 아래쪽의 두 가지 순위가있는 답변 가능성을 제거하고 가장 높은 순위의 두 가지 답변 가능성 사이의 교차점으로 대체합니다. 현지 mininma를 피하는 추가 도움을 위해, 나는 또한 돌연변이를 사용하고있다. 특정 세대 내에 응답이 결정되지 않으면 나의 인구는 완전히 새로운 무작위 상태 값으로 채워집니다. 그러나, 내 알고리즘은 로컬 미니 마에 갇혀있는 것 같습니다. 피트니스 기능으로, 내가 사용하고 :

(오픈 사각형의 총 금액은 * 7 (수 각 광장에서 위반, 행, 열 및 상자)) - 총 위반

을

인구은의 ArrayList에있다 각 배열이 입력을 기반으로하는 스도쿠의 가능한 종료 상태 인 정수 배열. 피트니스는 모집단의 각 배열에 대해 결정됩니다.

누군가 내 알고리즘이 로컬 미니 마에 수렴하는 이유를 판단하는 데 도움을 줄 수 있습니까, 아니면 로컬 미니 마를 피하기 위해 사용할 기술을 권장 할 수 있습니까? 어떤 도움이라도 대단히 감사합니다.

피트니스 기능 :

public int[] fitnessFunction(ArrayList<int[]> population) 
{ 
    int emptySpaces = this.blankData.size(); 
    int maxError = emptySpaces*7; 
    int[] fitness = new int[populationSize]; 

    for(int i=0; i<population.size();i++) 
    { 
     int[] temp = population.get(i); 
     int value = evaluationFunc(temp); 

     fitness[i] = maxError - value; 
     System.out.println("Fitness(i)" + fitness[i]); 
    } 

    return fitness; 
} 

크로스 오버 기능 :

public void crossover(ArrayList<int[]> population, int indexWeakest, int indexStrong, int indexSecStrong, int indexSecWeak) 
{ 
    int[] tempWeak = new int[16]; 
    int[] tempStrong = new int[16]; 
    int[] tempSecStrong = new int[16]; 
    int[] tempSecWeak = new int[16]; 

    tempStrong = population.get(indexStrong); 
    tempSecStrong = population.get(indexSecStrong); 
    tempWeak = population.get(indexWeakest); 
    tempSecWeak = population.get(indexSecWeak); 
    population.remove(indexWeakest); 
    population.remove(indexSecWeak); 


    int crossoverSite = random.nextInt(14)+1; 

    for(int i=0;i<tempWeak.length;i++) 
    { 
     if(i<crossoverSite) 
     { 
      tempWeak[i] = tempStrong[i]; 
      tempSecWeak[i] = tempSecStrong[i]; 
     } 
     else 
     { 
      tempWeak[i] = tempSecStrong[i]; 
      tempSecWeak[i] = tempStrong[i]; 
     } 
    } 
    mutation(tempWeak); 
    mutation(tempSecWeak); 
    population.add(tempWeak); 
    population.add(tempSecWeak); 

    for(int j=0; j<tempWeak.length;j++) 
    { 
     System.out.print(tempWeak[j] + ", "); 
    } 
    for(int j=0; j<tempWeak.length;j++) 
    { 
     System.out.print(tempSecWeak[j] + ", "); 
    } 
} 

돌연변이 기능 :

public void mutation(int[] mutate) 
{ 
    if(this.blankData.size() > 2) 
    { 
     Blank blank = this.blankData.get(0); 
     int x = blank.getPosition(); 

     Blank blank2 = this.blankData.get(1); 
     int y = blank2.getPosition(); 

     Blank blank3 = this.blankData.get(2); 
     int z = blank3.getPosition(); 

     int rando = random.nextInt(4) + 1; 

     if(rando == 2) 
     { 
      int rando2 = random.nextInt(4) + 1; 
      mutate[x] = rando2; 
     } 
     if(rando == 3) 
     { 
      int rando2 = random.nextInt(4) + 1; 
      mutate[y] = rando2; 
     } 
     if(rando==4) 
     { 
      int rando3 = random.nextInt(4) + 1; 
      mutate[z] = rando3; 
     } 
    } 

Answer 1

목 빠른 융합이 나타나는 이유는 "짝짓기"를위한 방법론이 그리 좋지 않다는 것입니다. 당신은 항상 상위 2 명의 득점자의 "짝짓기"에서 두 명의 자손을 낳고 있습니다. 새로운 자손 중 하나가 당신의 최고 개체와 동일 할 때 (우연히도, 교차 및 돌연변이가 없거나, 최소한 피트니스에 영향을주지 않는 경우) 어떻게되는지 상상해보십시오. 이것이 발생하면 상위 2 인의 개체가 동일하여 교차 효과를 제거합니다.

더 일반적인 방법은 모든 세대마다 모든 개인을 대체하는 것입니다. 여기에는 여러 가지 변형이있을 수 있지만 두 부모가 가중치를 매기는 임의 선택을 할 수 있습니다.

인구 규모에 대해 : 스도쿠가 유전 적 표현과 체력 기능에 얼마나 큰 어려움을 겪었는지 나는 알지 못하지만, 수십 명이 아니라 수백만 명의 개인을 생각해 보길 권합니다.

어려운 문제에 대해 작업하는 경우 유전자 알고리즘은 2D 그리드에 인구를 배치하고 근처 개체의 그리드에서 각 포인트에 대해 "부모"를 선택하는 경우 훨씬 더 효과적입니다. 당신은 지역 컨버전스를 얻지 만, 각 지역은 다른 솔루션으로 수렴 할 것입니다. 그리드의 국부적으로 수렴 된 영역들 사이의 경계로부터 생성 된 엄청난 양의 변동을 얻습니다.

당신이 생각할 수있는 또 다른 기술은 무작위 집단으로부터의 수렴을 여러 번 실행하고 각 실행으로부터 최고의 개인을 저장하는 것입니다. 여러 가지 다른 지역 미니 마 게놈을 구축 한 후 상위 개인으로부터 새로운 무작위 인구를 구축하십시오.

Answer 2

스도쿠는 순열 문제라고 생각합니다.그러므로 인구 초기화를 위해 무작위 순열 (random permutation) 숫자를 사용하고 순열 문제와 호환되는 교차 방법을 사용하는 것이 좋습니다.