Nature Inspired Optimization Algorithms — Genetic Algorithm
This is the part 4of the article series Nature Inspired Algorithms. Introductory article could be found at https://dindisn.medium.com/nature-inspired-optimization-algorithms-part-1-introduction-11dafcba07db
Genetic Algorithm is an evaluation based algorithm which follows the abstract process of Charles Darwins Evaluation theory and natural selection In biological systems.It has come into light that most of the companies at present use these as a back support system for the combinatorial optimization problems in their routine optimization problems like scheduling, planning and in many more scenarios.
Darwins theory starts from an existing population. Individuals in the population become parents and produce off springs and through heredity, characteristics of parents gets passed to the children. Variations will be introduced to the population through mutations happening in some scenarios.
Generally, as population tends to over produce only the fittest will survive and through natural selection some will survive whilst the others won’t. In natural scenarios this could be seen where the taller giraffes survive more than the shorter ones where there are only tall trees to consume as food, darker moths survive in industrially polluted blackened environment where as lighter ones are easily seen an captured to predators. So the traits of theses survivors will be more prominent in the survived and produced populations in future populations and this is how the evaluation happens.
In the genetic algorithm, concepts like natural selection, crossover, mutation have been mirrored.
- The process begins by initialising a set of individuals called a population. Each individual is a solution to the problem we want to solve.
An individual is characterised by a set of parameters (variables) known as Genes and collection of genes makes a Chromosome (solution).
- Fitness solution will then be developed to determine the most fittest solution. It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.
- The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction. Some algorithms use roulette wheel selection here to give the probability of selection.
- Chosen pairs will be called as parents and they are mated by choosing a random point as a crossover point.
- With some low random probability mutation can happen in some offsprings produced. For example X4 offspring might be converted to 11110 by mutating the 2nd gene.
Mutation occurs to maintain diversity within the population and prevent premature convergence ensuring exploration along with the exploitation of the algorithm.
- The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem