ML – Convergence of Genetic Algorithms

Introduction: 
 

• Genetic algorithms are probabilistic search optimization techniques, which operate on a population of chromosomes, representing potential solutions to the given problem.
• In a standard genetic algorithm, binary strings of 1s and 0s represent the chromosomes. Each chromosome is assigned a fitness value expressing its quality reflecting the given objective function. Such a population is evolved by means of reproduction and recombination operators in order to breed the optimal solution’s chromosome. The evolution keeps running until some termination condition is fulfilled. The best chromosome encountered so far is then considered as the found solution.
• Genetic algorithms simultaneously carry out exploitation of the promising regions found so far and exploration of other areas for potentially better solution.
• The weak point of a genetic algorithm is that it often suffers from so-called premature convergence, which is caused by an early homogenization of genetic material in the population. This means that no valuable exploration can be performed anymore.

Schematic Diagram 
 

Details: 
 

• Convergence is a phenomenon in evolutionary computation that causes evolution to halt because precisely every individual in the population is identical.
• Full Convergence might be seen in genetic algorithms using only cross-over.
• Premature convergence is when a population has converged to a single solution, but that solution is not as high of quality as expected, i.e. the population has gotten stuck.
• However, convergence is not necessarily a negative phenomenon, because populations often stabilize after a time, in the sense that the best programs all have a common ancestor and their behaviour is very similar/identical both to each other and to that of high fitness programs from the previous generations.
• Convergence can be avoided with a variety of diversity generating techniques.