Premature convergence
Encyclopedia
In genetic algorithm
s, the term of premature convergence means that a population for an optimization problem
converged too early, resulting in being suboptimal. In this context, the parental solutions, through the aid of genetic operator
s, are not able to generate offsprings that are superior to their parents. Premature convergence can happen in case of loss of genetic variation (every individual in the population is identical, see convergence
).
The genetic variation can also be regained by mutation
though this process is highly random.
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s, the term of premature convergence means that a population for an optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
converged too early, resulting in being suboptimal. In this context, the parental solutions, through the aid of genetic operator
Genetic operator
A genetic operator is an operator used in genetic algorithms to maintain genetic diversity, known as Mutation and to combine existing solutions into others, Crossover...
s, are not able to generate offsprings that are superior to their parents. Premature convergence can happen in case of loss of genetic variation (every individual in the population is identical, see convergence
Convergence (evolutionary computing)
Precisely every individual in the population is identical. While full convergence might be seen in genetic algorithms using only cross over, such convergence is seldom seen in genetic programming using Koza's subtree swapping crossover...
).
Strategies for preventing premature convergence
Strategies to regain genetic variation can be:- a mating strategy called incest prevention,
- uniform crossover,
- favored replacement of similar individuals (preselection or crowding),
- segmentation of individuals of similar fitness (fitness sharing),
- increasing population size.
The genetic variation can also be regained by mutation
Mutation
In molecular biology and genetics, mutations are changes in a genomic sequence: the DNA sequence of a cell's genome or the DNA or RNA sequence of a virus. They can be defined as sudden and spontaneous changes in the cell. Mutations are caused by radiation, viruses, transposons and mutagenic...
though this process is highly random.