Генетические алгоритмы: равномерный кроссовер только в части генотипа

Question

Мне нужно реализовать генетический оператор "равномерного кроссовера".

Редактировать: я понял, что это нормально иметь дубликаты (из-за случайного обмена), если число появляется у обоих лиц. Итак, я добавил это:

            if(anyDuplicate(p0_genome,minIndex) || anyDuplicate(p1_genome,minIndex)){
                                //rollback: swap again
                                swap(p0_genome,p1_genome,i);
                            }

но он все еще создает дубликаты (большую часть времени гена в положении minIndex (что исключено из цикла!!!) . Конечно, я тестировал функцию anyDuplicate, и она работает очень хорошо

Я пробовал с этим кодом

> Note: Individual 1 and 2 have the same length but a different number
> of valid bits.
> 
> Foe example: genotype length (of both individuals) = 10 ,
> representation as numbers from 1 to 10 without anyone repeated,the
> start delimiter is 1 and the end delimiter should be 2. Not used genes
> are = 0
> 
> individual 1(p0_genome) = {1,4,5,3,2,0,0,0,0,0}
> individual 2(p1_genome) = {1,4,6,3,8,2,0,0,0,0}

Желаемый выход:

Individual 1(p0_genome): **1** <some genes ALL DIFFERENTS> **2** 0,0,0,.....
Individual 2(p1_genome): **1** <some genes ALL DIFFERENTS> **2** 0,0,0,.....

Основной код:

            int indexOfLastP0 = findLast(p0_genome,gl); // last valid bit (the one = 2) of first individual
            int indexOfLastP1 = findLast(p1_genome,gl); // last valid bit (the one = 2) of second individual

            int minIndex = Math.min(indexOfLastP0,indexOfLastP1); // last valid bit of the "smaller" of the inviduals

    // Building sons
  /* exchange bit without considering delimiters bit (1 and 2)
   and according to the smaller individual */
            int threshold = 0.60;

    for (int i=1; i<minIndex; i++) {
        if (Math.Random()>threshold) {
            swap(p0_genome,p1_genome,i);
        }
    // when exiting the loop the remaining of genes remain the same

Код обмена:

    public void swap(int[] array1, int[] array2 ,int i){
        int aux=array1[i];
        if (array2[i]!=2){
        array1[i]=array2[i];
                }
        if (aux!=2){
        array2[i]=aux;
                }            

код anyDuplicate():

 public boolean anyDuplicate(int[] genoma,int min){
        for (int i=0;i<=min;i++){
            for (int j=0;j<=min;j++){
               if (genoma[i]==genoma[j] && i!=j){
                  return true;
               }
            }
        }
        return false;
    }        

findLast код:

    public int findLast(int[] mgenome,int genotypeLength){
        int k=1; // 1 element is not considered
        while (k<genotypeLength && mgenome[k]!=0){
            k++;
        }
        return k-1; // **I also tried returning k;**
    }

Проблема в том, что я получаю много одинаковых номеров у обоих лиц

Я также попытался с "дубликатом"(arraycopy от родителя к ребенку) "отцов":

    // Creating sons genotypes
    int [] s0_genome = new int[gl];
    int [] s1_genome = new int[gl];
    // Building sons
          int threshold = 0.60;
    for (int i=0; i<minIndex; i++) {
        if (Math.Random()>threshold)) {
            s0_genome[i] = p1_genome[i];
            s1_genome[i] = p0_genome[i];
        }
        else {
            s0_genome[i] = p0_genome[i];
            s1_genome[i] = p1_genome[i];
        }
             for (int i=minIndex; i<10; i++) {
               // copy what's left
            s0_genome[i] = p0_genome[i];
            s1_genome[i] = p1_genome[i];
        }

Я делаю что-то неправильно? Спасибо за любую подсказку!

Answer 1

Итак, вы пытаетесь поменяться местами один раз, и если любой из полученных геномов содержит повторяющиеся значения, вы попробуйте поменять местами снова. Если после второй попытки все еще есть дубликаты, вы сдаетесь. Это неэффективно, и чем дольше ваши геномы, тем менее вероятно, что это сработает.

Решение A: Вы можете попробовать выполнить обмен только в том случае, если измененное значение еще не находится в целевом геноме. Это дало бы функцию подкачки следующим образом:

public void swap(int[] array1, int[] array2 ,int i){
    int aux=array1[i];
    if (array2[i]!=2 && !Arrays.asList(array1).contains(array2[i]){
    array1[i]=array2[i];
            }
    if (aux!=2 && !Arrays.asList(array2).contains(array1[i]){
    array2[i]=aux;
            }

Проблема в том, что он может полностью блокировать геномы, которые содержат одинаковые значения в разных позициях. Для вашего примера, с

g1 = {1, 4, 8, 9, 3, 2, 0, 0}
g2 = { 1, 3, 9, 8, 4, 2, 0, 0}

Не было бы никаких действительных обменов вообще, и кроссовер возвратил бы оригинальные геномы.

Решение B. Если значение, которое нужно поменять местами, уже присутствует в целевом геноме, найдите индекс этого гена в целевом геноме и поменяйте его местами. Это может каскадно потребовать перестановок в больших частях генома, и, конечно, это не должно происходить, когда i=j.

Вид зависит от желаемого поведения. Для приведенных выше примеров геномов, как будет выглядеть успешный кроссовер?