Tabu-Suche

[Richard_2013]

Hallo,

ist es legitim im Fall der Tabu-Suche mit regelbasierter Nachbarschaft als feature, das nach einer Iteration in die Tabu-Liste aufgenommen wird, die komplette Permutation der Rechtecke zu verwenden?

Ich erzeuge Zur Zeit bei der regelbasierten Nachbarschaft einen Nachbarn, indem ich die Position zweier Rechtecke in einer Permutation der Rechtecke miteinander vertausche.
z.B. [1,2,3,4,5] -> [1,5,3,4,2], wobei ich dann [1,2,3,4,5] in die Tabu-Liste aufnehmen würde.


Eine zweite Frage wär noch folgendes:
Ist es sogar erlaubt eine komplette Anordnung der Rechtecke (also für jeden Rechteck seine Position und Orientierung) als feature für die Tabu-Liste zu benutzen? Dann könnte man diese Art von feature nämlich sogar für alle Nachbarschaftsarten verwenden.


Vielen Dank für jede Hilfe.

[Daniel Roth]

ist es legitim im Fall der Tabu-Suche mit regelbasierter Nachbarschaft als feature, das nach einer Iteration in die Tabu-Liste aufgenommen wird, die komplette Permutation der Rechtecke zu verwenden?

Ich erzeuge Zur Zeit bei der regelbasierten Nachbarschaft einen Nachbarn, indem ich die Position zweier Rechtecke in einer Permutation der Rechtecke miteinander vertausche.
z.B. [1,2,3,4,5] -> [1,5,3,4,2], wobei ich dann [1,2,3,4,5] in die Tabu-Liste aufnehmen würde.

Wenn du nicht die Änderung von Features aufnehmen willst (in deinem Bsp. wäre dass sowas wie swap(1, 4)), dann wäre das wohl noch der sinnvollste Ansatz. Genauer betrachtet macht das sogar mehr Sinn, als Änderungen aufzunehmen, da man ja tatsächlich vermeiden will, dass eine bisher gesehen Permutation wieder erreicht wird.

Eine zweite Frage wär noch folgendes:
Ist es sogar erlaubt eine komplette Anordnung der Rechtecke (also für jeden Rechteck seine Position und Orientierung) als feature für die Tabu-Liste zu benutzen? Dann könnte man diese Art von feature nämlich sogar für alle Nachbarschaftsarten verwenden.

Ich stell mir das bei der regelbasierten Nachbarschaft etwas schwierig vor. Man weiß ja, bevor man die Regel anwendet, nicht, an welcher Position die Rechtecke sich befinden werden. D.h. man müsste jedes mal die Regel komplett anwenden lassen, nur um festzustellen, ob die feasable Solution nicht vllt. doch schon in der Tabuliste ist. Dann ist der Vergleich zwischen 2 feasable Solutions recht aufwendig, da im schlimmst Fall jedes Rechteck mit dem anderen verglichen werden muss. Das ganze hält sich noch im Rahmen, jedoch musst du bedenken, dass es sehr oft einen Vergleich mit allen Einträgen der Tabuliste gibt.
Ein weiters Problem ist, dass jedesmal, wenn du einen Eintrag in die Tabuliste einfügen willst, du eine Kopie aller Rechtecke vornehmen musst.