[SOLVED] CS scheme algorithm THE BINARY GENETIC ALGORITHM

THE BINARY GENETIC ALGORITHM
DR H.K. LAM
Department of Engineering
Kings College London
Office S2.14, Strand Building, Strand Campus
Email: [email protected]
https://nms.kcl.ac.uk/hk.lam
Nature-Inspired Learning Algorithms (7CCSMBIM)
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 1/87

Outline
1 Problem and Difficulties
2 Introduction
3 The Binary Genetic Algorithm
Binary Encoding and Decoding Decision Variables and Cost Function Population
Natural Selection
Selection
Mating Crossover
Mutation
Convergence
4 Performance Evaluation
5 Binary GA Example by Hand
6 Why do GAs work? Schema Theorem
7 Examples
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 2/87

Learning Aims and Objectives
Aims
To understand the process of the binary genetic algorithms.
To apply the binary genetic algorithm to optimisation problems. To know the limitations of the binary genetic algorithms.
Objectives
To study how the binary genetic algorithm works in details.
To consider a number of applications and formulate as minimisation problems.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 3/87

Problem and Difficulties
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 4/87

Problem and Difficulties
Problem Statement:
Task: minimisation of a cost function. Gradient information is not required Function evaluation
Difficulties:
non-convexity multi-modality non-smoothness discontinuity dimensionality
DrH.K.Lam (KCL)
TheBinaryGeneticAlgorithm
NILAs2020-21 5/87

Introduction
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 6/87

Introduction
The Genetic Algorithm
Genetic algorithm (GA) is a technique to solve problems which need optimisation.
GA is a subclass of Evolutionary Computing.
GA is based on Charles Darwins theory of evolution History of GA
Evolutionary Computing evolved in the 1960s.
GA were proposed by John Hollan in the middle of 1970s.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 7/87

Introduction
Darwins Theory of Evolution 1
An offspring has many of the characteristics of its parents, which implies that
the population is stable.
There are variations in characteristics between individuals that can be passed from one generation to the next.
Only a small percentage of the offspring produced survive to adulthood. Which of the offspring survive depends on their inherited characteristics.
1Sue Ellen Haupt, ValliappaLakshmanan, CarenMarzban, AntonelloPasini, and John K. Williams. Environmental Science Models and Artificial Intelligence. Artificial Intelligence Methods in the Environmental Sciences. Springer Science (3-14, 103-126), 2009.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 8/87

Introduction
The Binary Genetic Algorithm
Biological Metaphor Natural Selection
Genetics and Evolution gene, chromosome, allele, genotype, phenotype, mitosis, meiosis, gamete, crossover, mutation,
Components of Binary Genetic Algorithm
Variable encoding and decoding, fitness function, population, selection, mating mutation, offspring and convergence,
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 9/87

Introduction
Advantages:
Optimise with continuous or discrete variables.
Derivative information is not required.
Able to deal with a large number of decision variables.
Optimise decision variables with extremely complex cost function. Is less likely trapped in local optimum.
Tends to search for global optimum.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 10/87

Notation
Nvar : number of decision variables of the chromosome
Nbits : total number of bits of the chromosome
Npop : population size
Npop Nbits : total number of bits of the population
Xrate : selection rate in the step of natural selection
Nkeep = Npop Xrate : number of chromosomes that are kept for each generation Npop Nkeep : number of chromosomes to be discarded
xlo: lower bound of variable x
xhi: upper bound of variable x
Pn : probability of the nth chromosome in the mating pool of Nkeep to be chosen cn : cost of the nth chromosome
Cn : normalised cost of the nth chromosome
: mutation rate (or probability of mutation)
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 11/87

The Binary Genetic Algorithm
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 12/87

The Binary Genetic Algorithm
Initial population with random members
Rating
Selection
Reproduction
Mutation
DrH.K.Lam (KCL)
TheBinaryGeneticAlgorithm
NILAs2020-21
13/87

The Binary Genetic Algorithm
COMPONENTS OF A BINARY GENETIC ALGORITHM 29
Define cost function, cost, variables Select GA parameters
Generate initial population
Decode chromosomes
Find cost for each chromosome
Select mates
Mating
Mutation
Convergence Check
done
Figure1:Flioguwrec2h.2artFolofwachbaritnoafraybignearnyeGtAic.algorithm. DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm
Initial population with random members
Rating
Selection
Reproduction
Mutation
NILAs2020-21
14/87

