Schematheorem

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.^[1]

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 ${\displaystyle \#101\#}$ die folgende Menge von Bitketten: ${\displaystyle \{01010,01011,11011,11010\}}$.

Das Schematheorem berechnet nun den Erwartungswert dafür, dass ein gewisses Schema ${\displaystyle H}$ von einer Generation zur nächsten „überlebt“. Hierzu werden die drei zentralen Schritte eines Genetischen Algorithmus untersucht:

• Selektion
• Crossover (Rekombination)
• Mutation

Es wird eine Population bestehend aus ${\displaystyle N}$ binären Genomen der Länge ${\displaystyle l}$ zu einem Zeitpunkt ${\displaystyle t}$ betrachtet. Die verwendete Fitnessfunktion ${\displaystyle f}$ sei normiert und für alle Bitketten der Länge ${\displaystyle l}$ definiert.

Im Zuge der Herleitung werden folgende Definitionen verwendet:

${\displaystyle o(H,t)}$

Anzahl der Genome zum Zeitpunkt ${\displaystyle t}$, die das Schema ${\displaystyle H}$ enthalten.

${\displaystyle d(H)}$

Durchmesser des Schemas ${\displaystyle H}$, definiert als Länge der kürzesten Teilkette, die noch alle festen Bits des Schemas enthält, z. B ${\displaystyle d(\#0101\#\#1\#\#)=7}$.

${\displaystyle b(H)}$

Anzahl der festen Bits in ${\displaystyle H}$, z. B. ${\displaystyle b(\#\#0\#\#11\#)=3}$

Da die Fitness normiert ist, gilt für die Wahrscheinlichkeit ${\displaystyle p}$, dass eine bestimmte Elternkette ${\displaystyle H_{i}}$ aus einer Population ausgewählt wird: ${\displaystyle p(H_{i})=f(H_{i})}$

Seien nun ohne Einschränkung ${\displaystyle H_{1},\dotsc ,H_{o(H,t)}}$ alle diejenigen Bitketten der Population zur Zeit ${\displaystyle t}$, die das Schema ${\displaystyle H}$ enthalten.

Die Fitness des Schemas ${\displaystyle H}$ wird dann definiert als Durchschnitt der Fitness aller Individuen: ${\displaystyle f(H)={\frac {f(H_{1})+\dotsc +f(H_{o(H,t)})}{o(H,t)}}}$.

Die Wahrscheinlichkeit, dass eine Kette ausgewählt wird, die ${\displaystyle H}$ enthält, ist somit: ${\displaystyle P_{Sel}=p(H_{1})+\dotsc +p(H_{o(H,t)})=o(H,t)f(H).}$

Für die Wahrscheinlichkeit, dass zwei Elternketten, die beide ${\displaystyle H}$ enthalten, ausgewählt werden, gilt: ${\displaystyle P_{2}={P_{Sel}}^{2}}$.

Beim 1-Point-Rekombination wird zunächst ein Trennpunkt zwischen den Bitstellen 1 und l-1 gewählt. Falls beide Elternteile ${\displaystyle H}$ enthalten, so enthält auch die Tochterkette dieses Schema. Enthält nur eine Elternkette das Schema, so wird ${\displaystyle H}$ 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: ${\displaystyle {\overline {P_{Cut}}}=1-{\frac {d(H)-1}{l-1}}.}$

Damit gilt für die Wahrscheinlichkeit ${\displaystyle W}$, dass beim Crossover das Schema ${\displaystyle H}$ weitergegeben wird: ${\displaystyle W\geq P_{2}+{\frac {1}{2}}P_{1}{\overline {P_{Cut}}}.}$

Falls beim Crossover das Schema ${\displaystyle H}$ 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 ${\displaystyle P_{Cut}}$, die Wahrscheinlichkeit, dass das Schema durchtrennt wird, steigt.

Sei ${\displaystyle p}$ die Mutationswahrscheinlichkeit, das heißt, jedes Bit der neuen Kette wird mit der Wahrscheinlichkeit ${\displaystyle p}$ negiert. Dies bedeutet, dass das Schema ${\displaystyle H}$ mit ${\displaystyle b(H)}$ festen Bits mit der Wahrscheinlichkeit ${\displaystyle {\overline {P_{Mut}}}=(1-p)^{b(H)}}$ erhalten bleibt.

Wird dieser Effekt berücksichtigt, so ergibt sich für die Wahrscheinlichkeit ${\displaystyle W'}$, dass eine durch die Operatoren Crossover und Mutation erzeugte Kette das Schema ${\displaystyle H}$ enthält:

${\displaystyle W'=W{\overline {P_{Mut}}}}$

${\displaystyle W'\geq \left(P_{2}+{\frac {1}{2}}P_{1}{\overline {P_{Cut}}}\right){\overline {P_{Mut}}}}$

${\displaystyle W'\geq \left(P_{Sel}^{2}+P_{Sel}\left(1-P_{Sel}\right)\left(1-{\frac {d(H)-1}{l-1}}\right)\right)(1-p)^{b(H)}\,.}$

Mit ${\displaystyle P_{Sel}=o(H,t)f(H)}$.

Werden also insgesamt ${\displaystyle N}$ neue Ketten erzeugt, so gilt für den Erwartungswert der Anzahl der Ketten, die das Schema ${\displaystyle H}$ zum Zeitpunkt ${\displaystyle t+1}$ enthalten: ${\displaystyle \langle o(H,t+1)\rangle =NW'}$

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 ${\displaystyle o(H,t)}$. 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 ${\displaystyle {\overline {P_{Mut}}}=(1-p)^{b(H)}}$ Beachtung. Eine hohe Mutationsrate ${\displaystyle p}$ 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 ${\displaystyle p}$ kann also die Suchaktivität des Algorithmus gesteuert werden.

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

1. ↑ 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.