Tabusuche mit geometriebasierter Nachbarschaft

Moderator: Optimierungsalgorithmen

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von aileen »

Hallo,
Die Tabusuche ist ja feature-basiert, d.h. jede Lösung muss als Auswahl von features darstellbar sein. Bei der regelbasierten Nachbarschaft kann man dafür Paare (i, j) nehmen, was bedeutet Rechteck i befindet sich in der Permutation an Stelle j. Wie soll das aber bei der geometriebasierten Nachbarschaft gehen? Die einzige Idee, die ich habe, ist, dass man für jedes Rechteck angeben könnte, an welcher Position sich die linke obere Ecke befindet, dann wäre die Anzahl an features allerdings nicht mehr endlich, was ja aber eigentlich Voraussetzung ist. Sollen wir das trotzdem so machen? Oder soll in die Tabuliste aufgenommen werden, mit welcher Änderung die neue Lösung erzeugt wurde (also z.B. drehen des i-ten Rechtecks)?

Daniel Roth
Erstie
Erstie
Beiträge: 17
Registriert: 19. Apr 2013 17:44

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von Daniel Roth »

Soweit ich das sehe, ist die Menge der Features sehr wohl endlich. Alleine schon durch die Beschränkung, dass eine zulässige Lösung kanonisch sein muss, ergeben sich ja für jedes Rechteck immer nur bestimmt Positionen, an denen es platziert werden kann.
Würde man diese Einschränkung rausnehmen und würden wir uns nicht im ganzzahligem Raum aufhalten, dann wäre es theoretisch möglich, dass die lokale Suche niemals terminiert, da ein Rechteck am äußeren Rand mit immer kleineren Schritten in die Mitte bewegt werden könnte (falls es nicht an ein anderes Rechteck stößt). Da sich in jedem Schritt die Lösung verbessert, würde die Suche auch nicht terminieren.

Ja, in die Tabuliste kommt die Änderung, die an der zulässigen Lösung vorgenommen wurde. Wenn man Features so darstellst, wie du das machst, dann kann man allerdings keine Rotation darstellen. Eine Erweiterung des Modells auf z.B. (i, (x, y), isRotated) würde da denke ich Abhilfe schaffen.
Ansonsten noch aus Wikipedia dazu:
"Ausgehend vom ausgeführten Zug wird die Tabu-Liste aktualisiert. Je nach gewählter Tabu-Strategie kann zum Beispiel das Komplement des Zuges für eine bestimmte Anzahl an Iterationen tabuisiert werden."

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von aileen »

Erstmal dankeschön für die Antwort :)
Daniel Roth hat geschrieben:Soweit ich das sehe, ist die Menge der Features sehr wohl endlich. Alleine schon durch die Beschränkung, dass eine zulässige Lösung kanonisch sein muss, ergeben sich ja für jedes Rechteck immer nur bestimmt Positionen, an denen es platziert werden kann.
Stimmt, ich habe hier nicht daran gedacht, dass jede Lösung kanonisch sein soll.
Daniel Roth hat geschrieben: Eine Erweiterung des Modells auf z.B. (i, (x, y), isRotated) würde da denke ich Abhilfe schaffen.
Wofür steht bei dir denn das i & (x, y)? Rechteck i befindet sich an Position (x, y)? Würde es nicht doch reichen, nur (i, isRotated) in die Tabuliste aufzunehmen, wenn die neue Lösung nur durch Drehen des i-ten Rechtecks entstanden ist?
Jede Lösung lässt sich dann ja beschreiben durch eine gewisse Anzahl features aus der Menge {(i, isRotated), (i, j), (i, (x, y)) für alle i, j}, wobei (i, j) für i-tes Rechteck wurde mit j-tem Rechtecke getauscht & (i, (x, y)) i-tes Rechteck wurde an Position (x, y) verschoben bedeutet.


Ich habe noch eine Frage zur Tabu-Suche: Auf Wikipedia steht: Eine Lösung wird als die aktuelle gewählt, wenn sie die beste Lösung der Nachbarschaft darstellt und nicht als Tabu klassifiziert worden ist (Tabu-Kriterium).
Wenn man sich an Wikipedia hält muss man also theoretisch erst die komplette Nachbarschaft erzeugen, um dann die beste benachbarte Lösung auswählen zu können.
In unseren Folien steht: Taboo search always moves on to the neighbor of minimal cost.
In unserem Fall sind ja keine Kosten definiert, was so wie ich das sehe auch nicht möglich, ist, da per Definition die Kosten einer Lösung die Summe der Kosten der features sind, was hier denke ich nicht machbar ist.
Das heißt, wenn man ganz korrekt ist, wäre die Tabusuche so wie wir sie auf den Folien stehen haben gar nicht durchführbar oder?

Daniel Roth
Erstie
Erstie
Beiträge: 17
Registriert: 19. Apr 2013 17:44

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von Daniel Roth »

