Schemasatz

Betrachten Sie binäre Strings der Länge 6. Das Schema 1*10*1 beschreibt die Menge aller Strings der Länge 6 mit 1 an den Positionen 1, 3 und 6 und einer 0 an Position 4. Das * ist ein Platzhaltersymbol, was bedeutet, dass die Positionen 2 und 5 entweder den Wert 1 oder 0 haben können. Die Reihenfolge eines Schemas o ( H ) {\displaystyle o(H)} ist definiert als die Anzahl der festen Positionen in der Vorlage, während die definierende Länge δ ( H ) {\displaystyle \delta (H)} der Abstand zwischen der ersten und letzten bestimmten Position ist. Die Ordnung von 1*10*1 ist 4 und seine definierende Länge 5. Die Fitness eines Schemas ist die durchschnittliche Fitness aller Strings, die dem Schema entsprechen. Die Fitness einer Zeichenfolge ist ein Maß für den Wert der kodierten Problemlösung, wie er durch eine problemspezifische Auswertungsfunktion berechnet wird. Unter Verwendung der etablierten Methoden und genetischen Operatoren genetischer Algorithmen besagt das Schema-Theorem, dass kurze Schemata niedriger Ordnung mit überdurchschnittlicher Fitness in aufeinanderfolgenden Generationen exponentiell zunehmen. Ausgedrückt als Gleichung:

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . {\Anzeigestil \Betreibername {E} (m(H,t+1))\geq {m(H,t)f(H) \über a_{t}}[1-p]. }

Dabei ist m ( H , t ) {\darstellungsstil m(H,t)} die Anzahl der zum Schema H {\darstellungsstil H} gehörenden Zeichenketten bei der Erzeugung t {\darstellungsstil t} , f ( H ) {\darstellungsstil f(H)} ist die beobachtete durchschnittliche Fitness des Schemas H {\darstellungsstil H} und a t {\darstellungsstil a_{t}} ist die beobachtete durchschnittliche Fitness bei der Generation t {\darstellungsstil t} . Die Wahrscheinlichkeit einer Störung p {\Darstellungsstil p} ist die Wahrscheinlichkeit, dass ein Crossover oder eine Mutation das Schema H {\Darstellungsstil H} zerstören wird. Sie kann ausgedrückt werden als:

p = δ ( H ) l - 1 p c + o ( H ) p m {\darstellungsstil p={\delta (H) \over l-1}p_{c}+o(H)p_{m}}

wobei o ( H ) {\displaystyle o(H)} die Reihenfolge des Schemas, l {\displaystyle l} die Länge des Codes, p m {\displaystyle p_{m}} die Wahrscheinlichkeit einer Mutation und p c {\displaystyle p_{c}} die Wahrscheinlichkeit einer Kreuzung ist. Ein Schema mit einer kürzeren Definitionslänge δ ( H ) {\displaystyle \delta (H)} ist also weniger wahrscheinlich, dass es gestört wird.
Ein oft missverstandener Punkt ist, warum das Schema-Theorem eher
eine Ungleichheit als eine Gleichheit
ist. Die Antwort ist in der Tat einfach: Das Theorem vernachlässigt die kleine, jedoch von Null verschiedene Wahrscheinlichkeit, dass eine zum Schema H {\Darstellungsstil H} gehörende Zeichenkette "von Grund auf" durch Mutation einer einzelnen Zeichenkette (oder Rekombination zweier Zeichenketten) erzeugt wird, die in der vorherigen Generation nicht zum Schema H {\Darstellungsstil H} gehörte.

Das Schema-Theorem gilt unter der Annahme eines genetischen Algorithmus, der eine unendlich große Population aufrechterhält, sich aber nicht immer auf die (endliche) Praxis überträgt: Aufgrund von Stichprobenfehlern in der Ausgangspopulation können genetische Algorithmen auf Schemata konvergieren, die keinen selektiven Vorteil haben. Dies geschieht insbesondere bei der multimodalen Optimierung, bei der eine Funktion mehrere Peaks haben kann: Die Population kann dahingehend driften, dass sie einen der Peaks bevorzugt und die anderen ignoriert.

Der Grund dafür, dass das Schema-Theorem die Macht genetischer Algorithmen nicht erklären kann, liegt darin, dass es für alle Problemfälle gilt und nicht zwischen Problemen unterscheiden kann, bei denen genetische Algorithmen eine schlechte Leistung erbringen, und Problemen, bei denen genetische Algorithmen eine gute Leistung erbringen.