REAL CODED GENETIC ALGORITHMS
Prof (Dr.) Rajib Kumar Bhattacharjya
Department of Civil Engineering
INDIAN INSTITUTE OF TECHNOLOGY, GUWAHATI
GUWAHATI-781039, ASSAM, INDIA
Real coded Genetic Algorithms
2 R.K. Bhattacharjya/CE/IITG
Disadvantage of binary coded GA
more computation
lower accuracy
longer computing time
solution space discontinuity
hamming cliff
16 October 2021
Real coded Genetic Algorithms
3 R.K. Bhattacharjya/CE/IITG
The standard genetic algorithms has the following steps
1. Choose initial population
2. Assign a fitness function
3. Perform elitism
4. Perform selection
5. Perform crossover
6. Perform mutation
In case of standard Genetic Algorithms, steps 5 and 6 require bitwise
manipulation.
16 October 2021
Real coded Genetic Algorithms
4 R.K. Bhattacharjya/CE/IITG
Simple crossover: similar to binary crossover
P1=[8 6 3 7 6]
P2=[2 9 4 8 9]
C1=[8 6 4 8 9]
C2=[2 9 3 7 6]
16 October 2021
Real coded Genetic Algorithms
5 R.K. Bhattacharjya/CE/IITG
Linear Crossover
• Parents: 𝑥1 , 𝑥2 , … , 𝑥𝑛 and 𝑦1 , 𝑦2 , … , 𝑦𝑛
• Select a single gene 𝑘 at random
• Three children are created as,
𝑥1 , 𝑥2 , … , 𝑥𝑘−1 , +0.5 ∙ 𝑦𝑘 + 0.5 ∙ 𝑥𝑘 , 𝑥𝑘+1 … , 𝑥𝑛
𝑥1 , 𝑥2 , … , 𝑥𝑘−1 , +1.5 ∙ 𝑦𝑘 − 0.5 ∙ 𝑥𝑘 , 𝑥𝑘+1 … , 𝑥𝑛
𝑥1 , 𝑥2 , … , 𝑥𝑘−1 , −0.5 ∙ 𝑦𝑘 + 1.5 ∙ 𝑥𝑘 , 𝑥𝑘+1 … , 𝑥𝑛
• From the three children, best two are selected for the next generation
16 October 2021
Real coded Genetic Algorithms
6 R.K. Bhattacharjya/CE/IITG
Single arithmetic crossover
• Parents: 𝑥1 , 𝑥2 , … , 𝑥𝑛 and 𝑦1 , 𝑦2 , … , 𝑦𝑛
• Select a single gene 𝑘 at random
• child is created as,
𝑥1 , 𝑥2 , … , 𝑥𝑘−1 , 𝛼 ∙ 𝑦𝑘 + 1 − 𝛼 ∙ 𝑥𝑘 , 𝑥𝑘+1 … , 𝑥𝑛
• reverse for other child. e.g. with 𝛼 = 0.5
0.5 0.7 0.7 0.5 0.2 0.8 0.3 0.9 0.4 0.5 0.7 0.7 0.5 0.2 0.5 0.3 0.9 0.4
0.1 0.3 0.1 0.3 0.7 0.2 0.5 0.1 0.2 0.1 0.3 0.1 0.3 0.7 0.5 0.5 0.1 0.2
16 October 2021
Real coded Genetic Algorithms
7 R.K. Bhattacharjya/CE/IITG
Simple arithmetic crossover
• Parents: 𝑥1 , 𝑥2 , … , 𝑥𝑛 and 𝑦1 , 𝑦2 , … , 𝑦𝑛
• Pick random gene 𝑘 after this point mix values
• child is created as:
𝑥1 , 𝑥2 , … , 𝑥𝑘−1 , 𝛼 ∙ 𝑦𝑘 + 1 − 𝛼 ∙ 𝑥𝑘 , … , 𝛼 ∙ 𝑦𝑛 + 1 − 𝛼 ∙ 𝑥𝑛
• reverse for other child. e.g. with = 0.5
0.5 0.7 0.7 0.5 0.2 0.8 0.3 0.9 0.4 0.5 0.7 0.7 0.5 0.2 0.5 0.4 0.5 0.3
0.1 0.3 0.1 0.3 0.7 0.2 0.5 0.1 0.2 0.1 0.3 0.1 0.3 0.7 0.5 0.4 0.5 0.3
16 October 2021
Real coded Genetic Algorithms
8 R.K. Bhattacharjya/CE/IITG
Whole arithmetic crossover
• Most commonly used
• Parents: 𝑥1 , 𝑥2 , … , 𝑥𝑛 and 𝑦1 , 𝑦2 , … , 𝑦𝑛
• child is:
𝛼 ∙ 𝑥𝑖 + 1 − 𝛼 ∙ 𝑦𝑖
• reverse for other child. e.g. with 𝛼 = 0.5
0.5 0.7 0.7 0.5 0.2 0.8 0.3 0.9 0.4 0.3 0.5 0.4 0.4 0.4 0.5 0.4 0.5 0.3
0.1 0.3 0.1 0.3 0.6 0.2 0.5 0.1 0.2 0.3 0.5 0.4 0.4 0.4 0.5 0.4 0.5 0.3
16 October 2021
Real coded Genetic Algorithms
Simulated binary crossover
9 R.K. Bhattacharjya/CE/IITG
Developed by (Deb and Agrawal, 1995)
Where, 𝑢𝑖 a random number and 𝜂𝑐 is a parameter that controls the crossover process. A high
value of the parameter will create near-parent solution
16 October 2021
Real coded Genetic Algorithms
Random mutation
10 R.K. Bhattacharjya/CE/IITG
Where 𝑢𝑖 is a random number between [0,1]
Where, Δ𝑖 is the user defined maximum perturbation
16 October 2021
Real coded Genetic Algorithms
Normally distributed mutation
11 R.K. Bhattacharjya/CE/IITG
A simple and popular method
Where 𝑁 0, 𝜎𝑖 is the Gaussian probability distribution with zero mean
16 October 2021
Real coded Genetic Algorithms
Polynomial mutation
12 R.K. Bhattacharjya/CE/IITG
𝑦𝑖1,𝑡+1 = 𝑥𝑖1,𝑡+1 + 𝛿𝑖 𝑥𝑖𝑢 − 𝑥𝑖𝑙
1
2𝑢𝑖 𝜂𝑚 +1−1 𝑖𝑓𝑢𝑖 ≤0.5
𝛿𝑖 = ൞ 1
1 − 2 1 − 𝑢𝑖 𝜂𝑚 +1, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
16 October 2021