Regelbasierte Nachbarschaft

Moderator: Optimierungsalgorithmen

nairolf
Erstie
Erstie
Beiträge: 18
Registriert: 31. Jul 2011 13:58

Regelbasierte Nachbarschaft

Beitrag von nairolf »

Hallo zusammen,

könnte mir einer bitte die Aufgabenstellung der Regelbasierten Nachbarschaft in anderen Worten (als auf dem Arbeitsblatt) erklären.
Ich verstehe nicht wirklich was man genau unter "Permutationen" hier in diesem Kontext verstehen soll. Kann mir einer ein kleines konkretes Beispiel geben? Insbesondere der Satzteil "Anstelle von zulässigen Lösungen [..]" verwirrt mich hier sehr :/

Und was ist hier unter "kanonische Lösung" genau zu verstehen? Ich kann mir hier momentan nicht wirklich was darunter vorstellen.

Schon mal besten Dank!

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Regelbasierte Nachbarschaft

Beitrag von Prof. Karsten Weihe »

nairolf hat geschrieben: Ich verstehe nicht wirklich was man genau unter "Permutationen" hier in diesem Kontext verstehen soll
Kann mir einer ein kleines konkretes Beispiel geben? Insbesondere der Satzteil "Anstelle von zulässigen Lösungen [..]" verwirrt mich hier sehr :/
Nehmen wir an, Sie haben N Rechtecke zu platzieren. Dann sollen Ihre Suchalgorithmen auf den Permutationen von 1..N arbeiten. Auf Folie 96 finden Sie das Thema "Nachbarschaften auf Permutationen". Aus einer solchen Permutation muss dann noch eine Platzierung der N Rechtecke generiert werden. Der Gedanke ist natürlich, dass die Rechtecke in der Reihenfolge der Permutation nacheinander "geschickt" platziert werden.
nairolf hat geschrieben: Und was ist hier unter "kanonische Lösung" genau zu verstehen? Ich kann mir hier momentan nicht wirklich was darunter vorstellen.
Sorry, dieser Begriff ist aus Versehen aus dem letzten Jahr stehengeblieben; können Sie ignorieren.

KW

nairolf
Erstie
Erstie
Beiträge: 18
Registriert: 31. Jul 2011 13:58

Re: Regelbasierte Nachbarschaft

Beitrag von nairolf »

Das heißt aber doch, dass diese Permutationen gerade zugelassene Lösungen sind oder nicht?

Habe ich das richtig verstanden, dass zB meine Startlösung als erste Permutation angesehen wird. Diese Permutation soll mithilfe von gewissen Regeln verändert werden (zB. durch Vertauschen oder Drehen von Rechtecken) dass eine neue Permutation (=Lösung) entsteht?

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Regelbasierte Nachbarschaft

Beitrag von Prof. Karsten Weihe »

nairolf hat geschrieben:Das heißt aber doch, dass diese Permutationen gerade zugelassene Lösungen sind oder nicht?
Sie haben einen Algorithmus zu entwickeln, der aus jeder Permutation eine zulässige Lösung (also Platzierung) generiert. Ich würde von der durch diese Permutation induzierten Platzierung sprechen, um das Verhältnis von Permutationen und Platzierungen zu beschreiben.

nairolf hat geschrieben: Habe ich das richtig verstanden, dass zB meine Startlösung als erste Permutation angesehen wird. Diese Permutation soll mithilfe von gewissen Regeln verändert werden (zB. durch Vertauschen oder Drehen von Rechtecken) dass eine neue Permutation (=Lösung) entsteht?
Ich denke (hoffe), es wird verständlicher, wenn ich es so formuliere: Sie haben keine Startlösung, sondern eine Startpermutation. Wie jede andere Permutation, so induziert auch diese eine gewisse Platzierung, die Sie dann Startlösung nennen können, wenn Sie wollen.

Die Permutationen durchlaufen Ihre drei lokalen Suchalgorithmen stellvertretend für die induzierten Platzierungen. Nachbarschaftsoperationen sind daher auf den Permutationen implementiert. Der Zielfunktionswert einer Permutation ist der Zielfunktionswert der Platzierung, die aus ihr generiert wird.

Das ist ähnlich wie bei genetischen Algorithmen in der Vorlesung: Dort durchlaufen die Stringpräsentationen stellvertretend für die induzierten zulässigen Lösungen die Suche, und der Zielfunktionswert einer Stringrepräsentationen ist gleich dem Zielfunktionswert der induzierten zulässigen Lösung.

Klarer geworden?

KW

nairolf
Erstie
Erstie
Beiträge: 18
Registriert: 31. Jul 2011 13:58

Re: Regelbasierte Nachbarschaft

Beitrag von nairolf »

Hmm... so ganz klar ist das mit irgendwie immer noch nicht. Ich steh grad wohl ziemlich auf dem Schlauch :(

Angenommen ich hätte jetzt eine Startpermutation. Diese arbeitet auf den N Rechtecken und es entsteht eine gewisse Platzierung der Rechtecke. Richtig soweit?
Wie sieht aber so eine Permutation aus? Ist das eine einfache Vorschrift, wie die Rechtecke zu platzieren sind (zB. alle nebeneinander; wäre das eine Permutation??))?

Was geschieht dann mit dieser Platzierung? Was versteht man genau unter
Die Permutationen durchlaufen Ihre drei lokalen Suchalgorithmen stellvertretend für die induzierten Platzierungen.
Die Algorithmen erhalten doch eine zulässige Lösung (induzierte Platzierung) und versuchen, darauf aufbauend, eine optimale Lösung zu finden...
... diese "Permutationen" machen mich grad voll kirre :/

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Regelbasierte Nachbarschaft

Beitrag von Prof. Karsten Weihe »

nairolf hat geschrieben: Wie sieht aber so eine Permutation aus?
So wie Sie es aus der Mathematik kennen (sollten). Zum Beispiel ist (6,3,4,7,1,5,2) eine Permutation von 1..7. Synonyme sind Umordnung, Reihung, Reihenfolge.

KW

Antworten

Zurück zu „Optimierungsalgorithmen“