Programmieraufgabe WS 2014/15
Moderator: Optimierungsalgorithmen
-
- Moderator
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Programmieraufgabe WS 2014/15
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
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
Re: Programmieraufgabe WS 2014/15
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.
Mein Vorschlag wäre es das Maximum von beiden zu nehmen.
-
- Moderator
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Programmieraufgabe WS 2014/15
Ja, das wäre so von mir gedacht gewesen.cypher hat geschrieben: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.
KW
Re: Programmieraufgabe WS 2014/15
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
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
-
- Moderator
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Programmieraufgabe WS 2014/15
Ja, genau darum soll es gehen. Manche Nachbarschaftsdefinitionen sind halt nicht so hilfreich wie anderen.the D hat geschrieben: 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)
KW
Re: Programmieraufgabe WS 2014/15
Dürfen wir die Programmieraufgabe auch in Scala umsetzen?
-
- Moderator
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Programmieraufgabe WS 2014/15
Meinetwegen.pSub hat geschrieben:Dürfen wir die Programmieraufgabe auch in Scala umsetzen?
KW