Binary Encoding and Decoding
Binary number conversion:
Example: Convert 25.3125 to binary. The integer part: 25
25/2 ! 12/2 ! 6/2 ! 3/2 ! 1/2 !
Binary to Decimal:
The fractional part: 0.3125
0.3125 2 = 0.625 ! 0.625 2 = 1.25 ! 0.252=0.5 ! 0.52=1 !
25.312510 = 11001.01012
1
0
0
(124 +123 +022 +021 +120).(021 +122 +023 +124)
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 15/87
0
1
0
1
1
1

Binary Encoding and Decoding
Given a number x 2 [xlo,xhi], how many bits (m) are required to achieve precision of d decimal places?
xhixlo 2m1 10d
Example: x 2 [25, 100], precision: 2 decimal places
10025 2m1)75012m )m=12.872913bits
102
0000000000000!25+010025 =25
213 1 0000000000001!25+110025 =25.0092
213 1 0000000000010!25+210025 =25.0183
213 1
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 16/87
Decoding: x = x + decimal(1001 001 ) xhi xlo lo 2 2m1

Decision Variables and Cost Function
The optimisation/decision variables are represented by chromosome. chromosome = [p1,p2, ,pNvar ]
Each gene (pi, i = 1, 2, , Nvar) is coded by mi bits. Nvar
Total number of bits per chromosome: Nbits = A mi i=1
The cost is evaluated by a cost (fitness) function.
cost = f (chromosome) = f (p1 , p2 , , pNvar )
Genotype: The bit string representation of the chromosome Phenotype: The decision variables. The genotype can be mapped to phenotype through decoding or vice versa through encoding.
Allele: the value of a single bit in the chromosome
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 17/87

Decision Variables and Cost Function
Example: Consider an optimisation problem with decision variables of p1, p2, , pNvar .
Phenotype: [p1,p2, ,pNvar ]
When each gene is represented by 10 bits,
Chromosome: 241100110011011110000111100111135 | {z }| {z } | {z }
gene1(p1) gene2(p2) geneNvar (pNvar ) Genotype: 1100110011 011110000 1111001111
Allele: the allele of the first bit from the left is 1.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 18/87

Population
The GA starts with a group of chromosomes known as the population. The population has Npop.
A population represented by a Npop Nbits matrix filled with random 0s and 1s.
Purposes: Population collects a group of potential solutions, which will be evolved to improve their quality in each generation.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 19/87

Population
Example: A cost function: cost = f (x, y) with 7 bits in each gene. chromosome = 241100011 001100135
xy
Chromosome 00101111000110 11100101100100 00110010001100 00101111001000 11001111111011 01000101111011 11101100000001 01001101110011
Cost
12359 11872 13477 12363 11631 12097 12588 11860
| {z }| {z }
Table 1: Example initial population
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 20/87

Natural Selection
Two approaches: Xrate and Thresholding.
Purposes: Determine who should survive and who should die. The stronger ones will survive and the weaker ones will die, i.e., Survival of the fittest from Darwinian evolutionary theory.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 21/87

Natural Selection: Xrate
Natural Selection using Xrate
Survival of the fittest: Only the best are selected to survive.
Natural selection occurs each generation or iteration of the algorithm.
The selection rate, Xrate, is the fraction of Npop that survives.
The number of chromosomes that are kept (for each generation):
Nkeep = XrateNpop.
The top Nkeep will be kept in each generation.
The bottom Npop Nkeep chromosomes will be discarded and replaced by new offspring.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 22/87

Natural Selection: Xrate
Example: Npop = 8 and Xrate = 50%. Nkeep = XrateNpop = 0.5 8 = 4.
Chromosome 00110010001100 11101100000001 00101111001000 00101111000110 01000101111011 11100101100100 01001101110011 11001111111011
Cost
13477 12588 12363 12359 12097 11872 11860 11631
Table 2: Ranked population. The upper four will be kept and the lower four will be discarded and replaced.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 23/87

Natural Selection: Thresholding
Natural Selection using Thresholding:
All chromosomes that have a cost lower than a pre-defined threshold survive. Chromosomes with a cost higher than the threshold will be discarded and
replaced.
If no chromosomes survive, a whole new population will be generated. The threshold can be changed in each generation.
Advantage over Xrate natural selection:
Less computationally expensive as population does not have to be sorted.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 24/87

