Genetic Algorithm

Local Search and GA

• Local search methods involve making small changes to potential
solutions to a problem until an optimal solution is identified.
• Genetic Algorithm (GA) is a search-based optimization technique
based on the principles of Natural Genetics and Natural Selection.
• It finds the Optimal Solution based in survival of the fittest.
• Optimization is the process of making something better i.e. to get the
“best” output value.
Evolutionary Computing
• Natural systems as guiding metaphors

• Charles Darwinian Evolution – 1859

• Theory of natural selection

• It proposes that the plants and animals that exist today are the result of
millions of years of adaptation to the demands of the environment

• Over time, the entire population of the ecosystem is said to evolve to

contain organisms that, on average, are fitter for environment than
those of previous generations of the population

3
Genetic Algorithms
• The concepts of GAs are directly derived from natural evolution.
• GAs emulate ideas from genetics and natural selection and can
search potentially large spaces
• Based on: survival of the most fittest individual
• Two key steps: reproduction, survive

4
Genetic Algorithm
• Based on Darwinian Paradigm
Reproduction Competition

Survive Selection

• Intrinsically a robust search and optimization mechanism

Genetic Algorithm
• The process for running a genetic algorithm is as follows.
1. Generate a random population of chromosomes (this is the first
generation).
2. If termination criteria are satisfied, stop. Otherwise, continue with step 3.
3. Determine the fitness of each chromosome.
4. Apply crossover and mutation to selected chromosomes from the current
generation to generate a new population of chromosomes—the next
generation.
5. Return to step 2.
Genetic Algorithms
• Before we can apply Genetic Algorithm to a problem, we need to
answer:
• How can an individual be represented?
• What is the fitness function?
• How are individuals selected?
• How do individuals are generated?

8
Representation of States (Solution)
• States as sequence of strings
• Each state or individual is represented as a string over finite alphabet
0,1 . It is also called chromosome which contains genes.
genes

Solution: 607 1001011111

Encoding
Chromosome: Binary String

Recall that every state is a solution in local search

Reproduction: Building New States
• After representing States (Solutions).
• Build a population of random solutions.
• Let them reproduce using genetic operations.

• At each generation: apply ”survival of the fittest”

• Hopefully better and better solutions evolve over time

• The best solutions are more likely to survive and more likely to produce
even better solutions
Evaluation and Selection

• We then see how good the solutions are, using an evaluation function
(recall f(n) in infomed search)
• Often it is a heuristic, especially if it is computationally expensive to do a
complete evaluation

• The final population can then be evaluated more deeply to decide on the best
solution

11
Survival of the Fittest
• Select the surviving population

• Likelihood of survival is related in some way to your score on the

fitness function
• The most common technique is roulette wheel selection

• Note we always keep the best solution so far

• Remember: Its local search

12
Genetic Operators
• These operators mimic what happens to our genetic material when
we reproduce
• Crossover
• Mutation

13
Crossover Operator
• Cut two solutions at a random point and switch the respective parts
• Typically a value of 0.7 for crossover probability gives good results.

a1 a2 a3 a4 a5 a6 b1 b2 b3 b4 b5 b6

 
a1 a2 a3 a4 b5 b6 b1 b2 b3 b4 a5 a6

14
Crossover
Crossover operator
• The crossover operator is applied to two chromosomes of the same
length as follows:
• 1. Select a random crossover point.
• 2. Break each chromosome into two parts, splitting at the crossover point.
• 3. Recombine the broken chromosomes by combining the front of one with
the back of the other, and vice versa, to produce two new chromosomes.
• For example, consider the following two chromosomes:
• 110100110001001
• 010101000111101
Mutation operator
• Randomly change one bit in the solution
• Mutation is a unary operator (i.e., applied to just one argument—a single
gene)
• Occasional mutation makes the method much less sensitive to the
original population and also allows ”new” solutions to emerge

a1 a2 a3 a4 a5 a6 Mutation of a2 = b1

a1 b1 a3 a4 a5 a6
17
Mutation
Fitness Function (Optimization)
• Fitness Function for a mathematic function
• Ex. attempt to maximize the function:
• 𝑓(𝑥) = sin(𝑥) in range 0 ≤ 𝑥 ≤ 15
1.5

0.5

0 f(x)=sin(x)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

-0.5

-1

-1.5

