Genetic Algorithms: Crossover Operators and Mutation

For this blog, I will be writing about the task designated for session 9.

Assume that your GA has chromosomes in the following structure:

ch = (x0, x1, x2, x3, x4, x5, x6, x7)

x0–7 can be any digit between zero to nine.
The fitness of each chromosome is calculated using the following formula:

f(ch) = (x0 + x1) − (x2 + x3) + (x4 + x5 ) − (x6 + x7)

This problem is a maximisation problem.

In this scenario we initially have a population of four chromosomes as shown below:

ch1 = (6, 5, 4, 1, 3, 5, 3, 2)

ch2 = (8, 7, 1, 2, 6, 6, 0, 1)

ch3 = (2, 3, 9, 2, 1, 2, 8, 5)

ch4 = (4, 1, 8, 5, 2, 0, 9, 4)

Part I: Calculating fitness of each individual:

ch1 = (6+5)-(4+1)+(3+5)-(3+2) = 7
ch2 = (8+7)-(1+2)+(6+6)-(0+1) = 23
ch3 = (2+3)-(9+2)+(1+2)-(8+5) = -16
ch4 = (4+1)-(8+5)+(2+0)-(9+4) = -19

Order of fitnesses: ch2, ch1, ch3, ch4

Part II: Crossover operators:

Get Becky Johnson’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

One-point chromosome to cross the best two chromosomes:

ch2 = (8, 7, 1, 2, | 6, 6, 0, 1)
ch1 = (6, 5, 4, 1, | 3, 5, 3, 2)
child1 = (6, 5, 4, 1, | 6, 6, 0, 1)
child2 = (8, 7, 1, 2, | 3, 5, 3, 2)

Two-point chromosome to cross the second and third best chromosomes:

ch1 = (6, 5, | 4, 1, 3, 5, | 3, 2)
ch3 = (2, 3, | 9, 2, 1, 2, | 8, 5)
child3 = (6, 5, | 9, 2, 1, 2, | 3, 2)
child4 = (2, 3, | 4, 1, 3, 5, | 8, 5)

Uniform crossover to cross the first and third best chromosomes:

ch2 = (8, 7, 1, 2, 6, 6, 0, 1)
ch3 = (2, 3, 9, 2, 1, 2, 8, 5)
child5 = (8, 3, 1, 2, 6, 2, 0, 5)
child6 = (2, 7, 9, 2, 1, 6, 8, 1)

Part III: Fitnesses of newly generated offspring:

child1 = (6, 5, 4, 1, | 6, 6, 0, 1) = (6+5)-(4+1)+(6+6)-(0+1) = 17
child2 = (8, 7, 1, 2, | 3, 5, 3, 2) = (8+7)-(1+2)+(3+5)-(3+2) = 15
child3 = (6, 5, | 9, 2, 1, 2, | 3, 2) = (6+5)-(9+2)+(1+2)-(3+2) = -2
child4 = (2, 3, | 4, 1, 3, 5, | 8, 5) = (2+3)-(4+1)+(3+5)-(8+5) = -5
child5 = (8, 3, 1, 2, 6, 2, 0, 5) = (8+3)-(1+2)+(6+2)-(0+5) = 11
child6 = (2, 7, 9, 2, 1, 6, 8, 1) = (2+7)-(9+2)+(1+6)-(8+1) = -4

In this particular instance, the crossover function created children with fitnesses that lie within the distance of their parents fitnesses. For example:

One-point: 23 and 7 --> 17 and 15
Two-point: 7 and -16 --> -2 and -5
Uniform: 23 and -16 --> 11 and -4

No child exceeded both of their parent’s fitness, however perhaps this is a natural occurrence of crossover within the first few generations. The children instead seem to average the strengths of their parents and lie within the difference of the two. In order to create children with fitnesses that either surpassing or fall below the fitness of both parents, mutation seems essential in order to create new chromosomes with new dissimilar and distinctive genes.

Part IV

As this is a maximisation problem, the optimal chromosome would provide a gene that subtracts nothing in the fitness equation whilst adding the highest value possible, 9. The optimal candidate solution would serve as [9, 9, 0, 0, 9, 9, 0, 0] so that the fitness evaluates to (9+9)-(0+0)+(9+9)-(0+0) = 36.

Part V

Without the mutation operator present, the optimal state would only be available if chromosomes possessed the necessary values 9, 9, 0, 0, 9, 9, 0, 0 between them. The chromosomes would also need to hold these values in the correct indices of the solution vector between them, because the three crossover operators do not change positions of values and instead stick segments of parents genes together to create the children genes. Reaching the optimal state without mutation is possible and increasing the population size to hold a higher genetic diversity would improve the chances to do so. As finding the solution vector would rely entirely on the crossover, the convergence may be extremely slower than without mutation.

Part VI:

I implemented a steady-state GA in which the best chromosome is passed onto each successive generation. Six offspring are also created through a roulette wheel selection. Each generation maintained a constant population size of 25 as well as a mutation rate of 0.15%. I thought that I would implement a higher mutation threshold as I previously mentioned that without mutation, if the chromosomes did not already have the genes capable to provide the solution then they would not reach the optimal state.

The uniform operator strongly outperforms the one-point and two-point methods. This may be that the operator is able to provide many more possible outcomes than the others. For example:

Parent 1 [1, 1, 2, 4, 5, 1, 9, 4]  Parent 2 [2, 2, 4, 3, 1, 6, 8, 2]
One-point: [1, 1, 2, 4, 1, 6, 8, 2] and [2, 2, 4, 3, 5, 1, 9, 4] are the only possible vectors from merging the two halves of each parent chromosome. 
Two-point: [1, 1, 4, 3, 1, 6, 8, 2] and [2, 2, 2, 4, 5, 1, 8, 2] are the only possible vectors from mixing the set segments from each parent chromosome. 

The uniform method generates a random number between 0 and 1, if above 0.5 it will choose parent one’s allele and if below will choose parent two’s. For every allele of the child’s gene, there are two possible outcomes. This results in 2⁸ possible solution vectors that can be generated using the uniform operator. This “shuffling” of the alleles may provide the genetic diversity needed to possibly find stronger solution vectors and therefore converge to the optimal state faster.

Next, I compared results of differing mutation rates when using the uniform operator. I compared the original 0.15% used previously to a mutation threshold of 0.05% instead.

Interestingly, using the lower mutation rate performed much better on average than the higher rate. I assumed that because of the requirement to use mutation mentioned previously, that a higher mutation rate would provide a solution faster by possibly providing a higher chance to generate the correct values needed for the optimal solution vector. The difference in 0.1% may push the algorithm into behaving more as a random search, and so does not utilise the strategy of simulating evolution and natural selection that GAs provide.

I then implemented DFO to solve this problem and compared the performance of itself and the GA using the uniform operator. As the uniform operator faired better when using a lower mutation rate, I used an equal disturbance threshold for the swarm.

Like the results found for my previous blog posts for the Travelling Salesman, knapsack, and the card organising problem, DFO outperforms GA. Again, I think that this is due to communication process between flies of the swarm. Each fly will update it’s feature vector in a direction that it views to be a more optimal state based upon it’s best neighbour and/or the best fly in the swarm. GAs have a blinder approach to finding the solution in that there is no communication between chromosomes. Despite using the steady-state modality to “save” the best chromosome of each generation and the roulette wheel method of selection, this does offer a strong governing or directing of the chromosomes to produce children with progressively and constantly stronger candidate solutions. The communication network present in DFO does offer this progressive and constant directing towards solutions, be it local or global, and so converges at a much faster rate than genetic algorithm in finding solutions for multiple problems.