Programmieraufgabe WS 2014/15

[Prof. Karsten Weihe]

Hallo allerseits,

hier nun die Programmieraufgabe für die OptAlgos im WS 2014/15:

Implementieren Sie die folgenden, demnächst in der Vorlesung zu besprechenden, nachbarschaftsbasierten Algorithmen:

-> Lokale Suche

-> Simulated Annealing

-> Tabusuche

Diese Implementationen sollen so generisch sein, wie sie in der Vorlesung dargestellt werden, also insbesondere völlig unabhängig vom folgenden konkreten Optimierungsproblem.

Sie wenden Ihre Algorithmen auf folgendes konkretes Optimierungsproblem an: Gegeben ist eine endliche Menge von Rechtecken, gesucht ist eine Platzierung aller dieser Rechtecke in der Ebene, so dass das kleinste Quadrat, das alle diese Rechtecke umfasst, minimale Kantenlänge hat. Dabei müssen je zwei Rechtecke offen disjunkt platziert sein, das heißt, sie dürfen nur Eckpunkte und (Segmente der) Randkanten gemeinsam haben, keine inneren Punkte. Rechtecke dürfen in beiden möglichen achsenparallelen Orientierungen platziert sein, also rotiert werden.

Im folgenden heiße eine zulässige Lösung kanonisch, wenn jedes Rechteck so platziert ist, dass es wegen anderer Rechtecke oder wegen des oberen und linken Quadratrandes nicht weiter nach oben oder nach links verschoben werden kann. Überlegen Sie sich, dass es unter den optimalen Lösungen immer auch eine kanonische Lösung geben muss, so dass Sie sich auf die Betrachtung von kanonische Lösungen beschränken können.

Für jeden Ihrer Algorithmen implementieren Sie drei Anwendungen auf das Problem, mit Nachbarschaften von drei grundsätzlich verschiedenen Arten:

-> Geometriebasiert: Ein Nachbar lässt sich erzeugen, indem ein Rechteck gedreht, verschoben oder mit einem anderen Rechteck vertauscht wird. Um die Nachbarschaft nicht unnötig aufzublähen, berechnen Sie nur kanonische Nachbarn.

-> Regelbasiert: Anstelle von zulässigen Lösungen, arbeiten die Algorithmen auf Permutationen von Rechtecken. Nach einer von Ihnen zu entwickelnden Regel werden die Rechtecke in der Reihenfolge der Permutation so platziert, dass sich eine kanonische Lösung ergibt. Die Nachbarschaft definieren Sie durch kleine Modifikationsschritte auf der Permutation.

-> Überlappungen teilweise zulassen: Die regelbasierte Nachbarschaft wird angepasst auf die Situation, dass Rechtecke sich zu einem gewissen Prozentsatz überlappen dürfen. Dieser Prozentsatz ist zu Beginn 100 (so dass die kanonische Optimalllösung trivial zu finden ist). Im Laufe der Zeit reduziert sich der Prozentsatz, und Verletzungen werden hart in der Zielfunktion bestraft. Am Ende müssen die jeweiligen Algorithmen natürlich noch ausreichend lange mit 0% zulässiger Überlappung laufen, um am Ende eine garantiert überlappungsfreie Lösung zu erhalten. Sie müssen sich also dazu Gedanken über die Terminierung der Algorithmen machen.

Weiter implementieren Sie eine einfache GUI mit Visualisierung, in der der Nutzer beliebig häufig eine zufällige Menge von Rechtecken mit ganzzahligen Seitenlängen erzeugen lassen und einen Algorithmus darauf anwenden kann. Der Nutzer kann die Anzahl Rechtecke und die minimale und maximale (ganzzahlige) Seitenlänge für die zufällige Erzeugung individuell für jede Instanz festlegen.