Selection
Selection:
Four approaches:
1) Pairingfromtoptobottom
2) Randompairing
3) Weightedrandompairing
3.1) Rank weighting
3.2) Cost weighting
4) Tournamentselection
Purposes: Determine who should reproduce offspring.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 25/87

Selection
Selection: Two chromosomes are selected from the mating pool of NKeep chromosomes to produce two new offspring. Selection will take place until Npop Nkeep offspring are born to replace the discarded chromosomes.
1) Pairing from top to bottom: Start at the top of the list and pair the two chromosomes at a time until the top Nkeep chromosomes are selected for mating.
Property: Simple and easy to implement.
2) Random pairing: A uniform random number generator to select chromosomes.
Property: All chromosomes (in the mating pool of NKeep) have chance to mate. Introduce diversity to the population resulting in higher chance of
producing offspring of quality.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 26/87

Selection
3) Weighted Random Paring (roulette wheel weighting): The probabilities assigned to the chromosomes in the mating pool are inversely proportional to their cost.
Property: A chromosome with the lowest cost has the greatest probability of mating, while the chromosome with the highest cost has the lowest probability of mating.
Two techniques: Rank weighting and cost weighting
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 27/87

Selection
3.1) Rank weighting (roulette wheel weighting): Pn = Nkeep n+1
ANkeep n n=1
where Pn: probability of the nth chromosome in the mating pool of Nkeep to be
chosen.
Example: Nkeep = 4
n Chromosome
1 00110010001100
2 11101100000001
3 00101111001000
4 00101111000110
n Cost Pn APn
i=1 13477 0.4 0.4
12588 0.3 0.7 12363 0.2 0.9 12359 0.1 1.0
Table 3: Probability table for rank weighting. DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm
NILAs2020-21
28/87

Selection
3.1) Rank weighting (roulette wheel weighting): Properties:
It is problem independent.
Small populations have a high probability of selecting the same chromosome. The probabilities only have to be calculated once ) less computationally expensive.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 29/87

Selection
3.2) Cost weighting (roulette wheel weighting): Normalised Cost: Cn = cn cN
Probability: Pn = n
C keep+1
ANkeep Cm m=1
Example: Nkeep = 4 n Chromosome
1 00110010001100
2 11101100000001
3 00101111001000
4 00101111000110
Cn = cn cNkeep+1
13477 + 12097 = 1380
12588 + 12097 = 491 12363 + 12097 = 266 12359 + 12097 = 262
n
Pn APn
i=1 0.575 0.575
0.205 0.780 0.111 0.891 0.109 1.000
Table 4: Probability table for cost weighting. DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm
NILAs2020-21
30/87

Selection
3.2) Cost weighting (roulette wheel weighting): Properties:
It is cost function dependent.
It tends to weight the top chromosome more when there is a large spread in the cost between the top and bottom chromosome.
It tends to weight the chromosomes evenly when all the chromosomes have approximately the same cost.
The probabilities have to be calculated each generation ) computationally expensive.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 31/87

Selection
Remark for Normalisation: Different scaling functions can be used. For example, a more general form of scaling function could be
Cn = acn + b
where a and b are scalars to be chosen that can be constants or functions.
Inourexample,wechoosea=1andb=cNkeep+1 sothat Cn = cn cNkeep+1 .
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 32/87

Selection
4) Tournament selection:
Randomly pick a small subset of chromosomes (two or three) from the mating
pool in the Nkeep, and the chromosome with the lowest cost in the subset becomes a parent.
Properties:
It is problem independent.
It works best for larger population sizes because sorting becomes time-consuming for large populations ) less computationally expensive. Chromosomes of good quality (with lower cost) have higher chance to be chosen.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 33/87

Crossover
Crossover:
Two approaches:
1) Single-pointcrossover
2) Double-pointcrossover 3) Uniformcrossover
Purposes: Create offspring from the parents selected in the selection process (by exchanging information).
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 34/87

