Genetic Algorithm
A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.
In the words of Charles Darwin:
It is not the strongest of the species that survives, nor the most intelligent , but the one most responsive to change.
Interestingly, the entire concept of genetic algorithms revolves around this single quote.
Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on bio-inspired operators such as mutation, crossover and selection.
Biological Inspiration
Cells are the building blocks of the body. Each cell consists of a set of chromosomes which are essentially strings of DNA, carrying heredity information across generations. Each chromosome consists of units called genes, which are essentially the DNA carriers.
The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. This inheritance of fittest characteristics is made possible by the passage of chromosomes, across the generations. Thus, in a way, the chromosomes are the storage structures holding the fitness information for a particular species.
The genetic algorithm also uses the concept of chromosomes as the data structures which shall consist the optimal solution set of the optimisation or the search heuristic problem.
Five phases are considered in a genetic algorithm.
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
Initial Population
The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. Each individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).
In a genetic algorithm, chromosomes are represented by a set of alphabets and the genes are encodes in binary.
Fitness Function
The fitness function is the one that assigns a fitness value/score to an individual in the solution set. The fitness score is a representative of the ability of the particular to compete with other individuals. The fitness value forms the basis of selection of an individual for the production of offsprings for the next generation.
Calculation of fitness value is done repeatedly in a GA and therefore it should be sufficiently fast. A slow computation of the fitness value can adversely affect a GA and make it exceptionally slow.
In most of the optimization problems, we seek to maximize or minimize an objective function. In most the applications of GA, the fitness function and the objective function are the same. However, for more complex problems with multiple objectives and constraints, a different fitness function might be chosen which follows the following norms:
- The fitness function should be sufficiently fast to compute.
- It must quantitatively measure the fitness of a given solution is or how fit individuals can be produced from the given solution.
Selection
Selection is the process of choosing parents which mate and recombine to create off-springs for the next generation. Parent selection is very crucial to the convergence rate of the GA as good parents drive individuals to better and fitter solutions. Maintaining diversity is also a key component of the selection process.
The various selection strategies employed in this process include the following:
- Roullete Wheel Selection
- Stochastic Universal Sampling (SUS)
- Tournament Selection
- Rank Selection
- Random Selection
Cross Over
The crossover operator is analogous to reproduction and biological crossover. The process selects more than one parent and one or more off-springs are produced using the genetic information of the parents.
For each pair of parents to be mated, a crossover point is chosen from within the genes. The chromosomes segments around the crossover points are swapped to result into new offsprings.
There are several kinds of crossover strategies employed the popular ones include:
- One-Point Crossover
- Multi-Point Crossover
- Uniform Crossover
- Davis’ Order Crossover (OX1)
- Whole Arithmetic Recombination Crossover
Mutation
A mutation may be defined as a small random tweak in the chromosome, to get a new solution. It is used to maintain and introduce diversity in the genetic population and is usually applied with a low probability. It implies the flipping of bits in the chromosome.
The various kinds of mutation operators available for choice of designers include,
Pseudocode
START
Generate the initial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
UNTIL population has converged
STOP