Нужна помощь для генетического алгоритма Однопоточный механизм кроссовера в Java

Question

Я использую простой генетический алгоритм (GA) с использованием Java. Шаги моей GA - это в основном двоичное кодирование, выбор турниров, одноточечный кроссовер и битовая мутация. Каждый индивидуум популяции представлен классом, состоящим из двоичных генов и значения пригодности.

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

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

кода ниже, не включает в себя побитовую мутации части, как я перед проблемой в одной точке части кроссовера ГА. Способ, которым я реализовал одноточечный алгоритм кроссовера, - это случайное обнаружение точки для двух последовательных отдельных элементов массива, а затем замена их хвостов. Затем происходит перестановка хвоста для каждой пары индивидуумов. Я также создал метод printGenome(), чтобы распечатать все массивы для сравнения, результирующий массив после того, как кроссовер не был правильно заменен. Я тестировал свой одноточечный алгоритм кроссовера отдельно, он работает. Однако, когда я попытался запустить его здесь в приведенных ниже кодах, кроссовер просто не работает. Могу ли я узнать, потому что в алгоритме выбора турнира есть что-то не так? Или это что-то еще (глупые ошибки)? Я перерабатывал его, и все же я не мог точно определить ошибку.

Я был бы признателен за любую информацию! :)

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

Проблема заключается в том, что в вашем выборе вы (скорее всего) дублируя лицо, когда вы говорите:

потомства [я] = население [Parent1]

Фактически вы сохраняете ссылку на популяцию [parent1] в потомстве [i]. В результате ваш массив потомков может содержать одну и ту же ссылку несколько раз, поэтому один и тот же объект будет участвовать в кроссовере несколько раз с несколькими партнерами.

В качестве решения вы можете хранить клон вместо ссылки на тот же объект. В индивидуальных оном:

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

И в своем выборе (обратите внимание на добавленную .clone()):

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

Таким образом, каждый элемент в потомстве является другим объектом, даже если геном таким же ,

Это решает часть Java. Что касается теории GA, я надеюсь, что некоторые вещи, например, ваша фитнес-мера - это просто заполнители, верно?