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 und die seltener genutzte Transformation), bestehende Lösungen (auch als Chromosomen bezeichnet) zu neuen Lösungen zu kombinieren (Rekombination) und Lösungen auszuwählen (Selektion).

Im weiten Sinne können deshalb unter genetischen Operatoren zusammengefasst werden:

• 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. 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.

Einzelnachweise

1. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, doi:10.1007/978-3-662-44874-8 (englisch). 
   1. 1 2 Variation Operators (Mutation and Recombination), S. 31–33
   2. ↑ Parent Selection Mechanism, S. 31
   3. ↑ Survivor Selection Mechanism (Replacement), S. 33–34
   4. ↑ Representation, Mutation, and Recombination, S. 49–78
2. ↑ Brian T. Luke: Genetic Algorithms and Beyond. In: Riccardo Leardi (Hrsg.): Nature-inspired Methods in Chemometrics: Genetic Algorithms and Artificial Neural Networks (= Data Handling in Science and Technology. Band 23). 1. Auflage. Elsevier Science, 2003, ISBN 978-0-444-51350-2, S. 38 (402 S.). 
3. ↑ Hartmut Pohlheim: Evolutionäre Algorithmen. Springer, Berlin, Heidelberg 2000, ISBN 978-3-642-63052-1, Grundlegende Verfahren und Operatoren, S. 13–59, doi:10.1007/978-3-642-57137-4. 
4. ↑ Genetic Algorithms (Memento vom 11. August 2015 im Internet Archive)