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

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 bezeichnet 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 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_{1},..,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_{1})+..+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.

Einzelnachweise

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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