imported>Wilfried Jakob am 3. Februar 2026 um 14:19 Uhr

2026-02-03T14:19:27Z

Neue Seite

Bei [[Evolutionärer Algorithmus|evolutionären Algorithmen]] (EA) ist '''Selektion''' ein Mechanismus, mit dem Individuen aus einer Population ausgewählt werden. Im weiteren Sinne wird Selektion oft zu den [[Genetischer Operator|genetischen Operatoren]] gezählt, obwohl Selektion bei EA nicht auf Gen-, sondern auf Individuenebene operiert. Evolutionäre Algorithmen suchen eine Lösung für ein [[Optimierungsproblem]] mit Prinzipien der natürlichen [[Evolution]]. Selektion wird benutzt, um Lösungskandidaten (Individuen) für [[Rekombination (evolutionärer Algorithmus)|Rekombination]] auszuwählen (''Elternselektion'') und um die nächste Generation festzulegen (''Umweltselektion''). Dazu wird die Qualität der Lösungskandidaten herangezogen, die ihnen durch eine [[Fitnessfunktion]] zugewiesen wird. Das biologische Vorbild ist die [[natürliche Selektion]]. Die aufgeführten Verfahren unterscheiden sich vor allem im [[Selektionsdruck]]<ref>{{Literatur |Autor=Thomas Bäck |Titel=Selective Pressure in Evolutionary Algorithms: a Characterization of Selection Mechanisms |Sammelwerk=Proceedings of the First IEEE Conference on Evolutionary Computation (CEC) |Verlag=IEEE |Ort=Orlando, FL, USA |Datum=1994 |ISBN=978-0-7803-1899-1 |Seiten=57–62 |DOI=10.1109/ICEC.1994.350042}}</ref><ref>{{Literatur |Autor=David E. Goldberg, Kalyanmoy Deb |Titel=A Comparative Analysis of Selection Schemes Used in Genetic Algorithms |Sammelwerk=Foundations of Genetic Algorithms |Band=1 |Verlag=Elsevier |Datum=1991 |ISBN=978-0-08-050684-5 |Seiten=69–93 |DOI=10.1016/b978-0-08-050684-5.50008-2}}</ref>, der bei der Rangselektion sogar durch einen Strategieparameter eingestellt werden kann. Je höher der Selektionsdruck ist, desto schneller [[Folgenkonvergenz|konvergiert]] eine Population gegen eine bestimmte Lösung und der [[Genetische Repräsentation#Unterscheidung Such- und Problemraum|Suchraum]] wird möglicherweise nicht ausreichend erkundet. Diesem Phänomen der ''[[Vorzeitige Konvergenz|vorzeitigen Konvergenz]]'' kann durch eine geeignete [[Populationsmodell (evolutionärer Algorithmus)#Nachbarschaftsmodelle oder zelluläre evolutionäre Algorithmen|Strukturierung der Population]] entgegengewirkt werden. Zwischen dem verwendeten [[Populationsmodell (evolutionärer Algorithmus)|Populationsmodell]] und einem geeigneten Selektionsdruck herrscht ein enger Zusammenhang. Bei zu niedrigem Druck konvergiert die Population auch nach langer [[Rechenzeit]] nicht.

Jedes Verfahren kann prinzipiell sowohl für Eltern- als auch Umweltselektion eingesetzt werden und es haben sich für die konkreten [[Evolutionärer Algorithmus|Typen evolutionärer Algorithmen]] jeweils spezielle Konzepte etabliert. Bei den [[Memetischer Algorithmus|memetischen Algorithmen]], einer Erweiterung der EAs, findet eine Selektion auch bei der [[Memetischer Algorithmus#Wie werden die Nachkommen für die lokale Verbesserung ausgewählt?|Auswahl derjenigen Nachkommen]] statt, die mit Hilfe eines Mems (z. B. einer [[Heuristik]]) verbessert werden sollen.

== Häufige Methoden ==
Grundsätzlich wird bei der Umweltselektion zwischen ''elitären'' und ''nicht elitären'' Selektionsformen unterschieden. Bei einem elitären EAs gewährleistet der verwendete Selektionsmechanismus, dass das beste Individuum immer überlebt, auch über mehrere Generationen hinweg.<ref>{{Literatur |Autor=Karsten Weicker |Titel=Evolutionäre Algorithmen |Verlag=Springer Fachmedien |Ort=Wiesbaden |Datum=2015 |ISBN=978-3-658-09957-2 |DOI=10.1007/978-3-658-09958-9 |Seiten=68–71, Varianten der Umweltselektion |Fundstelle=Definition 3.12, S. 69}}</ref> Insofern weichen elitäre EAs vom biologischen Vorbild ab. Der Selektionsdruck eines elitären EAs ist im Allgemeinen höher als bei nicht-elitären Varianten des gleichen Selektionsverfahrens.

=== Bestenselektion ===
Die einfachste Methode, <math>\mu</math> Individuen aus einer Population von Lösungskandidaten auszuwählen, ist die Population nach der Fitness zu sortieren und die ersten <math>\mu</math> Individuen zu übernehmen. Im Falle der Umweltselektion wird unterschieden zwischen der Berücksichtigung von ausschließlich <math>\lambda</math> Nachfahren (''Kommaselektion'': <math>\mu , \lambda </math>) oder <math>\mu</math> Eltern und <math>\lambda</math> Nachfahren (''Plusselektion'': <math>\mu + \lambda </math>), um die <math>\mu</math> Individuen der Nachfolgegeneration zu bestimmen. Notation und Vorgehensweise gehen auf die [[Evolutionärer Algorithmus#Evolutionsstrategien (ES)|Evolutionstrategie]] zurück.<ref>{{Literatur |Autor=Hans-Paul Schwefel |Titel=Evolution and Optimum Seeking |Verlag=John Wiley & Sons |Ort=New York |Datum=1995 |ISBN=0-471-57148-2 |Online=https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking}}</ref><ref>{{Literatur |Autor=Ingo Rechenberg |Titel=Evolutionsstrategie; Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. |TitelErg=Dissertation |Verlag=Frommann-Holzboog |Ort=Stuttgart-Bad Cannstatt |Datum=1973 |ISBN=3-7728-0373-3 }}</ref> Da die Plusselektion gewährleistet, dass das beste Individuum immer überlebt, sind die darauf basierenden EAs elitär.
[[Datei:13-02-27-spielbank-wiesbaden-by-RalfR-065.jpg|200px|mini|Fitness-proportionale Selektion entspricht dem Werfen von Roulettekugeln in einen Kessel mit unterschiedlich großen Kammern.]]
[[Datei:Statistically Uniform.png|mini|Auswahlpunkte mit gleichen Abständen beim stochastischen universellen Sampling]]

=== Fitnessproportionale Selektion ===
Die ursprünglich von [[John H. Holland]] für [[Genetischer Algorithmus|genetischen Algorithmen]] vorgeschlagene Methode der Umweltselektion, ist die Fitnessproportionale Selektion<ref>{{Literatur |Autor=John H. Holland |Titel=Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence |TitelErg=PhD thesis |Verlag=University of Michigan Press |Ort=Ann Arbor |Datum=1975 |ISBN=0-472-08460-7}}</ref>. Die Selektion von <math>n</math> Individuen entspricht dabei dem <math>n</math>-maligen Wurf einer Kugel beim [[Roulette]], wobei jedem Individuum ein Anteil des [[Roulettekessel]]s zugewiesen wird, der seiner Fitness entspricht. Zwar haben auch schlechtere Lösungskandidaten auf diese Weise eine Chance, selektiert zu werden, jedoch dominieren am Anfang der Optimierung oft wenige Kandidaten mit höherer Qualität den gesamten Auswahlprozess<ref>{{Literatur |Autor=Robert Ghanea-Hercock |Titel=Applied Evolutionary Algorithms in Java |Verlag=Springer New York |Ort=New York, NY |Datum=2003 |ISBN=978-1-4684-9526-3 |Seiten=37 |DOI=10.1007/978-0-387-21615-7}}</ref>, da deutlich überdurchschnittliche Individuen von der Tatsache profitieren, dass jede Auswahl einzeln getroffen wird und bei jeder Auswahl eine hohe Wahrscheinlichkeit besteht, dass sie ausgewählt werden. Dahingehend stellt das '''stochastische universelle Sampling''' eine Verbesserung dar. Hier werden <math>n</math> [[äquidistanz|äquidistante]] Kugeln auf einmal geworfen. Zwar können Individuen auch hier mehrfach ausgewählt werden, jedoch wirkt stochastisches universelles Sampling im Vergleich zur fitnessproportionale Selektion diversitätserhaltend<ref>{{Literatur |Autor=Hüseyin Bostanci |Titel=Clusterbasierte Datenanalyse auf Grundlage genetischer Algorithmen in SAP-BI: Ein Verfahren zur selbständigen Ermittlung der optimalen Anzahl Cluster. |Verlag=Diplomica Verlag |Ort=Hamburg |Datum=2011 |ISBN=978-3-8428-0426-5 |Seiten=26}}</ref>.

=== Turnierselektion ===
Bei der Turnierselektion werden wiederholt <math>k</math> Individuen aus der Population ausgewählt. Ihre Fitnesswerte werden verglichen und das beste Individuum gewinnt (das Turnier). Der Prozess wird <math>n</math>-mal ausgeführt. Vorteile sind die leichte Umsetzbarkeit, die geringe [[Komplexitätstheorie|Komplexität]] und die Tatsache, dass nicht Fitnesswerte zu jedem Individuum vorliegen müssen, sondern nur zu den, die an den Turnieren teilnehmen. Problematisch ist, dass die besten Individuen nicht unbedingt selektiert werden müssen<ref>{{Literatur |Autor=Xinjie Yu, Mitsuo Gen |Titel=Introduction to Evolutionary Algorithms |Verlag=Springer |Ort=London |Datum=2010 |ISBN=978-1-84996-128-8 |Seiten=74 |DOI=10.1007/978-1-84996-129-5}}</ref>.

=== Rangselektion ===
Im Fall der Rangselektion ({{enS|ranking}}) hängt die Auswahlwahrscheinlichkeit nicht direkt von der Fitness, sondern vom Fitnessrang eines Individuums innerhalb der Population ab. Dadurch relativieren sich große Fitnessunterschiede, außerdem müssen nicht die genauen Fitnesswerte selbst vorliegen, sondern nur eine Sortierung der Individuen nach Qualität.

Am häufigsten wird das auf Baker zurückgehende ''lineare Ranking''<ref>{{Literatur |Autor=James E. Baker |Hrsg=John J. Grefenstette |Titel=Adaptive Selection Methods for Genetic Algorithms. |Sammelwerk=Conf. Proc. of the 1st Int. Conf. on Genetic Algorithms and Their Applications (ICGA) |Verlag=L. Erlbaum Associates |Ort=Hillsdale, NJ |Datum=1985 |ISBN=0-8058-0426-9 |Seiten=101-111}}</ref><ref>{{Literatur |Autor=James E. Baker |Hrsg=John J. Grefenstette |Titel=Reducing Bias and Inefficiency in the Selection Algorithm |Sammelwerk=Conf. Proc. of the 2nd Int. Conf. on Genetic Algorithms and Their Applications (ICGA) |Verlag=L. Erlbaum Associates |Ort=Hillsdale, New. Jersey |Datum=1987 |ISBN=0-8058-0158-8 |Seiten=14-21}}</ref> verwendet.<ref>{{Literatur |Autor=Darrell Whitley |Hrsg=J. David Schaffer |Titel=The GENITOR Algorithm and Selective Pressure: Why Rank-Based Allocation of Reproductive Trials is Best |Sammelwerk=Conf. Proc. of the 3rd Int. Conf. on Genetic Algorithms and Their Applications (ICGA) |Verlag=Morgan Kaufmann Publishers |Ort=San Francisco, CA |Datum=1989 |ISBN=1-55860-066-3 |Seiten=116–121}}</ref><ref>{{Literatur |Autor=Martina Gorges-Schleuter |Titel=Genetic Algorithms and Population Structures - A Massively Parallel Algorithm |TitelErg=Dissertation |Verlag=Universität Dortmund, Fakultät für Informatik |Datum=1990}}</ref><ref>{{Literatur |Autor=Christian Blume, Wilfried Jakob |Titel=GLEAM - General Learning Evolutionary Algorithm and Method: ein Evolutionärer Algorithmus und seine Anwendungen |Sammelwerk=Schriftenreihe des Instituts für Angewandte Informatik – Automatisierungstechnik. |Nummer=32 |Verlag=KIT Scientific Publishing |Ort=Karlsruhe |Datum=2009 |ISBN=978-3-86644-436-2 |DOI=10.5445/ksp/1000013553}}</ref><ref>{{Literatur |Autor=Hartmut Pohlheim |Titel=Evolutionäre Algorithmen: Verfahren, Operatoren und Hinweise für die Praxis |Verlag=Springer |Ort=Berlin |Datum=1999 |ISBN=978-3-540-66413-0}}</ref> Es erlaubt die Einstellung des Selektionsdrucks durch den Parameter <math>sp</math> (selective pressure), der Werte zwischen 1,0 (kein Selektionsdruck) und 2,0 (hoher Selektionsdruck) annehmen kann. Die Wahrscheinlichkeit <math>P </math> für <math>n</math> Rangpositionen <math>R_i</math> ergibt sich nach folgender Formel:
:<math>P(R_i) =\frac{1}{n}\Bigl(sp-(2sp-2)\frac{i-1}{n-1}\Bigr) \quad \quad 1\leq i \leq n ,\quad 1 \leq sp \leq 2 </math>
wobei gilt:
:<math>P(R_i) \ge 0, \quad \sum_{i=1}^nP(R_i)=1 </math>

[[Datei:Beispiel fuer lineares Ranking.svg|mini|Beispiel für lineares Ranking von fünf Individuen und drei Werten des Selektionsdruckparameters ''sp''.]]
Ein Beispiel für die rangbasierte Selektion von fünf Individuen mag die Wirkung von <math>sp</math> verdeutlichen. Nebenstehendes Bild zeigt die Wahrscheinlichkeiten der Rangpositionen für die beiden Grenzwerte und einen mittleren Wert von <math>sp</math>. Bei einem Wert von 1,0 besteht kein Selektionsdruck mehr (blaue Linie), bei 1,4 ein moderater (grün) und bei 2,0 der maximal mit linearem Ranking einstellbare (rot). Man beachte aber, dass die Auswahlwahrscheinlichkeit für das beste Individuum bei fitnessproportionaler Selektion und hinreichend großen Fitnessunterschieden größer sein kann als bei rangbasierter. Damit dämpft die rangbasierte Selektion den Selektionsdruck bei größeren Fitnessunterschieden auch noch bei einem Wert von 2,0 für <math>sp</math> gegenüber der fitnessproportionalen.

Ein Vorteil der rangbasierten Selektion kann neben dem einstellbaren Selektionsdruck auch darin gesehen werden, dass sie auch schlechteren Individuen eine Chance zur Vermehrung und damit zur Verbesserung gibt. Dies kann insbesondere bei Anwendungen mit Restriktionen hilfreich sein, da es die [[Fitnessfunktion|Überwindung einer Restriktion in mehreren Zwischenschritten]] erleichtert, also über eine Abfolge von mehreren aufgrund von Restriktionsverletzungen schlecht bewerteten Individuen.

Turnier- und Rangselektion werden häufig für die Elternselektion verwendet.

== Literatur ==
* [[Hartmut Pohlheim]]: ''Evolutionäre Algorithmen. Verfahren, Operatoren und Hinweise für die Praxis.'' Springer, Berlin 1999, ISBN 3-540-66413-0.
* [[Karsten Weicker]]: ''Evolutionäre Algorithmen.'' Teubner, Stuttgart 2002, ISBN 3-519-00362-7.
* {{Literatur |Autor=A. E. Eiben, J. E. Smith |Titel=Introduction to Evolutionary Computing |Reihe=Natural Computing Series |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2015 |ISBN=978-3-662-44873-1 |DOI=10.1007/978-3-662-44874-8}}
* [[Hans-Paul Schwefel]]: ''[https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking Evolution and Optimum Seeking]''. Wiley & Sons, New York 1995, ISBN 0-471-57148-2.

== Einzelnachweise ==
<references />

[[Kategorie:Evolutionärer Algorithmus]]

Selektion (evolutionärer Algorithmus) - Versionsgeschichte

imported>Wilfried Jakob am 3. Februar 2026 um 14:19 Uhr