Regelbasiert == Swaps?

[hanneswernery]

Hallo zusammen

Ich habe die Geometriebasierte Nachbarschaft implementiert mit den erzeugenden Aktionen rotate, swap und move
Jetzt ich habe eine Frage zur Regelbasierten Nachbarschaft.

Ich verstehe den Text so, dass Permutation (=Vertauschung) von Rechtecken so gemeint ist, dass zwei Lösungen benachbart sind, wenn wir zwei Rechtecke vertauscht haben. Wäre das dann aber nicht ein swap?
Oder ist mit Permutation nicht die Vertauschen von Rechtecks-positionen gemeint, sondern Vertauschungen von "Besetzung" auf unserer Fläche, sprich ich vertausche diese leere Position mit der Position eines Rechtecks? Wäre das dann nicht aber nicht ein move?

Bei Permutation denke ich immer an eine Liste, beispielsweise "p[0]=R1": R1 steht an Stelle 0. Oder interpretiere ich die Permutation hier zu simpel?

[Atlantaphoenix]

Hallo,

ich habe die Permutation so verstanden: Du hast ja eine Funktion, die dir die Anfangslösung erzeugt (Rechtecke bereits mehr oder weniger gut im Quadrat angeordnet), danach werden die Algorithmen angewendet (also z.B. bei Geometriebasierter Nachbarschaft die Aktionen rotate, swap und move).
Bei Regelbasierter Nachbarschaft habe ich nun Änderungen an der Reihenfolge vorgenommen, wie die Rechtecke in der Anfangslösung hinzugefügt werden. Ich habe also z.B. die Reichenfolge des Hinzufügens zweier Rechtecke vertauscht und danach eine neue Anfangslösung erzeugt.

Klärt das deine Frage?

Viele Grüße
Max

[hanneswernery]

Ich denke ich habe verstanden, was du meinst, auch wenn ich das so nie aus dem Aufgabentext gelesen hätte

Du hast also eine Aufbaufunktion, bei der man nur die Reihenfolge ändern kann, in der sie die Rechtecke hinzufügt (da ist die Permutation). Das heisst aber auch, dass diese Funktion etwas intelligenter sein muss, an welche Position das Rechteck neu eingefügt wird, richtig? Beispielsweise ob das zweite Rechteck neben das erste gesetzt wird oder darunter, etc. Ich stelle mir das gerade so vor, dass du mit jedem neuen Einsetzen eine kleine Nachbarschaftssuche machen musst und dann abwägst an welcher Stelle man es am besten einfügt (vergleichbar mit einem Schritt der lokalen Suche, wenn man einen move macht) Bin ich da auf dem richtigen Weg?

Randbemerkung: meine Startlösung wird erzeugt, indem alle Rechtecke strikt nebeneinander gesetzt werden

[Atlantaphoenix]

Du hast also eine Aufbaufunktion, bei der man nur die Reihenfolge ändern kann, in der sie die Rechtecke hinzufügt (da ist die Permutation). Das heisst aber auch, dass diese Funktion etwas intelligenter sein muss, an welche Position das Rechteck neu eingefügt wird, richtig? Beispielsweise ob das zweite Rechteck neben das erste gesetzt wird oder darunter, etc. Ich stelle mir das gerade so vor, dass du mit jedem neuen Einsetzen eine kleine Nachbarschaftssuche machen musst und dann abwägst an welcher Stelle man es am besten einfügt (vergleichbar mit einem Schritt der lokalen Suche, wenn man einen move macht) Bin ich da auf dem richtigen Weg?

Meine Aufbaufunktion ist auch nicht so viel intelligenter: Ich nehme einfach den Flächeninhalt aller erzeugten Rechtecke, nehme daraus die Wurzel und habe ja somit die Seitenlänge des "perfekten" minimalen Quadrats.
Und wenn ich anfange, die Rechtecke nebeneinanderzusetzen, dann mache ich eine Art "Zeilemumbruch", sobald die Breite der Quadrate diese Seitenlänge überschritten hat und die nächsten Rechtecke werden dann darunter gesetzt. Dadurch kommen eigentlich ganz gute Anfangslösungen zustande (60% - 80%).

