CODEWITHSUNDEEP
genetic-algorithmevolutionary-algorithmgenetic-programming
John
John

Reputation: 3080

BB-wise uniform crossover operator in GA

I am using Building Block-wise uniform crossover in GA. I have a question that need your help. I assume that I have two population such as I1 and I2

I1: 10010 11100 00110
I2: 00011 00011 11111

I asume that my Building Block in two populations are (bold number)

I1: 10010 11100 00110

I2: 00011 00011 11111

My question is how to apply Building Block-wise uniform crossover for I1 and I2. As my known, It will swat each building block in two population together, Is it right? So the result is (assumes probability crossover is 1)

I1: 10011 00011 11111

I2: 00010 11100 00110

Upvotes: 1

Views: 259

Answers (2)

Setu Kumar Basak
Setu Kumar Basak

Reputation: 12042

Single and multi-point crossover define cross points as places between loci where an individual can be split. Uniform crossover generalizes this scheme to make every locus a potential crossover point. A crossover mask, the same length as the individual structure is created at random and the parity of the bits in the mask indicate which parent will supply the offspring with which bits. This method is identical to discrete recombination.

Consider the following two individuals with 11 binary variables each:

individual 1: 0 1 1 1 0 0 1 1 0 1 0
individual 2: 1 0 1 0 1 1 0 0 1 0 1

For each variable the parent who contributes its variable to the offspring is chosen randomly with equal probability. Here, the offspring 1 is produced by taking the bit from parent 1 if the corresponding mask bit is 1 or the bit from parent 2 if the corresponding mask bit is 0. Offspring 2 is created using the inverse of the mask, usually.

sample 1: 0 1 1 0 0 0 1 1 0 1 0
sample 2: 1 0 0 1 1 1 0 0 1 0 1

After crossover the new individuals are created:

offspring 1: 1 1 1 0 1 1 1 1 1 1 1
offspring 2: 0 0 1 1 0 0 0 0 0 0 0

  • The Uniform Crossover uses a fixed mixing ratio between two parents.
  • Unlike one- and two-point crossover, the Uniform Crossover enables the parent chromosomes to contribute the gene level rather than the segment level.
  • If the mixing ratio is 0.5, the offspring has approximately half of the genes from first parent and the other half from second parent.

Implementation in MatLab:

for i=1:2:lengthCross
            % mask1=round(rand(1,IndLength));
            mask1=randperm(IndLength)>(IndLength/2);
            mask2=not(mask1);
            child1=round(rand(1,IndLength));
            child2=round(rand(1,IndLength));

            for j=1:IndLength
                if mask1(j)==1
                    child1(j)=SelectedPop(CrossInd(i,1),j:j);
                    child2(j)=SelectedPop(CrossInd(i+1,1),j:j);
                else
                    child1(j)=SelectedPop(CrossInd(i+1,1),j:j);
                    child2(j)=SelectedPop(CrossInd(i,1),j:j);
                end
            end
            SelectedPop(CrossInd(i,1),1:IndLength)=child1;
            SelectedPop(CrossInd(i+1,1),1:IndLength)=child2;

        end

Upvotes: 0

Mihai Oltean
Mihai Oltean

Reputation: 211

crossover is performed between individuals not between populations... for each gene you randomly choose to which offspring to go. Something like this:

void uniform_crossover(chromosome parent1, chromosome parent2, chromosome offspring1, chromosome offspring2, int num_dims)
{
    // for each gene we decide randomly where it goes
    // (to the first or second offspring)
    for (int i = 0; i < num_dims; i++) {
        if (rand() % 2) {// flip
            offspring1.x[i] = parent2.x[i];
            offspring2.x[i] = parent1.x[i];
        }
        else {
            offspring1.x[i] = parent1.x[i];
            offspring2.x[i] = parent2.x[i];
        }
    }
}

full source code is here: http://create-technology.blogspot.ro/2015/03/a-genetic-algorithm-for-solving.html

Upvotes: 2

Related Questions