Generative Methoden

Zum Ausführen der Programme, die zip-Dateien lokal speichern, entpacken und die exe Dateien starten.


STRATEGIE 1: Dichte-Packung


Sortwaremuster zum InfAR Arbeitspapier 04: Generierung von Grundriss-Layouts mittels hybrider Evolutions-Strategie (März 2011)

Download zip | Nach dem Entpacken des Archivs die Datei "Einpassung.exe" ausführen.


 Kombination des Dichte-Packung Layoutsystems mit Sichtbarkeitsanalysen


Softwaremuster für die Nachbarschaftsbeziehungen (Download zip)
Für die Testumgebung wird eine sternförmige Topologie verwendet. Für das Grundrisslayout bedeutet dies, dass alle Räume von einem Gang aus erschlossen werden. Für die vorliegende Problemkonstellation hat sich die (μ, λ)- ES bewährt. Interaktion via Maus funktioniert nur beim Layout oben links.

Das System bleibt oft in lokalen Optima hängen. Mögliche Verbesserungen unseres Verfahrens bestehen in der Verwendung anderer Mechanismen zur Kombination der durch die verschiedenen EAs erzeugten Teillösungen.


Softwaremuster für die Einpassung (Download zip)
Die Polygone werden mittels EA (Evolutionäre Strategie) in ein umgebendes Rechteck eingepasst. Durch den EA werden die Proportionen der Rechtecke und deren x- und y-Koordinaten variiert. Bei der hier vorgestellten Variante wird nur eine Population verwendet. Die Rechtecke können via Maus per drag&drop verschoben werden. Das System ist so justiert, dass bei Veränderungen so schnell wie möglich eine neue Lösung gesucht wird, wobei sich das System möglichst kontinierlich verhält. Das bedeutet, dass Teile der Lösung, die bereits gut funktionieren, nicht zerstört werden. Getestet wurde die (μ+λ)- ES und die (μ, λ)- ES, jeweils mit und ohne Elite Selection. Im vorliegenden Fall hat sich die (μ+λ)- ES ohne Elite Selection als geeignet erwiesen.

 


Softwaremuster für die Kollissionserkennung (Download zip)
Die Rechtecke bewegen sich so lange voneinander weg, bis keine Überlagerung (Kollission) mehr auftritt. Der Kontrollparameter "repel factor" gibt an, welcher Anteil des Kollissionsvektors als Bewegungsvektor für jedes Polygon verwendet wird. Der Parameterwert 2 bedeutet beispielsweise, dass jedem der beiden kollidierenden Polygone der Betrag des halben Vektors zugewiesen wird.



STRATEGIE 2: KD-Tree


Softwaremuster Nachbarschaftsbeziehungen (Download zip)

Die Lösungssuche wurde hier auf drei parallel laufende Populationen verteilt. In der ersten Population werden die Raumgrößen optimiert, so dass sie den eingegebenen oder berechneten Idealwerten entsprechen bzw. diesen möglichst nahe kommen. Die zugehörige Fitnessfunktion berechnet die Summe der Abweichungen von der jeweiligen idealen Raumgröße. Hier wird ein evolutionärer Algorithmus eingesetzt, der die Positionen der Datenpunkte verändert.

Die zweite Population optimiert das Nachbarschaftsverhältnis. Hier wird ein genetischer Algorithmus eingesetzt, der die Folge der Raumindizes rekombiniert und mutiert bzw. „die Räume vertauscht“. Die zugehörige Fitnessfunktion berechnet die Summe der Abstände zwischen notwendigen Nachbarpolygonen. Liegen die Räume direkt nebeneinander so ist deren Abstand gleich null, wobei eine Mindestüberlappung notwendig ist, welche der Mindestdurchgangsbreite entspricht.

Die dritte Population  dient der Optimierung der Raumproportionen. Mithilfe eines genetischen Algorithmus wird die Unterteilungsfolge rekombiniert bzw. mutiert. Zur Bestimmung des Fittest Individuals wird eine Fitnessfunktion aus der Summe der Raumproportionen aus der längsten zur kürzesten Seite eingesetzt, sowie die Nachbarschaftsfitness der besten Individuen verglichen.

Zur Überprüfung der einzelnen Populationen sind in Version 8 noch zwei Übersichtsfenster eingefügt worden, welche zum einen die aktuell beste Schnittfolge und zum anderen die aktuell beste Indexfolge anzeigen.


Softwaremuster für die Anpassung der Raumgrößen (Download zip)

Es wurde ein einfacher evolutionärer Algorithmus implementiert, welcher es erlaubt, bestimmte Raumgrößen zu definieren. Hierbei werden die Datenpunkte so lange verschoben, bis die n Räume die vorgegebene Größe  besitzen. Die Fitnessfunktion berechnet die Summe der Abweichungen der Flächen vom Idealwert.

Die gewünschte Raumgröße ist im jeweiligen Texteingabefeld für jede Zelle editierbar. Die aktuelle, tatsächliche Größe des Raums wird unterhalb des Texteingabefelds angezeigt. Die Punkte (und dadurch die Räume) können via Maus per drag&drop verschoben werden



STRATEGIE 3: Unterteilungs-Grammatik


Softwaremuster Unterteilungs-Grammatik (Download zip)
Das Unterteilungssystem nutzt die Funktionsweise von L-Systemen. Ein Rechteck wird nach bestimmten Regeln unterteilt, die in Form einer Zeichenkette angegeben werden. Bei dem vorliegenden Beispiel werden Horizontale Teilungen durch ein H gekennzeichnet und Vertikale Teilungen durch ein V. Räume, die nicht weiter unterteilt werden erhalten ein o. Die Baumstruktur wird mittels der Klammern () abgebildet.