[SOLVED] CS algorithm THE CONTINUOUS GENETIC ALGORITHM

THE CONTINUOUS 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) TheContinuousGeneticAlgorithm NILAs2020-21 1/36

Outline
1 The Continuous Genetic Algorithm Variables and Cost Function Population
Natural Selection
Selection Crossover Mutation
2 Examples
DrH.K.Lam (KCL)
TheContinuousGeneticAlgorithm
NILAs2020-21 2/36

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

The Continuous Genetic Algorithm
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 4/36

Introduction
The Continuous Genetic Algorithm
Requires less storage than the binary GA.
A single floating-point number v.s. Nbit of 0s and 1s.
Allows representation to the machine precision.
Inherently runs faster than the binary GA as no encoding and decoding needed.
Deals with complex problem with high dimensionality.
More logical to represent variables by floating-point numbers when the problems are continuous.
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 5/36

The Continuous Genetic Algorithm
E CONTINUOUS GENETIC ALGORITHM
Define cost function, cost, variables Select GA parameters
Generate initial population
Find cost for each chromosome
Select mates
Mating
Mutation
Convergence Check
Figure 3.1
Flowchart of a continuous GA.
Initial population with random members
Rating
Selection
Reproduction
Mutation
done
Figure 1: Flowchart of a continuous genetic algorithm
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 6/36
MPONENTS OF A CONTINUOUS GENETIC ALGORITHM
H
O

Variables and Cost Function
The optimisation variables are represented by chromosome. chromosome = [p1,p2, ,pNvar ]
Each gene (pi, i = 1, 2, , Nvar) is a real-coded variable. The cost is evaluated by a cost (fitness) function.
cost = f (chromosome) = f (p1 , p2 , , pNvar )
Variable values are represented as floating-point number; no longer need to consider how many bits are necessary to accurately represent a value.
No encoding and decoding before cost function evaluation.
Only limited to the internal precision and round-off error of computers.
Natural form of real-valued cost function can be used directly.
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 7/36

Population
The GA starts with an initial population with Npop chromosomes with an
Npop Nvar matrix filled with randomly generated real values.
Example: A cost function: cost = f (x, y) = x sin(4x) + 1.1y sin(2y) subject to 0 x 10 and 0 y 10.
chromosome = [x, y] x y Cost
6.9745 0.8342 0.30359 9.6828 2.402 9.3359 0.18758 8.9371 2.6974 6.2647 5.613 0.1289 7.7246 5.5655 6.8537 9.8784
3.4766
5.5408
2.2528 8.0108 2.8957 2.4601 9.8884 13.752
Table 1: Example initial population
DrH.K.Lam (KCL)
TheContinuousGeneticAlgorithm
NILAs2020-21 8/36

Natural Selection: Xrate
Npop chromosomes are ranked from lowest cost to highest cost. Only the best are selected to continue, while the rest are discarded.
nx y Cost
1 7.7246 5.5655 9.8884 2 0.1876 8.9371 8.0108 3 2.6974 6.2647 2.8957 4 5.6130 0.1289 2.4601
Table 2: Surviving chromosomes after a 50 % selection rate.
DrH.K.Lam (KCL)
TheContinuousGeneticAlgorithm
NILAs2020-21 9/36

Selection
Pairing from top to bottom until the top Nkeep chromosomes are selected for mating.
Random pairing: All chromosomes have the same probabilities to mate. Weighted random pairing (roulette wheel)
Rank weighting Cost weighting
Tournament selection picks randomly a small subset of two or three, and the chromosome with the lowest cost in this subset becomes a parent.
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 10/36

Crossover
1) Swapping
1a) Single-pointcrossover
1b) Double-pointcrossover 1c) Uniformcrossover
2) Blending
3) Extrapolation
DrH.K.Lam (KCL)
TheContinuousGeneticAlgorithm
NILAs2020-21
11/36

Crossover: Swapping
Single-point crossover:
parent1 = [pm1,pm2,pm3,pm4,pm5,pm6, ,pmNvar ] parent2 = [pd1,pd2,pd3,pd4,pd5,pd6, ,pdNvar ] offspring1 = [pm1,pm2, pd3,pd4,pd5,pd6, ,pdNvar ] offspring2 = [pd1,pd2, pm3,pm4,pm5,pm6, ,pmNvar ]
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 12/36

