GA Operators
Following are the GA operators in Genetic Algorithms.
1 Encoding
2 Convergence test
3 Mating pool
4 Fitness Evaluation
5 Crossover
6 Mutation
7 Inversion
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 2 / 42
Encoding Operation
1 Encoding
2 Convergence test
3 Mating pool
4 Fitness Evaluation
5 Crossover
6 Mutation
7 Inversion
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 3 / 42
Different Encoding Schemes
Often, GAs are specified according to the encoding scheme it follows.
For example:
Encoding Scheme
Binary encoding –> Binary Coded GA or simply Binary GA
Real value encoding –> Real Coded GA or simply Real GA
Order encoding –> Order GA (also called as Permuted GA)
Tree encoding
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 5 / 42
Encoding Schemes in GA
Genetic Algorithm uses metaphor consisting of two distinct elements :
1 Individual
2 Population
An individual is a single solution while a population is a set of
individuals at an instant of searching process.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 6 / 42
Individual Representation :Phenotype and
Genotype
An individual is defined by a chromosome. A chromosome stores
genetic information (called phenotype) for an individual.
Here, a chromosome is expressed in terms of factors defining a
problem.
Genotype
Factor 1 Factor 2 …. Factor n
Gene 1 Gene 2 …. Gene n
Phenotype
a b c 1 0 1 2 9 6 7 $ α β..................
Chromosome
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 7 / 42
Individual Representation :Phenotype and
Genotype
Note :
A gene is the GA’s representation of a single factor (i.e. a design
parameter), which has a domain of values (continuous,
discontinuous, discrete etc.) symbol, numbering etc.
In GA, there is a mapping from genotype to phenotype. This
eventually decideds the performance (namely speed and
accuracy) of the problem solving.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 8 / 42
Encoding techniques
There are many ways of encoding:
1 Binary encoding: Representing a gene in terms of bits (0s and
1s).
2 Real value encoding: Representing a gene in terms of values or
symbols or string.
3 Permutation (or Order) encoding: Representing a sequence of
elements)
4 Tree encoding: Representing in the form of a tree of objects.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 9 / 42
Binary Encoding
In this encoding scheme, a gene or chromosome is represented by a
string (fixed or variable length) of binary bits (0’s and 1’s)
A: 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 Individual 1
B: 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 Individual 2
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 10 / 42
Example: 0-1 Knapsack problem
There are n items, each item has its own cost (ci ) and weight (wi ).
There is a knapsack of total capacity w.
The problem is to take as much items as possible but not
exceeding the capacity of the knapsack.
This is an optimization problem and can be better described as follows.
Maximize :
P
i ci ∗ wi ∗ xi
Subject to
P
xi ∗ wi ≤ W
where xi ∈ [0 · · · 1]
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 11 / 42
Example: 0-1 Knapsack problem
Consider the fallowing, an instance of the 0-1 Knapsack problem.
I3
I2
I1
Max. Weight
30 50
50
20
10
$60 $100 $120 Knapsack
Brute force approach to solve the above can be stated as follows:
Select at least one item
[10], [20], [30], [10, 20], [10, 30], [, 20, 30], [10, 20, 30]
So, for n-items, are there are 2n − 1 trials.
0 - means item not included and 1 - means item included
[100], [010], [011], [110], [101], [011], [111]
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 12 / 42
Example: 0-1 Knapsack problem
The encoding for the 0-1 Knapsack, problem, in general, for n items
set would look as follows.
Genotype :
1 2 3 4 ..... n-1 n
.....
Phenotype :
0 1 0 1 1 0 1 0 1 0 1 0 1. . . . . .1 0 1
A binary string of n-bits
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 13 / 42
Few more examples
Example 1 :
Minimize :
2
f (x) = x2 + 125
x
where 0 ≤ x ≤ 15 and x is any discrete integer value.
Genotype :
Phenotype :
01101
A binary string of 5-bits
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 14 / 42
Few more examples
Example 2 :
Maximize :
f (x, y ) = x 3 − x 2 y + xy 2 + y 3
Subject to :
x + y ≤ 10
and
1 ≤ x ≤ 10
−10 ≤ y ≤ 10
Genotype :
x y
Phenotype :
01101 11001
Two binary string of 5-bits each
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 15 / 42
Order Encoding
Let us have a look into the following instance of the Traveling
Salesman Problem (TSP).
All cities are to be visited A possible tour
TSP
- Visit all the cities
- One city once only
- Starting and ending city is the same
How we can formally define the TSP?
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 22 / 42
Order Encoding for TSP
Understanding the TSP:
There is a cost of visiting a city from another city and hence the total
cost of visiting all the cities but exactly once (except the starting city).
Objective function: To find a tour (i.e. a simple cycle covering all the
cities) with a minimum cost involved.
Constraints:
All cities must be visited.
There will be only one occurrence of each city (except the starting
city).
Design parameters:
Euclidean distance may be taken as the measurement of the cost,
otherwise, if it is specified explicitly.
The above stated information are the design variables in this case.
We are to search for the best path out of n! possible paths.
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 23 / 42
A small instance of the TSP
d A B C D E 6
2 4
A 0 2 6 4
B 2 0 7 5
5 D
C 7 0 3 1 B
E
D 6 3 0 3
7
E 4 5 1 0
d= Distance matrix C
Connectivity among cities
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 24 / 42
Defining the TSP
Minimizing
Pn−2
cost = i=0 d(ci , ci+1 ) + d(cn−1 , c0 )
Subject to
P = [c0 , c1 , c2 , · · · , cn−1 , c0 ]
where ci ∈ X ;
Here, P is an ordered collection of cities and ci 6= cj such that
∀i, j = 0, 1, · · · , n − 1
Note: P represents a possible tour with the starting cities as c0 .
and
X = x1 , x2 , · · · , xn , set of n number of cities,
d(xi , xj ) is the distance between any two cities xi and xj .
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 01.03.2016 25 / 42