Der genetische Algorithmus wurde mit Layout-Benchmarks,
welche ursprünglich vom MCNC (North Carolina's microelectronics, computing and networking center)
für einen Workshop zur Verfügung gestellt wurden, getestet.
Die Testinstanzen sind partitionierte Schaltkreise mit 10 bis 49 Modulen
und 123 bis 408 Netzen.
Abbildung 7 zeigt ein mit dem genetischen Algorithmus generiertes Layout
für den Schaltkreis ami33 mit 33 Modulen und 123 Netzen.
Dieses Layout wurde in 500 Generationen berechnet, was bei einer
Populationsgrö von 20 Individuen 10000 Operationen (Mutation bzw.\
Crossover) entspricht.
Figure: Die Entwicklung der Layoutfläche in Abhängigkeit von der Generierung der Ausgangspopulation
Die Entwicklung der Qualität des besten
Individuums in der Population zeigt Abbildung 6.
Dargestellt ist der Durchschnitt über jeweils 10 Läufe des genetischen
Algorithmus für den Schaltkreis ami49 mit 49 Modulen und 408
Netzen.
Anhand dieser Grafik wird der Vorteil des iterierten Matchings bei der
Konstruktion der Ausgangspopulation deutlich.
Die oberen Kurven beschreiben die Qualität der Layouts für Optimierungen, die mit vollkommen
zufällig erzeugten Individuen starteten, während die durch die unteren
Kurven dargestellten Daten von Läufen des genetischen Algorithmus stammen,
bei denen alle Individuen mit Hilfe des iterierten Matchings erzeugt
wurden.
Neben der eigentlichen Fitneß, nämlich der Gesamtfläche
(rechte Grafik), ist auch die Entwicklung des inneren Teils des besten Layouts
gezeigt (linke Grafik), da sich nur hier das iterierte Matching direkt
auswirkt.
Die Grö des Verdrahtungsplatzes am Rand des Layouts, über den die
Verdrahtung der Pads und die Vereinigung von Netzen mit Terminals an
unterschiedlichen Seiten des Layouts realisiert wird, kann beim iterierten
Matching nicht berücksichtigt werden, da dieser Platzbedarf erst nach
der vollständigen Konstruktion des Schnittbaumes ermittelt werden kann.
Bemerkenswert ist, daß die innere Layoutfläche in der mit dem
Matching-Verfahren konstruierten Ausgangspopulation schon besser
ist, als die entsprechenden Ergebnisse der zufälligen Läufe nach 400 Generationen.
Figure: Ein Layout für eine Instanz mit 33 Blöcken und 123 Netzen