Threshold Accepting / Schwellenakzeptanz Algorithmus in Java

Bitte aktiviere JavaScript!
Kann man pauschalisieren welches T und TF in der Praxis als sinnvoll erachtet wird?
Ist mir im Allgemeinen nichts bekannt, was aber nichts heißt. TA wird mit der Zeit immer gieriger, weil T via TF reduziert wird. Sobald T einen vorab nicht bekannten Wert unterschreitet, entspricht TA einem einfachen Greedy-Algorithmus. Wählt man T dagegen sehr groß, dann werden (je nach TF) sehr viele, sehr schlechte Lösungen akzeptiert, was zu erhöhter Laufzeit führt.

Mir ist klar, dass T, TF und minDelta fallspezifisch sind. Dennoch frage ich mich mit welcher Fragestellung man an die Auswahl der Werte rangeht?
Im Allgemeinen empirisch. Das ist in der Anwendung oft das größte Problem am Ganzen: gute Parameter finden.

Wenn ich in meinem Beispiel mich um die Werte zwischen 1800km-2200km bewege und das weiß ich vor der Ausführung, dann ist es Sinnvoll einen T in der Nähe zu wählen (bsp.: 200, da 2000 einfach unnötig viele Schritte zulassen würde?) und TF 0.9 (nur weiß ich nicht mit welcher Begründung?).
Begründung: empirisch ermittelt :)

- Jede Kombination verweist auf einen Wert im Array im Java Code der die Gesamtstrecke repräsentiert
Wie meinen?

Und ist mein Beispiel mit dem Studenten überhaupt TA-tauglich?
Warum nicht?
 
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
Ich meine damit ich wähle ein Array mit (z.B.) 2000, 2100, 1900, 1800 etc. ..
Das ist in meinem Beispiel die zurückgelegte Gesamtstrecke.
Die erste Konfiguration C ist 1 und somit 2100.
Die Konfiguration bedeutet eine bestimmte Route durch die 15 Städte die insgesamt 2100km ergibt.
 
Ach so, Du gehst her und betrachtest nur einen kleinen Teil der Konfigurationen. Dann wirst Du erklären müssen, warum Du das so machst, also ein Array mit vorberechneten Werten hast bzw. Du nicht einfach das Minimum aus dem Array wählst :)
 
Habe das einfachheitshalber gewählt, um das Prinzip vom Algorithmus zu verdeutlichen, ohne auf die einzelnen Berechnungen der Werte einzugehen.

Aber bin jetzt bisschen verwirrt... :D
Genau, ich kann ja aus dem Array einfach das Minimum wählen...
Das Beispiel soll eigentlich bloß hypotetisch die Vorgehensweise darstellen.

Weil die einzelnen Konfigurationen werden ja berechnet in dem man die nächsten Städte zufällig wählt und die Entfernungen der einzelnen Städte berechnet. Daraus ergeben sich die Gesamtstrecken, die ich zum verdeutlichen des Prinzips des Algorithmus in einem Array bereits bereitstelle...

Oder verwende ich gerade Birnen um Äpfel zu präsentieren? :D
 
Weil die einzelnen Konfigurationen werden ja berechnet in dem man die nächsten Städte zufällig wählt und die Entfernungen der einzelnen Städte berechnet. Daraus ergeben sich die Gesamtstrecken, die ich zum verdeutlichen des Prinzips des Algorithmus in einem Array bereits bereitstelle...
Genau.
 
Ich habe mir jetzt noch gedanken über die Nachteile gemacht. So einfach ist es nicht, aber ich glaube der wesentliche Nachteil ist, dass die Verschlechterungsakzeptanz im gewissen Rahmen problematisch sein kann, sprich dass bereits gefundene gute Lösungen durch iterative Verschlechterungen wieder verloren gehen können.
Die anderen Nachteile die mir einfallen sind allgemein auf alle heuristischen Algorithmen bezogen.
Würde Dir noch was speziell zu TA einfallen?
 
sprich dass bereits gefundene gute Lösungen durch iterative Verschlechterungen wieder verloren gehen können.
Nein. Es kann passieren, dass Pfade im Suchraum nicht besucht werden, die zu einem besseren Ergebnis führen. Das gilt aber ganz Allgemein für Heuristiken (mit Ausnahmen in bestimmten Fällen), da der Anspruch gerade nicht darin besteht, das globale Optimum zu finden.

Kurz: das Problem ist so komplex, dass das globale Optimum nicht effizient gefunden werden kann. Daher verzichtet man darauf und wendet eine Heuristik an, von der man annimmt, dass sie "möglichst" nah (= zufriedenstellend) ans Optimum führt.

Das hört sich alles ziemlich unbefriedigend an, aber man muss mal sehen, was es für ein Unternehmen bedeutet, wenn es z. B. "nur" 5 % zusätzlich einsparen kann.

Wenn man TA mit Greedy startet, wird TA nie schlechter als Greedy abschneiden. Man kann TA auch als Meta-Heuristik verwenden. D. h. die nächste TA-Konfiguration ist ein von einer ggf. anderen Heuristik optimiertes Ergebnis.

Beispiel: Rucksackproblem (https://de.wikipedia.org/wiki/Rucksackproblem); der Greedy-Algorithmus packt jeweils den Gegenstand mit dem höchsten Nutzen-Kosten-Verhältnis ein. Im schlechtesten Fall (s. Wikipedia) liefert Greedy eine Lösung, die 50 % unter dem Optimum liegt.

Jetzt kann man hergehen und z. B. den Rucksack greedy packen aber mit TA verschiedene Konfigurationen (Gegenstände zufällig entfernen und durch einen anderen austauschen) durchlaufen. Die Optimierung wird nie schlechter als Greedy abschneiden, aber die Wahrscheinlichkeit besteht, besser zu sein.

Als Nachteil würde ich sehen, dass bei TA der Schwellwert absolut ist und daher abhängig von der "Qualitätsfunktion" und ggf. den Eingabedaten ist. Allerdings gibt es viele Probleme, wo gute obere/untere Schranken bekannt sind (z. B. stellt die Luftlinie beim Finden von kürzesten Strecken das globale Minimum dar; dem entsprechend läge das Verhältnis Luftlinie/gefundene Strecke immer zwischen ]0,1], wenn man annimmt, dass Ausgangs- und Zielpunkt verschieden sind). In so einem Fall lassen sich natürlich T und TF finden, die für viele Fälle gleichermaßen verwendet werden können.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben