Java의 유전 알고리즘 단일 포인트 크로스 오버 메커니즘에 대한 도움이 필요합니다.

Question

저는 Java를 사용하여 간단한 유전 알고리즘 (GA)을 구현했습니다. 내 GA의 단계는 기본적으로 이진 인코딩, 토너먼트 선택, 단일 포인트 크로스 오버 및 비트 현자 변이입니다. 모집단의 각 개체는 이진 유전자와 적합성 값으로 구성된 클래스로 표현됩니다.

public class Individual { 
    int gene[]; 
    int fitness; 

    public Individual(int n){ 
     this.gene = new int[n]; 
    } 
} 

나는 조지아의 단일 - 포인트 크로스 오버 부분에서 문제에 직면 한대로 코드는 아래의 비트 단위 돌연변이 부분을 포함하지 않습니다. 단일 포인트 크로스 오버 알고리즘을 구현 한 방법은 무작위로 2 개의 연속적인 개별 배열 요소에 대한 포인트를 찾아서 꼬리를 교환하는 것입니다. 꼬리 교환은 개인의 각 쌍마다 반복됩니다. 또한 비교할 모든 배열을 출력하기 위해 printGenome() 메서드를 만들었습니다. 결과 배열은 크로스 오버 프로세스가 제대로 바뀌지 않은 후에 나타납니다. 내 싱글 포인트 크로스 오버 알고리즘을 별도로 테스트했지만 작동합니다. 그러나 아래의 코드에서이 코드를 실행하려고하면 크로스 오버가 작동하지 않습니다. Tournament Selection 알고리즘에 잘못된 것이 있기 때문에 그 사실을 알 수 있습니까? 아니면 뭔가 다른 것입니까 (어리석은 실수)? 나는 그것에 재 작업하고 여전히 오류를 정확하게 지적 할 수 없었다.

제공된 도움말 및 정보에 감사드립니다. :)

public class GeneticAlgorithm { 

    public static void main(String[] args) { 
     int p = 10; 
     int n = 10; 
     Individual population[]; 

     //create new population 
     population = new Individual[p]; 

     for (int i = 0; i < p; i++) { 
      population[i] = new Individual(n); 
     } 

     //fills individual's gene with binary randomly 
     for (int i = 0; i < p; i++) { 
      for (int j = 0; j < n; j++) { 
       population[i].gene[j] = (Math.random() < 0.5) ? 0 : 1; 
      } 
      population[i].fitness = 0; 
     } 

     //evaluate each individual 
     for (int i = 0; i < p; i++) { 
      for (int j = 0; j < n; j++) { 
       if (population[i].gene[j] == 1) { 
        population[i].fitness++; 
       } 
      } 
     } 

     //total fitness check 
     System.out.println("Total fitness check #1 before tournament selection: " + getTotalFitness(population, p)); 
     System.out.println("Mean fitness check #1 before tournament selection: " + getMeanFitness(population, p)); 
     System.out.println(""); 

     //tournament selection 
     Individual offspring[] = new Individual[p]; 

     for (int i = 0; i < p; i++) { 
      offspring[i] = new Individual(n); 
     } 

     int parent1, parent2; 
     Random rand = new Random(); 
     for (int i = 0; i < p; i++) { 
      parent1 = rand.nextInt(p); //randomly choose parent 
      parent2 = rand.nextInt(p); //randomly choose parent 

      if (population[parent1].fitness >= population[parent2].fitness) { 
       offspring[i] = population[parent1]; 
      } else { 
       offspring[i] = population[parent2]; 
      } 
     } 

     //total fitness check 
     System.out.println("Total fitness check #2 after tournament selection: " + getTotalFitness(offspring, p)); 
     System.out.println("Mean fitness check #2 after tournament selection: " + getMeanFitness(offspring, p)); 
     System.out.println(""); 

     //genome check 
     System.out.println("Before Crossover: "); 
     printGenome(offspring, p, n); 

     //crossover 
     for (int i = 0; i < p; i = i + 2) { 
      int splitPoint = rand.nextInt(n); 
      for (int j = splitPoint; j < n; j++) { 
       int temp = offspring[i].gene[j]; 
       offspring[i].gene[j] = offspring[i + 1].gene[j]; 
       offspring[i + 1].gene[j] = temp; 
      } 
     } 

     //genome check 
     System.out.println("After Crossover:"); 
     printGenome(offspring, p, n); 

     //evaluate each individual by counting the number of 1s after crossover 
     for (int i = 0; i < p; i++) { 
      offspring[i].fitness = 0; 
      for (int j = 0; j < n; j++) { 
       if (offspring[i].gene[j] == 1) { 
        offspring[i].fitness++; 
       } 
      } 
     } 

     //total fitness check 
     System.out.println("Total fitness check #3 after crossover: " + getTotalFitness(offspring, p)); 
     System.out.println("Mean fitness check #3 after crossover: " + getMeanFitness(offspring, p)); 
    } 

    public static void printGenome(Individual pop[], int p, int n) { 
     for (int i = 0; i < p; i++) { 
      for (int j = 0; j < n; j++) { 
       System.out.print(pop[i].gene[j]); 
      } 
      System.out.println(""); 
     } 
    } 

    public static int getTotalFitness(Individual pop[], int p) { 
     int totalFitness = 0; 
     for (int i = 0; i < p; i++) { 
      totalFitness = totalFitness + pop[i].fitness; 
     } 
     return totalFitness; 
    } 

    public static double getMeanFitness(Individual pop[], int p) { 
     double meanFitness = getTotalFitness(pop, p)/(double) p; 
     return meanFitness; 
    } 

} 

Answer 1

문제는, 당신의 선택에 당신은 당신이 말하는 개인, 복제 (가능성이) 있다고 :

자손 [내가] = 인구 [상위 1]

을

실제로 인구 [parent1]에 대한 참조를 자식들 [i]에 저장하고 있습니다. 결과적으로 자손 배열에는 동일한 참조가 여러 번 포함될 수 있으므로 동일한 객체가 여러 파트너와 교차하여 여러 번 참여하게됩니다.

해결책으로 동일한 객체에 대한 참조 대신 복제본을 저장할 수 있습니다. 개인 담기 : 게놈이 동일한 경우에도, 자손의 모든 요소가 다른 객체이다

for (int i = 0; i < p; i++) { 
     parent1 = rand.nextInt(p); //randomly choose parent 
     parent2 = rand.nextInt(p); //randomly choose parent 

     if (population[parent1].fitness >= population[parent2].fitness) { 
      offspring[i] = population[parent1].clone(); 
     } else { 
      offspring[i] = population[parent2].clone(); 
     } 
    } 

이 방법 :

public Individual clone(){ 
     Individual clone = new Individual(gene.length); 
     clone.gene = gene.clone(); 
     return clone; 
    } 

그리고 당신의 선택에

은 (추가 .clone()를 참고) .

그게 자바 부분을 해결합니다. GA 이론에 관해서는, 예를 들어 피트니스 측정이 단지 자리 표시 자일 뿐이라는 희망이 있습니다.