Genetic Algorithm for optimization problem.
Introduction
Genetic Algorithms (GAs) are adaptive heuristic search algorithms that generates high-quality solutions for optimization and search problems.
The genetic algorithm (GA), developed by John Holland and his collaborators in the 1960s and 1970s (Holland, 1975; De Jong, 1975), is a model or abstraction of biological evolution based on Charles Darwin’s theory of natural selection. Algorithm relies on the idea of natural selection and genetics (evolutionary biology). It is obvious that Genetic Algorithm is targeted to leverage reasonable solutions cause of which it is highly capable of solving complex constrained and unconstrained optimization issues.
GA simulate the process of natural selection which means those species who can adapt to changes their environment are able to survive and reproduce and go to next generation. That is only the most suited elements in a population are likely to survive and generate offspring, thus transmitting their biological heredity to new generations. Most commonly employed is a way of creating a group of individual randomly from a given population. Each generation consist of a population of individuals where each individual represents a point(chromosomes) in search space and possible solution. Each individual is represented as a string of character/float/integer/bits. This combinational string is analogous to the Chromosome.
GA is widely used in the fields such as optimized telecommunication routing, computer aided-molecular design, robotics, engineering and the list goes on.
Foundation of Genetic Algorithm
In the reproduction phase, initially individuals are being selected from available population and recombined. Parents are selected randomly on the scheme of which has higher fitness score. Having selected two parents, their chromosomes are recombined, typically using the mechanisms of crossover and mutation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. The process continues iterate till the generation with fittest individuals will be found.
Typical genetic algorithm has considerably five stages.
1. Initial population
2. Fitness Function: Used to guide simulations towards optimal design solutions. Or it is a metric to evaluate how well each chromosomes fits and to identify them.
3. Selection: The concept of selection is ensuring that the best performing (higher fitness function) chromosome are ensured higher chance (probability) to be used to produce offspring for the next level.
4. Crossover: Combining the genetic information of parents resulting new offspring.
5. Mutation: Mutations are used in GA’s in order to push hypothesis toward optimal. Achieved by randomly flipping a bit of gene and carry the chromosome to the subsequent generation process.
Pseudo Code
