Jump to content

Premature convergence

Edit links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Iridescent (talk | contribs) at 20:24, 7 April 2020 (→Self-adaptive mutations: Cleanup and typo fixing, typo(s) fixed: doesn’t → doesn't, ’s → 's). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In genetic algorithms, 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 operators, are not able to generate offspring that are superior to, or outperform, their parents. Premature convergence is a common problem found in genetic algorithms, as it leads to a loss, or convergence of, a large number of alleles, subsequently making it very difficult to search for a specific gene in which the alleles were present.[1][2] An allele is considered lost if, in a population, a gene is present, where all individuals are sharing the same value for that particular gene. An allele is, as defined by De Jong, considered to be a converged allele, when 95% of a population share the same value for a certain gene (see also convergence).[3]

Strategies for preventing premature convergence

Strategies to regain genetic variation can be:

  • a mating strategy called incest prevention,[4]
  • 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 though this process is highly random.

Identification of the occurrence of premature convergence

It is hard to determine when premature convergence has occurred, and it is equally hard to predict its presence in the future.[2][1] One measure is to use the difference between the average and maximum fitness values, as used by Patnaik & Srinivas, to then vary the crossover and mutation probabilities.[5] Population diversity is another measure which has been extensively used in studies to measure premature convergence. However, although it has been widely accepted that a decrease in the population diversity directly leads to premature convergence, there have been little studies done on the analysis of population diversity. In other words, by using the term population diversity, the argument for a study in preventing premature convergence lacks robustness, unless specified what their definition of population diversity is.[6]

Causes for premature convergence

There are a number of presumed or hypothesized causes for the occurrence of premature convergence.

Self-adaptive mutations

Rechenberg introduced the idea of self-adaptation of mutation distributions in evolutionary strategies.[7] According to Rechenberg, the control parameters for these mutation distributions evolved internally through self-adaptation, rather than predetermination. He called it the 1/5-success rule of evolutionary strategies (1 + 1)-ES: The step size control parameter would be increased by some factor if the relative frequency of positive mutations through a determined period of time is larger than 1/5, vice versa if it is smaller than 1/5. Self-adaptive mutations may very well be one of the causes for premature convergence.[6] Accurately locating of optima can be enhanced by self-adaptive mutation, as well as accelerating the search for this optima. This has been widely recognized, though the mechanism's underpinnings of this have been poorly studied, as it is often unclear whether the optima is found locally or globally.[6] Self-adaptive methods can cause global convergence to global optimum, provided that the selection methods used are using elitism, as well as that the rule of self-adaptation doesn't interfere with the mutation distribution, which has the property of ensuring a positive minimum probability when hitting a random subset.[8] This is for non-convex objective functions with sets that include bounded lower levels of non-zero measurements. A study by Günter suggests that self-adaption mechanisms among elitist evolutionary strategies do resemble the 1/5-success rule, and could very well get caught by a local optimum that include a positive probability.[6]

References

  1. ^ a b Leung, Y., et al. (1997). Degree of population diversity – A perspective on premature convergence in genetic algorithms and its markov chain, IEEE Transactions on Neural Networks, vol. 8, pp. 1165 – 1176.
  2. ^ a b Baker, J.E. & Grefenstette, J. (2014). Proceedings of the First International Conference on Genetic Algorithms and their Applications. Hoboken: Taylor and Francis, pp. 101 - 105.
  3. ^ De Jong, K.A. (1975). Analysis of the behaviour of a class of genetic adaptive systems, ph.D. dissertation, University of Michigan.
  4. ^ Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edition. Springer-Verlag. p. 58. ISBN 3-540-60676-9.
  5. ^ Patnaik, L.M. & Srinivas, M. (1994). Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans. Syst. Man Cybern., vol. 24, pp. 656-667.
  6. ^ a b c d Günter, R. (2001). Self-adaptation may lead to premature convergence , Fachbereich Informatik, LS XI, Universität Dortmund, pp. 1 - 13.
  7. ^ Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart.
  8. ^ Rudolph, G. (1999). Global convergence and self-adaptation: A counter-example. In Proceedings of the 1999 Congress of Evolutionary Computation (CEC 1999). IEEE Press, New Jersey, pp. 646–651.

See also


Stub icon

This evolution-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Premature_convergence&oldid=949667003"