Threshold Accepting

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 Zahl von Probierschritten Zmax
Wähle eine anfängliche Konfiguration C
Referenzlösung C_ref := C
Wiederhole bis Abbruchbedingung erfüllt
   Wiederhole Zmax mal
      Wähle neue Konfiguration C' (ausgehend von C)
      Falls Qualität(C´) > Qualität(C_ref)
         C_ref := C´
      dQ := Qualität(C') - Qualität(C)
      Falls dQ > -T
         C := C'
   T := T * TF
Gib C_ref aus

Die Konfiguration stellt eine mögliche Lösung des Optimierungsproblems dar. Um eine erfolgreiche Optimierung durchzuführen, ist die sinnvolle Wahl neuer Konfigurationen - meist als kleine Änderungen der momentanen Konfiguration - nötig. Ebenfalls von großer Bedeutung für die Qualität der Lösung ist die Strategie zum Verringern des Schwellwerts.

Als Abbruchbedingung sind verschiedenste Kriterien vorstellbar, zum Beispiel die Dauer des Optimierungsvorgangs oder eine zu erreichende Qualität der Lösung.

Unterschiede zu simulierten 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.

Experimente der Erfinder deuten außerdem darauf hin, dass die Schwellenakzeptanz unter vergleichbaren Bedingungen häufig qualitativ bessere Lösungen liefert als die simulierte Abkühlung.

Literatur

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