Crossover
1) Single-point crossover:
Step 1: Step 2:
Step 3: Step 4:
A crossover point is randomly selected between the first and last bits of the parents chromosomes. Generate two offspring by swapping the chromosomes from the crossover point between two parents.
Replace any two chromosomes to be discarded in the pool of Npop Nkeep in the population.
Repeat Steps 1 to 3 for the next two parents until the pool of Npop Nkeep is replaced. One point crossover
Crossover point
Parent chromosomes
Crossover points
Parent chromosomes
Parent chromosomes
0
0
0
1
0
0
1
0
1
1
1
1
0
0
1
1
1
1
1
0
0
1
0
0
Offspring chromosomes
Two point crossover
0
0
0
1
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1
0
0
1
0
1
Uniform crossover
Offspring chromosomes
Offspring chromosomes
0
0
0
1
0
0
1
0
1
1
1
1
1
0
0
1
0
1
0
0
1
1
1
0
Figure 1: Illustration of one-point, two-point, and uniform crossover methods.
DrH.K.Lam (KCL)
TheBinaryGeneticAlgorithm NILAs2020-21 35/87
two-point crossover. In uniform crossover (figure 1), every allele is exchanged between the tw

Crossover
1) Single-point crossover: Example: Nkeep = 4
Chromosome Family 3 ma(1) 2 pa(1)
5 offspring1
6 offspring2
3 ma(2)
4 pa(2)
7 offspring3
8 offspring4
Binary String
00101111001000
11101100000001 00101100000001 11101111001000 00101111001000 00101111000110 00101111000110 00101111001000
Table 5: Pairing and mating process of single-point crossover.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 36/87

Crossover
2) Double-point crossover: The segments in between two randomly generated crossover points are swapped between parents.
3) Uniformcrossover:Bitsarerandomlychosenforswappingbetweenparents.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 37/87

Mutations
Mutations:
Purposes: Random mutations alter a certain percentage of the bits in the list of chromosomes. It allows the GA to explore a cost surface by introducing new information.
Mutation process:
Step 1: Choose the mutation rate (or probability of mutation), (0 to 1). Step 2: Determine the number of bits to be mutated:
#mutation = (Npop 1)Nbits (elitism is implemented) Step 3: Flip the chosen bits.
Remark: If elitism is NOT implemented,
#mutation = NpopNbits.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 38/87

Mutations
Mutations:
Example: Nkeep = 4, = 0.2, #mutation = 0.2(8 1)14 = 19.6 20
Population after Mating 00110010001100 11101100000001 00101111001000 00101111000110 00101100000001 11101111001000 00101111000110 00101111001000
Population after Mutations 00110010001100 11101100000001 00101111010000 00001011000111 00101000000001 11110111010010 00100111101000 00110111001000
New Cost
13477 12588 12415 13482 13171 12146 12716 12103
NILAs2020-21
Table 6: Mutating the population. DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm
39/87

Mutations
Chromosome 00001011000111 00110010001100 00101000000001 00100111001000 11101100000001 00101111010000 11110111010010 00110111001000
Cost
13482 13477 13171 12716 12588 12415 12146 12103
Table 7: New ranked population at the start of the second generation.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 40/87

Convergence
Stopping Criteria: 64 THE CONTINUOUS GENETIC ALGORITHM
Whether an acceptance solution is reached. A set number of iterations is exceeded.
No changes on the chromosomes.
No changes on the cost.
Population statis
Figure 3.5
Contour plot of the cost function with the population after the third and
fin
n
mean and minimum cost.
t
c
a
i
s
o
l
ge
ner
ati
on.
0 -5 -10 -15 -20
0123
population average
best
generation
DrH.K.Lam (KCL)
rithm converged in three generations.
Figure 3.6
Plot of the minimum and mean costs as a function of generation. The algo-
TheBinaryGeneticAlgorithm
NILAs2020-21
41/87
cost

Convergence
Question: Find the maximum percentage of the possible solution being searched after 3 generations.
Total number of possible solutions: 128 128 = 16384 maximum number of solutions searched at the 3rd generation:
8+ 7 3=29 |{z} |{z} |{z}
initial population max cost evaluations per generation generations (elitism is implemented)
29 100 = 0.18% of the solution space has been searched. 128128
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 42/87

Performance Evaluation
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 43/87

Random-Based Optimisation: Performance Evaluation
Statistics
mean, standard deviation, the worst and the best of the cost of multiple runs.
Convergence rate
Benchmark functions
Functions of different properties
Function 1:
n
f1(x) = Axi2,5.12 xi 5.12
i=1 minimum: x = 0, f1(x) = 0
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 44/87