aileen hat geschrieben: Erstmal dankeschön für die Antwort
gern :)
aileen hat geschrieben: Wofür steht bei dir denn das i & (x, y)?
Die Menge {(i, (x, y), isRotated} ist die Menge der features. Die zulässige Lösung setzt sich demnach aus Rechtecken i zusammen, die sich an der Position (x, y) befinden und die rotiert sind oder nicht.
aileen hat geschrieben: Würde es nicht doch reichen, nur (i, isRotated) in die Tabuliste aufzunehmen, wenn die neue Lösung nur durch Drehen des i-ten Rechtecks entstanden ist?
Jap, in die Tabuliste kommen schließlich die Änderungen der Feasable Solution.
aileen hat geschrieben: Jede Lösung lässt sich dann ja beschreiben durch eine gewisse Anzahl features aus der Menge {(i, isRotated), (i, j), (i, (x, y)) für alle i, j}, wobei (i, j) für i-tes Rechteck wurde mit j-tem Rechtecke getauscht & (i, (x, y)) i-tes Rechteck wurde an Position (x, y) verschoben bedeutet.
Diese Menge würde ich eher als die Menge der möglichen Operationen beschreiben. Diese kann man der Tabuliste hinzufügen, um sich zu merken, welche Operationen in den nächsten Zügen nicht wiederholt werden soll.
aileen hat geschrieben: Ich habe noch eine Frage zur Tabu-Suche: Auf Wikipedia steht: Eine Lösung wird als die aktuelle gewählt, wenn sie die beste Lösung der Nachbarschaft darstellt und nicht als Tabu klassifiziert worden ist (Tabu-Kriterium).
Wenn man sich an Wikipedia hält muss man also theoretisch erst die komplette Nachbarschaft erzeugen, um dann die beste benachbarte Lösung auswählen zu können.
So habe ich das auch verstanden. Beim geometriebasierten Ansatz ist die Nachbarschaft noch relativ klein. Bei den Permutationen muss man sich halt Gedanken darüber machen, welche Operationen man auf der Permutation zulässt. Könnte mir vorstellen, dass die Nachbarschaft ein bisschen groß wird, wenn man sowohl swap als auch rotational shift zulässt.
aileen hat geschrieben: In unseren Folien steht: Taboo search always moves on to the neighbor of minimal cost.
In unserem Fall sind ja keine Kosten definiert, was so wie ich das sehe auch nicht möglich, ist, da per Definition die Kosten einer Lösung die Summe der Kosten der features sind, was hier denke ich nicht machbar ist.
Die Aufgabe ist ja, das Quadrat, das alle Rechtecke umschließt, zu minimieren. Die Kostenfunktion wäre dann also z.B. einfach die Seitlänge/Fläche des Quadrats.
Ich glaube die Kostenfunktionen, die wir in der Vorlesung hatten, bezogen sich immer auf konkrete Beispiele.

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von aileen »

Daniel Roth hat geschrieben:
Jap, in die Tabuliste kommen schließlich die Änderungen der Feasable Solution. ... Diese Menge würde ich eher als die Menge der möglichen Operationen beschreiben. Diese kann man der Tabuliste hinzufügen, um sich zu merken, welche Operationen in den nächsten Zügen nicht wiederholt werden soll.
Also in der Theorie hatte ich es eher so verstanden, dass in die Tabuliste das feature reinkommt, welches benötigt wird, um von der alten auf die neue Lösung zu kommen, also dass die Tabuliste selbst aus features besteht. In der Praxis ist es denke ich aber eher sinnvoll die Änderungen in die Liste aufzunehmen, so wie du das auch sagst.
Daniel Roth hat geschrieben: Die Aufgabe ist ja, das Quadrat, das alle Rechtecke umschließt, zu minimieren. Die Kostenfunktion wäre dann also z.B. einfach die Seitlänge/Fläche des Quadrats.
Ich glaube die Kostenfunktionen, die wir in der Vorlesung hatten, bezogen sich immer auf konkrete Beispiele.
Die Seitenlänge des Quadrats entspricht ja der objective-function.
So wie wir den Algorithmus auf den Folien haben, verstehe ich das so, dass jedes feature eine Kostenfunktion haben muss & die Kostenfunktion einer Lösung die Summe der Kostenfunktion der features der Lösung ist. Da im Algorithmus steht "Taboo search always moves on to the neighbor of minimal cost", bin ich davon ausgegangen, dass die Tabusuche nur auf Probleme anzuwenden ist, bei denen den features eben so eine Kostenfunktion zugeordnet werden kann, was nicht für alle Probleme gegeben ist.
Die so definierte Kostenfunktion einer Lösung ist denke ich äquivalent zur objective-function, sodass der Algorithmus natürlich trotzdem angewendet werden könnte, auch wenn keine Kostenfunktion der features vorhanden ist, nur sehe ich das auf den Folien eben als Voraussetzung..

Daniel Roth
Erstie
Erstie
Beiträge: 17
Registriert: 19. Apr 2013 17:44

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von Daniel Roth »

aileen hat geschrieben: Also in der Theorie hatte ich es eher so verstanden, dass in die Tabuliste das feature reinkommt, welches benötigt wird, um von der alten auf die neue Lösung zu kommen, also dass die Tabuliste selbst aus features besteht. In der Praxis ist es denke ich aber eher sinnvoll die Änderungen in die Liste aufzunehmen, so wie du das auch sagst.
Also zumindest auf den Folien ist von den "most recent changes of features" die Rede. Ich würde eher noch das Komplement der Änderung in die Liste aufnehmen. Wenn ich ein Rechteck von A nach B bewege, dann will ich ja in Zukunft verhindern, dass ich es wieder zurück bewege, also von B nach A.
aileen hat geschrieben: Die so definierte Kostenfunktion einer Lösung ist denke ich äquivalent zur objective-function, sodass der Algorithmus natürlich trotzdem angewendet werden könnte, auch wenn keine Kostenfunktion der features vorhanden ist, nur sehe ich das auf den Folien eben als Voraussetzung..
Sowohl objective- als auch cost-functions bilden ja einfach nur von einer Domäne auf einen Zahlenwert ab, weshalb ich da sowieso nicht unterscheiden würde. Habs trotzdem noch mal gegoogelt und zumindest im englischen Wikipedia steht unter Mathematical_optimization
The function f is called, variously, an objective function, a loss function or cost function (minimization),[2] a utility function (maximization), a fitness function (maximization), or, in certain fields, an energy function, or energy functional. A feasible solution that minimizes (or maximizes, if that is the goal) the objective function is called an optimal solution.

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von aileen »

Daniel Roth hat geschrieben: Also zumindest auf den Folien ist von den "most recent changes of features" die Rede. Ich würde eher noch das Komplement der Änderung in die Liste aufnehmen. Wenn ich ein Rechteck von A nach B bewege, dann will ich ja in Zukunft verhindern, dass ich es wieder zurück bewege, also von B nach A.
Und noch genau auf der selben Folie steht "As long as a change is "kept in mind", the search must not undo this
change. -> Must not drop a feature recently inserted nor reinsert a feature recently dropped."
Hier wird für nicht nicht gerade deutlich was von beidem den nun in der Tabuliste stehen soll, in der Umsetzung spielt das aber wohl eh keine Rolle.
Daniel Roth hat geschrieben: Sowohl objective- als auch cost-functions bilden ja einfach nur von einer Domäne auf einen Zahlenwert ab, weshalb ich da sowieso nicht unterscheiden würde.
Ich persönlich würde hier auch nicht unterscheiden, die Frage, die ich mir stelle, ist nur, ob Herr Weihe hier eine Unterscheidung fordert (nicht konkret auf unsere Aufgabe bezogen, sondern allgemein in der Tabusuche)..

Richard_2013
Neuling
Neuling
Beiträge: 6
Registriert: 26. Mai 2014 14:51

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von Richard_2013 »

Daniel Roth hat geschrieben:Wenn ich ein Rechteck von A nach B bewege, dann will ich ja in Zukunft verhindern, dass ich es wieder zurück bewege, also von B nach A.
Und deshalb würde man in dem Fall der Verschiebung eines Rechtecks von Position A nach Position B in der Tabu-Liste speichern, dass dieses Rechteck nicht wieder an Position A stehen darf.

Doch was macht man nun im Falle der Vertauschung zweier Rechtecke (Rechteck1 an Position1 mit Rechteck2 an Position2)?
Darf man dann sozusagen zwei features (Rechteck1 darf nicht wieder an Position1 kommen, Rechteck2 darf nicht wieder an Position2 kommen) in die Tabu-Liste aufnehmen?

Daniel Roth
Erstie
Erstie
Beiträge: 17
Registriert: 19. Apr 2013 17:44

Re: Tabusuche mit geometriebasierter Nachbarschaft

Beitrag von Daniel Roth »

Richard_2013 hat geschrieben: Und deshalb würde man in dem Fall der Verschiebung eines Rechtecks von Position A nach Position B in der Tabu-Liste speichern, dass dieses Rechteck nicht wieder an Position A stehen darf.

Doch was macht man nun im Falle der Vertauschung zweier Rechtecke (Rechteck1 an Position1 mit Rechteck2 an Position2)?
Darf man dann sozusagen zwei features (Rechteck1 darf nicht wieder an Position1 kommen, Rechteck2 darf nicht wieder an Position2 kommen) in die Tabu-Liste aufnehmen?
Das ist das Problem, wenn man in die Tabuliste nur Positionen von Rechtecken bzw Features speichert. Bei Vertauschung nimmt man in die Tabuliste ein Objekt auf, das kennzeichnet, dass die Rechteck1 mit Rechteck2 vertauscht wurden. Das ist kein Feature!

Genauso bei der Verschiebung von Rechteck1 an Position A nach Position B. Dann speichert man ein Objekt, dass genau diese Verschiebung beschreibt. Man will ja in Zukunft verhindern, dass das Objekt von Position B wieder nach Position A bewegt wird und nicht, dass es überhaupt nicht mehr nach Position A gelangt.

Aber ich denke man kann auch die Positionen speichern, wie du das vorgeschlagen hast. Dann musst du in der Tat 2 Features aufnehmen. Das ganze wird nur dann bei Rotation problematisch.

Antworten

Zurück zu „Optimierungsalgorithmen“