11 EC Encoding

Encoding Techniques in Genetic Algorithms
Debasis Samanta
Indian Institute of Technology Kharagpur

dsamanta@iitkgp.ac.in
13.03.2023
Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 1 / 47

Framework of GA
Start
Define parameters
Parameter representation
Create population
Initialize population
Apply cost
function to each of
the population
No
Converge ? Evaluate the fitness
Selection
Yes
Select Mate
Stop
Crossover
Reproduction
Mutation
Inversion

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

Encoding Operation
1 Encoding
2 Convergence test
3 Mating pool
4 Fitness Evaluation
5 Crossover
6 Mutation
7 Inversion

Different Encoding Schemes
Different GAs
Simple Genetic Algorithm (SGA)
Steady State Genetic Algorithm (SSGA)
Messy Genetic Algorithm (MGA)
Encoding Schemes
Binary encoding
Real value encoding
Order encoding
Tree encoding

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

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.

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
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.

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.

Binary Encoding Techniques

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

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]

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]
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

Few more examples: Example 2
Example 2:
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

Few more examples: Example 3
Example 3:
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

Pros and cons of Binary encoding scheme
Limitations:
1 Needs an effort to convert into binary from
2 Accuarcy depends on the binary reprresentation
Advantages:
1 Since operations with binary representation is faster, it provide a
faster implementations of all GA operators and hence the execution
of GAs.
2 Any optimization problem has it binary-coded GA implementation

Real Value Encoding

Real value encoding
The real-coded GA is most suitable for optimization in a

continuous search space.
Uses the direct representations of the design paparmeters.
Thus, avoids any intermediate encoding and decoding steps.
Genotype :
x y
Phenotype :
5.28 -475.36
Real-value representation

Real value encoding with binary codes
Methodology: Step 1 [Deciding the precision]
For any continuous design variable x such that XL ≤ x ≤ XU , and if ε is

the precision required, then string length n should be equal to

n = log2 XU −Xε
L
where XL ≤ x ≤ XU
Equivalently,
ε = XU2−Xn
L
In general, ε = [0 · · · 1]. It is also called, Obtainable accuracy
Note:If ε = 0.5, then 4.05 or 4.49 ≡ 4 and 4.50 or 4.99 ≡ 4.5 and so
on.

Real value encoding: Illustration 1
1 Example 1:
1 ≤ x ≤ 16, n = 6. What is the accuracy?
16−1 15
ε= 26
= 64 = 0.249 ≈ 0.25
2 Example 2:
What is the obtainable accuracy, for the binary representation for a
variable X in the range range 20.1 ≤ X ≤ 45.6 with 8-bits?
3 Example 3:
In the above case, what is the binary representation of X = 34.35?

Real value encoding with binary codes
Methodology: Step 2[Obtaining the binary representation]
Once, we know the length of binary string for an obtainable accuracy

(i.e precision), then we can have the following mapping relation from a
real value X to its binary equivalent decoded value XB ,which is given
by
X = XL + X2Un−X
−1 × XB
L
where XB = Decoded value of a binary string,

n is the number of bits in the representation,
XL → 0 0 0 0 · · · 0 and
XU → 1 1 1 1 · · · 1
are the decoded values of the binary representation of the lower and
upper values of X .

Real value encoding: Illustration 2
Example:
Suppose, XL = 2 and XU = 17 are the two extreme decoded values of

a variable x.
n = 4 is the number of binary bits in the representation for x.
XB = 10(= 1 0 1 0) is a decoded value for a given x.
What is the value of x =? and its binary representation??

17−2
Here, x = 2 + 24 −1
× 10 = 12
Binary representation of x = 1 1 0 0

Order Encoding

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?

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.
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

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 ̸= 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 .
Tree Encoding

Tree encoding
In this encoding scheme, a solution is encoded in the form of a binary

tree.
A D A B E G C F (In-order)
(TL R TR)
B C
A B D C E G F (Pre-order)
D E F (R TL TR)
D B G E E C A (Post-order)
G
(TL TR R)
A binary tree Three compact representation

Floor Planning : An example of tree encoding
Floor planning is a standard problem in VLSI design. Here, given n
circuits of different area requirements, we are to arrange them into a
floor of chip layout, so that all circuits are placed in a minimum layout
possible.
C2
C1
C3
C1
C2
C9 C5
C5
C6
C7 C4
C4 C8
C6 C8
C7
C9
C10 C3
10 circuits A floor plan

Formulation of floor planning problem
A possible formulation of Floor planning problem of VLSI circuit is as

follows.
Given :
1 A set of n rectangular blocks B = b1 , b2 , · · · , bi , · · · , bn
2 For each bi ∈ B, we have the following specification:
the width wi and height hi (which are constant for rigid blocks and
variable for flexible blocks)
1 hi
ρi , the desirable aspect ratio about where ρi ≤ wi ≤ ρi , where
ρi = 1, if the block bi is rigid.
ai = wi × hi , the area of each block bi .

Formulation of floor planning problem
3 A set of nets N = {n1 , n2 , · · · , nk } describing the connectivity

