Geometry Based - Simulated Annealing/Tabusuche

Moderator: Optimierungsalgorithmen

KentenFina
Neuling
Neuling
Beiträge: 7
Registriert: 6. Mär 2015 13:10

Geometry Based - Simulated Annealing/Tabusuche

Beitrag von 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
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Geometry Based - Simulated Annealing/Tabusuche

Beitrag von Prof. Karsten Weihe »

KentenFina hat geschrieben: 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
Erstie
Erstie
Beiträge: 19
Registriert: 14. Sep 2013 02:51

Re: Geometry Based - Simulated Annealing/Tabusuche

Beitrag von TimBo »

Hi,


ich habe auch eine Frage zur geometriebasierten Nachbarschaft:
test.png
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
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Geometry Based - Simulated Annealing/Tabusuche

Beitrag von Prof. Karsten Weihe »

TimBo hat geschrieben: 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. 8)

KW

Antworten

Zurück zu „Optimierungsalgorithmen“