Template:Evolutionary algorithms Premature convergence is an unwanted effect in evolutionary algorithms (EA), a metaheuristic that mimics the basic principles of biological evolution as a computer algorithm for solving an optimization problem. The effect means that the population of an EA has 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 evolutionary 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.<ref name="Leu97">Template:Cite journal</ref><ref name=":1">Template:Citation</ref> 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.<ref>Template:Cite thesis</ref>
Strategies for preventing premature convergenceEdit
Strategies to regain genetic variation can be:
- a mating strategy called incest prevention,<ref name=zhigl1991>Template:Cite book</ref>
- uniform crossover,
- mimicking sexual selection,<ref>Template:Cite book</ref>
- favored replacement of similar individuals (preselection or crowding),
- segmentation of individuals of similar fitness (fitness sharing),
- increasing population size
- niche and specie
The genetic variation can also be regained by mutation though this process is highly random.
A general strategy to reduce the risk of premature convergence is to use structured populations instead of the commonly used panmictic ones.
Identification of the occurrence of premature convergenceEdit
It is hard to determine when premature convergence has occurred, and it is equally hard to predict its presence in the future.<ref name=":1" /><ref name="Leu97" /> 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.<ref>Template:Cite journal</ref> 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.<ref name=":2">Template:Cite journal</ref>
There are models to counter the effect and risk of premature convergence that do not compromise core GA parameters like population size, mutation rate, and other core mechanisms. These models were inspired by biological ecology, where genetic interactions are limited by external mechanisms such as spatial topologies or speciation.<ref>Davidor, Y., & Ben-Kiki, O. (1991). Local ecological-like evolutionary computing framework for global robustness. In Emergent Computing Methods in Engineering Design (pp. 1–9). Springer.</ref><ref>Davidor, Y. (1991). An Adaptation Anomaly of a Genetic Algorithm. In J. A. Meyer & S. W. Wilson (Eds.), First International Conference on Simulation of Adaptive Behavior (pp. 510–517). MIT Press.</ref> These ecological models, such as the Eco-GA, adopt diffusion-based strategies to improve the robustness of GA runs and increase the likelihood of reaching near-global optima.<ref>Davidor, Y. (1991). A Naturally Occurring Niche & Species Phenomenon: The Model and First Results. In R. K. Belew & L. B. Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms (pp. 257–263). Morgan Kaufmann.</ref><ref>Davidor, Y. (1993). The ECOlogical Framework II: Improving GA Performance with Virtually Zero Cost. In Proceedings of the Fifth International Conference on Genetic Algorithms and Their Applications.</ref><ref>Davidor, Y. (1993). An Ecological Model for Evolutionary Computing. Systems, Control and Information, 37(8).</ref><ref>Davidor, Y. (1994). Free the Spirit of Evolutionary Computing: The Ecological Genetic Algorithm Paradigm. In R. Paton (Ed.), Computing with Biological Metaphors. Chapman & Hall.</ref>
Causes for premature convergenceEdit
There are a number of presumed or hypothesized causes for the occurrence of premature convergence.
Self-adaptive mutationsEdit
Rechenberg introduced the idea of self-adaptation of mutation distributions in evolution strategies.<ref>Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart.</ref> 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 evolution 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.<ref name=":2" /> 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.<ref name=":2" /> 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.<ref>Template:Cite book</ref> This is for non-convex objective functions with sets that include bounded lower levels of non-zero measurements. A study by Rudolph suggests that self-adaption mechanisms among elitist evolution strategies do resemble the 1/5-success rule, and could very well get caught by a local optimum that include a positive probability.<ref name=":2" />
Panmictic populationsEdit
Most EAs use unstructured or panmictic populations where basically every individual in the population is eligible for mate selection based on fitness.<ref>Template:Citation</ref><ref>Template:Cite journal</ref> Thus, The genetic information of an only slightly better individual can spread in a population within a few generations, provided that no better other offspring is produced during this time. Especially in comparatively small populations, this can quickly lead to a loss of genotypic diversity and thus to premature convergence.<ref name="Leu97" /> A well-known countermeasure is to switch to alternative population models which introduce substructures into the population<ref name=":0">Template:Cite book</ref><ref>Template:Cite thesis</ref> that preserve genotypic diversity over a longer period of time and thus counteract the tendency towards premature convergence. This has been shown for various EAs such as genetic algorithms,<ref name=":0" /> the evolution strategy,<ref>Template:Citation</ref> other EAs<ref name=":3">Template:Cite journal</ref> or memetic algorithms.<ref name=":3" /><ref>Template:Cite journal</ref>