information.
Wire = f1 (B, N)
4 H
Desirable floor plan aspect ratio ρ such that 1ρ ≤ W ≤ ρ, where H
and W are the height and width of the floor plan, respectively.
Area = f2 (B, N, ρ)
5 Timing information.
Delay = f3 (B, N, ρ)

Formulation of Floor planning problem
A legal floor plan is a floor plan that satisfies the following constraints.
Constraints :
3 Each block bi is assigned to a location say (xi , yi ).
4 No two blocks overlap
5 For each flexible block say bi , ai = wi × hi and should meet aspect
ratio constraint.
Objectives :
We are to find a floor plan, which would
1 Minimize floor plan area.
2 Minimize wire length.
3 Minimize circuit delay.

Tree encoding for Floor planning problem
3 4 5
1 1
4 5 6 7
2 2
6 7 3
Floor Plan I Floor Plan II
1 How many floor plans are possible?

2 Can we find a binary tree representation of a floor plan??

Binary tree representation for floor planning
A floor plan can be modeled by a binary tree with n leaves and n − 1

nodes where
each node represents a vertical cut-line or horizontal cut-line, and

Letter V and H refer to vertical and horizontal cut-operators.
each leaf node represents a rectangle blocks.

Example : Floor plane I
H H
3
1
2 1 H 3
4 5
2 V V
6 7
6 7 4 5
Floor Plan I Binary tree representation of the floor plan I

Note 1:
The operators H and V expressed in polish notation carry the following
meanings:
ijH → Block bj is on top of the block bi .
ijV → Block bi is on the left of block bj .
Note 2: A tree can be represented in a compact form using Polish

notation
Note 3: Polish notation
a + b ÷ c = a + (b ÷ c) = abc ÷ +
a + b − c = ab + c−

Note 4:
Post order traversal of a binary tree is equivalent to polish notation
+ -
abc÷+ ab+c-
a ÷ + c
b c
a b
Note 5:
There is only one way to performing a post order traversal of a binary
tree.

Example : Floor Plane I (with Polish notation
H H
3
1
2 1 H 3
4 5
2 V V
6 7
6 7 4 5
Floor Plan I Binary tree representation of the floor plan I
Polish notation : 2 1 H 6 7 V 4 5 V H 3 H V

Example : H and V operators
H
V2
2
3 1 V
H3 2
V4
3
4 5
2
H1 H 2
1 4
V 3
Floor Plan
4 5
Binary tree
Polish notation : 4 5 V 3 H 2 V 1 H

Example :Floor plan II
H H
2 1 V
H
?
6 7
V 3
4 5
2 1 H 6 7 V 4 5 V 3 H H V

Example :Floor plan II
H H 3
1
2 1 V
H 4 5
6 7 2
V 3 6 7
4 5
2 1 H 6 7 V 4 5 V 3 H H V

Problem
Problem :
How many number of solutions possible with n blocks in a floor

planning problem?

Problem
Problem :
How many number of solutions with n blocks in a floor planning

problem?
1 2n

N = n+1 n

Any question??

11 EC Encoding

Uploaded by

Copyright:

Available Formats

11 EC Encoding

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

11 EC Encoding

Uploaded by

Copyright:

Available Formats

Encoding Techniques in Genetic Algorithms

Indian Institute of Technology Kharagpur

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 1 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 2 / 47

Following are the GA operators in Genetic Algorithms.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 3 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 4 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 5 / 47

Often, GAs are specified according to the encoding scheme it follows.

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)

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 6 / 47

Genetic Algorithm uses metaphor consisting of two distinct elements :

An individual is a single solution while a population is a set of

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 7 / 47

Factor 1 Factor 2 …. Factor n

Gene 1 Gene 2 …. Gene n

A gene is the GA’s representation of a single factor (i.e. a design

In GA, there is a mapping from genotype to phenotype. This

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 9 / 47

There are many ways of encoding:

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 10 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 11 / 47

In this encoding scheme, a gene or chromosome is represented by a

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 12 / 47

There is a knapsack of total capacity W .

The problem is to take as much items as possible but not

This is an optimization problem and can be better described as follows.

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 13 / 47

$60 $100 $120 Knapsack

Brute force approach to solve the above can be stated as follows:

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 15 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 16 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 17 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 18 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 19 / 47

The real-coded GA is most suitable for optimization in a

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 20 / 47

Methodology: Step 1 [Deciding the precision]

For any continuous design variable x such that XL ≤ x ≤ XU , and if ε is

In general, ε = [0 · · · 1]. It is also called, Obtainable accuracy

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 21 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 22 / 47

Methodology: Step 2[Obtaining the binary representation]

Once, we know the length of binary string for an obtainable accuracy

where XB = Decoded value of a binary string,

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 23 / 47

Suppose, XL = 2 and XU = 17 are the two extreme decoded values of

n = 4 is the number of binary bits in the representation for x.

XB = 10(= 1 0 1 0) is a decoded value for a given x.

What is the value of x =? and its binary representation??

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 24 / 47

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 25 / 47

Let us have a look into the following instance of the Traveling

All cities are to be visited A possible tour

How we can formally define the TSP?

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 26 / 47

Connectivity among cities

Debasis Samanta (IIT Kharagpur) Soft Computing Applications 13.03.2023 28 / 47