"Überlappungen teilweise zulassen"

[Richard_2013]

Hallo,

ich bin soweit fertig mit den ersten beiden Nachbarschaftsformen und jetzt fehlt nur noch die regelbasierte Nachbarschaft mit Überlappungen.

Dabei stell ich mir die Frage, an welcher Stelle der Parameter, der den zulässigen Prozentsatz an Überlappungen regelt, kontrolliert und verändert wird.
Z.B. die lokale Suche fragt meine Probleminstanz ja "von außen" in jeder Iteration nach einem besseren Nachbarn, also wann und wo wird der angesprochene Parameter, der die Überlappungen kontrolliert, verändert? Die lokale Suche an sich hat mit diesem Parameter schließlich selbst nichts zu tun.

Oder ist "Im Laufe der Zeit reduziert sich der Prozentsatz, und Verletzungen werden hart in der Zielfunktion bestraft." so zu verstehen, dass z.B. die lokale Suche mehrmals mit unterschiedlichen Prozentsätzen, die dann jeweils während eines Durchlaufs der lokalen Suche konstant bleiben, auf ein und derselben Probleminstanz ausgeführt wird?

Und außerdem frage ich mich: Was soll passieren, wenn die lokale Suche an einer Stelle keinen besseren Nachbarn findet und deshalb abbricht, aber der Parameter z.B. gerade bei 50% liegt? Dann ist ja nicht sichergestellt, dass die aktuelle Lösung überlappungsfrei ist, aber gleichzeitig geht es auch bzgl. der Nachbarschaft nicht weiter.


Ich hoffe die Problematik ist klar geworden.
Danke schon einmal.

[Daniel Roth]

also wann und wo wird der angesprochene Parameter, der die Überlappungen kontrolliert, verändert?

Ich hab das so gemacht, dass er immer bevor nach einer anderen zulässigen Lösung gesucht wird, der Parameter gesenkt wird. Was evtl. auch gehen würde wäre, wenn man ihn am Anfang einmal und dann immer wenn eine bessere Lösung gefunden wurde herabsetzt. So müsste garantiert sein, dass eine bessere Lösung gefunden wird und wenn man diese hat, muss man weiter garantieren, dass beim nächsten Suchlauf wieder eine bessere gefunden wird. Das ganze so lange, bis der Parameter auf 0% ist.

dass z.B. die lokale Suche mehrmals mit unterschiedlichen Prozentsätzen, die dann jeweils während eines Durchlaufs der lokalen Suche konstant bleiben, auf ein und derselben Probleminstanz ausgeführt wird?

Wie meinst du das mit auf derselben Probleminstanz? Also während nach einer zulässigen Lösung gesucht wird, würde ich den Parameter konstant lassen.

Was soll passieren, wenn die lokale Suche an einer Stelle keinen besseren Nachbarn findet und deshalb abbricht, aber der Parameter z.B. gerade bei 50% liegt?

Wenn du Überlappungen bestrafst (in der Kostenfunktion), sollte die lokale Suche immer ein besseres Ergebnis finden, solange es noch Überlappungen gibt.

[Richard_2013]

dass z.B. die lokale Suche mehrmals mit unterschiedlichen Prozentsätzen, die dann jeweils während eines Durchlaufs der lokalen Suche konstant bleiben, auf ein und derselben Probleminstanz ausgeführt wird?

Wie meinst du das mit auf derselben Probleminstanz? Also während nach einer zulässigen Lösung gesucht wird, würde ich den Parameter konstant lassen.

Ich meinte mit "Probleminstanz" eine Instanz des "Rechteckplatzierungsproblems", also letztendlich eine Menge von gegebenen Rechtecken. Das hat sich jetzt schon dank deines Kommentars geklärt, wonach die lokale Suche, wenn sie nach einem besseren Nachbarn sucht, der Parameter während dieser konkreten Iteration konstant bleibt.

