Genetic Algorithms: Motivation and  Genetic Algorithm-Representing

Genetic algorithm- Motivation

Genetic algorithms are preferred for solving optimization problems as they can yield a result in optimum time and is also relatively faster. 

The need for the genetic algorithm is as follows:

1. Gradient base model failures

In the gradient base method, traditional calculus is used. It starts at a random point and moves in the direction of the gradient, till it reaches the top point. Though this method is effective for single peaked objective functions such as the cost function in linear regression, it cannot be very useful in real life where the problems are more complex such as landscapes, they are made of many peaks and valleys leading to the failure of these models. They will ultimately get stuck at the local optima.

2. Solving difficult problems with ease.

In computer science, we have many problems that even the most powerful computers take ages to compute. In this situation, a generic algorithm comes handy as it can give approximated solutions in optimal time.

3. Time-efficient. 

Many problems such as the Travelling Salesperson Problem or TSP has many practical uses such as pathfinding and VLSI design. GA can give efficient results in optimum time. For example, how much of a trouble it would be if our GPS took hours to give us the path from our source to destination. But with GA involved we can get a good result in a small time. 

Genotype representing 

Genotype representation is very important during the implementation of a genetic algorithm, as it directly impacts the performance of the genetic algorithm. A proper representation is where the phenotype and the genotype mappings have proper spaces between them. 

The most common representation methods for GA are as follows:

1. Binary representation

Binary representation is one of the most common methods of representing GA.

The genotype in this method consists of bit strings. In the case of a Knapsack problem, where the solution space consists of Boolean decision variables, the binary representation is natural.

For other problems, which may deal with numbers, we represent the numbers with their binary representation. The only drawback in this situation is that different bits have different meanings, which results in undesired consequences for the mutation and crossover operators.

2. Integer representation

In the case of discrete-valued genes, we cannot always limit the results to binary, so instead, we use integer representation. For example,  if we had to encode the three directions, we could have encoded them as: {1,2,3,4}, and represented using integer representation.

3. Permutation representation

Whenever the solutions are represented by an order of elements we can use permutation representation. We can take the same example of TSP, let us assume the person has to travel all the cities, visiting one city at a time, and then comes back to the source city. As we can see the order of the TSP is naturally becoming a permutation, therefore we can use the permutation representation. 

4. Real valued representation

In the problems where we require to define the genes using continuous variables, we use real-valued representation. 

Reference

Genetic Algorithms: Motivation and  Genetic Algorithm-Representing