Schließlich schreiben Sie unabhängig von der GUI noch eine kleine Testumgebung, die mit einer Folge von Quadrupeln (Anzahl Instanzen, Anzahl Rechtecke, minimale Seitenlänge, maximale Seitenlänge) parametrisiert ist. Für jedes Quadrupel werden so viele Instanzen generiert und durchgerechnet, wie das erste Element des Quadrupels es sagt. Jeder Algorithmus wird auf jede Instanz angewandt, und die erreichten Quadratlängen sowie die dafür notwendigen Laufzeiten werden geeignet mitprotokolliert, um die Güte der Algorithmen miteinander zu vergleichen.

Realisieren Sie am Besten die Aufgabe auf Ihrem eigenen Laptop, den Sie dann auch zum Testatstermin mitbringen. Java, C, C++ und C# sind ok; für andere Programmiersprachen bitte ich vorab um Anfrage - am Besten im Forum. Sollte aber normalerweise kein Problem sein.

Falls Sie frühzeitig mit der Bearbeitung der Aufgabe beginnen wollen, können Sie schon mit ZG, GUI und Testumgebung beginnen, bevor die Algorithmen in der Vorlesung behandelt werden.

Fragen von allgemeinem Interesse am Besten im Forum. Wenn Sie einen einzelnen konkreten inhaltlichen Punkt ansprechen wollen, bietet es sich an, einen eigenen Thread dafür aufzumachen.

KW

[cypher]

Wie genau soll die prozentuale Überlappung von Rechtecken implementiert werden? Nach meinem Verständnis kann man nur sagen Rechteck A überlappt Rechteck B zu x%, also dass x% der Fläche von B sich mit der Fläche von A schneiden. Das heißt allerdings nicht dass sich auch x% der Fläche von A mit der Fläche von B schneiden, außer wenn die Rechtecke die gleiche Fläche haben.
Mein Vorschlag wäre es das Maximum von beiden zu nehmen.

[Prof. Karsten Weihe]

Wie genau soll die prozentuale Überlappung von Rechtecken implementiert werden? Nach meinem Verständnis kann man nur sagen Rechteck A überlappt Rechteck B zu x%, also dass x% der Fläche von B sich mit der Fläche von A schneiden. Das heißt allerdings nicht dass sich auch x% der Fläche von A mit der Fläche von B schneiden, außer wenn die Rechtecke die gleiche Fläche haben.
Mein Vorschlag wäre es das Maximum von beiden zu nehmen.

Ja, das wäre so von mir gedacht gewesen.

KW

[the D]

Hallo,

Ich habe eine Verständnisfrage zur geometriebasierten Nachbarschaftsbeziehung:

Was ist mit der Vertauschung zweier Rechtecke hier genau gemeint? Dass zwei Rechtecke ihre Position tauschen macht ja eigentlich nur Sinn, wenn diese entweder genau gleich groß sind, oder das kleinere eben genau so am Rand liegt, dass auch Platz für ein größeres wäre (ansonsten käme es zu Überlappungen).
Ist es so gedacht, dass eben nur jene Vertauschungs-Nachbarn betrachtet werden sollen, die zulässig wären (was denke ich dann eher selten wäre) oder sollte die Vertauschung hier anders definiert sein, so dass in jeder denkbaren Konfiguration immer jede zwei beliebigen Rechtecke vertauscht werden können und dabei immer wieder eine zulässige Lösung entsteht?

Für letzteres fehlt mir momentan das Verständnis wie so eine Vertauschung aussehen könnte.
(hoffe mein Problem ist klar geworden)

lg Dominik

[Prof. Karsten Weihe]

Ist es so gedacht, dass eben nur jene Vertauschungs-Nachbarn betrachtet werden sollen, die zulässig wären (was denke ich dann eher selten wäre)

Ja, genau darum soll es gehen. Manche Nachbarschaftsdefinitionen sind halt nicht so hilfreich wie anderen.

KW

[pSub]

Dürfen wir die Programmieraufgabe auch in Scala umsetzen?

[Prof. Karsten Weihe]

Dürfen wir die Programmieraufgabe auch in Scala umsetzen?

Meinetwegen.

KW