imported>DeWikiMan: + Übersicht

2023-03-07T20:26:59Z

+ Übersicht

Neue Seite

Das '''Schematheorem''' nach [[John H. Holland]] behandelt das Konvergenzverhalten [[Evolutionärer Algorithmus|genetischer Algorithmen]]. Das Theorem beweist, dass sich [[Individuum|Individuen]] mit überdurchschnittlicher [[Fitness (Biologie)|Fitness]] mit höherer Wahrscheinlichkeit durchsetzen.<ref>{{Literatur |Autor=John H. Holland |Titel=Adaptation in natural and artificial systems : an introductory analysis with applications to biology, control, and artificial intelligence |Auflage=1st MIT Press ed |Verlag=MIT Press |Ort=Cambridge, Mass. |Datum=1992 |ISBN=0-585-03844-9}}</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 [[Bit]]muster, 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:
* [[Selektion (evolutionärer Algorithmus)|Selektion]]
* [[Rekombination (evolutionärer Algorithmus)|Crossover]] (Rekombination)
* [[Mutation (evolutionärer Algorithmus)|Mutation]]

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 ==
* {{Literatur |Autor=David White |Titel=An Overview of Schema Theory |Sammelwerk=Graduate Journal of Mathematics |Band=3 |Nummer=2 |Datum=2018 |Seiten=37–59 |DOI=10.48550/arXiv.1401.2651}}

== Einzelnachweise ==
<references />

[[Kategorie:Evolutionärer Algorithmus]]
[[Kategorie:Satz (Mathematik)]]

Schematheorem - Versionsgeschichte

imported>DeWikiMan: + Übersicht