Schematheorem

Da die Fitness normiert ist, gilt für die Wahrscheinlichkeit ${\displaystyle p}$, dass eine bestimmte Elternkette ${\displaystyle H_{i}}$ aus einer Population ausgewählt wird: ${\displaystyle p(H_{i})=f(H_{i})}$

Seien nun ohne Einschränkung ${\displaystyle H_{1},\dotsc ,H_{o(H,t)}}$ alle diejenigen Bitketten der Population zur Zeit ${\displaystyle t}$, die das Schema ${\displaystyle H}$ enthalten.

Die Fitness des Schemas ${\displaystyle H}$ wird dann definiert als Durchschnitt der Fitness aller Individuen: ${\displaystyle f(H)={\frac {f(H_{1})+\dotsc +f(H_{o(H,t)})}{o(H,t)}}}$.

Die Wahrscheinlichkeit, dass eine Kette ausgewählt wird, die ${\displaystyle H}$ enthält, ist somit: ${\displaystyle P_{Sel}=p(H_{1})+\dotsc +p(H_{o(H,t)})=o(H,t)f(H).}$

Für die Wahrscheinlichkeit, dass zwei Elternketten, die beide ${\displaystyle H}$ enthalten, ausgewählt werden, gilt: ${\displaystyle P_{2}={P_{Sel}}^{2}}$.

Beim 1-Point-Rekombination wird zunächst ein Trennpunkt zwischen den Bitstellen 1 und l-1 gewählt. Falls beide Elternteile ${\displaystyle H}$ enthalten, so enthält auch die Tochterkette dieses Schema. Enthält nur eine Elternkette das Schema, so wird ${\displaystyle 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: ${\displaystyle {\overline {P_{Cut}}}=1-{\frac {d(H)-1}{l-1}}.}$

Damit gilt für die Wahrscheinlichkeit ${\displaystyle W}$, dass beim Crossover das Schema ${\displaystyle H}$ weitergegeben wird: ${\displaystyle W\geq P_{2}+{\frac {1}{2}}P_{1}{\overline {P_{Cut}}}.}$

Falls beim Crossover das Schema ${\displaystyle 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 ${\displaystyle P_{Cut}}$, die Wahrscheinlichkeit, dass das Schema durchtrennt wird, steigt.

Sei ${\displaystyle p}$ die Mutationswahrscheinlichkeit, das heißt, jedes Bit der neuen Kette wird mit der Wahrscheinlichkeit ${\displaystyle p}$ negiert. Dies bedeutet, dass das Schema ${\displaystyle H}$ mit ${\displaystyle b(H)}$ festen Bits mit der Wahrscheinlichkeit ${\displaystyle {\overline {P_{Mut}}}=(1-p)^{b(H)}}$ erhalten bleibt.

Wird dieser Effekt berücksichtigt, so ergibt sich für die Wahrscheinlichkeit ${\displaystyle W'}$, dass eine durch die Operatoren Crossover und Mutation erzeugte Kette das Schema ${\displaystyle H}$ enthält:

${\displaystyle W'=W{\overline {P_{Mut}}}}$

${\displaystyle W'\geq \left(P_{2}+{\frac {1}{2}}P_{1}{\overline {P_{Cut}}}\right){\overline {P_{Mut}}}}$

${\displaystyle 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 ${\displaystyle P_{Sel}=o(H,t)f(H)}$.

Werden also insgesamt ${\displaystyle N}$ neue Ketten erzeugt, so gilt für den Erwartungswert der Anzahl der Ketten, die das Schema ${\displaystyle H}$ zum Zeitpunkt ${\displaystyle t+1}$ enthalten: ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle {\overline {P_{Mut}}}=(1-p)^{b(H)}}$ Beachtung. Eine hohe Mutationsrate ${\displaystyle 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 ${\displaystyle p}$ kann also die Suchaktivität des Algorithmus gesteuert werden.