Das Schematheorem nach John H. Holland behandelt das Konvergenzverhalten genetischer Algorithmen. Das Theorem beweist, dass sich Individuen mit überdurchschnittlicher Fitness mit höherer Wahrscheinlichkeit durchsetzen.
Herleitung Bearbeiten
Das Schematheorem betrachtet das Genom eines Individuums, in der Regel also eine Bitkette, die Werte kodiert. Zunächst muss der Begriff Schema erläutert werden: Ein Schema ist ein Bitmuster, das eine Menge von Bitketten repräsentiert. Ein Schema besteht aus den Zeichen 0 1 oder #. Das Zeichen # fungiert als Platzhalter für eine 0 oder 1.
Beispielsweise repräsentiert das Schema die folgende Menge von Bitketten: .
Das Schematheorem berechnet nun den Erwartungswert dafür, dass ein gewisses Schema von einer Generation zur nächsten „überlebt“. Hierzu werden die drei zentralen Schritte eines Genetischen Algorithmus untersucht:
Es wird eine Population bestehend aus binären Genomen der Länge zu einem Zeitpunkt betrachtet. Die verwendete Fitnessfunktion sei normiert und für alle Bitketten der Länge definiert.
Im Zuge der Herleitung werden folgende Definitionen verwendet:
Selektion Bearbeiten
Da die Fitness normiert ist, gilt für die Wahrscheinlichkeit , dass eine bestimmte Elternkette aus einer Population ausgewählt wird:
Seien nun ohne Einschränkung alle diejenigen Bitketten der Population zur Zeit , die das Schema enthalten.
Die Fitness des Schemas wird dann definiert als Durchschnitt der Fitness aller Individuen: .
Die Wahrscheinlichkeit, dass eine Kette ausgewählt wird, die enthält, ist somit:
Für die Wahrscheinlichkeit, dass zwei Elternketten, die beide enthalten, ausgewählt werden, gilt: .
Rekombination (Crossover) Bearbeiten
Beim 1-Point-Rekombination wird zunächst ein Trennpunkt zwischen den Bitstellen 1 und l-1 gewählt. Falls beide Elternteile enthalten, so enthält auch die Tochterkette dieses Schema. Enthält nur eine Elternkette das Schema, so wird im Mittel in der Hälfte der Fälle weitergegeben, falls es nicht beim Crossover selbst durchtrennt wird.
Die Wahrscheinlichkeit, dass es nicht durchtrennt wird, ist:
Damit gilt für die Wahrscheinlichkeit , dass beim Crossover das Schema weitergegeben wird:
Falls beim Crossover das Schema durchtrennt wird, besteht die Möglichkeit, dass das fehlende Teilstück an passender Stelle in der anderen Elternkette enthalten ist. Daher rührt die Ungleichung. Falls 2-Point-Crossover durchgeführt wird, hat das lediglich Auswirkungen auf , die Wahrscheinlichkeit, dass das Schema durchtrennt wird, steigt.
Mutation Bearbeiten
Sei die Mutationswahrscheinlichkeit, das heißt, jedes Bit der neuen Kette wird mit der Wahrscheinlichkeit negiert. Dies bedeutet, dass das Schema mit festen Bits mit der Wahrscheinlichkeit erhalten bleibt.
Wird dieser Effekt berücksichtigt, so ergibt sich für die Wahrscheinlichkeit , dass eine durch die Operatoren Crossover und Mutation erzeugte Kette das Schema enthält:
Mit .
Fazit Bearbeiten
Werden also insgesamt neue Ketten erzeugt, so gilt für den Erwartungswert der Anzahl der Ketten, die das Schema zum Zeitpunkt enthalten:
Die letzten beiden Formeln zeigen, dass Schemata mit überdurchschnittlicher Fitness und kleinem Durchmesser sich mit großer Wahrscheinlichkeit durchsetzen. Die Reproduktionswahrscheinlichkeit steigt aber auch mit der Häufigkeit eines Schemas . Das heißt, ein durchschnittliches Schema kann sich innerhalb einer Population durchsetzen, wenn es oft genug vorkommt. Dieser Effekt wird genetisches Driften genannt.
Weiterhin verdient der Faktor Beachtung. Eine hohe Mutationsrate bewirkt eine verstärkte Destruktion erfolgreicher Muster. Andererseits ist eine gewisse Mutationshäufigkeit nötig, um den Suchraum möglichst umfassend zu durchsuchen. Durch Justierung von kann also die Suchaktivität des Algorithmus gesteuert werden.
Literatur Bearbeiten
- David White: An Overview of Schema Theory. In: Graduate Journal of Mathematics. Band 3, Nr. 2, 2018, S. 37–59, doi:10.48550/arXiv.1401.2651.
Einzelnachweise Bearbeiten
- John H. Holland: Adaptation in natural and artificial systems : an introductory analysis with applications to biology, control, and artificial intelligence. 1st MIT Press ed Auflage. MIT Press, Cambridge, Mass. 1992, ISBN 0-585-03844-9.