Genotype Representation - Genetic Algorithms

What is Genotype Representation?

One of the maximum significant choices to make while applying a genetic algorithm is determining the representation that we will use to represent our solutions. It has been experiential that improper representation can lead to poor performance of the GA.

As a result, selecting a proper representation, having a proper definition of the mappings between the phenotype and genotype spaces is vital for the success of a GA.

In this unit, we present some of the most usually used depictions for genetic algorithms. However, depiction is highly problem precise and the reader might find that another representation or a mix of the representations mentioned here might suit his/her problem better.

Binary Representation

This is one of the modest and most extensively used representations in GAs. In this type of representation the genotype consists of bit strings.
For some difficulties when the solution space contains of Boolean decision variables – yes or no, the binary representation is natural. Take for instance the 0/1 Knapsack Problem. If there are n items, we can represent a solution by a binary string of n elements, where the xth element tells whether the item x is picked (1) or not (0).
binary_representation

For other difficulties, precisely those dealing with numbers, we can represent the numbers with their binary representation. The difficult with this kind of encoding is that different bits have different meaning and therefore alteration and crossover operators can have undesired consequences. This can be determined to some degree by using Gray Coding, as a change in one bit does not have an enormous effect on the solution.

Real Valued Representation

For difficulties where we want to describe the genes using continuous rather than discrete variables, the real valued representation is the most natural. The exactness of these real valued or floating point numbers is though limited to the computer.

real_valued_representation

Integer Representation

For distinct valued genes, we cannot all the time limit the solution space to binary ‘yes’ or ‘no’. For instance, if we want to encode the four distances – North, South, East and West, we can encode them as {0,1,2,3}. In such cases, integer representation is desirable.
integer_representation

Permutation Representation

In numerous difficulties, the solution is signified by an order of elements. In such cases permutation representation is the most suited.
A common instance of this representation is the travelling salesman problem (TSP). In this the salesman has to take a tour of all the cities, visiting each city precisely once and come back to the starting city. The total distance of the tour has to be minimized. The solution to this TSP is obviously an ordering or permutation of all the cities and therefore using a permutation representation makes sense for this problem.

permutation_representation

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Genetic Algorithms Topics