Schemasatz - LinkFang.de





Schemasatz


Dieser Artikel oder Abschnitt ist nicht ausreichend belegt.

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:

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:

  • [math]o(H,t)[/math]
     Anzahl der Genome zum Zeitpunkt t, die das Schema H enthalten.
  • [math]d(H)[/math]
     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.
  • [math]b(H)[/math]
     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 [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, .. ,H_{o(H,t)}[/math] alle diejenigen Bitketten der Population zur Zeit t, die das Schema H enthalten Die Fitness des Schemas H wird dann definiert durch: [math]f(H) = \frac{f(H_1)+ .. + f(H_{o(H,t)})}{o(H,t)} [/math].

Die Wahrscheinlichkeit, dass eine Kette ausgewählt wird, die H enthält, ist somit: [math] P_{Sel} = p(H_1) + .. + p(H_{o(H,t)}) = o(H,t)f(H). [/math]

Für die Wahrscheinlichkeit, dass zwei Elternketten, die beide H 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 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: [math]\overline{P_{Cut}} = 1-\frac{d(H)-1}{l-1}.[/math]

Damit gilt für die Wahrscheinlichkeit W, dass beim Crossover das Schema H weitergegeben wird:

[math] W \geq P_2 + \frac{1}{2} P_1 \overline{P_{Cut}}. [/math]

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 [math]\overline{P_{Cut}}[/math], 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 [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 H 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 N neue Ketten erzeugt, so gilt für den Erwartungswert der Anzahl der Ketten, die das Schema H 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 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.


Kategorien: Evolutionärer Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Schemasatz (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.