Genetische Repräsentation

Als genetische Repräsentation (auch Problemrepräsentation) wird die Art und Weise bezeichnet, wie ein ein Optimierungsproblem codiert wird, sodass es mit einem evolutionären Algorithmus (EA) gelöst werden kann. EA suchen Lösungen für Optimierungsprobleme mit Methoden der natürlichen Evolution. Der Begriff der genetischen Repräsentation umfasst dabei sowohl die konkreten Datenstrukturen und Datentypen, mit denen das genetische Material der Lösungskandidaten realisiert wird, als auch die Beziehungen zwischen Suchraum und Problemraum. Im einfachsten Fall entspricht der Suchraum dem Problemraum (direkte Repräsentation). Die Wahl der Problemrepräsentation ist gebunden an die Wahl der genetischen Operatoren, beide wirken sich entscheidend auf die Effizienz der Optimierung aus.

Das Genom eines Lösungskandidaten hat oft die Form eines Bitstrings, einer Liste reeller Zahlen, einer Reihenfolge (bei kombinatorischen Problemen wie Travelling Salesman) oder eines Baumes.

Unterscheidung Such- und Problemraum

In der Natur ist die Information über sämtliche grundlegenden Eigenschaften (Phänotyp) eines Organismus (z. B. Äußere Erscheinung, Stoffwechsel oder basales Verhalten) innerhalb jedes Organismus gespeichert, wie schon Gregor Mendel um 1860 entdeckte. Heute ist bekannt, dass diese Speicherung mit dem genetischen Code realisiert wird. Auf molekularer Ebene sind die definierenden Eigenschaften als DNA codiert. Die gesamte genetische Austattung eines Organismus wird als Genotyp bezeichnet. Der Genotyp bestimmt den Phänotyp, allerdings über einen komplizierten Prozess, die Genexpression.

Analog zur Biologie wird bei evolutionären Algorithmen zwischen Problemraum (entspricht Genotyp) und Suchraum (entspricht Phänotyp) unterschieden. Der Problemraum enthält also konkrete Lösungen für das behandelte Problem, während der Suchraum die codierten Lösungen enthält. Die Abbildung (engl. map) von Suchraum auf Problemraum wird als Genotype-Phenotype-Mapping bezeichnet. Die genetischen Operatoren werden auf Elemente des Suchraums angewandt, zur Auswertung werden Elemente des Suchraums per Genotype-Phenotype-Mapping auf Elemente des Problemraums abbgebildet.

Beziehungen zwischen Such- und Problemraum

Redundanz

Wenn mehr mögliche Genotypen als Phänotypen existieren, heißt die genetische Repräsentation des EA redundant, in der Natur spricht man vom degenerierten genetischen Code. Bei einer redundanten Repräsentation sind neutrale Mutationen möglich, Mutationen die den Genotyp verändern, aber den Phänotyp nicht. In der Biologie besagt die Neutrale Theorie der molekularen Evolution, dass dieser Effekt eine dominierende Rolle in der natürlichen Evolution spielt. Forschungsergebnisse im Bereich der evolutionären Algorithmen legen nahe, dass neutrale Mutation die Funktionsfähigkeit von EA verbessern und Populationen die zu einem lokalen Optimum konvergiert sind, mit genetischem Drift eine weitere Möglichkeit geben, diesem lokalen Optimum zu entkommen.

Lokalität

Die Lokalität einer genetischen Repräsentation entspricht dem Maß, zu dem Abstände im Suchraum nach dem Genotype-Phenotype-Mapping im Problemraum erhalten bleiben. Das heißt, eine hohe Lokalität hat eine Repräsentation genau dann, wenn Nachbarn im Suchraum auch Nachbarn im Problemraum sind. Damit erfolgreiche Schemata durch das Genotype-Phenotype-Mapping nach einer geringfügigen Mutation nicht zerstört werden, muss die Lokalität einer Repräsentation hoch sein.

Skalierung

Beim Genotype-Phenotype-Mapping können die Elemente des Genotyps verschieden skaliert (gewichtet) werden. Der einfachste Fall ist die uniforme Skalierung: Alle Elemente des Genotyps sind im Phänotyp gleich gewichtet. Eine häufige Skalierung ist die exponentielle. Werden ganze Zahlen binär codiert, haben die einzelnen Stellen der entstandenen binären Zahl exponentiell verschiedene Gewichtungen bei der Repräsentation des Phänotyps.

Beispiel: Die Zahl 90 wird binär (also zur Basis zwei) als 1011010 geschrieben. Verändert man nun eine der vorderen Stellen in der binären Schreibweise, hat dies deutlich größere Auswirkungen auf die eigentliche Zahl, als Änderungen an den hinteren Stellen (Der Selektionsdruck wirkt an den vorderen Stellen exponentiell stärker).

Aus diesem Grund tritt bei exponentieller Skalierung der Effekt auf, dass die „hinteren“ Stellen im Genotyp zufällig fixiert werden, bevor die Population nahe genug am Optimum angelangt ist, um diese Feinheiten anzupassen.

Literatur

• Franz Rothlauf: Representations for Genetic and Evolutionary Algorithms. Springer-Verlag, Berlin Heidelberg, ISBN 3-540-25059-X.