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

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

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

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

найти последний код:

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

Проблема в том, что я получаю много повторяющихся чисел у обоих людей

Я также пытался использовать «дубликат» (массив копий от родителя к дочернему) «отцов»:

    // 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];
        }

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


person dragonmnl    schedule 02.06.2012    source источник
comment
как примечание, Math.Random более предвзят и неэффективен по сравнению со Random. id предлагает вместо этого использовать класс Random.   -  person Dhruv Gairola    schedule 02.06.2012
comment
Или, что еще лучше, используйте генератор чисто случайных чисел, основанный на /dev/random или подобном; любой PRNG в конечном итоге приведет к шаблонам, которые могут вызвать неожиданные, но тонкие вещи.   -  person fluffy    schedule 02.06.2012
comment
Где код для swap()? Что вы подразумеваете под дубликатом и как будет выглядеть желаемый результат?   -  person Junuxx    schedule 02.06.2012


Ответы (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}

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

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

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

person Junuxx    schedule 02.06.2012
comment
Я пробовал с Решением А, но проблема та же. Раньше я пробовал с Solution B, но это было еще хуже - person dragonmnl; 02.06.2012
comment
Похоже, проблема вызвана побочным эффектом равномерного кроссовера. Однако я попробую еще немного и приму ваш ответ за усилия. - person dragonmnl; 03.06.2012
comment
@dragonmnl: Вы можете попытаться продолжить обмен до тех пор, пока вы получаете дубликаты (измените if(anyDuplicate... на while(anyDuplicate...), но это может занять очень много времени или может вообще не завершиться, если кроссовер без дубликатов невозможен. - person Junuxx; 03.06.2012
comment
В связи с этим я решил переписать код с нуля и изменить еще кое-что в приложении. Большое спасибо за приложенные усилия! - person dragonmnl; 04.06.2012