Crossover: Swapping
Single-point crossover:
parent1 = [pm1,pm2,pm3,pm4,pm5,pm6, ,pmNvar ] parent2 = [pd1,pd2,pd3,pd4,pd5,pd6, ,pdNvar ] offspring1 = [pm1,pm2, pd3,pd4,pd5,pd6, ,pdNvar ] offspring2 = [pd1,pd2, pm3,pm4,pm5,pm6, ,pmNvar ] Double-point crossover:
offspring1 = [pm1,pm2, pd3,pd4, pm5,pm6, ,pmNvar ] offspring2 = [pd1,pd2, pm3,pm4, pd5,pd6, ,pdNvar ]
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 12/36

Crossover: Swapping
Single-point crossover:
parent1 = [pm1,pm2,pm3,pm4,pm5,pm6, ,pmNvar ]
parent2 = [pd1,pd2,pd3,pd4,pd5,pd6, ,pdNvar ]
offspring1 = [pm1,pm2, pd3,pd4,pd5,pd6, ,pdNvar ]
offspring2 = [pd1,pd2, pm3,pm4,pm5,pm6, ,pmNvar ]
Double-point crossover:
offspring1 = [pm1,pm2, pd3,pd4, pm5,pm6, ,pmNvar ]
offspring2 = [pd1,pd2, pm3,pm4, pd5,pd6, ,pdNvar ]
Uniform crossover: randomly chooses whether or not to swap information between the two parents.
Disadvantage: Crossover by swapping does not introduce new information, just differet combinations. It totally relies on mutation to introduce new genetic material.
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 12/36

Crossover: Blending
The new offspring comes from a combination of the two parents.
pnew1 =bpmn+(1b)pdn
pnew2 = (1b)pmn +bpdn pmn is the nth variable in the mother chromosome.
pdn is the nth variable in the father chromosome.
b is a random number in the range of 0 and 1.
The same or different b can be used for each variable.
Linear combination process is done for all variables to the right or to the left of some crossover point.
Any number of points can be chosen to blend.
Disadvantage: It does not allow the introduction of values beyond the extremes already represented in the population.
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 13/36

Crossover: Blending
Generate a random position n.
Method 1: blending at the nth point and swap genes from n + 1 to Nvar
offspring1 = 264pm1,pm2, , pnew1 ,pd,n+1, ,pdNvar 375 |{z}
nth gene
offspring2 = 264pd1,pd2, , pnew2 ,pm,n+1, ,pmNvar 375 |{z}
nth gene
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 14/36

Crossover: Blending
Method 2: blending genes from the point n to point Nvar
offspring1 = 264pm1,pm2, ,pnew1,n,pnew1,n+1, ,pnew1,Nvar 375
nth gene
offspring2 = 264pd1,pd2, ,pnew2,n,pnew2,n+1, ,pnew2,Nvar 375 | {z }
| {z }
nth gene
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 15/36

Crossover: Extrapolation
The new offspring comes from a combination of the two parents.
pnew1 =pmnb(pmnpdn)
pnew2 =pdn+b(pmnpdn) where b 0 is a random number.
It allows offspring generation outside of the two parent variable values.
The offspring is discarded if outside of the allowed range, and run again.
Variations include choosing any number of variables to modify and generating different b for each variable.
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 16/36

Crossover: Extrapolation
Method 1: blending at the nth point and swap genes from n + 1 to Nvar
offspring1 = 26pm1,pm2, , pnew1 ,pd,n+1, ,pdNvar 37,offspring2 = 26pd1,pd2, , pnew2 ,pm,n+1, ,pmNvar 37
4 |{z} 5 4 |{z} 5 nth gene nth gene
Method 2: blending genes from the point n to point Nvar
offspring1 = 26pm1,pm2, ,pnew1,n,pnew1,n+1, ,pnew1,Nvar 37,offspring2 = 26pd1,pd2, ,pnew2,n,pnew2,n+1, ,pnew2,Nvar 37 4 |{z} 5 4 |{z} 5
nth gene nth gene
Example (method 1): Consider b = 0.0272
chromosome2 = [0.1876, 8.9371]
chromosome3 = [2.6974, 6.2647]
offspring1 =[0.18760.0272(0.18762.6974),6.2647]=[0.2559,6.2647]
offspring2 =[2.6974+0.0272(0.18762.6974),8.9371]=[2.6291,8.9371] DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21
17/36

Mutations
Mutations:
Choose a mutation rate .
Total number of variables that can be mutated in the population: (Npop 1)Nvar (Elitism is implemented).
Mutate the chosen variable as: p0n = pn +sNn(0,1)
s is a chosen constant.
Nn(0,1): standard normal distribution (mean = 0 and standard deviation = 1).
Replace the chosen variable by p0n.
If bounds exceed, discard and generate again. Generally not allowed on the best solution (elitism).
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 18/36

