- Genom (genetischer Algorithmus)
-
Ein Genom ist im Kontext eines genetischen Algorithmus' diejenige Information, die Eigenschaften eines Individuums ausmacht. Damit ist ein Genom eine Datenstruktur. Es ist vom biologischen Genom inspiriert.
Inhaltsverzeichnis
Genomtypen
Nicht selten wird ein Genom einfach als Bitstring dargestellt. Es existieren jedoch auch komplexere Genom-Typen mit speziell darauf angepassten Mutations- und Rekombinations-Typen:
Genomtyp Mutationstyp Rekombinationstyp Anwendung des Genomtyps Bitstring Mutation von Bitstrings Rekombination von Bitstrings allgemein Gray-Code Mutation von Bitstrings Rekombination von Bitstrings Zahlen binäre Zahl Mutation von binären Zahlen Rekombination von binären Zahlen Zahlen zusammengesetzte Daten Mutation von zusammengesetzten Daten Rekombination von zusammengesetzten Daten zusammengesetzte Daten (Records, Structs) Permutation Mutation von Permutationen Rekombination von Permutationen Reihenfolgeproblem Pfad Mutation von Pfaden Rekombination von Pfaden Routing-Problem Baum Mutation von Bäumen Rekombination von Bäumen Ausdrücke, Regelwerke Schema
Ein Schema in diesem Kontext ist ein regulärer Ausdruck auf Genome, also eine kompakte geschriebene Vorschrift, um zu entscheiden, ob ein Genom zu einer bestimmten Menge von Genomen gehört oder nicht.
Beispiel
Wenn ein Genom als Bitstring der Länge 5 dargestellt wird, ist ein Schema für solche Genome zum Beispiel: "1*0*1", wobei '*' für egal steht. Mit einem solchen Schema sind also die Bitstrings "10001", "10011", "11001", "11011" gemeint.
Idee
Die Idee ist, dass einige Informationen im Genom weniger wichtig sind als andere. Damit gibt es für jede Kombination von wichtigen Informationen ein entsprechendes Schema. Beispielsweise werden die wichtigen Bits mit '1' oder '0' bezeichnet, die unwichtigen dagegen mit '*'. Von der Menge aller Schemata, so die Idee, gibt es nun einige, die besonders gut sind (also deren Individuen entsprechend gute Werte bei der Fitness-Funktion erzielen).
Da Mutation der unwichtigen Information nur wenig beiträgt zur Änderung der Fitness, bleiben gute Schemata im Genom-Pool einer Population erhalten, selbst wenn konkrete Genome nicht erhalten bleiben. Deswegen sind gute Schemata Attraktoren. Auch deswegen wird angenommen, dass am Ende des Laufens eines genetischen Algorithmus' einige wenige Schemata automatisch erscheinen, indem viele erfolgreiche Individuen an bestimmten Stellen ihres Genoms immer dieselben Werte zeigen.
Fitness
Die Fitness-Funktion für Schemata kann man über die Fitness-Funktion über Individuen definieren, und zwar so: Die Fitness eines Schemas ist gleich der durchschnittlichen Fitness aller des durch das Schema bezeichneten Individuen.
Wikimedia Foundation.
