GA Exercise
For this task, we were given a set of instructions to complete with initial GA chromosomes. Below is these set of instructions along with my accompanying answers for each part.
Scenario:
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)
1.
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.
- f(ch1) = (6+5) — (4+1) + (3+5) — (3+2) = 9
- f(ch2) = (8+7) — (1+2) + (6+6) — (0+1) = 23
- f(ch3) = (2+3) — (9+2) + (1+2) — (8+5) = -16
- f(ch4) = (4+1) — (8+5) + (2+0) — (9+4) = -19
- This gives us a order from best to worst chromosome of ch4, ch3, ch1, ch2.
2.
Use one-point crossover (at the middle) to cross the best two chromosomes. [This would lead in creating the first two children]
- ch3 = (2, 3, 9, 2, 1, 2, 8, 5)
- ch4 = (4, 1, 8, 5, 2, 0, 9, 4)
- Child 1 = (4, 1, 8, 5, 1, 2, 8, 5)
- Child 2 = (2, 3, 9, 2, 2, 0, 9, 4)
Use two-point crossover (after x1 and after x5) to cross the 2nd and 3rd best individual. [This would results in creating two extra children]
- ch3 = (2, 3, 9, 2, 1, 2, 8, 5)
- ch1 = (6, 5, 4, 1, 3, 5, 3, 2)
- Child 3 = (2, 3, 4, 1, 3, 5, 8, 5)
- Child 4 = (6, 5, 9, 2, 1, 2, 3, 2)
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]
- ch4 = (4, 1, 8, 5, 2, 0, 9, 4)
- ch1 = (6, 5, 4, 1, 3, 5, 3, 2)
- Child 5 = (4, 5, 8, 2, 3, 5, 9, 2)
- Child 6 = (6, 1, 4, 5, 3, 0, 3, 4)
3.
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.
- f(Child 1) = (4+1) — (8+5) + (1+2) — (8+5) = -18
- f(Child 2) = (2+3) — (9+2) + (2+0) — (9+4) = -17
- f(Child 3) = (2+3) — (4+1) + (3+5) — (8+5) = -5
- f(Child 4) = (6+5) — (9+2) + (1+2) — (3+2) = -2
- f(Child 5) = (4+5) — (8+2) + (3+5) — (9+2) = -4
- f(Child 6) = (6+1) — (4+5) + (3+0) — (3+4) = -6
- The best fitness from the previous population was a -19 and since the best fitness of this new population is -18 it does not show any improvement from the previous population.
4.
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)
The optimal Chromosome would return the lowest possible result so observing the fitness function will give us this result by putting in the appropriate values.
Get Sebastian Smith’s stories in your inbox
Join Medium for free to get updates from this writer.
f(OptimalCh) = (0+0) — (9+9) + (0+0) — (9+9) = -36
OptimalCh = (0, 0, 9, 9, 0, 0, 9, 9)
5.
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?
In order to reach this optimal state without mutation, each value and it’s index would have to match at least one of the initial chromosome’s values and indices. Since none of the initial chromosomes contain a value of 0 in its first index, it’s already impossible to reach this optimal chromosome without mutation. The best chromosome possible from purely using crossover techniques given an infinite number of iterations would be (2, 1, 9, 5, 1, 0, 9, 5), returning a fitness of -24. Essentially, x0, x1, x4 and x5 must be the lowest values possible while x2, x3, x6 and x7 must be the highest possible.
6.
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.
After implementing this problem, I found that it would never reach the optimal state shown above as the chances to reach this configuration were virtually impossible even with mutation and crossover operations in place. In fact, the chances for this configuration to happen randomly would be (1/10)⁸ which equals 1*10^-8 or 0.00000001.
Even after setting a limit of 500,000 evaluations, a population size of 500 and mutation rate of 0.2, it still failed to reach its optimal configuration which came as a surprise to me as I thought this problem would be just as hard to complete, if not easier than the knapsack and travelling salesman problems. What’s different here is that we are not dealing with binary numbers. Instead we are dealing with 10 different values for each index which complicates the problem a lot more than it may seem making GA a non-optimal algorithm to solve it.
