Schematheorem
# 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.

## Herleitung

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

Das Schematheorem berechnet nun den Erwartungswert dafür, dass ein gewisses Schema $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 $N$ binären Genomen der Länge $l$ zu einem Zeitpunkt $t$ betrachtet. Die verwendete Fitnessfunktion $f$ sei normiert und für alle Bitketten der Länge $l$ definiert.

Im Zuge der Herleitung werden folgende Definitionen verwendet:

### $o(H,t)$

    Anzahl der Genome zum Zeitpunkt $t$, die das Schema $H$ enthalten.

### $d(H)$

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

### $b(H)$

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

### Selektion

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

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

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

Die Wahrscheinlichkeit, dass eine Kette ausgewählt wird, die $H$ enthält, ist somit: $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 $H$ enthalten, ausgewählt werden, gilt: $P_{2}={P_{Sel}}^{2}$.

### Rekombination (Crossover)

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

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

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

### Mutation

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

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

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

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

$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 $P_{Sel}=o(H,t)f(H)$.

### Fazit

Werden also insgesamt $N$ neue Ketten erzeugt, so gilt für den Erwartungswert der Anzahl der Ketten, die das Schema $H$ zum Zeitpunkt $t+1$ enthalten: $\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 $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 ${\overline {P_{Mut}}}=(1-p)^{b(H)}$ Beachtung. Eine hohe Mutationsrate $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 $p$ kann also die Suchaktivität des Algorithmus gesteuert werden.