Randbemerkung: meine Startlösung wird erzeugt, indem alle Rechtecke strikt nebeneinander gesetzt werden

Das hatte ich am Anfang auch, aber irgendwie wurden die durch die Algorithmen erzeugten Lösungen nicht viel besser.

Mal eine Frage an dich: Wie hast du die move-Funktion eingebaut? Werden alle möglichen Positionen innerhalb des Feldes überprüft oder sucht das Rechteck nur in der näheren Umgebung nach besseren Positionen?

[hanneswernery]

Mein move sieht so aus, dass ich mir zunächst alle "interessanten Koordinaten" raussuche. Das sind freie Felder an Ecken, also ein freies Feld rechts neben einer oberen-rechten Ecke eines Rechtecks oder eins unterhalb der unteren-linken Ecke. Das sind also alle interessanten Positionen wo man ein Rechteck ansetzen würde. Dann wird das betrachtete Rechteck auf so eine interessante Koordinate gezwungen (überlappt also ggf) und alles entsprechend angepasst, dass es eine zulässige Lösung wird (andere Rechtecke verschoben). Ich vergleiche die Ergebnisse dieser interessanten Koordinaten und schaue welche die beste war.

Das hatte ich am Anfang auch, aber irgendwie wurden die durch die Algorithmen erzeugten Lösungen nicht viel besser.

Sollte es nicht egal sein, wie du anfängst - der Algorithmus kommt egal mit welchem Anfang auf eine Optimallösung?

Entspricht dein Permutationsaufbau (so nenne ich das jetzt mal) deiner Anfangsaufbau-Funktion? Ich kann mir kaum vorstellen, dass diese Zeilenumbruch Geschichte (auch wenn man alle Permutationen durchgeht) zur Optimallösung kommt

[Atlantaphoenix]

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.

Ich verstehe das folgendermaßen: Es soll eine kanonische Lösung erstellt werden anhand einer Liste von Rechtecken mithilfe einer von uns zu entwickelnden Regel (bei mir: Rechtecke mit Zeilenumbruch). Dann sollen Veränderungen in dieser Liste vorgenommen werden und mit dem gleichen Algorithmus eine neue kanonische Lösung erzeugt werden.

Sollte es nicht egal sein, wie du anfängst - der Algorithmus kommt egal mit welchem Anfang auf eine Optimallösung?

Theoretisch ja, ich vermute, dass mein move-Algorithmus zu schlecht ist.

Entspricht dein Permutationsaufbau (so nenne ich das jetzt mal) deiner Anfangsaufbau-Funktion?

Ja.

Ich kann mir kaum vorstellen, dass diese Zeilenumbruch Geschichte (auch wenn man alle Permutationen durchgeht) zur Optimallösung kommt

Die Lösungen sind im Vergleich zu den Geometriebasierten Algorithmen und Überlappungsalgorithmen bei mir deutlich besser. Ob es die Optimallösung ist, kann ich nicht sagen, aber ich verstehe die Programmieraufgabe so, dass wir mit verschiedenen Nachbarschaftsbeziehungen und Algorithmen unterschiedliche "Optimallösungen" bekommen sollen, mal besser und mal schlechter.

[hanneswernery]

Ich habe nun beide Neighbourhood Strategien laufen.

Mir ist auch aufefallen, dass die Strategien unterschiedliche Lösungen auswerfen. Ich notiere mir fleissig warum ^^

[Daniel Roth]

Ich habe nun beide Neighbourhood Strategien laufen.

Mir ist auch aufefallen, dass die Strategien unterschiedliche Lösungen auswerfen. Ich notiere mir fleissig warum ^^

Du meinst lokale Optima? Lokale Suche würde nur in einer exakten Nachbarschaft immer die gleiche optimale (globale) Lösung finden.

[Prof. Karsten Weihe]

Lokale Suche würde nur in einer exakten Nachbarschaft immer die gleiche optimale (globale) Lösung finden.

Achtung:
Es kann auch mehrere globale Optima geben. Bei verschiedenen Startlösungen läuft lokale Suche natürlich potentiell in unterschiedliche globale Optima.

KW