Schwellenakzeptanz - LinkFang.de





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 Schellwert 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

Kategorien: Optimierungsalgorithmus | Planung und Organisation

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Schwellenakzeptanz (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.