Genetischer Operator

Als genetischer Operator werden Operatoren bezeichnet, mit denen evolutionäre Algorithmen (EA) arbeiten. Mit EAs werden Lösungen für Optimierungsprobleme mit Prinzipien der natürlichen Evolution gesucht. Die Mechanismen, mit denen dabei einzelne Lösungskandidaten verändert werden, heißen genetische Operatoren. In der Literatur werden Selektionsmechanismen oft auch zu diesen gezählt, obwohl sie im eigentlichen Sinn kein genetisches Material verändern, sondern Individuen aus einer Population auswählen. Genetische Operatoren dienen dazu, genetische Vielfalt zu erzeugen und zu erhalten (Mutation<ref name="sel" details="Variation Operators (Mutation and Recombination), S. 31–33" /> und die seltener genutzte Transformation<ref name="nimic" />), bestehende Lösungen (auch als Chromosomen bezeichnet) zu neuen Lösungen zu kombinieren (Rekombination<ref name="sel" details="Variation Operators (Mutation and Recombination), S. 31–33" />) und Lösungen auszuwählen (Selektion)<ref name="sel" details="Parent Selection Mechanism, S. 31" /><ref name="sel" details="Survivor Selection Mechanism (Replacement), S. 33–34" />.

Im weiten Sinne können deshalb unter genetischen Operatoren zusammengefasst werden:<ref name="ea" />

• Rekombination, die zufällige Kombination mehrerer Lösungen zu einer neuen und
• Mutation, die zufällige und ungerichtete Veränderung eines Lösungskandidaten,
• Transformation, die zufällige Veränderung eines Lösungskandidaten durch Chromosomenfragmente
• Selektion, die Auswahl von Lösungen aus der Population, entweder zur Rekombination oder zur Bestimmung der neuen Generation. Die Selektion basiert in der Regel auf der Fitness der Individuen.

Wie auch das allgemeine Funktionsprinzip der EAs haben alle genetischen Operatoren biologische Vorbilder: Mutation, Transformation, Rekombination und Selektion.

Neben den allgemein anwendbaren genetischen Operatoren gibt es auch solche, die auf eine Anwendung oder ein Anwendungsfeld zugeschnitten sind. So werden beispielsweise bei kombinatorischen Aufgabenstellungen häufig Mutations- oder Rekombinationsoperatoren verwendet, die an die Veränderung oder Mischung von Permutationen angepasst sind.

Effekte der Operatoren und ihres Zusammenwirkens

Zwar trägt jeder Operator für sich dazu bei, die vom EA erzeugten Lösungen zu verbessern, doch erst ihr Zusammenwirken versetzt den Algorithmus in die Lage, erfolgreich eine gute Lösung zu finden<ref name="sel" details="Representation, Mutation, and Recombination, S. 49–78" />. Wird der Selektionsoperator allein verwendet, führt dies dazu, dass die Lösungspopulation in steigendem Maße mit Kopien der besten Lösung der Population gefüllt wird. Werden der Selektions- und der Rekombinationsoperator ohne die Mutation eingesetzt, konvergiert der Algorithmus tendenziell zu einem lokalen Minimum, d. h. zu einer guten, aber suboptimalen Lösung des Problems. Die alleinige Verwendung des Mutationsoperators führt zu einer zufallsbasierten Wanderung durch den Suchraum. Nur durch die gemeinsame Anwendung aller drei Operatoren wird der evolutionäre Algorithmus zu einem rauschresistenten globalen Suchalgorithmus, der gute Lösungen für das jeweilige Problem liefert.<ref>Genetic Algorithms (Memento vom 11. August 2015 im Internet Archive)</ref>

Einzelnachweise

<references> <ref name="ea"></ref> <ref name="sel"></ref> <ref name="nimic"></ref> </references>