Random-Based Optimisation: Performance Evaluation
Function 2:
n1
f2(x) = A 100(xi+1 xi2)2 +(xi 1)2 ,2.048 xi 2.048
i=1 minimum: x = 0, f2(x) = 0
Function 3:
n f3(x)=6n+Afloor(xi),5.12xi 5.12
i=1 minimum: xi = [5,5.12], f3(x) = 0
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 45/87

Random-Based Optimisation: Performance Evaluation
Function 4:
n f4(x)=Aixi4+Gauss(0,1),1.28xi 1.28
i=1 minimum: x = 0, f4(x) = 0
Function 5:
125 1
f5(x)= k +A 2 ,65.356xi 65.356
j=1 j + A(xi aij)6 i=1
maximum: xi = 32, f5(x) 1 with k = 500 aij= 32 16 0 16 32 32 16 0 16 32
32 32 32 32 32 16 16 16 16 16 # 32 16 0 16 32 32 16 0 16 32 32 16 0 16 32
0 0 0 0 0 0 16 16 16 16 16 32 32 32 32
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm
NILAs2020-21
46/87

Random-Based Optimisation: Performance Evaluation
Function 6:
i=1 minimum: x = 0, f6(x) = 0
n
f6(x) = A(xi2 10cos(2pxi)+10),5.12 xi 5.12
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 47/87

Binary GA Example by Hand
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 48/87

Binary GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2 x, y, z 5. Each variable is represented by 2 bits.
Chromosome: [x,y,z] Afterencoding:24XX XX XX35
Decoding: x = x + decimal(1001 001 ) xhi xlo lo 2 2m1
00 ! 2+decimal(00) 52 22 1
01 ! 2+decimal(01) 52 22 1
10 ! 2+decimal(10) 52 22 1
11 ! 2+decimal(11) 52
= 2 = 3 = 4 = 5
|{z} |{z} |{z}
xyz
EncodingDecoding {2, 3, 4, 5} $ {00, 01, 10, 11} Withxlo =2,xhi =5andm=2,
DrH.K.Lam (KCL)
22 1
TheBinaryGeneticAlgorithm
NILAs2020-21
49/87

Binary GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2 x, y, z 5. Each variable is represented by 2 bits.
Step 1: Population initialised with population size = 4
n Chromosome
1 101110
2 000011
3 001100
4 110100
Decoded x, y, z Cost 4, 5, 4 24
2, 2, 5 9
2, 5, 2 12 5, 3, 2 19
DrH.K.Lam (KCL)
TheBinaryGeneticAlgorithm
NILAs2020-21
50/87

Binary GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2 x, y, z 5. Each variable is represented by 2 bits.
Step 2: Ranked population and natural selection with Nkeep = 3
n Chromosome
1 101110
2 110100
3 001100
4 000011
Decoded x, y, z Cost 4, 5, 4 24 5, 3, 2 19 2, 5, 2 12
2, 2, 5 9
DrH.K.Lam (KCL)
TheBinaryGeneticAlgorithm
NILAs2020-21
51/87

Binary GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2 x, y, z 5. Each variable is represented by 2 bits.
Step 3: Selection with cost weighting (roulette wheel weighting)
n Chromosome 1 101110
Decoded x, y, z 4, 5, 4
5, 3, 2 2, 5, 2 2, 2, 5
Cost Cn =cncNkeep+1 24 24 9 = 33
19 19 9 = 28 12 12 9 = 21 9
n
Pn APn
i=1 0.4024 0.4024
0.3415 0.7439 0.2561 1.0000
2 110100
3 001100
4 000011
Pn = N Cn
A keep Cm
= 3Cn =
Cn
= Cn 82
m=1
P1 = 33, P2 = 28; P3 = 21


Am=1 Cm
332821

82
Generate two random numbers: 0.9649, 0.2785
82
82
What happen if the same chromosome is chosen?
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm
NILAs2020-21
52/87

Binary GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2 x, y, z 5. Each variable is represented by 2 bits.
Step 4: Crossover with single-point crossover technique p3: 001100
p1: 101110
Generate randomly a crossover point: 2
offspring1: 001110 offspring2: 101100
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 53/87

