See discussions, stats, and author profiles for this publication at: [Link]

net/publication/353477460

Metaheuristic Lesson: Genetic Algorithm - Real Coded

Method · July 2021

DOI: 10.13140/RG.2.2.10100.27528

CITATIONS READS

0 147

2 authors:

Valdecy Pereira Mozart Heymann

Fluminense Federal University Fluminense Federal University
196 PUBLICATIONS 911 CITATIONS 16 PUBLICATIONS 23 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Valdecy Pereira on 27 July 2021.

The user has requested enhancement of the downloaded file.

 UNIVERSIDADE FEDERAL FLUMINENSE

Programa de Mestrado e Doutorado em Engenharia de Produção

Metaheuristics

Lesson: Genetic Algorithm – Real Coded

Professor: Valdecy Pereira, D. Sc./ Mozart Caetano Heymann

email: [Link]@[Link] / [Link]@[Link]
 Outline

1. Genetic Algorithm

2. Initialization

3. Selection

4. Crossover

5. Mutation

6. Elitism

7. Github

2
The GA (Genetic Algorithm) is a metaheuristic inspired by the process of natural selection that is used for solving
optimization problems. The GA selects the fittest individuals (solutions) that are used for reproduction in order to produce
offspring (usually a better solution) for the next generation. John Henry Holland (February 2, 1929 – August 9, 2015) was
the father of the GA and Holland popularized this term in his paper published in 1973, entitled “Genetic Algorithms and the
Optimal Allocation of Trials”.
 MH – Genetic Algorithm
The GA (Genetic Algorithm) can be understood as a search and optimization technique, inspired
by the Darwinian principle of the evolution of species and genetics. It can find the global
optimum solution or local optimum solutions depending on the initial setup and parameter
calibration.
The GA creates an abstract representations (chromosome or genome) of a candidate solution
(individual). Traditionally, solutions are encoded in a binary form, but other encodings are also
possible. To solve an optimization problem, initially a random set of candidate solutions are
created (population), and them it evolves towards a better solution using genetic operations
called crossover and mutation to create a new population.
The GA represents an iterative process, where each iteration is called a generation. Then,
evaluating the fitness of each individual, we can select a pair for breeding that will generate an
offspring. To create the offspring, the crossover operator exchanges parts of the pair of
chromosomes, and the mutation operator changes the gene value in some randomly chosen
location of the offspring chromosome. This process is repeated until the new population has
enough members, ending the current generation. A common practice is to terminate a GA after a
specified number of generations.
The best solution (elite) of a generation can be stored and then given to next generation, this
optional process is called elitism.
5
 MH – Genetic Algorithm

GA Pseudocode

Randomly initialize the first Population (𝑖 = 0)

Set 𝜼 (Population size) and 𝒌 (number of generations)
for (𝑖 = 1 ; 𝑖 = 𝑘; 𝑖++) do
𝐴𝑑𝑑 the Elite as a member of the Population 𝑖 (Optional)
while card(Population 𝑖) < 𝜼 do
Evaluate the Fitness of all Individuals the Population 𝑖 − 1
Using the Fitness from the Population 𝑖 − 1, select any two Individuals to breed
Create one Offspring using the genetic operators Crossover and Mutation
𝐴𝑑𝑑 the Offspring as a member of the Population 𝑖
next 𝒊
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

7
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

Individual 1

Encoding a
Solution

8
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
Individual 1

Chromossome

9
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
Individual 1

Gene

10
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
Individual 1 0.91

Allele

11
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22

Fitness

12
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Fitness

13
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Individual 3 0.28 0.84 0.53 0.15 0.57 0.22

Individual 4 0.99 0.92 0.19 0.81 0.06 1.06

Population

14
 MH – Genetic Algorithm
Suppose that we want to minimize the following function:

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Individual 3 0.28 0.84 0.53 0.15 0.57 0.22