19
Fitness Function (Optimization)
• Using population size of 4 chromosomes
• First Generation: Generate a random population:
c1 = 1001 (9) c3 = 1010 (10)
c2 = 0011 (3) c4 = 0101 (5)
• To calculate fitness of a chromosome, we calculate 𝑓(𝑥) for its decimal value
• Assign fitness as a numeric value from 0 to 100
• 0 is the least fit
• 100 is the most fit.
• 𝑓(𝑥) generates real numbers between -1 and 1.
• Assign a fitness score of 100 to 𝑓(𝑥) = 1 and fitness of 0 to 𝑓 𝑥 = −1
• Fitness of 50 will be assigned to 𝑓(𝑥) = 0

20
 x f(x)=sin(x) f'(x) = 50(f(x)+1)
Fitness Function (Optimization) 0
1
2
Fitness of x, 𝒇′ 𝒙 : 3
4
5
• 𝑓′(𝑥) = 50(𝑓(𝑥) + 1) 6
• 𝑓′(𝑥) = 50(sin(𝑥) + 1) 7
8
22.8, 15%
9
3 10
57.06, 38% 5 11
9 12
70.61, 46%
10
13
2.05, 1%
14
15
21
Fitness Function (Optimization)
• The range of real numbers from 0 to 100 is divided up between the
chromosomes proportionally to each chromosome’s fitness.
• In first generation:
• c1 has 46.3% of the range (i.e., from 0 to 46.3)
• c2 37.4% of the range (i.e., from 46.4 to 83.7)
• ….

22
Roulette-wheel selection
• A random number is generated between 0 − 100
• This number will fall in the range of one of the chromosomes (suppose c1)
• c1 chromosome has been selected for reproduction
• The next random number is used to select second chromosome’s (suppose
c2)
• Hence, fitter chromosomes will tend to produce more offspring than less
fit chromosomes.

• Important: Method does not stop less fit chromosomes from reproducing,
to ensure that populations do not stagnate, by constantly breeding from
the same parents.

23
Next Generation
• Need 4 random numbers for next generation
• Assume that:
• First random number is 56.7 (c2 is chosen)
• Second random number is 38.2 (c1 is chosen)
• Third random number is 20 (c1 is chosen)
• Fourth random number is 85 (c3 is chosen)

24
Next Generation cont.
• Combine first two to produce two new offspring:
• Crossover point
c1 = 1001 (9) c2 = 0011 (3)
 
c5 = 1011 (11) c6 = 0001 (1)

• Combine last two to produce two new offspring:

• Crossover point c1 = 1001 (9) c3 = 1010 (10)
 
c8 = 1011 (11) c7 = 1000 (8)

25
Second generation: c5 to c8
• c4 did not have a chance to reproduce (its genes will be lost)
• Fittest chromosome in the first generation (c1), able to reproduce
twice
• Passing on its highly fit genes to all members of the next generation

Extremely fit

26
Termination criteria
• Termination criteria would probably determine that c7 is the most fit
(local optimum) and the algorithm will be stopped.

27
 2
Example: 𝑓 𝑥 = 𝑥
• Problem: Maximize the function 𝒇 𝒙 = 𝒙𝟐 where 𝒙 varies between
1 and 31.

• Step 1:
• Code the decision variable of the problem a binary unsigned integer of length
5.
• To start we select an initial population of size 4 by tossing a fair coin times.
• Fitness function is defined by 𝑓 𝑥 = 𝑥 2
 2
Example: 𝑓 𝑥 = 𝑥
String No. Initial Pop. 𝑥-value 𝑓 𝑥 = 𝑥 2
1 01101 13 169
2 11000 24 576
3 01000 8 64
4 10011 19 361

String No. 𝑥-value 𝑓 𝑥 = 𝑥2 𝒇

P-select σ 𝒊𝒇
𝒇 𝒊
Expected Count 𝒂𝒗𝒈 Roulette Wheel

1 13 169 0.14 0.58 1

2 24 576 0.49 1.97 2
3 8 64 0.06 0.22 0
4 19 361 0.31 1.23 1
 2
𝑓 𝑥 =𝑥
• The best strings get more copies, while the weak ones just die off.
• After selection, crossover takes place
• Strings combined randomly using one point cross over
• Apply one bit mutation

String No. 𝑥-value One Point New Children

