Crossover and Mutation

To understand the importance of the mutation operator interacting with the crossover operator one has to consider the contributions of each of these operators more concretely. The implementation of the crossover operator used in the algorithm is given below.

//***************************************************
// Apply a crossover operation onto two adjacent strings at intersection x
// The strings are assumed to be randomly paired in the area at position 1
//
// p := number of parameters between strings left and right (actually  p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)

function[POP]= crossover(POP,l,p,n)
  
  // Take a first row
  r=1 
  while(r < n)
    
   // printf('crossover r = %d\n',j)
   
   // Select randomly a point in this row
   
   x = round(l * rand()), if(x == 0) then x=1,end,
   
        // printf('crossover x = %d\n',x)
         
         for i=x:l, m=POP(r+1,i)
           POP(r+1,i) = POP(r,i)
           POP(r,i) = m
         end
         
         r=r+2
    end

endfunction

According to this code the crossover operator takes two strings $s, s'$ embedded in the population $POP$ in a row indicated by the index $r$ in $POP(r,...)$ and reaching from column $1$ to column $5$ represented by the index $i$.

Within a first string $s$ a random point $x$ is selected as point of reference $\langle -,-,x,-,-\rangle$.

Then will all values of the strings $s, s'$ from the selected point $x$ until the end of the both strings $l$ be exchanged. This is shown below:

$$s = \langle 0,0,0,0,0\rangle : fitness = 0$$ (4.9)

$$s' = \langle 1,1,1,1,1\rangle : fitness = 31^2$$ (4.10)

$$x = 3$$ (4.11)

$$s = \langle 0,0,1,0,0\rangle : fitness = 4^2$$ (4.12)

$$s' = \langle 1,1,0,1,1 : fitness = 27^2\rangle$$ (4.13)

$$s = \langle 0,0,1,1,0\rangle$$ (4.14)

$$s' = \langle 1,1,0,0,1\rangle$$ (4.15)

$$s = \langle 0,0,1,1,1\rangle : fitness = 5^2$$ (4.16)

$$s' = \langle 1,1,0,0,0\rangle : fitness = 24^2$$ (4.17)

In this example the overall number of zeros has not changed, not even there positions. If we would repeat the crossover-operation with different $x$ values this would not change. The only difference would be the computed fitness value which depends from the position of the 'ones' in the string.

Using selection we could select the string with the highest fitness value twice and repeat the application of the crossover operator:

$$s = \langle 1,1,0,0,0\rangle : fitness = 24^2$$ (4.18)

$$s' = \langle 1,1,0,0,0\rangle : fitness = 24^2$$ (4.19)

As one can see directly the application of the crossover operator will not change the fitness of these strings. Because they are equal in shape no exchange can change this structure furthermore.

From this follows that the application of the crossover operator only makes sense as long as the involved strings are at least in one position different.

From this one can deduce the following hypothesis when to apply the mutation operator additionally to the crossover operator.

Hypothesis: If a population $P$ has reached a 'sufficient' similarity between the information strings and the sum of all fitness values of these strings is 'sufficiently' below a known theoretical maximum, then one can apply mutation. This is nicely illustrated in the following examples.

The initial population $p$ has 11 zeros and a population $P'$ generated only by crossover after 50 cycles still 8 zeros. The 'leading' zeros have been selected out by the fitness values.

  (P) POP  =
 
    0.    1.    1.    0.    1.    13.    169.    0.    0.    0.  
    1.    1.    0.    0.    0.    24.    576.    0.    0.    0.  
    0.    1.    0.    0.    0.    8.     64.     0.    0.    0.  
    1.    0.    0.    1.    1.    19.    361.    0.    0.    0.

 (P') POP  =

         column 1 to 9
 
    1.    1.    0.    0.    1.    28.    784.    0.2774239    1.1096957  
    1.    1.    0.    0.    0.    25.    625.    0.2211607    0.8846426  
    1.    1.    1.    0.    0.    24.    576.    0.2038217    0.8152866  
    1.    1.    1.    0.    1.    29.    841.    0.2975938    1.1903751

Figure 4.13: Development without Mutation in 50 Cycles

The population $P'''$ is generated during a run of 80 cycles using crossover and every 10th cycle mutation. This population contains only 4 zeros and this population can be improved further.

 (P''') POP  =
         column 1 to 9
 
    1.    1.    1.    0.    0.    31.    961.    0.3085072    1.2340289  
    1.    1.    1.    1.    1.    23.    529.    0.1698234    0.6792937  
    1.    1.    1.    1.    1.    29.    841.    0.2699839    1.0799358  
    1.    0.    1.    0.    1.    28.    784.    0.2516854    1.0067416

Figure 4.14: Development with Mutation in 80 Cycles