Individual 4 0.99 0.92 0.19 0.81 0.06 1.06

15
Initialization

16
 MH – Genetic Algorithm
In the first generation, the population size depends on the nature of the problem, but a common
approach is to have a population size with hundreds of individuals. Traditionally, this
population is generated randomly, but it can start with any set of solutions.

17
 MH – Genetic Algorithm
In the first generation, the population size depends on the nature of the problem, but a common
approach is to have a population size with hundreds of individuals. Traditionally, this
population is generated randomly, but it can start with any set of solutions.

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
Individual 1 0.12 0.03 0.91 0.73 0.22

Individual 2 0.50 0.76 0.88 0.14 0.62

Individual 3 0.28 0.84 0.53 0.15 0.57

Individual 4 0.99 0.92 0.19 0.81 0.06

18
Selection

19
 MH – Genetic Algorithm
For each successive generation, the fitter individuals (solutions with the best fitness values) are
typically more likely to be selected to breed to form the new population. A small proportion of
less fit individuals can also be selected to breed, helping keep the diversity of the population,
preventing premature convergence on poor solutions.
A popular and well-studied selection method, called Roulette Wheel Selection, can be
performed to make selections of individuals in a way that is directly proportionate to their
fitness.
Each pair can generate one or more offspring, however as a good practice, different pairs should
be used to generate the new population.

20
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1. Take from each individual the fitness value. For
maximization problems, use the fitness values without modifications, for minimization problems
go to Step 1b.

𝑓 𝒙
Individual 1 0.29

Individual 2 0.84

Individual 3 0.22

Individual 4 1.06

