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.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
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 <math>\#101\#</math> die folgende Menge von Bitketten: <math>\{01010, 01011, 11011, 11010\}</math>.
Das Schematheorem berechnet nun den Erwartungswert dafür, dass ein gewisses Schema <math>H</math> von einer Generation zur nächsten „überlebt“. Hierzu werden die drei zentralen Schritte eines Genetischen Algorithmus untersucht:
Es wird eine Population bestehend aus <math>N</math> binären Genomen der Länge <math>l</math> zu einem Zeitpunkt <math>t</math> betrachtet. Die verwendete Fitnessfunktion <math>f</math> sei normiert und für alle Bitketten der Länge <math>l</math> definiert.
Im Zuge der Herleitung werden folgende Definitionen verwendet:
- <math>o(H,t)</math>
- Anzahl der Genome zum Zeitpunkt <math>t</math>, die das Schema <math>H</math> enthalten.
- <math>d(H)</math>
- Durchmesser des Schemas <math>H</math>, definiert als Länge der kürzesten Teilkette, die noch alle festen Bits des Schemas enthält, z. B <math>d(\#0101\#\#1\#\#)=7</math>.
- <math>b(H)</math>
- Anzahl der festen Bits in <math>H</math>, z. B. <math>b(\#\#0\#\#11\#)=3</math>
Selektion
Da die Fitness normiert ist, gilt für die Wahrscheinlichkeit <math>p</math>, dass eine bestimmte Elternkette <math>H_i</math> aus einer Population ausgewählt wird: <math>p(H_i) = f(H_i)</math>
Seien nun ohne Einschränkung <math>H_1, \dotsc,H_{o(H,t)}</math> alle diejenigen Bitketten der Population zur Zeit <math>t</math>, die das Schema <math>H</math> enthalten.
Die Fitness des Schemas <math>H</math> wird dann definiert als Durchschnitt der Fitness aller Individuen: <math>f(H) = \frac{f(H_1) + \dotsc + f(H_{o(H,t)})}{o(H,t)} </math>.
Die Wahrscheinlichkeit, dass eine Kette ausgewählt wird, die <math>H</math> enthält, ist somit: <math>P_{Sel} = p(H_1) + \dotsc + p(H_{o(H,t)}) = o(H,t)f(H).</math>
Für die Wahrscheinlichkeit, dass zwei Elternketten, die beide <math>H</math> enthalten, ausgewählt werden, gilt: <math>P_2 = {P_{Sel}}^2</math>.
Rekombination (Crossover)
Beim 1-Point-Rekombination wird zunächst ein Trennpunkt zwischen den Bitstellen 1 und l-1 gewählt. Falls beide Elternteile <math>H</math> enthalten, so enthält auch die Tochterkette dieses Schema. Enthält nur eine Elternkette das Schema, so wird <math>H</math> 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: <math>\overline{P_{Cut}} = 1-\frac{d(H)-1}{l-1}.</math>
Damit gilt für die Wahrscheinlichkeit <math>W</math>, dass beim Crossover das Schema <math>H</math> weitergegeben wird: <math>W \geq P_2 + \frac{1}{2} P_1 \overline{P_{Cut}}.</math>
Falls beim Crossover das Schema <math>H</math> 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 <math>P_{Cut}</math>, die Wahrscheinlichkeit, dass das Schema durchtrennt wird, steigt.
Mutation
Sei <math>p</math> die Mutationswahrscheinlichkeit, das heißt, jedes Bit der neuen Kette wird mit der Wahrscheinlichkeit <math>p</math> negiert. Dies bedeutet, dass das Schema <math>H</math> mit <math>b(H)</math> festen Bits mit der Wahrscheinlichkeit <math>\overline{P_{Mut}} = (1-p)^{b(H)}</math> erhalten bleibt.
Wird dieser Effekt berücksichtigt, so ergibt sich für die Wahrscheinlichkeit <math>W'</math>, dass eine durch die Operatoren Crossover und Mutation erzeugte Kette das Schema <math>H</math> enthält:
<math> W' = W \overline{P_{Mut}} </math>
<math> W' \geq \left(P_2 + \frac{1}{2} P_1 \overline{P_{Cut}}\right)\overline{P_{Mut}} </math>
<math> 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)}\,.
</math>
Mit <math>P_{Sel} = o(H,t)f(H)</math>.
Fazit
Werden also insgesamt <math>N</math> neue Ketten erzeugt, so gilt für den Erwartungswert der Anzahl der Ketten, die das Schema <math>H</math> zum Zeitpunkt <math>t+1</math> enthalten: <math>\langle o(H,t+1) \rangle = NW'</math>
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 <math>o(H,t)</math>. 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 <math>\overline{P_{Mut}} = (1-p)^{b(H)}</math> Beachtung. Eine hohe Mutationsrate <math>p</math> 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 <math>p</math> kann also die Suchaktivität des Algorithmus gesteuert werden.
Literatur
- {{#invoke:Vorlage:Literatur|f}}
Einzelnachweise
<references />