Binary GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2 x, y, z 5. Each variable is represented by 2 bits.
Step 5: Mutation
Ranked population for mutation with = 0.2; #mutation = 0.2(4 1)6 = 3.6 4
row = [2 2 3 4]; column = [4 5 2 5].
n Chromosome
1 101110
2 110100
3 001100
4 001110
Dr H.K. Lam (KCL)
Chromosome after mutation 101110
110010
011100
001100
Decoded x, y, z 4,5,4 5,2,4 3,5,2 2,5,2
Cost
24 3 21 12
The Binary Genetic Algorithm
NILAs 2020-21
54 / 87

Binary GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2 x, y, z 5. Each variable is represented by 2 bits.
The 1st generation is done.
Ranked population for next generation.
n Chromosome
1 101110
2 011100
3 001100
Decoded x, y, z Cost 4, 5, 4 24 3, 5, 2 21 2, 5, 2 12 5, 2, 4 3
4 110010
Repeat steps 1 to 5 until stopping criteria have been met.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm
NILAs2020-21
55/87

Why do GAs work? Schema Theorem
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 56/87

Why do GAs work? Schema Theorem
Binary genetic algorithms are considered. Schema Theorem (Michalewicz, 1992)
Short, low-order, above-average schemata receive exponentially increasing trials in subsequent generations of a genetic algorithm.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 57/87

Why do GAs work? Schema Theorem
A scheme: a template representing a subset of binary strings using symbols 0, 1 and ? (dont care symbol).
Example:
Schema ?1100 matches 2 strings: {01100, 11100}.
Schema ?110? matches 4 strings: {01100, 01101, 11100, 11101}.
Schema ? ? ? ? ? matches 25 strings: {00000, 00001, , 11110, 11111}. Schema 11100 matches 1 string {11100}.
String 11100 is matched by 25 schemata: {11100, ?1100, 1?100, , ? ? ? ? 0, ?????}.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 58/87

Why do GAs work? Schema Theorem
Schema properties:
1. Order of the schema S (denoted by o(S)): the number of fixed positions (0 and 1 positions), i.e., the length of the template minus the number of dont care symbols.
2. Defining length of the schema S (denoted by d (S)): the distance between the first and the last fixed positions.
Example:
S1 = ???001?110 ) o(S1) = 6,d(S1) = 104 = 6 S2 = ????00??0? ) o(S2) = 3,d(S2) = 95 = 4 S3 = 11101??001 ) o(S3) = 8,d(S3) = 101 = 9
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 59/87

Why do GAs work? Schema Theorem
Binary GAs:
1. selectP(t)basedonP(t1) 2. recombine P(t)
3. evaluate P(t)
4.t t+1
Binary GA configurations:
Nkeep = 0.
Selection: roulette wheel weighting, cost weighting.
Crossover: single-point crossover (crossover points are allowed any point in between the first and last bits).
Mutation: uniform mutation (with the probability of mutation pm for each bit).
Elitism is not implemented.
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 60/87

Why do GAs work? Schema Theorem
x (S, t): the number of strings in the population at generation t matched by a schema S.
Example: Consider the following population (costs are normalised and thus of all negative):
S1 = ??01??, DrH.K.Lam (KCL)
x(S1,t) = 3
v1 = 100101 f(v1)=15 v2 = 011100 f(v2)=22 v3 = 110111 f(v3)=6 v4 = 000110 f(v4)=1 v5 = 110001 f(v5)=8 v6 = 110011 f(v6)=3
TheBinaryGeneticAlgorithm
NILAs2020-21
61/87

Why do GAs work? Schema Theorem
f (S, t): average cost of all strings in the population matched by the schema S. Assuming that there are p strings {u1, ,up} in the population matched by a
schema S at generation t, Example:
S1 = ??01?? is matched by {v1,v3,v4} = {100101,110111,000110} f(S1,t) = f(v1)+f(v3)+f(v4) = 1561 = 7.3333
f ( S , t ) = A pi = 1 f ( u i ) p
33
DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 62/87

Why do GAs work? Schema Theorem
Objective: Investigate the probability of survival of all schemata S (S1 , , S2Nbits ) in the GA process (selection, crossover, mutation).
Selection: The probability of selecting the string vi:
pi = f(vi),i = 1, ,Npop
F(t) whereF(t)= Af(vj).
Npop j=1
1. The number of strings matched by schema S: x(S,t).
2. The average probability of a string matched by schema S to be selected:
f (S,t) . F(t)
3. The number of strings to be selected for recombination: Npop (Nkeep = 0). DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 63/87

