Gentle introduction to Genetic Algorithm

by keshav

---

---

Introduction

Genetic Algorithms are a type of optimization algorithms that falls under the category of evolutionary computations. In evolutionary computation, the algorithms are inspired by the biological evolution processes like reproduction, crossovers, selection, and mutation.

Genetic algorithms rely on biologically inspired operators such as mutation, crossover, and selection to develop high-quality solutions to optimization and search problems.

Before we get into the genetic algorithm let’s look at some of the basic concepts required to understand the algorithm better.

Population: It constitutes the subset of all the possible solutions to the given problem. The solutions are present in encoded form. Encoding represents the mapping of actual solutions to some string code. There are several encoding techniques like binary encoding, octal encoding, value encoding, permutation encoding, etc. out of these, binary encoding is most commonly used.

Chromosomes: Chromosome represents one of the many solutions to the problem. Sometimes chromosomes are also called individuals.

Genes: Set of parameters that are combined to form chromosomes.

 

 

Fitness Function: The fitness functions are the type of objective functions that is used to check how well the solution with respect to the problem is taken into consideration. In simple words, it is the function that is to be optimized.

Algorithm

There are five stages involved in genetic algorithm.

1. Population Initialization
2. Calculation of Fitness value
3. Selection
4. Crossover
5. Mutation
6. Termination

Flow chart:

Let us understand the flow of the genetic algorithms with the help of a flow chart as below.

 

1. Population Initialization: Genetic algorithm starts with the initialization of the population. The population represents the subset of all the possible solutions to our problem. Initialization is usually done randomly.

The size of the population is an important parameter in a genetic algorithm. It directly influences the ability to search for an optimum solution. Many researchers have found that a larger size of population leads to high accuracy and chances of getting an optimum solution. But taking a very large population may be computationally expensive.

 

2. Calculation of Fitness value: The fitness value is calculated from the initialized population using the fitness function. On the basis of fitness value calculated the section of the individual is done. From the population, the individuals with high fitness values are selected for the next steps i.e. crossover and mutation.

 

3. Selection: Selection is the process of selecting the fittest individuals and lets them pass their genes to the next generation. Selection is performed on the basis of fitness value. A pair of individuals from the selected ones undergo further phases i.e. crossover and mutation.

 

4. Crossover: Crossover also called recombination is the process of exchange of genetic materials (genes) between the parents. For the pair of individuals (or parents) to be recombined, a random crossover point is chosen. Then the genes are exchanged between the parents beyond the crossover point.

There are several crossover techniques/operators. Some of the most commonly used ones are,

    i. One Point Crossover: A random crossover point is chosen and the part beyond the crossover point is swapped between the parents to get new offspring.

    ii. Multipoint or N-Point Crossover: In the multipoint crossover, multiple crossover points are chosen randomly and the genes between the crossover points are swapped between the parents.

 

    iii. Uniform Crossover: In this type of crossover each gene can take part in the crossover as a separate entity. To decide which gene to swap, we opt for some selection techniques like the tossing of a coin.

 

5. Mutation: It is analogous to biological mutation. Mutation maintains the genetic diversity from one generation of the population to the next. In mutation some of the genes of the obtained off-springs are altered from its previous state, thus creating an entirely new solution. Hence mutation can help to get a better solution.

The mutation is performed on the basis of user-defined probability. As it mimics the biological mutation, so the probability should be kept low.

There are several types of mutation. Some of the most common ones are,

Flip Bit: In this one or more random bits (genes) are flipped (i.e. if it is 1, it is changed to 0 and vice versa). It is most common in case of binary encoding.

Swap: In this type of mutation, two genes from two random positions are swapped.

Boundary: In this mutation, a random genome is replaced by the boundary (lower or upper) value in the chromosome

Scramble Mutation: In this mutation, a set of genes are chosen and their values are shuffled randomly. It is commonly used when permutation encoding is used.

There are several other types also like, Bit-string Mutation, Uniform Mutation, Gaussian Mutation, Shrink Mutation, etc.

 

6. Termination: The termination condition in the genetic algorithm decides how long the looping in the algorithm will run. The GA produces better results in every loop, therefore to have the right number of loops, the termination criteria should be selected wisely. Usually, the algorithm terminates when the population converges (means, when the offspring generated, are not significantly different from the previous ones). In some cases, we may also terminate the algorithm if the value of the objective function has reached some predefined value.

Pseudocode:

The pseudo-code for the genetic algorithm is as explained below

Start
Initialize Population
Calculate fitness
Repeat (termination criteria is reached)
          Selection
          Crossover
          Mutation (optional)
          Calculate fitness
          Find best
Return best

  

 

---