In Anlehnung an die Biologie unterscheidet man die Genotyp- und
die Phenotyp-Darstellung eines Individuums.
Der Genotyp ist die Kodierung, auf der die genetischen Operatoren
arbeiten, und der die gesamte genetische Information eines Individuums
enthält, während der Phenotyp die ,, physikalische`` Ausprägung
des Individuums festlegt.
Die Genotyp-Kodierung besteht in der klassischen Definition der genetischen
Algorithmen aus einzelnen Genen, die unterschiedliche Werte,
die sogenannten Allele annehmen können.
Die einfachste Kodierung eines Genotypen ist ein Bitstring, wobei jedes
Bit ein Gen darstellt, die Allelen sind 0 und 1.
Für die Optimierung von kontinuierlichen Zielfunktionen ist
der Genotyp ein Vektor von Gleitkommazahlen.
Die genetischen Operatoren für diese Fälle verändern ein
oder mehrere Gene (Mutation), oder kreuzen zwei Gen-Strings,
indem jedes Gen des Offsprings eines der beiden möglichen
Allele aus dem entsprechenden Gen eines Parents
übernimmt (Crossover).
Figure: Ein Floorplan und die Repräsentation als binärer Schnittbaum
Für ein diskretes Optimierungsproblem wie die Layoutgenerierung
kann die Genotyp-Kodierung nicht wie in der Biologie als ein String von Genen erfolgen.
Um die Lage der Module auf dem Layout -- also den Floorplan -- zu beschreiben, ist ein binärer
Schnittbaum geeignet (siehe Abb. 2).
Die Blätter dieses Baumes beschreiben die Module (Blöcke) des Schaltkreises, und
die inneren Knoten repräsentieren Teil-Layouts (Meta-Blöcke).
Da der Schnittbaum nur die relative Position der Blöcke beschreibt,
werden den inneren Knoten noch zusätzliche Informationen bezüglich
der Anordnung der zusammengefa Blöcke, der Verdrahtung und der möglichen
Layout-Alternativen (über Form-Funktionen) zugeordnet.
Existieren für einen Block mehrere Implementierungen, so ergeben sich für
alle Meta-Blöcke, welche diesen Block enthalten, mehrere Layout-Alternativen,
die durch Form-Funktionen für die Meta-Blöcke gespeichert werden.
Dieses führt zu einer deutlich schnelleren Konvergenz des genetischen
Algorithmus, da bei der Konstruktion eines Individuums bzw. nach der
Anwendung eines genetischen Operators immer die global günstigste
Layout-Alternative für jedes einzelne Modul ausgewählt werden kann [9].
Figure: Ein Graph für vier Blöcke und die drei möglichen Matchings
Die Konstruktion des Schnittbaumes für ein Individuum der Ausgangspopulation
erfolgt ,, bottom-up`` , d.h. es werden zunächst jeweils
zwei Elementar-Blöcke zu einem Meta-Block zusammengefa und im folgenden
jeweils zwei Meta-Blöcke vereinigt, bis der Schnittbaum vollständig ist.
Dabei werden die Blöcke nicht zufällig gepaart, sondern mit Hilfe eines
iterierten Matching-Verfahrens Individuen erzeugt, die dicht gepackte
Meta-Blöcke enthalten.
Hierzu wird ein vollständiger Graph konstruiert, dessen Knoten die Blöcke
repräsentieren und dessen Kanten mit einem Wert gewichtet sind, der die
Qualität des Meta-Blockes beschreibt, der entsteht, wenn die beiden zu einer
Kante adjazenten Blöcke zusammengefa würden (siehe Abb. 3).
Ein Matching in dem Graphen ist eine Menge von disjunkten Knotenpaaren,
wobei die gepaarten Knoten durch eine Kante verbunden sind.
Es wird in dem Graphen ein maximal gewichtetes Matching (maximum weight matching)
ermittelt, d.h. ein Matching, bei dem die Summe aller beteiligten Kantengewichte
maximal ist.
Dieses entspricht einer Menge von Meta-Blöcken mit maximaler Qualität,
also mit einem minimalen Gesamtverschnitt.
Das Matching wird in mehreren Iterationen durchgeführt, d.h. in der
zweiten Iteration werden Meta-Blöcke, die aus jeweils zwei Elementar-Blöcken
bestehen, gepaart und dieses Verfahren wird angewendet, bis nur noch zwei
Meta-Blöcke vorhanden sind, die dann in der Wurzel des Schnittbaumes
vereinigt werden.