Genom (genetischer Algorithmus)

aus Wikipedia, der freien Enzyklopädie

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 1 Genomtypen 2 Schema 2.1 Beispiel 2.2 Idee 2.3 Fitness

[Bearbeiten] 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

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.