Schemasatz

Der Schemasatz nach John H. Holland behandelt das Konvergenzverhalten genetischer Algorithmen. Der Satz beweist, dass sich Individuen mit überdurchschnittlicher Fitness mit höherer Wahrscheinlichkeit durchsetzen.

Herleitung

Der Schemasatz 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 bezeichnet das Schema #101# die folgende Menge von Bitketten:

01010, 01011, 11011, 11010.

Der Schemasatz 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 Fitness-Funktion f sei normiert und für alle Bitketten der Länge l definiert.

Im Zuge der Herleitung werden folgende Schreibweisen verwendet:

• o(H,t)

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

• d(H)

     Der Durchmesser des Schemas H, wird 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)

     Steht für die 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₁,..,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 durch: $f(H) = \frac{f(H_1)+ .. + 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₁) + .. + 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-Crossover 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 $\overline{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.