Apply Mutation New Population
Cross Over
11001 11101
1 13 0110|1 11001
01100 01101
2 24 1100|0 01100
10000 10100
2 24 11|000 10000
11011 11001
4 19 10|011 11011
 2
𝑓 𝑥 =𝑥
• New Population

String No. Initial Pop. 𝑥-value 𝑓 𝑥 = 𝑥2

1 11101 29 841

2 01101 13 169

3 10100 20 400

4 11001 25 625
 Chromosome Chromosome Decoded Chro
label string integer f
X1 1 1 00 12

Practice Question X2
X3
X4
0
0
1
1
0
1
00
01
10
4
1
14
X5 0 1 11 7
X6 1 0 01 9

• Find the maximum value of function f(x) 60

50
60

50

f(x) = –x2 + 15x 40 40

30 30

• Represent problem using chromosomes built from 20 20

10 10

four genes: 0
0 5 10 15
0
0

• Initial random population of size N = 6: x

(a) Chromosome initial locations. (b) Chr

Integer Binary code Integer Binary code Integer Binary code

1 0001 6 0110 11 1011
2 0010 7 0111 12 1100
3 0011 8 1000 13 1101
4 0100 9 1001 14 1110
5 0101 10 1010 15 1111
Practice Question
• Determine chromosome fitness for each chromosome:

Chromosome Chromosome Decoded Chromosome Fitness

label string integer fitness ratio, %
X1 1 1 00 12 36 16.5
X2 0 1 00 4 44 20.2
X3 0 0 01 1 14 6.4
X4 1 1 10 14 14 6.4
X5 0 1 11 7 56 25.7
X6 1 0 01 9 54 24.8
60 60
f(x)
50 50

40 40

30 30
Practice Question
• Use fitness ratios to determine which chromosomes are selected for
crossover and mutation operations:

100 0
X1: 16.5%
X2: 20.2%
75.2 X3: 6.4%
X4: 6.4%
X5: 25.3%
36.7 X6: 24.8%
49.5 43.1
Practice Question
• Assume we have the following function
𝑓 𝑥 = 𝑥 3 − 60𝑥 2 + 900𝑥 + 100
where x is constrained to 0 − 31 . We wish to maximize 𝑓 𝑥 (the optimal is 𝑥 = 10). Using a
binary representation we can represent 𝑥 using five binary digits.
• Given the following four chromosomes give the values for 𝑥 and 𝑓 𝑥 .
Chromosome Binary String
P1 11100
P2 01111
P3 10111
P4 00100
• If P3 and P2 are chosen as parents and we apply one point crossover show the resulting children,
C1 and C2. Use a crossover point of 1 (where 0 is to the very left of the chromosome)
• Do the same using P4 and P2 with a crossover point of 2 and create C3 and C4
• Calculate the value of x and f(x) for C1 to C4.
• Assume the initial population was 𝑥 = 17, 21, 4, 28 . Using one-point crossover, what is the
probability of finding the optimal solution? Explain your reasons.
Practice Question – SOLUTION
• Given the following four chromosomes give the values for 𝒙 and
𝒇 𝒙 .

Chromosome Binary String x f(x)

P1 11100 28 212
P2 01111 15 3475
P3 10111 23 1227
P4 00100 4 2804
Practice Question – SOLUTION
• If P3 and P2 are chosen as parents and we apply one point crossover
show the resulting children, C1 and C2. Use a crossover point of 1
(where 0 is to the very left of the chromosome)
• Calculate the value of x and f(x) for C1 to C4.
Chromosome Binary String x f(x)
C1 11111 31 131
C2 00111 7 3803
C3 00111 7 3803
C4 01100 12 3998
GA Example - Crossover

P3 1 0 1 1 1 P4 0 0 1 0 0

P2 0 1 1 1 1 P2 0 1 1 1 1

C1 1 1 1 1 1 C3 0 0 1 1 1

C2 0 0 1 1 1 C4 0 1 1 0 0
GA Example - After First Round of Breeding
• The average evaluation has risen P2, was the strongest individual in
the initial population. It was chosen both times but we have lost it
from the current population
• We have a value of x=7 in the population which is the closest value to
10 we have found
Chromosome Binary String x f(x)
P1 11111 31 131
P2 00111 7 3803
P3 00111 7 3803
P4 01100 12 3998
TOTAL 11735
AVERAGE 2933.75