Genetic Algorithm Task – 01/12/2016

From Natural Computing Lab on 01/12/2016.


Assume that your GA has chromosomes in the following structure:

ch = (g0, g1, g2, g3, g4, g5, g6, g7)

g0-7 can be any digits between zero to nine.
The fitness of each chromosome is calculated using the following formula:

f(ch) = (g0 + g1) − (g2 + g3) + (g4 + g5 ) − (g6 + g7)

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)



Calculate the fitness of each individual (and show your workings even if you initially think I might be mean to ask this, you’ll gradually change your mind!).

Then arrange the chromosomes by putting the fittest one first and the least fit at the end.


Now apply the following crossover to the chromosomes:

  1. Use one-point crossover (at the middle) to cross the best two chromosomes. [This would lead in creating the first two children]
  2. Use two-point crossover (after g1 and after g5) to cross the 2nd and 3rd best individual. [This would results in creating two extra children]
  3. Use uniform crossover (the way you’d like to) to cross the 1st and 3rd best chromosomes. [Now you should have two more children; six in total]


Following the crossover operations conducted above, the population size is six (for a moment ignore that classically, population size doesn’t change in GA). Now calculate the fitness of each of the newly generated offspring (again showing your workings), and state if there are any improvement compared to the initial population.


Acknowledging that the value of each gene is in the range of [0,9], suggest a chromosome that would return the optimal solution (i.e. with the maximum fitness)


Looking at the initial population and based on the answer to part IV, is it possible to reach the optimal state without the mutation operator? State why?


Implement GA to solve this problem (for the implementation purposes, keep the population size constant from one generation to the next, purely to stay loyal to the soul of the GA inventor!)

Feel free to experiments with a larger population size and different initial chromosomes.


Only if you feel brave
attempt to solve the problem with DFO!

Click for more info on DFO

and then SDS if you can come up with an idea to utilise [partial function evaluation]!

Click here for more info on SDS

Acquired from VLE created by Mohammad Majid Al-Rifaie.