Mutations
Example: = 20%.
Number of variables to be mutated: 0.272 = 2.8 3 Randomly generate row and column numbers.
Row=[4
4 7]; Column=[1 2
1]
Population after crossover
xy xyCost
Population after Mutation
7.7246 5.5655 0.18758 8.9371 2.6974 6.2647 5.6130 0.1289 0.2558 6.2647 2.6292 8.9371 6.6676 5.5655 3.7544 6.2647
7.7246 5.5655 0.18758 8.9371 2.6974 6.2647 9.819 7.1315 0.2558 6.2647 2.6292 8.9371 9.1602 5.5655 3.7544 6.2647
Table 3: Mutating Population.
9.8884 8.0108 2.8957 17.601 0.03688 10.472 14.05 2.1359
Dr H.K. Lam (KCL)
The Continuous Genetic Algorithm
NILAs 2020-21
19 / 36

Continuous GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 20/36

Continuous GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Chromosome: [x, y, z]
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 20/36

Continuous GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Chromosome: [x, y, z]
Step 1: Population initialised with population size = 4
n Chromosome
1 [4.7401, 3.8971, 2.2926]
2 [2.8355, 3.6406, 4.8725]
3 [4.4442, 4.7174, 2.3810]
4 [4.8947, 2.4728, 4.9118]
Cost
25.3274 3.1928 30.3429 4.5771
DrH.K.Lam (KCL)
TheContinuousGeneticAlgorithm
NILAs2020-21
20/36

Continuous GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Step 2: Ranked population and natural selection with Nkeep = 3
n Chromosome
1 [4.4442, 4.7174, 2.3810]
2 [4.7401, 3.8971, 2.2926]
3 [4.8947, 2.4728, 4.9118]
4 [2.8355, 3.6406, 4.8725]
Cost
30.3429 25.3274 4.5771 3.1928
DrH.K.Lam (KCL)
TheContinuousGeneticAlgorithm
NILAs2020-21
21/36

Continuous GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Step 3: Selection with rank weighting (roulette wheel weighting)
n Chromosome
1 [4.4442, 4.7174, 2.3810]
2 [4.7401, 3.8971, 2.2926]
3 [4.8947, 2.4728, 4.9118]
4 [2.8355, 3.6406, 4.8725]
Cost
30.3429 25.3274 4.5771 3.1928
N n+1 n Pn= keep APn
Generate two random numbers: 0.0975, 0.6324 DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm
NILAs2020-21
22/36
1+2+3 i=1
0.5 0.3333 0.1667
0.5 0.8333 1.0000

Continuous GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Step 4: Crossover with single-point crossover technique p1: [4.4442, 4.7174, 2.3810]
p2: [4.7401, 3.8971, 2.2926]
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 23/36

Continuous GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Step 4: Crossover with single-point crossover technique p1: [4.4442, 4.7174, 2.3810]
p2: [4.7401, 3.8971, 2.2926]
Generate randomly the crossover point: 2
offspring1: [4.4442, 3.8971, 2.2926] ) Cost: 23.3170 offspring2: [4.7401, 4.7174, 2.3810] ) Cost: 32.8388
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm NILAs2020-21 23/36

Consider GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Step 5: Mutation
= 0.2; #mutation = 0.2(41)3 = 1.8 2
Row = [2 3]; Column = [1 2]
n
1 2 3 4
s=1
4.7401
Chromosome
[4.4442, 4.7174, 2.3810] [4.7401, 3.8971, 2.2926] [4.8947, 2.4728, 4.9118] [4.7401, 4.7174, 2.3810]
Chromosome after mutation [4.4442, 4.7174, 2.3810] [4.5570, 3.8971, 2.2926] [4.8947, 3.3312, 4.9118] [4.7401, 4.7174, 2.3810]
Cost
30.3429 24.0834 12.9803 32.8388
+ s rand = 4.7401 0.1831 = 4.5570 + s rand = 2.4728 + 0.8584 = 3.3312
2.4728
DrH.K.Lam (KCL) TheContinuousGeneticAlgorithm
NILAs2020-21
24/36

Consider GA example by hand
Example: Consider a function f (x, y, z) = x 2xy + 3z to be minimised, where 2x,y,z5.
Ranked population at the next iteration:
n Chromosome
1 [4.7401, 4.7174, 2.3810]
2 [4.4442, 4.7174, 2.3810]
3 [4.5570, 3.8971, 2.2926]
4 [4.8947, 3.3312, 4.9118]
Cost
32.8388 30.3429 24.0834 12.9803
DrH.K.Lam (KCL)
TheContinuousGeneticAlgorithm
NILAs2020-21
25/36