Editing Evolutionary algorithm (section)

=== Convergence ===
For EAs in which, in addition to the offspring, at least the best individual of the parent generation is used to form the subsequent generation (so-called elitist EAs), there is a general proof of [[Convergence (logic)|convergence]] under the condition that an [[optimum]] exists. [[Without loss of generality]], a maximum search is assumed for the proof:

From the property of elitist offspring acceptance and the existence of the optimum it follows that per generation <math>k</math> an improvement of the fitness <math>F</math> of the respective best individual <math>x'</math> will occur with a probability <math>P > 0</math>. Thus:
:<math>F(x'_1) \leq F(x'_2) \leq F(x'_3) \leq \cdots \leq F(x'_k) \leq \cdots</math>
I.e., the fitness values represent a [[Monotonic function|monotonically]] non-decreasing [[sequence]], which is [[bounded set|bounded]] due to the existence of the optimum. From this follows the convergence of the sequence against the optimum.

Since the proof makes no statement about the speed of convergence, it is of little help in practical applications of EAs. But it does justify the recommendation to use elitist EAs. However, when using the usual [[Panmixia|panmictic]] [[Population model (evolutionary algorithm)|population model]], elitist EAs tend to [[Premature convergence|converge prematurely]] more than non-elitist ones.<ref>{{Cite journal |last1=Leung |first1=Yee |last2=Gao |first2=Yong |last3=Xu |first3=Zong-Ben |date=1997 |title=Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis |url=https://ieeexplore.ieee.org/document/623217 |journal=IEEE Transactions on Neural Networks |volume=8 |issue=5 |pages=1165–1176 |doi=10.1109/72.623217 |pmid=18255718 |issn=1045-9227|url-access=subscription }}</ref> In a panmictic population model, mate selection (see step 4 of the [[Evolutionary algorithm#Generic definition|generic definition]]) is such that every individual in the entire population is eligible as a mate. In [[Population model (evolutionary algorithm)|non-panmictic populations]], selection is suitably restricted, so that the dispersal speed of better individuals is reduced compared to panmictic ones. Thus, the general risk of premature convergence of elitist EAs can be significantly reduced by suitable population models that restrict mate selection.<ref>{{Citation |last=Gorges-Schleuter |first=Martina |title=A comparative study of global and local selection in evolution strategies |date=1998 |url=http://link.springer.com/10.1007/BFb0056879 |work=Parallel Problem Solving from Nature — PPSN V |series=Lecture Notes in Computer Science |volume=1498 |pages=367–377 |editor-last=Eiben |editor-first=Agoston E. |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/bfb0056879 |isbn=978-3-540-65078-2 |access-date=2022-10-21 |editor2-last=Bäck |editor2-first=Thomas |editor3-last=Schoenauer |editor3-first=Marc |editor4-last=Schwefel |editor4-first=Hans-Paul|url-access=subscription }}</ref><ref>{{Cite book |last1=Dorronsoro |first1=Bernabe |url=http://link.springer.com/10.1007/978-0-387-77610-1 |title=Cellular Genetic Algorithms |last2=Alba |first2=Enrique |date=2008 |publisher=Springer US |isbn=978-0-387-77609-5 |series=Operations Research/Computer Science Interfaces Series |volume=42 |location=Boston, MA |doi=10.1007/978-0-387-77610-1}}</ref>