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 die selben 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.
- ZenoServer 2.4.26
- Zenodot
- Digitale Bibliothek
- Downloadshop
- Retrodigitalisierung
- Nutzungsbedingungen
- Impressum