Geometry Based - Simulated Annealing/Tabusuche

[KentenFina]

Hallo,

ich hätte mal eine Frage zum Geometrie-basierten Ansatz. Als Nachbarn gibt es ja nur bessere Lösungen, weil ja eine Seite näher an die Mitte geschoben wird. Daher gibt es ja keine Nachbarn mehr wenn wir ein lokales Optimum erreicht haben. Folglich terminieren dann ja auch Simulated Annealing und Tabusuche zum gleichen Zeitpunkt wie die lokale Suche (ohne Nachbarn können sie ja auch nicht mehr an einen schlechteren Nachbarn gehen), oder liege ich mit dieser Annahme falsch?

Die Annahme verwirrt mich halt etwas, weil sich dadurch ja alle 3 Algorithmen für diese Nachbarschaft fast nicht unterscheiden (sie kommen alle nur bis zum ersten lokalen optimum).

Gruß Kenten

[Prof. Karsten Weihe]

ich hätte mal eine Frage zum Geometrie-basierten Ansatz. Als Nachbarn gibt es ja nur bessere Lösungen, weil ja eine Seite näher an die Mitte geschoben wird. Daher gibt es ja keine Nachbarn mehr wenn wir ein lokales Optimum erreicht haben. Folglich terminieren dann ja auch Simulated Annealing und Tabusuche zum gleichen Zeitpunkt wie die lokale Suche (ohne Nachbarn können sie ja auch nicht mehr an einen schlechteren Nachbarn gehen), oder liege ich mit dieser Annahme falsch?

Ich sehe ein, meine Formulierung war nicht in meinem Sinne. Selbstverständlich gibt es auch Nachbarn in die umgekehrte, schlechtere Richtung. Ich werde eine neue Version der Aufgabenstellung asap hochladen und per moodle-Mail ankündigen.

KW

[TimBo]

Hi,


ich habe auch eine Frage zur geometriebasierten Nachbarschaft:

test.png (4.54 KiB) 765 mal betrachtet

angenommen das rote Rechteck wurde als Kandidat für eine Nachbarschaft ausgewäht, da ich mich zufällig für den rechten Rand entschieden habe.
Nun darf ich das rote Rechteck nicht nach rechts verschieben. Aber ebenso kann ich es auch nicht nach oben / unten / links verschieben, da so Überlappungen entstehen würden.

Würde das Rechteck dann soweit nach (link/oben/unten) verschoben werden bis keine Kollision mehr existiert oder terminiert der Algorithmus in so einer Situation?

Natürlich würde ich noch oben unten und links nach Rechtecken suchen, aber der Einfachheit sieht es dort analog wie in der Grafik aus.

Liebe Grüße,
TimBo

[Prof. Karsten Weihe]

Nun darf ich das rote Rechteck nicht nach rechts verschieben. Aber ebenso kann ich es auch nicht nach oben / unten / links verschieben, da so Überlappungen entstehen würden.

Man kann ein Rechteck auch über andere Rechtecke hinweg auf Plätze verschieben, an denen es keine Überlappungen mehr gibt. Und die Verschiebung muss auch nicht achsenparallel sein.

KW