[erledigt] Überlappungen teilweise zulassen in regelbasierter Nachbarschaft

Moderator: Optimierungsalgorithmen

Daniel2357
Neuling
Neuling
Beiträge: 4
Registriert: 16. Mai 2013 14:31

[erledigt] Überlappungen teilweise zulassen in regelbasierter Nachbarschaft

Beitrag von Daniel2357 » 3. Apr 2016 13:14

Hallo,

ich bin mir nicht sicher, wie wir in der regelbasierten Nachbarschaft Überlappungen zulassen sollen.
Die Nachbarschaft verändert ja nur eine Permutation und diese hat ja kein Konzept von Überlappungen.

Ich könnte mir jetzt vorstellen, dass man bei der Platzierung der Rechtecke basierend auf der Permutation eine gewisse
maximale Überlappung zulässt. Aber dann macht die Anmerkung in der Aufgabenstellung, dass die Algorithmen ausreichend lange mit 0% Überlappung laufen müssen, meiner Meinung nach keinen Sinn, denn bei 0% zulässiger Überlappung werden die Rechtecke dann
auch automatisch überlappungsfrei plaziert. Außerdem müssen wir Überlappungen dann auch nicht in der Zielfunktion bestrafen.

Für mich macht es mehr Sinn Überlappungen in der geometriebasierten Nachbarschaft zuzulassen.
Da können Rechtecke vom Rand ins Innere bewegt werden ohne sich Gedanken um Überlappungen mit anderen Rechtecken zu machen
und die entstehende Überlappung kann dann in der Zielfunktion bestraft werden. Um am Ende eine überlappungsfreie Lösung zu bekommen,
muss man die Algorithmen dann ausreichend lange laufen lassen und sich überlegen, wie man die bestehenden Überlappungen
wieder auflösen kann. Die Anmerkung passt also auch.
Zuletzt geändert von Daniel2357 am 5. Apr 2016 18:30, insgesamt 1-mal geändert.

Daniel2357
Neuling
Neuling
Beiträge: 4
Registriert: 16. Mai 2013 14:31

Re: Überlappungen teilweise zulassen in regelbasierter Nachbarschaft

Beitrag von Daniel2357 » 5. Apr 2016 18:30

Hat sich erledigt. Ich habe jetzt anhand der Permutation die Rechtecke mit einer gewissen Überlappung platziert.

Benutzeravatar
mmi1991
Computerversteher
Computerversteher
Beiträge: 349
Registriert: 20. Okt 2011 18:46
Wohnort: Hattersheim

Re: [erledigt] Überlappungen teilweise zulassen in regelbasierter Nachbarschaft

Beitrag von mmi1991 » 6. Apr 2016 16:05

Ich verstehe es auch nicht; gegeben eine Permutation sollen ja die Rechtecke gemäß der Regel platziert werden. Selbst wenn in einer vorigen Iteration eine Permutation mit mehr Überlappung erlaubt war, heißt das ja nicht, dass wir in dieser Iteration dieselbe Permutation haben, also die vorherige Platzierung irgendwo wiederverwenden können.
Oder anders gesagt: Jede Platzierung nach der Regel gegeben einer Permutation ist doch unabhängig von jeder vorherigen, oder?
Oder hast du einen Loop innerhalb der regelbasierten Permutation, die irgendwie wieder die Zielfunktion benutzt?
Ich bin verwirrt.
Ophasentutor SoSe 2014, WiSe 2015/16
Alle Angaben wie immer ohne Gewähr

Daniel2357
Neuling
Neuling
Beiträge: 4
Registriert: 16. Mai 2013 14:31

Re: [erledigt] Überlappungen teilweise zulassen in regelbasierter Nachbarschaft

Beitrag von Daniel2357 » 9. Apr 2016 18:27

mmi1991 hat geschrieben:Selbst wenn in einer vorigen Iteration eine Permutation mit mehr Überlappung erlaubt war, heißt das ja nicht, dass wir in dieser Iteration dieselbe Permutation haben, also die vorherige Platzierung irgendwo wiederverwenden können.
Aber wir haben eine ähnliche Permutation und deshalb vielleicht eine ähnliche Platzierung.
mmi1991 hat geschrieben:Oder anders gesagt: Jede Platzierung nach der Regel gegeben einer Permutation ist doch unabhängig von jeder vorherigen, oder?
Ja.

Es hat sich bei mir auch rausgestellt, dass diese Nachbarschaft nicht besonders gut funktioniert. Also ist das vielleicht nicht der beste Ansatz.
Wenn du noch weitere Fragen hast, würde ich an deiner Stelle wahrscheinlich besser einen neuen Thread aufmachen. Dann ist es klarer, dass das Problem noch nicht erledigt ist.

Antworten

Zurück zu „Optimierungsalgorithmen“