Selektion (evolutionärer Algorithmus) - LinkFang.de





Selektion (evolutionärer Algorithmus)


Bei 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 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 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. Je höher der Selektionsdruck ist, desto schneller konvergiert eine Population gegen eine bestimmte Lösung und der Suchraum wird nicht ausreichend erkundet. 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, es haben sich für die konkreten Typen evolutionärer Algorithmen jeweils spezielle Konzepte etabliert.

Häufige Methoden

Bestenselektion

Die einfachste Methode, [math]n[/math] Individuen aus einer Population von Lösungskandidaten auszuwählen, ist die Population nach Fitness zu sortieren und die ersten [math]n[/math] Individuen zu übernehmen. Im Falle der Umweltselektion wird unterschieden zwischen der Berücksichtung von ausschließlich Nachfahren (Kommaselektion: [math]\mu , \lambda [/math]) oder Eltern und Nachfahren (Plusselektion: [math]\mu + \lambda [/math])[1].

Fitnessproportionale Selektion

Die ursprünglich von John H. Holland für genetischen Algorithmen vorgeschlagene Methode der Umweltselektion, ist die Fitnessproportionale Selektion. 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 Roulettekessels 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[2], 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 da. Hier werden [math]n[/math] ä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[3].

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ä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[4].

Rangselektion

Im Fall der Rangselektion 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.

Einzelnachweise

  1. Karsten Weicker:Evolutionäre Algorithmen, Seite 70.
  2. Robert Ghanea-Hercock:Applied Evolutionary Algorithms in Java, Seite 37.
  3. Hüseyin Bostanci: Clusterbasierte Datenanalyse auf Grundlage genetischer Algorithmen in SAP-BI, Seite 26.
  4. Xinjie Yu, Mitsuo Gen: Introduction to Evolutionary Algorithms, Seite 74.

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Selektion (evolutionärer Algorithmus) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.