Die Building-Block-Hypothese

Ein Building-Block (BB) ist im Bereich des Evolutionary Computing - und dort vor allem bei den Genetischen Algorithmen und bei der Genetischen Programmierung - eine eng gegliederte Gruppe von Genen, deren Allele, wenn sie in ein beliebiges Chromosom eingesetzt werden, die Fitness dieses Individuums mit großer Wahrscheinlichkeit verbessern würden.

Die zuerst von Goldberg in [19] vorgestellte Building-Block-Hypothese erklärt den Erfolg von Genetischen Algorithmen dadurch, dass diese in frühen Laufzeitstadien so viele Building-Blocks wie möglich finden und diese später, durch Crossover kombiniert, eine möglichst optimale Fitness ergeben [27]. Somit stellen sie überproportional fitte (Teil-)Schemata kleiner Ordnung und kurzer definierender Länge dar. Building-Blocks kurzer Länge werden als eng gekoppelt bezeichnet.

Als eine direkte Folge dieser Hypothese steht die Feststellung dass, je größer die Anfangspopulation eines GA, desto wahrscheinlicher das Vorhandensein einiger guter Fundamente für den raschen Aufbau von Building-Blocks in Nachfolgegenerationen ist. Doch setzen in vielen Fällen Zeit- und Speicherplatzmangel enge Grenzen für die maximal mögliche Populationsgröße, weshalb ein wichtiger Forschungsschwerpunkt die Möglichkeit zum Aufbau guter Building-Blocks auch bei kleinen Populationen darstellt.

Eng verbunden mit der Building-Block-Hypothese ist der Begriff Deception^3.16. Dieser beschreibt den Effekt, dass eine Rekombination guter Building-Blocks zu einer Verschlechterung der Fitness von Individuen führt anstatt zu einer Verbesserung. Dieses Verhalten von GAen bei manchen Kodierungen und Problemen wurde von Goldberg als einer der Gründe für deren Versagen bei manchen Aufgabenstellungen angesehen.

Eine erklärende Theorie, wann und wie welche im Lauf eines Genetischen Algorithmus auftauchenden und überlebenden Building-Blocks zusammengefügt eine größere Chance für bessere Fitness repräsentieren, ist zur Zeit noch nicht vorgestellt worden [20].