Problemverursacher

Goldberg et al. konnten in [20] vier wichtige Problemkreise identifizieren, welche für Genetische Algorithmen - wie allerdings für andere Such- und Optimierungsstrategien auch - schwierig zu lösen sind:

1. pikartige oder isolierte Optima,
2. Deception,
3. Noisiness,
4. und massive Multimodalität

in der Ergebnisfunktion wirken einzeln oder kombiniert massiv erschwerend.

Mit Blick auf das Schema-Theorem und die Building-Block-Hypothese impliziert dies nach einer Untersuchung von Harik in [24] folgende kodierungs- oder ablauftechnische Probleme, von denen mindestens eines erfüllt sein muss:

1. es gibt für diesen Genetischen Algorithmus in der vorliegenden Informations- bzw. Variablenkodierung keine Building-Blocks.
2. die Fortpflanzung von Building-Blocks, die eine optimale Lösung formen, muss erschwert sein.
3. die Rekombination gefundener kleiner Building-Blocks zu einer optimalen Lösung ist nicht trivial oder nicht existent.

Besonders das erste Problem kann bei unbedachter bzw. falscher Informationskodierung entstehen und sollte bei schwachen Leistungen des GA als erstes überprüft werden^4.1.

Eine Fortpflanzung von Building-Blocks wird in erster Linie durch Blöcke hoher Ordnung und großer definierender Länge erschwert. Es ist nachvollziehbar, dass je niedriger die Ordnung und die definierende Länge von Blöcken ist, desto einfacher ein GA diese finden und rekombinieren können wird.

Als Schwierigkeitsgrad eines Problems kann deshalb die Ordnung des größten Building-Blocks mit ``guten'' Eigenschaften gelten, der nicht durch Rekombination kleinerer Blöcke erzeugt werden kann. Je größer diese Ordnung ist, desto schwieriger ist es für den GA, diesen zu finden, wenn ein solcher Block nicht per Zufall oder dank einer ``ausreichend großen'' Anfangspopulation vorhanden ist. Goldberg & Bridges zeigten 1990, dass GAen bei Problemen mit Building-Blocks großer definierender Länge sehr häufig zu lokalen Optima hinkonvergieren anstatt zu einem globalen Optimum [24]. Eine Umordnung der Genrepräsentation kann Besserung in der Leistung schaffen und wenn dies nicht möglich ist, so kann die Wahl eines anderen Crossover-Operators helfen.

Das dritte der oben genannten Probleme stammt aus dem Bereich der Deception und ist bisher nicht gelöst worden. Die Tatsache, dass Rekombination kleiner, potentiell guter Building-Blocks zusammen eine schlechtere Fitness ergeben, zeigt deutlich die theoretischen Grenzen von Schema-Theorem und Building-Block-Hypothese.