21
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1b. Use the inverse formula to transform a minimization
problem into a maximization problem.
1
𝑖𝑛𝑣𝑒𝑟𝑠𝑒 =
1 + 𝑓 𝒙 + (min 𝑓 𝒙

𝑓 𝒙
Individual 1 0.29

Individual 2 0.84

Individual 3 0.22

Individual 4 1.06

22
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1b. Use the inverse formula to transform a minimization
problem into a maximization problem.
1
𝑖𝑛𝑣𝑒𝑟𝑠𝑒 =
1 + 𝑓 𝒙 + (min 𝑓 𝒙

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒
Individual 1 0.29

Individual 2 0.84

Individual 3 0.22

Individual 4 1.06

23
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1b. Use the inverse formula to transform a minimization
problem into a maximization problem.
1
𝑖𝑛𝑣𝑒𝑟𝑠𝑒 =
1 + 𝑓 𝒙 + (min 𝑓 𝒙

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒
Individual 1 0.29 0.66

Individual 2 0.84
1
Individual 3 1 + 0.29 + 0.22
0.22

Individual 4 1.06

24
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1b. Use the inverse formula to transform a minimization
problem into a maximization problem.
1
𝑖𝑛𝑣𝑒𝑟𝑠𝑒 =
1 + 𝑓 𝒙 + (min 𝑓 𝒙

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒
Individual 1 0.29 0.66

Individual 2 0.84 0.48

1
Individual 3 1 + 0.84 + 0.22
0.22

Individual 4 1.06

25
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1b. Use the inverse formula to transform a minimization
problem into a maximization problem.
1
𝑖𝑛𝑣𝑒𝑟𝑠𝑒 =
1 + 𝑓 𝒙 + (min 𝑓 𝒙

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒
Individual 1 0.29 0.66

Individual 2 0.84 0.48

1
Individual 3 0.69
1 + 0.22 + 0.22
0.22

Individual 4 1.06

26
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1b. Use the inverse formula to transform a minimization
problem into a maximization problem.
1
𝑖𝑛𝑣𝑒𝑟𝑠𝑒 =
1 + 𝑓 𝒙 + (min 𝑓 𝒙

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒
Individual 1 0.29 0.66

Individual 2 0.84 0.48

1
Individual 3 0.69
1 + 1.06 + 0.22
0.22

Individual 4 1.06 0.44

27
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 1b. Use the inverse formula to transform a minimization
problem into a maximization problem.
1
𝑖𝑛𝑣𝑒𝑟𝑠𝑒 =
1 + 𝑓 𝒙 + (min 𝑓 𝒙

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒
Individual 1 0.29 0.66

Individual 2 0.84 0.48

Individual 3 0.22 0.69

Individual 4 1.06 0.44

28
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 2. Accumulate the values sequentially.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66

Individual 2 0.84 0.48

Individual 3 0.22 0.69

Individual 4 1.06 0.44

29
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 2. Accumulate the values sequentially.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66

Individual 2 0.84 0.48

0.66
Individual 3 0.22 0.69

Individual 4 1.06 0.44

30
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 2. Accumulate the values sequentially.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66 0.66

Individual 2 0.84 0.48

0.66
Individual 3 0.22 0.69

Individual 4 1.06 0.44

31
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 2. Accumulate the values sequentially.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66 0.66

Individual 2 0.84 0.48 1.15

0.48 + 0.66
Individual 3 0.22 0.69

Individual 4 1.06 0.44

32
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 2. Accumulate the values sequentially.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66 0.66

Individual 2 0.84 0.48 1.15

0.69 + 1.15
Individual 3 0.22 0.69 1.84

Individual 4 1.06 0.44

33
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 2. Accumulate the values sequentially.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66 0.66

Individual 2 0.84 0.48 1.15

0.44 + 1.84
Individual 3 0.22 0.69 1.84

Individual 4 1.06 0.44 2.28

34
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 2. Accumulate the values sequentially.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66 0.66

Individual 2 0.84 0.48 1.15

Individual 3 0.22 0.69 1.84

Individual 4 1.06 0.44 2.28

35
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 3. Divide each value of the acc. column by the sum of the
inverse column.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐.
Individual 1 0.29 0.66 0.66

Individual 2 0.84 0.48 1.15

Individual 3 0.22 0.69 1.84

Individual 4 1.06 0.44 2.28

𝑆𝑢𝑚 2.28

36
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 3. Divide each value of the acc. column by the sum of the
inverse column.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐. %
Individual 1 0.29 0.66 0.66

Individual 2 0.84 0.48 1.15

Individual 3 0.22 0.69 1.84

Individual 4 1.06 0.44 2.28

𝑆𝑢𝑚 2.28

37
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 3. Divide each value of the acc. column by the sum of the
inverse column.

0.66
𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐. % 2.28
Individual 1 0.29 0.66 0.66 29.04%

Individual 2 0.84 0.48 1.15

Individual 3 0.22 0.69 1.84

Individual 4 1.06 0.44 2.28

𝑆𝑢𝑚 2.28

38
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 3. Divide each value of the acc. column by the sum of the
inverse column.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐. %
Individual 1 0.29 0.66 0.66 29.04% 1.15
2.28
Individual 2 0.84 0.48 1.15 50.03%

Individual 3 0.22 0.69 1.84

Individual 4 1.06 0.44 2.28

𝑆𝑢𝑚 2.28

39
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 3. Divide each value of the acc. column by the sum of the
inverse column.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐. %
Individual 1 0.29 0.66 0.66 29.04%

Individual 2 0.84 0.48 1.15 50.03% 1.84

2.28
Individual 3 0.22 0.69 1.84 80.77%

Individual 4 1.06 0.44 2.28

𝑆𝑢𝑚 2.28

40
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 3. Divide each value of the acc. column by the sum of the
inverse column.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐. %
Individual 1 0.29 0.66 0.66 29.04%

Individual 2 0.84 0.48 1.15 50.03%

Individual 3 0.22 0.69 1.84 80.77% 2.28

2.28
Individual 4 1.06 0.44 2.28 100%

𝑆𝑢𝑚 2.28

41
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 3. Divide each value of the acc. column by the sum of the
inverse column.

𝑓 𝒙 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑎𝑐𝑐. %
Individual 1 0.29 0.66 0.66 29.04%

Individual 2 0.84 0.48 1.15 50.03%

Individual 3 0.22 0.69 1.84 80.77%

Individual 4 1.06 0.44 2.28 100%

𝑆𝑢𝑚 2.28

42
Roulette Wheel Selection – Step 4. Create the wheel.
0%

i1 i2 i3 i4

80.77%
19,23%
29,04%

30,45%
21,28%
29.04%

50.03%
43
Generate random numbers between 0 and 1 to select
0%
an individual.

i1 i2 i3 i4

18.50%

80.77%
19,23%
29,04%

30,45%
21,28%
29.04%

50.03%
44
Generate random numbers between 0 and 1 to select
0%
an individual.

i1 i2 i3 i4

18.50%

80.77%
Individual 1 was
19,23%
29,04% selected

30,45%
21,28%
29.04%

50.03%
45
If the individual is selected to breed with
0%
itself, them generate another random
number, until a different individual is
selected.

i1 i2 i3 i4

80.77%
19,23%
29,04%

30,45%
21,28%
29.04%

50.03%
46
 MH – Genetic Algorithm
Roulette Wheel Selection – Step 5. Select the pairs.

Random Number Random Number

18.50% 35.44%

49.97% 91.87%

Individual 1 Individual 2

Individual 2 Individual 4

47
Crossover

48
 MH – Genetic Algorithm
The crossover may happen always (100% chance) or have a probability to occur, for example, a crossover
for a selected pair may have a chance of 70% to breed, and if no crossover occurs then the selected pair is
copied directly to the new population. For real-coded GA, the most common type o crossover operator is
the Simulated Binary Crossover (SBX). The SBX creates offspring, mixing each gene of the selected pair,
through the following equations:
1
2×𝜇 𝜂+1 𝑖𝑓 𝜉 < 0.5
1
𝛽=
1 𝜂+1
𝑖𝑓 𝜉 ≥ 0.5
2−2×𝜇

1 − 𝛽 × parent1 + 1 + 𝛽 × parent 2
𝑖𝑓 𝜉 < 0.5
offspring = 2
1 + 𝛽 × parent1 + 1 − 𝛽 × parent 2
𝑖𝑓 𝜉 ≥ 0.5
2
Generating a random number 𝝃~ 𝟎, 𝟏 , a random number 𝝁~ 𝟎, 𝟏 and a constant 𝜼 , a pair
(𝐩𝐚𝐫𝐞𝐧𝐭 𝟏 and 𝐩𝐚𝐫𝐞𝐧𝐭 𝟐 ) can be used to generate offspring. Varying 𝝃 and 𝝁, allows the same pair to
generate different offspring.

49
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring

50
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring

51
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring
𝜉 = 0.52
𝜇 = 0.26

1 1 1
1 𝜂+1 1 1+1 1 2
𝛽= = = = 0.82
2−2×𝜇 2 − 2 × 0.26 1.48

1 + 𝛽 × parent1 + 1 − 𝛽 × parent 2
offspring =
2
52
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring
𝜉 = 0.52
𝜇 = 0.26

1 1 1
1 𝜂+1 1 1+1 1 2
𝛽= = = = 0.82
2−2×𝜇 2 − 2 × 0.26 1.48

1 + 𝛽 × parent1 + 1 − 𝛽 × parent 2 1 + 0.82 × 0.12 + 1 − 0.82 × 0.50

offspring = = = 0.15
2 2
53
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring 0.15
𝜉 = 0.52
𝜇 = 0.26

1 1 1
1 𝜂+1 1 1+1 1 2
𝛽= = = = 0.82
2−2×𝜇 2 − 2 × 0.26 1.48

1 + 𝛽 × parent1 + 1 − 𝛽 × parent 2 1 + 0.82 × 0.12 + 1 − 0.82 × 0.50

offspring = = = 0.15
2 2
54
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring 0.15 0.05

𝜉 = 0.74
𝜇 = 0.45

1
1 𝜂+1
𝛽= = 0.95
2−2×𝜇

1 + 𝛽 × parent1 + 1 − 𝛽 × parent 2
offspring = = 0.05
2
55
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring 0.15 0.05 0.92

𝜉 = 0.88
𝜇 = 0.84

1
1 𝜂+1
𝛽= = 1.77
2−2×𝜇

1 + 𝛽 × parent1 + 1 − 𝛽 × parent 2
offspring = = 0.92
2
56
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring 0.15 0.05 0.92 0.07

𝜉 = 0.01
𝜇 = 0.75

1
𝛽 = 2×𝜇 𝜂+1 = 1.22

1 − 𝛽 × parent1 + 1 + 𝛽 × parent 2
offspring = = 0.07
2
57
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring 0.15 0.05 0.92 0.07 0.53

𝜉 = 0.42
𝜇 = 0.15

1
𝛽 = 2×𝜇 𝜂+1 = 0.55

1 − 𝛽 × parent1 + 1 + 𝛽 × parent 2
offspring = = 0.53
2
58
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring 0.15 0.05 0.92 0.07 0.53

If necessary, clip the offspring values

to respect the boundaries:0 ≤ 𝒙 ≤ 1

59
 MH – Genetic Algorithm
Let’s suppose that the pair (individual 1 & individual 2) will breed, the pair (individual 2 & individual 4)
will be copied to directly to the new population, 𝜼 = 1, and 0 ≤ 𝒙 ≤ 1. Therefore:
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Offspring 0.15 0.05 0.92 0.07 0.53 0.70

60
Mutation

61
 MH – Genetic Algorithm
The mutation is a genetic operator that, for a small chance, can modify one or more genes of the
offspring. This process ensures the genetic diversity and avoids solutions to be trapped in local
maxima/minima. For real-coded GA, the most common type of mutation operator is The Real-
coding Jumping Gene Genetic Algorithm (RJGGA) that works through the following
equations:

1
2×𝜉 𝜑+1 −1 𝑖𝑓 𝜉 < 0.5
ρ=൞ 1
1− 2−2×𝜉 𝜑+1 𝑖𝑓 𝜉 ≥ 0.5

gene = gene + ρ

Generating a random number for each gene of each offspring 𝜉~ 0,1 , and a constant 𝝋, a gene
can have its value increased or decreased by a 𝛒 amount.

62
 MH – Genetic Algorithm
Let’s suppose that the offspring can mutate with a chance 𝒄 of 10% or lower, and 𝝋 = 1. Therefore:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙

Offspring 0.15 0.05 0.92 0.07 0.53 0.70

𝜉 = 0.82 𝜉 = 0.77 𝜉 = 0.21 𝜉 = 0.02 𝜉 = 0.63
𝑐 = 25% 𝑐 = 92% 𝑐 = 44% 𝑐 = 2% 𝑐 = 14%

63
 MH – Genetic Algorithm
Let’s suppose that the offspring can mutate with a chance 𝒄 of 10% or lower, and 𝝋 = 1. Therefore:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙

Offspring 0.15 0.05 0.92 0.07 0.53 0.70

𝜉 = 0.02
𝑐 = 2%

64
 MH – Genetic Algorithm
Let’s suppose that the offspring can mutate with a chance 𝒄 of 10% or lower, and 𝝋 = 1. Therefore:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙

Offspring 0.15 0.05 0.92 0.07 0.53 0.70

𝜉 = 0.02
𝑐 = 2%

1 1 1
ρ= 2×𝜉 𝜑+1 − 1 = 2 × 0.02 1+1 − 1 = 0.04 2 − 1 = −0.80

gene = gene + ρ = 0.07 − 0.80 = −0.73

65
 MH – Genetic Algorithm
Let’s suppose that the offspring can mutate with a chance 𝒄 of 10% or lower, and 𝝋 = 1. Therefore:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙

Offspring 0.15 0.05 0.92 −0.73 0.53

𝜉 = 0.02
𝑐 = 2%

1 1 1
ρ= 2×𝜉 𝜑+1 − 1 = 2 × 0.02 1+1 − 1 = 0.04 2 − 1 = −0.80

gene = gene + ρ = 0.07 − 0.80 = −0.73

66
 MH – Genetic Algorithm
Let’s suppose that the offspring can mutate with a chance 𝒄 of 10% or lower, and 𝝋 = 1. Therefore:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙

Offspring 0.15 0.05 0.92 −0.73 0.53

If necessary, clip the offspring values

to respect the boundaries:0 ≤ 𝒙 ≤ 1

67
 MH – Genetic Algorithm
Let’s suppose that the offspring can mutate with a chance 𝒄 of 10% or lower, and 𝝋 = 1. Therefore:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙

Offspring 0.15 0.05 0.92 0 0.53 0.72

If necessary, clip the offspring values

to respect the boundaries:0 ≤ 𝒙 ≤ 1

68
Elitism

69
The elitism is an optional process, where the best individual of the last the population is
included in the new population. Hence:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Individual 3 0.28 0.84 0.53 0.15 0.57 0.22

Individual 4 0.99 0.92 0.19 0.81 0.06 1.06

The elitism is an optional process, where the best individual of the last the population is
included in the new population. Hence:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Individual 3 0.28 0.84 0.53 0.15 0.57 0.22

Individual 4 0.99 0.92 0.19 0.81 0.06 1.06

The elitism is an optional process, where the best individual of the last the population is
included in the new population. Hence:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Individual 3 0.28 0.84 0.53 0.15 0.57 0.22

Individual 4 0.99 0.92 0.19 0.81 0.06 1.06

Elite
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
New Individual 1 0.12
0.28 0.03
0.84 0.91
0.53 0.73
0.15 0.22
0.57 0.29
0.22
The elitism is an optional process, where the best individual of the last the population is
included in the new population. Hence:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Individual 3 0.28 0.84 0.53 0.15 0.57 0.22

Individual 4 0.99 0.92 0.19 0.81 0.06 1.06

Copied
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
New Individual 1 0.12
0.28 0.03
0.84 0.91
0.53 0.73
0.15 0.22
0.57 0.29
0.22

New Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

New Individual 3 0.99

0.28 0.92
0.84 0.19
0.53 0.81
0.15 0.06
0.57 1.06
0.22
The elitism is an optional process, where the best individual of the last the population is
included in the new population. Hence:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
Individual 1 0.12 0.03 0.91 0.73 0.22 0.29

Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

Individual 3 0.28 0.84 0.53 0.15 0.57 0.22

Individual 4 0.99 0.92 0.19 0.81 0.06 1.06

Crossover & Mutation

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙
New Individual 1 0.12
0.28 0.03
0.84 0.91
0.53 0.73
0.15 0.22
0.57 0.29
0.22

New Individual 2 0.50 0.76 0.88 0.14 0.62 0.84

New Individual 3 0.99

0.28 0.92
0.84 0.19
0.53 0.81
0.15 0.06
0.57 1.06
0.22

New Individual 4 0.15

0.99 0.05
0.92 0.92
0.19 0
0.81 0.53
0.06 0.72
1.06
After 250 generations

75
 MH – Genetic Algorithm
For the problem,

𝑥3 − 𝑥4
𝑓 𝒙 = 2𝑥1 − sin 𝑥2 + + 𝑥5 2 ; where 0 ≤ 𝒙 ≤ 1
5

The best individual found was:

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓 𝒙

0 1 0 1 0 −1.41

76
 MH – Genetic Algorithm

[Link]

77
View publication stats