Genetic Algorithms
Chapter 4b
(based on AIMA Slides)
November 2020 SU, FMI – Boris Velichkov 1
Genetic Algorithms
= stochastic local beam search
+ generate successors from pairs of states
2
Genetic Algorithms
In computer science and operations research,
a genetic algorithm (GA) is a metaheuristic
inspired by the process of natural selection that
belongs to the larger class of evolutionary
algorithms (EA). Genetic algorithms are
commonly used to generate high-quality solutions
to optimization and search problems by relying on
bio-inspired operators such as mutation, crossover
and selection.
3
Genetic Algorithms
A Genetic Algorithm is a type of local search
that mimics evolution by taking a population of
strings, which encode possible solutions and
combines them based on a fitness function to
produce individuals that are more fit.
4
Selection
Selection is the stage of a genetic algorithm in
which individual genomes are chosen from a
population for later breeding (using the crossover
operator).
5
Crossover
In GAs, crossover is a genetic operator used to
vary the programming of a chromosome (or
chromosomes) from one generation to the next. It
is analogous to reproduction and biological
crossover, upon which GA are based.
Crossover is a process of taking more than one
parent solutions and producing a child solution
from them.
6
Mutation
Mutation is a genetic operator used to maintain
genetic diversity from one generation of a
population of genetic algorithm chromosomes to
the next. It is analogous to biological mutation.
Mutation alters one or more gene values in a
chromosome from its initial state.
7
GAs & Biology
8
GAs & Biology
9
GAs & Biology
10
GAs: The „Reproduction“ Cycle
11
GAs: The „Reproduction“ Cycle
12
GAs: Main Steps
Initialization
Population
Selection
Fitness Function
Crossover
Mutation
13
Crossover
14
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
15
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
16
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3
5 4 3
17
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 _
5 4 3
18
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5
5 4 3
19
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 _
5 4 3
20
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 4
5 4 3
21
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 4
5 4 3
22
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 4
5 4 3 _
23
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 4
5 4 3 1
24
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 4
5 4 3 1 _
25
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 4
5 4 3 1 2
26
One-Point Crossover
1 2 3 4 5
5 4 3 2 1
Let‘s i=3
1 2 3 5 4
5 4 3 1 2
27
One-Point Crossover
28
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
29
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
30
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
3 4 5
2 4 3
31
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
3 4 5 _
2 4 3
32
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
3 4 5 _
2 4 3
33
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
3 4 5 1
2 4 3
34
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
3 4 5 1 _
2 4 3
35
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
3 4 5 1 7
2 4 3
36
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
_ 3 4 5 1 7
2 4 3
37
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
6 3 4 5 1 7
2 4 3
38
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
6 _ 3 4 5 1 7
2 4 3
39
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
6 2 3 4 5 1 7
2 4 3
40
Two-Point Crossover
1 2 3 4 5 6 7
7 6 2 4 3 5 1
Let‘s i=3, j=5
6 2 3 4 5 1 7
2 4 3
41
Two-Point Crossover
42
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
43
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
44
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
3 4 5
4 1 2
45
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
3 4 5
4 1 2
46
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
3 4 5
4 1 2
47
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
3 4 5
4 1 2
48
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
1 3 4 5
4 1 2
49
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
1 3 4 5
4 1 2
50
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
1 3 4 5
4 1 2
51
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
1 3 4 5 2
4 1 2
52
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
1 3 4 5 2
4 1 2
53
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
_ 1 3 4 5 _ 2
4 1 2
54
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
6 1 3 4 5 7 2
4 1 2
55
Partially-mapped Crossover
1 2 3 4 5 6 7
6 3 4 1 2 7 5
Let‘s i=3, j=5
6 1 3 4 5 7 2
4 1 2
56
Partially-mapped Crossover
57
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
58
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
59
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
60
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
61
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
62
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
63
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
64
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
65
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
66
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
67
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
68
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
69
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
70
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
71
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
72
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
73
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
74
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
75
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
76
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
77
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
78
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
79
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
80
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 9 0
0 8 9
81
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 1 2 4 5 6 7 9 0
0 4 7 6 2 5 1 8 9
82
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 1 2 4 5 6 7 9 0
0 4 7 6 2 5 1 8 9
83
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 1 2 4 5 6 7 9 0
0 4 7 6 2 5 1 8 9
84
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 1 2 4 5 6 7 9 0
0 4 7 6 2 5 1 8 9
85
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 1 2 3 4 5 6 7 9 0
0 4 7 3 6 2 5 1 8 9
86
Cycle Crossover
8 4 7 3 6 2 5 1 9 0
0 1 2 3 4 5 6 7 8 9
8 1 2 3 4 5 6 7 9 0
0 4 7 3 6 2 5 1 8 9
87
Cycle Crossover
88
Cycle Crossover
89
Cycle Crossover
90
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
91
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
92
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
93
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
94
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2
95
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4
96
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4
97
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4 5
98
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4 5 7
99
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4 5 7 7
100
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4 5 7 7 9
101
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4 5 7 7 9 9
102
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4 5 7 7 9 9 0
103
Uniform Crossover
1 2 3 4 5 6 7 8 9 1
2 3 4 5 5 7 7 9 9 0
Getting a gene from one of the parents randomly!
2 2 4 4 5 7 7 9 9 0
104
Uniform Crossover
105
Mutation
106
Travelling salesman problem
107
Knapsack problem
108
109
