Schwellenakzeptanz
Schwellenakzeptanz (englisch threshold accepting, TA) ist ein heuristischer Optimierungsalgorithmus. Verfahren dieses Typs werden meist eingesetzt, wenn die Komplexität des Problems, d. h. die Anzahl der möglichen Lösungen, so groß ist, dass ein einfaches Durchprobieren keinen Erfolg verspricht. Außerdem finden solche Verfahren aufgrund ihrer einfachen Struktur häufig Verwendung, wenn unklar ist, wie sich eine Lösung einfacher als durch Ausprobieren aller Möglichkeiten ermitteln lässt – wenn also keine "schlaue" Lösung existiert oder bekannt ist.
Vorgestellt wurde der Schwellenakzeptanz-Algorithmus 1990 von Dueck und Scheuer in Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing (Journal of Computational Physics, 90(1):161-175, 1990) als eine Abwandlung des Verfahrens der simulierten Abkühlung (englisch simulated annealing).
Ein weiterer Ansatz, die average - accepting - procedure wurde 1998 von Bogatzki entwickelt in Fabrikplanung, Verfahren zur Optimierung der Maschinenaufstellung (Theorie und Forschung Wirtschaftswissenschaften Bd. 534, Seite 249).
Algorithmus
Wähle einen anfänglichen Schwellwert T > 0 Wähle einen Schwellwertfaktor TF (0 < TF < 1) Wähle eine anfängliche Konfiguration C C_best := C Wiederhole bis Abbruchbedingung erfüllt Wähle neue Konfiguration C' (ausgehend von C) Falls Qualität(C') > Qualität(C_best) C_best := C' Falls Qualität(C') > Qualität(C) - T C := C' T := T * TF Gib C_best aus
Eine Konfiguration stellt eine mögliche Lösung des Optimierungsproblems dar. Der Algorithmus wählt wiederholt eine neue Konfiguration C' durch eine kleine zufällige Änderung der momentanen Konfiguration C. Ebenfalls von Bedeutung ist die geeignete Wahl des Anfangsschwellwerts T und des Faktors TF, mit dem man den Schwellwert nach jedem Schritt verkleinert. Hier ist ein Kompromiss zwischen der Qualität der gefundenen Lösung und der aufgewendeten Rechenzeit zu treffen.
Als Abbruchbedingung sind verschiedene Kriterien vorstellbar, zum Beispiel die Dauer des Optimierungsvorgangs oder eine zu erreichende Qualität der Lösung, oder man bricht ab, wenn ein Mindestschwellwert erreicht wurde, oder wenn innerhalb der letzten N Schritte keine Verbesserung von C_best mehr gefunden wurde.
Unterschiede zu simulierter Abkühlung
Der Unterschied zur simulierten Abkühlung (simulated annealing) liegt in der Behandlung von Verschlechterungen der gefundenen Konfiguration.
Während die simulierte Abkühlung Verschlechterungen in der Bewertung eines Zwischenergebnisses nur mit einer bestimmten – im Verlauf der Optimierung kleiner werdenden – Wahrscheinlichkeit akzeptiert, tut Schwellenakzeptanz dies stets, sofern die Verschlechterung nicht größer als ein vorgegebener Schwellwert (threshold) ist. Dieser Schwellwert wird im Verlauf der Optimierung ebenfalls gesenkt.
Vorteile der Schwellenakzeptanz gegenüber der simulierten Abkühlung ergeben sich deshalb vor allem im Hinblick auf die Laufzeit. Die Schwellenakzeptanz verzichtet auf die Ermittlung einer Zufallszahl und die aufwändige Berechnung der Exponentialfunktion und kann daher unterschiedliche Konfigurationen schneller durchprobieren.
Eine allgemeine Überlegenheit der Schwellenakzeptanz hinsichtlich der Lösungsgüte gegenüber der simulierten Abkühlung konnte unter vergleichbaren Bedingungen nicht gezeigt werden.
Literatur
- G. Dueck und T. Scheuer: Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. In: Journal of Computational Physics. Band 90, 1990, S. 161–175, doi:10.1016/0021-9991(90)90201-B.
- I. Althöfer und K.-U. Koschnick: On the convergence of “Threshold Accepting”. In: Applied Mathematics and Optimization. Band 24, 1991, S. 183–195, doi:10.1007/BF01447741.
- Bogatzki, Arnd: Fabrikplanung - Verfahren zur Optimierung der Maschinenaufstellung. S. Roderer Verlag, Regensburg 1998, ISBN 3-89073-234-8
- Kinnebrock, Werner: Optimierung mit genetischen und selektiven Algorithmen, Oldenbourg Verlag, München 1994, ISBN 3-486-22697-5