Maximisation Scenario Breakdown

Understanding an optimisation problem helps thinking about how best to approach solving it. This post follows the process of analysing a maximisation scenario and implementing a genetic algorithm to solve it. Chromosomes in the scenario are encoded with the structure:

ch = {x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇}

^{where x_0-7 can be any digit between zero and nine}

Fitness is calculated using the formula:

• f (ch) = (x₀+x₁) - (x₂+x₃) + (x₄+x₅) - (x₆+x₇)

I: Calculate fitnesses and sort a sample population…

ch₂ = {8, 7, 1, 2, 6, 6, 0, 1}

• f (ch₂) = (8+7) - (1+2) + (6+6) - (0+1) = 23

ch₁ = {6, 5, 4, 1, 3, 5, 3, 2}

• f (ch₁) = (6+5) - (4+1) + (3+5) - (3+2) = 9

ch₃ = {2, 3, 9, 2, 1, 2, 8, 5}

• f (ch₃) = (2+3) - (9+2) + (1+2) - (8+5) = -16

ch₄ = {4, 1, 8, 5, 2, 0, 9, 4}

• f (ch₄) = (4+1) - (8+5) + (2+0) - (9+4) = -19

II: Apply crossovers…

Single point crossover (at the middle) on the best two chromosomes…

Parent 1: ch₂ = {8, 7, 1, 2, 6, 6, 0, 1}

Parent 2: ch₁ = {6, 5, 4, 1, 3, 5, 3, 2}

• Child 1: {8, 7, 1, 2, 3, 5, 3, 2}
• Child 2: {6, 5, 4, 1, 6, 6, 0, 1}

Two point crossover (after x₁ and after x₅) to cross the 2nd and 3rd best…

Parent 1: ch₁ = {6, 5, 4, 1, 3, 5, 3, 2}

Parent 2: ch₃ = {2, 3, 9, 2, 1, 2, 8, 5}

• Child 3: {6, 5, 9, 2, 1, 2, 3, 2}
• Child 4: {2, 3, 4, 1, 3, 5, 8, 5}

Uniform crossover (0.5 probability) to cross the 1st and 3rd best…

Parent 1: ch₂ = {8, 7, 1, 2, 6, 6, 0, 1}

Parent 2: ch₃ = {2, 3, 9, 2, 1, 2, 8, 5}

• Child 5: {2, 7, 9, 2, 6, 2, 8, 1}
• Child 6: {8, 3, 1, 2, 1, 6, 0, 5}

III: Evaluate new offspring…

of₁ = {8, 7, 1, 2, 3, 5, 3, 2}

• f (of₁) = (8+7) - (1+2) + (3+5) - (3+2) = 15

of₂ = {6, 5, 4, 1, 6, 6, 0, 1}

• f (of₂) = (6+5) - (4+1) + (6+6) - (0+1) = 17

of₃ = {6, 5, 9, 2, 1, 2, 3, 2}

• f (of₃) = (6+5) - (9+2) + (1+2) - (3+2) = -2

of₄ = {2, 3, 4, 1, 3, 5, 8, 5}

• f (of₄) = (2+3) - (4+1) + (3+5) - (8+5) = -5

of₅ = {2, 7, 9, 2, 6, 2, 8, 1}

• f (of₅) = (2+7) - (9+2) + (6+2) - (8+1) = -3

of₆ = {8, 3, 1, 2, 1, 6, 0, 5}

• f (of₆) = (8+3) - (1+2) + (1+6) - (0+5) = 10

The offspring have a mean fitness of five (rounded from 5.33) which is a signifigant improvement on negative one (rounded from 0.75) of their parents. However the maximum chromosome of both generations ( f [ch₂]=23 got six greater than the second best ( f [of₂]=17).

IV: Chromosome with the maximum fitness…

op = {9, 9, 0, 0, 9, 9, 0, 0}

• f (op) = (9+9) - (0+0) + (9+9) - (0+0) = 36

V: Reaching the optimal solution…

The initial population would be able to crossover to the solution if each gene in op were present, however they are missing:

x₀=9, x₁=9, x₃=0, x₄=0, x₅=9, x₆=9 and x₈=0

Due to this, using crossover alone would not reach the optimal solution no matter how many generations or large a population. A stochastic type of exploration like the mutation modification would work.

For Natural Computing (IS53052A)