Was soll passieren, wenn die lokale Suche an einer Stelle keinen besseren Nachbarn findet und deshalb abbricht, aber der Parameter z.B. gerade bei 50% liegt?

Wenn du Überlappungen bestrafst (in der Kostenfunktion), sollte die lokale Suche immer ein besseres Ergebnis finden, solange es noch Überlappungen gibt.

Stimmt, das sollte gegeben sein, aber dafür kommt es darauf an wie stark diese Überlappungen bestraft werden, richtig?
Hast du Überlappungen pauschal bestraft (also die Anwesenheit von Überlappungen, egal wie viele es davon gerade gibt und wie groß die überlappenden Flächen sind) oder ist der Wert, um den die Zielfunktion wegen der Überlappungen erhöht wird, von der Größe der überlappenden Flächen abhängig?
Zur Zeit bin ich nämlich der Meinung, dass ich nur sicherstellen kann, dass es immer einen besseren Nachbarn gibt (solange Überlappungen vorhanden sind), wenn ich Überlappungen pauschal bestrafe. Denn ich werde, so wie es jetzt aussieht, nicht sicherstellen, dass immer auch ein Nachbar ohne Überlappungen in der Nachbarschaft vorhanden ist.


Vielen Dank auf jeden Fall für deine Antwort. Das hat mir schon viel weitergeholfen.

[Daniel Roth]

Hast du Überlappungen pauschal bestraft (also die Anwesenheit von Überlappungen, egal wie viele es davon gerade gibt und wie groß die überlappenden Flächen sind) oder ist der Wert, um den die Zielfunktion wegen der Überlappungen erhöht wird, von der Größe der überlappenden Flächen abhängig?

Ich habe die Kostenfunktion direkt vom Überlappungsfaktor abhängig gemacht. Bsp. obj(x) = Seitenlänge des minimalen Quadrats * (Überlappungsfaktor+1)

Zur Zeit bin ich nämlich der Meinung, dass ich nur sicherstellen kann, dass es immer einen besseren Nachbarn gibt (solange Überlappungen vorhanden sind), wenn ich Überlappungen pauschal bestrafe.

Der Nachbar ist immer dann besser als der vorherige, wenn die Kostenfunktion einen niedrigeren Wert ausgibt. Wenn du diese abhängig vom Überlappungsfaktor hast, dann sollte der Wert bei weniger Überlappungen in den meisten Fällen besser sein.

Denn ich werde, so wie es jetzt aussieht, nicht sicherstellen, dass immer auch ein Nachbar ohne Überlappungen in der Nachbarschaft vorhanden ist.

Wenn der Überlappungsfaktor auf 0 ist, dann muss deine Regel, die die Rechtecke anordnet, doch dafür sorgen, dass es keine Überlappungen gibt. Ich kann mir sonst zumindest nicht vorstellen, wie man das effizient lösen kann. Vor allem weil die Nachbarschaft ja so unglaublich statisch ist. Du kannst nur durch Änderung der Permutation zu neuen zulässigen Lösungen gelangen. Da ist meiner Meinung nach nicht viel Spielraum, das anders zu machen.

Habe eben noch mal die Aufgabestellung gelesen. Da geht das tatsächlich so hervor, dass trotz Überlappungsfaktor von 0 Nachbarschaften gefunden werden können, in denen sich Rechtecke überlappen können und dass das Ganze nur mit der Kostenfunktion geregelt werden soll. Ich wüsste jetzt nicht, wie man das auf einem regelbasierten Ansatz umsetzten sollte.

[Richard_2013]

Ich habe die Kostenfunktion direkt vom Überlappungsfaktor abhängig gemacht. Bsp. obj(x) = Seitenlänge des minimalen Quadrats * (Überlappungsfaktor+1)