Why do GAs work? Schema Theorem
x (S, t + 1): the number of strings matched by S after the selection process. x(S,t+1) = x(S,t)f(S,t)Npop
F(t) = x(S,t)f(S,t)
F(t) where F(t) = F(t) is the average cost of the population.
Npop
x(S,t+1) = x(S,t)f(S,t)
F(t)
= x(S,t)F(t)+f(S,t)F(t)
F(t) = x(S,t)(1+e(t))
where e(t) = f(S,t))F(t). F(t)
DrH.K.Lam (KCL)
TheBinaryGeneticAlgorithm
NILAs2020-21
64/87

Why do GAs work? Schema Theorem
x(S,t+1) = x(S,t)(1+e(t))
= x(S,t1)(1+e(t1))(1+e(t))
| {z }
x (S,t)
= x(S,t2)(1+e(t2))(1+e(t1))(1+e(t))
| {z }
x (S,t1)
= x(S,t3)(1+e(t3))(1+e(t2))(1+e(t1))(1+e(t))
| {z }
x (S,t2) .
= x(S,1)(1+e(1))(1+e(2))(1+e(t1))(1+e(t)) e(t) > 0 for most of t: x(S,t+1) is increasing
e(t) < 0 for most of t: x(S,t+1) is decreasing Implication: Above average schemata receive increasing number of strings in the next genera- tion; however, below average schemata will die out as t increases.DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 65/87Why do GAs work? Schema Theorem Recombination – CrossoverProbability of destruction of a schema S: pd (S) = d (S) Nbits 1 ProbabilityofschemaSsurvival:ps(S)=1 d(S)Nbits 1A string v1 = 1101110010 is matched by 210 schemata. ExampleS1 = 1101110010 pd(S1) = 9 = 1,ps(S1) = 0 .9.Sa = ???111???? pd(Sa) = 2,ps(Sa) = 7 .99.Sb = 11??????10 pd(Sb) = 9 = 1,ps(Sb) = 0 .9.S N = ? ? ? ? ? ? ? ? ? ? 2bitsDrH.K.Lam (KCL)p (S N ) = 0 = 0, p (S N) = 1 NILAs2020-21d 2bits TheBinaryGeneticAlgorithm9 s 2bits66/87Why do GAs work? Schema Theorem v01 = 1101110010 v02 = 0100000011Example 1: After crossover oc1 = 110111|0011oc2 = 010000|0010Sa survives but not Sb.Example 2: After crossover oc1 = 110|0000011oc2 = 010|1110010Sa survives but not Sb. DrH.K.Lam (KCL)Example 3: After crossover oc1 = 1101|000011oc2 = 0100|110010Both Sa and Sb cannot survive.Example 4: After crossover oc1 = 11011|00011oc2 = 01000|10010Both Sa and Sb cannot survive. TheBinaryGeneticAlgorithm NILAs2020-21 67/87 Why do GAs work? Schema Theorem ps(S)=1 d(S) Nbits 1Modification of ps(S) considering that, e.g., the schema of v01 and v02 is the same ps(S)1 d(S)Nbits 1 Schema growth equation with the consideration of crossover:x(S,t+1) x(S,t)f(S,t) 1 d(S) F(t) Nbits 1 DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 68/87Why do GAs work? Schema Theorem Mutation: Uniform mutation – each bit will be mutated if a random number r < pm, where pm 2 [0, 1] is the probability of mutation.Probability of a single bit survival (no mutation takes place):1pmProbability of a schema S survival (no mutation takes place in fixed bits):ps(S) = (1 pm)o(S)DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 69/87 Why do GAs work? Schema TheoremSchema growth equation with the consideration of crossover and mutation:x(S,t+1) x(S,t)f(S,t) 1 d(S) (1pm)o(S) F(t) Nbits 1 Schema Theorem (Michalewicz, 1992)Short, low-order, above-average schemata receive exponentially increasing trials in subsequent generations of a genetic algorithm. DrH.K.Lam (KCL) TheBinaryGeneticAlgorithm NILAs2020-21 70/87