Kriss Jessop About Me Projects Personal Projects RPGs

GA: Analysis to Implementation

Posted on December 3rd, 2016

Scenario:

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)
BODMAS is a thing…

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) => 11 – 5 +Â 8 – 5 = -7
ch2 = (8, 7, 1, 2, 6, 6, 0, 1) => 15 – 3 +Â 12 – 1 = -1
ch3 = (2, 3, 9, 2, 1, 2, 8, 5) => 5 – 11 +Â 3 – 13 = -22
ch4 = (4, 1, 8, 5, 2, 0, 9, 4) => 5 – 13 +Â 2 – 13 = -23

PART I:

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.

ch2 = (8, 7, 1, 2, 6, 6, 0, 1) => 15 – 3 +Â 12 – 1 = -1
ch1 = (6, 5, 4, 1, 3, 5, 3, 2) => 11 – 5 +8 – 5 = -7
ch3 = (2, 3, 9, 2, 1, 2, 8, 5) => 5 – 11 +Â 3 – 13 = -22
ch4 = (4, 1, 8, 5, 2, 0, 9, 4) => 5 – 13 +Â 2 – 13 = -23

PART II:

Now apply the following crossover to the chromosomes:

Use one-point crossover (at the middle) to cross the best two chromosomes. [This would lead in creating the first two children]

ch1 = (6, 5, 4, 1, 6, 6, 0, 1)
ch2 = (8, 7, 1, 2, 3, 5, 3, 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]

ch3 = (6, 5, 9, 2, 1, 2, 3, 2)
ch4 = (2, 3, 4, 1, 3, 5, 8, 5)

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]

ch5 = (8, 7, Â 1, 2, 1, 2, 8, 5)
ch6 = (2, 3, 9, 2, 6, 6, 0, 1)

PART III:

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.

TheÂ children’s fitness’s are -7 and -3, compared to -7 and -1 of their parents.Â Worse.

ch1 = (6, 5, 4, 1, 6, 6, 0, 1) => 11 – 5 + 12 – 1 = -7
ch2 = (8, 7, 1, 2, 3, 5, 3, 2) => 13 – 3 + 8 – 5 = -3

The children’s fitness’s are -8 and -21, compared to -7 and -22. The worse one was improved, and the better one worsened.

ch3 = (6, 5, 9, 2, 1, 2, 3, 2) => 11 – 11 + 3 – 5 = -8
ch4 = (2, 3, 4, 1, 3, 5, 8, 5) => 5 – 5 +Â 8 – 13 = -21

The children’s fitness’s are -4 and -19, compared to -1 and -22. The worse one was improved, and the better one worsened.

ch5 = (8, 7, Â 1, 2, 1, 2, 8, 5) => 15 – 3 +Â 3 – 13Â = -4
ch6 = (2, 3, 9, 2, 6, 6, 0, 1) => 5 – 11 +Â 12 – 1 = -19

PART IV:

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)

optimum = (9, 9, 0, 0, 0, 0, 0, 0) => 18 – 0 +Â 0 – 0 = 18

PART V:

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?

Nope. There’s not enough zeroes in the population to fill the six genes that need zeroes.

PART VI:

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!)