Ich bin mir nicht sicher, ob das eine zulässige Zielfunktion ist, da die Aufgabenstellung fordert, dass "Verletzungen" hart bestraft werden ("und Verletzungen werden hart in der Zielfunktion bestraft"). Mit der von Dir gegebenen Zielfunktion würde man ja auch erlaubte Überlappungen bestrafen:
Z.B.: aktueller Überlappungsfaktor = 50% und eine Lösung weißt nur Überlappungen von maximal 40% auf, dann sollten diese Überlappungen meines Verständnisses nach nicht bestraft werden.

Habe eben noch mal die Aufgabestellung gelesen. Da geht das tatsächlich so hervor, dass trotz Überlappungsfaktor von 0 Nachbarschaften gefunden werden können, in denen sich Rechtecke überlappen können und dass das Ganze nur mit der Kostenfunktion geregelt werden soll.

So habe ich das jetzt auch verstanden.
Das bedeutet dann, dass die Nachbarschaft unabhängig vom aktuellen Überlappungsfaktor ist. Es ist also egal, ob von einer aktuellen Lösung ausgehend mit Überlappungsfaktor 50% oder 40% Nachbarn erzeugt werden, in beiden Fällen ist die Nachbarschaft identisch. (Die Wahl des z.B. besten Nachbarn ist natürlich nicht unabhängig vom Überlappungsfaktor.)
Dann ist meiner Meinung nach aber nicht garantiert, dass am Ende eine überlappungsfreie Lösung gefunden wird.

Der Nachbar ist immer dann besser als der vorherige, wenn die Kostenfunktion einen niedrigeren Wert ausgibt. Wenn du diese abhängig vom Überlappungsfaktor hast, dann sollte der Wert bei weniger Überlappungen in den meisten Fällen besser sein.

Kannst du mit deiner Implementierung denn garantieren, dass immer ein besserer Nachbar gefunden wird, solange es Überlappungen gibt?


Vielleicht sollten wir auch mal klären, was wir unter dem Überlappungsfaktor konkret verstehen, um Missverständnissen vorzubeugen. Ich wollte als Überlappungsfaktor einer aktuellen Lösung das Maximum über alle vorhandenen prozentualen Überlappungen zweier Rechtecke verwenden.

[Daniel Roth]

Ich bin mir nicht sicher, ob das eine zulässige Zielfunktion ist, da die Aufgabenstellung fordert, dass "Verletzungen" hart bestraft werden ("und Verletzungen werden hart in der Zielfunktion bestraft"). Mit der von Dir gegebenen Zielfunktion würde man ja auch erlaubte Überlappungen bestrafen:
Z.B.: aktueller Überlappungsfaktor = 50% und eine Lösung weißt nur Überlappungen von maximal 40% auf, dann sollten diese Überlappungen meines Verständnisses nach nicht bestraft werden.

Ok, dann würde ich die Funktion von der aktuellen Verletzung abhängig machen.
Seitenlänge des minimalen Quadrats * (1 + (Tatsächlicher Überlappungsgrad - Überlappungsfaktor))

Kannst du mit deiner Implementierung denn garantieren, dass immer ein besserer Nachbar gefunden wird, solange es Überlappungen gibt?

Also wenn man von meiner ursprünglichen Kostenfunktion
Seitenlänge des minimalen Quadrats * (Überlappungsfaktor+1)
ausgeht, dann nein, denn eine neue Lösung mit niedrigerem Überlappungsfaktor kann immer noch eine Erhöhung der Seitenlänge hervorrufen, die so stark ist, dass dennoch ein schlechterer Kostenwert rauskommt. Da es jedoch in den meisten Fällen keine so starke Veränderung des minimalen Quadrats gibt, ist dieser Fall eher unwahrscheinlich. Zur Not passt man die Kostenfunktion an und bestraft Überlappungen härter.

[Richard_2013]

Kannst du mit deiner Implementierung denn garantieren, dass immer ein besserer Nachbar gefunden wird, solange es Überlappungen gibt?

