Encoding Techniques In Genetic Algorithm
Binary encoding
- Most common method of encoding.
- Represent a gene in terms of bits (0s and 1s).
- Most suitable for optimization in a discrete search space.
Example 1
Question
Define the initial population for the following 0-1 Knapsack problem:
Solution
Some of the possible solutions without breaking the constraint (max capacity) are A, AB, AC, and BC.
There are three weights (A, B, and C). So we’ll take 3 bits to represent every chromosome in the population. 1 means that the weight is present and 0 means it is not.
The illustration below also aims to clarify some of the important terms like Population, Chromosome, Gene, and Allele.
or we can simply represent the solution like:
Example 2
Question
Define the initial population for the following problem:
Solution
Some of the possible solutions without breaking the constraint (0≤x≤15) are 5, 8, 10, and 13.
Maximum value that x can take is 15, which can be represented in 4 bits. So we’ll take 4 bits to represent every chromosome in the population.
Value encoding
- Represent a gene as some value.
- Value can be an integer, real number, character, or some object.
- Uses direct representations of the variables/design parameters.
- Avoids any intermediate encoding and decoding steps.
- Most suitable for optimization in a continuous search space.
Example 1
Question
Define the initial population for the following problem:
Solution
Some of the possible solutions without breaking the constraint (0≤x≤15) are 5, 8, 10, and 13.
Example 2
Question
Define the initial population for the following problem:
Solution
Some of the possible solutions without breaking the three constraints mentioned in the question are (1,2), (2,4), (3,5), and (4,6). The chromosomes represent the (x,y) combination.
Permutation (or Order) encoding
- Each chromosome represents a sequence (order of elements).
- Used in ordering problems.
Example 1
Question
Define the initial population for the following Travelling Salesman problem:
Solution
Some of the possible solutions without breaking the two constraints mentioned in the question are ABDECA, ADBECA, ACBDEA, and AEBCDA.
The chromosomes represent the order of cities visited by salesmen. For example, chromosome ABDECA means the salesmen move from city A to B, B to D, D to E, E to C, and C to A.
That will be it for this article.
Don’t forget to 👏 if you liked the article.
If you want to learn more about GA, check out my series of articles:
If you have any questions or would like something clarified, you can find me on LinkedIn.
~happy learning.
