Das Schema-Theorem

Ein Schema ist ein Muster von Allelen eines Genoms, welches als Alphabet die möglichen Allele der jeweiligen Gene mit einem zusätzlichen Joker-Zeichen hat. Dieses Joker-Zeichen - meist ein # - steht für die Bedeutung ``don't care''. Ein Schema enthält ein bestimmtes Genom, wenn dieses dem vorgegebenen Muster entspricht.

Das Schema eines binären Genoms wird somit mit dem trinären Alphabet {0, 1, #} aufgebaut und könnte z.B. #1##00# sein. In diesem Schema ist z.B. das Genom 0101001 enthalten, aber auch 1101001. Ein Schema für ein menschliches Genom beinhaltet die Zeichen {A, T, G, C, #}, und das Schema A#G enthält die vier möglichen Genome {AAG, ATG, AGG, ACG}.

In einem Genom mit der Bitlänge $l$ ist ein Schema mit einer Hyperebene in einem $l$-dimensionalen, bit-transformierten d.h. diskretisierten Suchraum gleichzusetzen.

Drei Maßzahlen sind für die theoretische Beschreibung eines Schemas von Bedeutung:

• die Ordnung eines Schemas ist die Anzahl der Zeichen, welche keine ``don't cares'' (#) sind.
• die definierende Länge eines Schemas entspricht der maximalen Distanz zwischen zwei Zeichen im Schema, welche keine ``don't cares'' sind.
• die Fitness eines Schemas wird durch den Mittelwert aller darin enthaltenen Genome beschrieben [19].

In den oben genannten Beispielen hat #1##00# die Ordnung 3 und die definierende Länge 4, A#G hat die Ordnung 2 und die definierende Länge 2. Die Fitness dieser Schemata lässt sich allerdings ohne dazugehörige Zielfunktion nicht bestimmen.

Das von Holland erstmals in seinem Buch [31] vorgestellte Schema-Theorem stellt einen Erklärungsansatz für das Verhalten von GAen dar. Die Kurzform besagt, dass Genetische Algorithmen überdurchschnittlichen Schemata exponentiell steigende Chancen zur Reproduktion geben. Da jedes Genom eine Vielzahl an Schemata enthält, ist die Schemaevaluationsrate sehr hoch. Dieses Phänomen nannte Holland ``impliziten Parallelismus'' und beschreibt die Steigerung der Bewertungsgeschwindigkeit durch kumulative Lerneffekte bei der sukzessiven Bewertung von Hyperebenen über mehrere Generationen hinweg [60]. Die Steigerungsrate wurde von ihm bei einer Population mit $N$ Individuen mit $N^2$ angegeben [27]. Das bedeutet, dass die Schemaevaluationsrate einer Population mit $N$ Individuen pro Generation $N^3$ beträgt.