Also wenn man von meiner ursprünglichen Kostenfunktion
Seitenlänge des minimalen Quadrats * (Überlappungsfaktor+1)
ausgeht, dann nein, denn eine neue Lösung mit niedrigerem Überlappungsfaktor kann immer noch eine Erhöhung der Seitenlänge hervorrufen, die so stark ist, dass dennoch ein schlechterer Kostenwert rauskommt. Da es jedoch in den meisten Fällen keine so starke Veränderung des minimalen Quadrats gibt, ist dieser Fall eher unwahrscheinlich. Zur Not passt man die Kostenfunktion an und bestraft Überlappungen härter.

Vor allen Dingen kann doch folgende Situation auftreten:
erlaubter Überlappungsfaktor = 50% und die aktuelle Lösung, deren Nachbarschaft nach einem besseren Nachbarn durchsucht wird, weißt nur Überlappungen von maximal 30% (-> ihr Zielfunktionswert wird wegen der Überlappungen nicht bestraft, da sie innerhalb es erlaubten Rahmens (z.B. 5 Prozentpunkte höher in der vorherigen Iteration) lagen), aber ihre Nachbarn haben Überlappungen von >50% und deshalb wird deren Zielfunktionswert bestraft, in Folge dessen sie dann alle schlechter sind, als die aktuelle Lösung. -> es wird kein besserer Nachbar gefunden -> lokale Suche terminiert mit einer Lösungen, die Überlappungen beinhaltet

[Daniel Roth]

Vor allen Dingen kann doch folgende Situation auftreten:
erlaubter Überlappungsfaktor = 50% und die aktuelle Lösung, deren Nachbarschaft nach einem besseren Nachbarn durchsucht wird, weißt nur Überlappungen von maximal 30% (-> ihr Zielfunktionswert wird wegen der Überlappungen nicht bestraft, da sie innerhalb es erlaubten Rahmens (z.B. 5 Prozentpunkte höher in der vorherigen Iteration) lagen), aber ihre Nachbarn haben Überlappungen von >50% und deshalb wird deren Zielfunktionswert bestraft, in Folge dessen sie dann alle schlechter sind, als die aktuelle Lösung. -> es wird kein besserer Nachbar gefunden -> lokale Suche terminiert mit einer Lösungen, die Überlappungen beinhaltet

Seitenlänge des minimalen Quadrats * (1 + (Tatsächlicher Überlappungsgrad - Überlappungsfaktor))

also in dem Bsp. hat man im Schritt 1 den Überlappungsfaktor von 0,5 und tatsächlichen Überlappungsgrad von 0,3 also sind die Kosten
a * (1 + (0,3 - 0,5)) = a * 0.8

im Schritt 2 ändert sich nur der Überlappungsfaktor auf 0,45
a * (1 + (0,3 - 0,45)) = a * 0.85

Ok das wäre natürlich wenig optimal. Ich schlage vor die Distanz von Tatsächlichen Überlappungsgrad und Überlappungsfaktor zu bestrafen

Seitenlänge des minimalen Quadrats * (1 + |Tatsächlicher Überlappungsgrad - Überlappungsfaktor|)

1.) a * (1 + |0,3 - 0,5|) = a * 1.2
2.) a * (1 + |0,3 - 0,45|) = a * 1.15

Dann bestraft man jedoch wieder eine bessere Lösung.

Ich hätte noch die Idee, dass man dafür sorgt, dass immer Überlappungsfaktor <= tatsächlicher Überlappungsgrad gilt. Wenn der Überlappungsfaktor runtergesetzt wird, dann setzt man immer um einen konstanten Wert - tatsächlichen Überlappungsfaktor runter. Dann kann man auch die ursprüngliche Kostenfunktion verwenden.
Das sollte laut Aufgabenstellung in Ordnung sein und es ist (praktisch) immer möglich eine bessere Lösung zu finden.