Downhill-Simplex-Verfahren
aus Wikipedia, der freien Enzyklopädie
Der Simplex-Algorithmus nach Nelder und Mead (Comp. J., vol. 7, 1965, p. 308) oder auch Downhill-Simplex-Verfahren oder manchmal auch einfach Simplex-Algorithmus ist im Unterschied zum Namensvetter für lineare Probleme (Simplex-Algorithmus) eine Methode zur Optimierung nichtlinearer Funktionen von mehreren Parametern. Er fällt in die Kategorie der Hillclimbing- oder Downhill-Suchverfahren. Angewendet werden kann er z. B. auch beim Kurvenfitten.
Inhaltsverzeichnis |
[Bearbeiten] Grundlagen
Als Besonderheit kommt dieser Simplex-Algorithmus ohne Ableitungen der Funktion nach den Parametern aus, welche bei manchen Problemstellungen einfach nicht mit vertretbarem Aufwand berechenbar sind. Durch sinnvolle Vergleiche der Funktionswerte mehrerer Punkte im Parameterraum wird ähnlich wie bei einer Regula falsi mit Schrittweitensteuerung die Tendenz der Werte und der Gradient Richtung Optimum angenähert. Das Verfahren konvergiert in etwa linear, ist also nicht extrem schnell, dafür einfach und relativ robust.
Der Algorithmus basiert auf einem Simplex, dem einfachsten Volumen im N-dimensionalen Parameterraum, das aus N+1 Punkten aufgespannt wird. Im Eindimensionalen auf der Zahlengerade ist das eine Strecke, im Zweidimensionalen ein Dreieck usw. Jeder Punkt entspricht dabei einem Satz Parameter (bzw. Variablen), und zu jedem Punkt kann man einen Funktionswert berechnen. Unter diesen N+1 Punkten ermittelt man dann den "schlechtesten" und den "besten". Von einem Iterationsschritt zum nächsten wird normalerweise der "schlechteste" dieser Punkte durch einen neuen ersetzt, der hoffentlich "besser" ist. Den "besten" Punkt behält man als bisher beste Lösung immer bei.
Bei einer Visualisierung im Zweidimensionalen mit Höhenlinien für die zu optimierende Funktion sieht man (in den Bildern rechts) ein Dreieck, das sich erstaunlich zielstrebig dem Optimum nähert, indem es sich um eine seiner Seiten klappt, sich streckt oder in der Nähe des Optimums um dieses zusammenzieht. Siehe auch die Abbildung ganz unten.
Ohne Ableitungen entfallen diverse Fallen wie pathologisches Verhalten dieser Ableitungen bei Unstetigkeiten, so dass das Verfahren zwar im Allgemeinen nicht so schnell konvergiert (nämlich linear) wie Optimierungsverfahren mit Ableitungen, aber wesentlich robuster arbeitet. Die möglichen Fallen beim Simplex-Verfahren sind ähnlich wie bei den meisten Optimierungsverfahren unverhoffte lokale Nebenminima (bzw. -optima), auf die konvergiert werden kann, oder dass das Verfahren sich für einen oder mehrere Parameter zu früh auf einen konstanten Wert zusammenzieht.
[Bearbeiten] Der Algorithmus selbst
Das Verfahren findet das Optimum einer Funktion mit N Variablen (Parametern) einer Funktion im N-dimensionalen Parameterraum. Ein Programm geht üblicherweise so vor, dass
(1) N+1 Anfangspunkte gewählt werden (Beispiel: man wählt einen Punkt als Startpunkt und ermittelt N weitere, indem man von diesem aus jeweils einen der Parameter um einen bestimmten Faktor − z. B. 1.1 − erhöht; alternativ: man gibt für jeden Parameter zwei verschiedene Werte vor, berechnet den ersten Punkt mit allen Erstwerten und die anderen N Punkte auch mit den Erstwerten, nur dass jeweils einer der Parameter durch seinen Zweitwert ersetzt wird);
(2) die Funktionswerte an diesen Punkten berechnet werden (je nach Problemstellung ein Fehlerwert, Höhenwert, Kosten, Zeitaufwand usw.) und der beste und der schlechteste unter ihnen ermittelt wird;
(3) bei einem genügend guten Wert das Verfahren beendet wird, ansonsten (nur) den bisher schlechtesten der N+1 Punkte durch einen neuen ersetzen (wodurch ein neues Simplex-Volumen gebildet wird); und
(4) die Schleife mit Schritt (2) weitergeführt wird.
Das eigentliche Verfahren nach Nelder und Mead besteht in der Strategie, mit der in Schritt (3) der neue Simplex gebildet wird.
Nelder und Mead haben dazu folgende Regeln aufgestellt:
Immer den schlechtesten Punkt am Mittelpunkt des Simplex reflektieren (unter Benutzung des Faktors alpha).
a) Wenn dieser Punkt besser ist als alle anderen, mache einen weiteren, noch größeren Schritt (Faktor gamma) in die selbe Richtung.
b) Wenn dieser Punkt immerhin eine Verbesserung bringt, ersetze den schlechtesten durch ihn und beginne den Algorithmus wieder von vorn.
c) Wenn dieser Punkt eine weitere Verschlechterung bringt, verwerfe ihn und komprimiere den Simplex um einen bestimmten Faktor beta um den bisher besten Punkt und beginne den Algorithmus wieder von vorn.
Die Koordinatenveränderungen der Parameter während dieser Schritte werden mittels der Nelder/Mead-Parameter alpha, beta und gamma berechnet, die normalerweise als 1, 1/2 und 2 angesetzt werden.
Nach diesen Regeln wird die Iteration so lange weitergeführt, bis ein Konvergenzkriterium erfüllt ist. Der Simplex wird sich dabei in Richtung des Optimums verlagern und sich schließlich um dieses herum zusammenziehen.
[Bearbeiten] Erweiterungen für Notfälle
Wie bei anderen Verfahren besteht immer die Gefahr, dass auf ein Nebenoptimum konvergiert wird. Diese Gefahr kann man durch mehrere Maßnahmen mindern:
- Nach einer bestimmten Anzahl von Schritten wird neu angesetzt. Dazu wird der bisher beste Punkt beibehalten und um ihn herum ein neuer Start-Simplex aufgebaut, indem bei jedem weiteren Punkt die Koordinate (nur) eines Parameters z. B. um 5 % variiert wird.
- Genau wie eben, nur werden die zusätzlichen Simplex-Punkte durch Zufallswerte noch mehr flexibilisiert.
- Statt solche Maßnahmen nach einer festen Anzahl von Schritten zu ergreifen, kann man den Zeitpunkt auch vom aktuellen Stand der Iteration abhängig machen. Dazu muss das Problem natürlich besser bekannt sein, dass man sich dessen auch sicher sein kann.
- Alternativ kann man sogar den Zeitpunkt der Neuansetzung per Zufallszahl variabel gestalten.
- Eine zusätzliche Sicherheitsabfrage könnte den Fall abfangen, dass sich nur einer der Parameter vorzeitig festgelaufen hat, dann könnte man ihm eine Spezialbehandlung zukommen lassen.
All diese Varianten erfordern eine intensive Beschäftigung mit dem jeweiligen konkreten Problem, es gibt leider keine allgemein gültigen Kochrezepte dafür.
[Bearbeiten] Erweiterung zum Kurvenfitten
Will man nicht eine einzelne analytische Funktion von N Parametern (Koordinaten) optimieren, sondern eine Theoriefunktion an eine Messkurve anpassen, ist nur ein kleiner zusätzlicher Schritt notwendig: Als zu optimierende Funktion verwendet man die Fehlerquadratsumme, also die Summe aus den Quadraten der Differenzen aus den einzelnen Messwerten (Kurvenpunkten) und den Theoriefunktionswerten an den selben Stellen, wobei letztere einerseits von der x-Koordinate der Messkurve abhängen und zusätzlich von den N Parametern. Ob man aus der Fehlerquadratsumme noch die Wurzel zieht, ist für das Simplex-Verfahren irrelevant.
[Bearbeiten] Beispielimplementation
' Dieses Programm wurde ursprünglich vor 1982 auf einem Commodore PET 2001
' erstellt, daher teilweise noch 40 Zeichen/Zeile und magere Variablennamen.
' Das Programm ist unter dem QBasic-Interpreter lauffähig!
' Ein einfaches Beispiel ist eingebaut.
' Hier Formulierung für die Minimierung einer Fehlerfunktion.
REM NACH J.A. NELDER, R. MEAD
REM Comp. J., vol. 7, 1965, S. 308
REM Simplex-Parameter:
NA = 1: NB = .5: NC = 2: REM ALPHA,BETA,GAMMA
REM Daten wurden hier noch über DATA-Zeilen im Programm eingegeben!
PRINT "Anzahl Funktionsparameter:"; : READ NP: PRINT NP
DIM Y0(NP + 3, NP), YP(NP) ' Arrays mit Parameterwerten,
' Y0 bildet den eigentlichen Simplex plus ein paar neue Punkte
PRINT : PRINT "Param.-Startwerte, Erst- und Zweitwert:": PRINT
FOR NI = 1 TO NP
READ Y: PRINT NI, Y,
FOR NJ = 0 TO NP: Y0(NJ, NI) = Y: NEXT
READ Y: PRINT Y: Y0(NI, NI) = Y
NEXT
PRINT : PRINT "Berechnung der Anfangs-Fehlersummen"
FOR N0 = 0 TO NP
PRINT "Satz"; N0; " , Fehler:"; : GOSUB FQS: PRINT YS
NEXT
PRINT "Abbruch muss durch Benutzer erfolgen!"
NT = 0 ' Iterationszähler
Schleife:
NT = NT + 1: PRINT : PRINT "Simplex-Schritt Nr. "; NT
' schlechtesten und besten Punkt ermitteln (höchster bzw. niedrigster Fehlerwert)
YP = Y0(0, 0): Y1 = YP: REM Y-H,Y-L
FOR N3 = 1 TO NP
IF Y0(N3, 0) > YP THEN
N2 = 0: GOSUB Tausch: YP = Y0(0, 0) ' schlechtesten Punkt Y-H nach Index 0
ELSEIF Y0(N3, 0) < Y1 THEN
N2 = 1: GOSUB Tausch: Y1 = Y0(1, 0) ' besten Punkt Y-L nach Index 1
PRINT "Bester Wert:"; Y1: N3 = 1
ELSE
END IF
NEXT
' Hier müsste eine Konvergenzabfrage auf erfolgreiches Ende eingefügt werden,
' die ist aber sehr problemabhängig und nicht allgemein formulierbar.
' Eine Formulierung, die für das eingebaute Beispiel funktioniert:
NJ = 1 > 0
FOR N3 = 1 TO NP: NJ = NJ AND (ABS(Y0(0, N3) - Y0(1, N3)) < .0001 * ABS(Y0(1, N3))): NEXT
IF NJ THEN END
' Mittelpunkt P-QUER des Simplex nach Index NP+3
FOR NI = 1 TO NP
YS = 0: REM P-QUER
FOR NJ = 1 TO NP: YS = YS + Y0(NJ, NI): NEXT
Y0(NP + 3, NI) = YS / NP
NEXT
' Punkt P* durch Reflexion des schlechtesten Punkts Y-H
' am Mittelpunkt P-QUER (mit Nelder/Mead-Parameter alpha) nach Index NP+1
FOR NJ = 1 TO NP: REM P*
Y0(NP + 1, NJ) = (1 + NA) * Y0(NP + 3, NJ) - NA * Y0(0, NJ)
NEXT
N0 = NP + 1: GOSUB FQS: PRINT "p* "; YS; ' für P* den Fehlerwert berechnen
' Fallunterscheidung, ob Verbesserung erreicht
IF YS < Y1 THEN ' neuer Punkt P* im Vergkleich zu bisher bestem Y-L
PRINT "< y-l" ' ja, besser!
' weiteren Schritt zu Punkt P** in selbe Richtung nach Index NP+2
' (mit Nelder/Mead-Parameter gamma)
PRINT "p**"; : N0 = NP + 2: N2 = NP + 1: N3 = NP + 3
FOR NI = 1 TO NP
Y0(N0, NI) = (1 + NC) * Y0(N2, NI) - NC * Y0(N3, NI)
NEXT
GOSUB FQS: PRINT YS; ' für P** Fehlerwert berechnen
IF YS >= Y1 THEN ' wieder Vergleich mit bisher bestem Punkt
' keine weitere Verbesserung: P** verwerfen, P* nach Index 0,
' also bisher schlechtesten Wert durch neuen ersetzen
PRINT "> y-l": N2 = 0: N3 = NP + 1: GOSUB Tausch
ELSE
' ja, auch eine Verbesserung!
PRINT "< y-l";
' auch besser als P* ?
IF YS > Y0(NP + 1, 0) THEN
' nein, P* weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen
PRINT " , > y*": N2 = 0: N3 = NP + 1: GOSUB Tausch
ELSE
' ja, P** weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen
N2 = 0: N3 = N0: GOSUB Tausch: PRINT " , < y*"
END IF
END IF
ELSE
' nicht besser als bisher bester, nun prüfen, ob wenigstens überhaupt eine Verbesserung
PRINT "> y-l , "; : N3 = -1 ' N3 auf "TRUE"
IF NP > 1 THEN FOR NI = 2 TO NP: N3 = N3 AND (YS > Y0(NI, 0)): NEXT
' N3 sagt, ob P* besser als mindestens einer der anderen Punkte ist
IF N3 = 0 THEN
' ja, besser als mindestens einer, mit P* den bisher schlechtesten Punkt auf Index 0 ersetzen
PRINT "Mitte": N2 = 0: N3 = NP + 1: GOSUB Tausch
ELSE
' nein, weiterhin schlechter als die anderen Punkte
PRINT "> yi , ";
' sogar schlechter als bisher schlechtester Punkt Y-H ?
IF YS > YP THEN
' ja, erstmal nichts tun
PRINT "> y-h"
ELSE
' nein, also wenigstens bisher schlechtesten Punkt damit ersetzen
N2 = 0: N3 = NP + 1: GOSUB Tausch: PRINT "< y-h"
END IF
' neuen Punkt P** durch Kompression zwischen bisher schlechtestem Punkt (Index 0)
' und P-QUER (Index NP+3) nach Index NP+2 (mit Nelder/Mead-Parameter beta)
PRINT "p**"; : N0 = NP + 2: N2 = NP + 3
FOR NI = 1 TO NP
Y0(N0, NI) = NB * Y0(0, NI) + (1 - NB) * Y0(N2, NI)
NEXT
GOSUB FQS: PRINT YS; ' Fehlerwert für P** berechnen
' P** besser als bisher schlechtester Punkt?
IF YS < YP THEN
' ja, bisher schlechtesten durch P** ersetzen
PRINT "< y-h": N2 = 0: N3 = NP + 2: GOSUB Tausch
ELSE
' nein, allgemeine Kompression um Faktor 2 um den bisher besten Punkt herum
PRINT "> y-h": PRINT "Kompression!"
FOR N0 = 0 TO NP
IF N0 <> 1 THEN ' bisher besten Punkt unverändert lassen
FOR NI = 1 TO NP: Y0(N0, NI) = (Y0(N0, NI) + Y0(1, NI)) / 2: NEXT
GOSUB FQS: PRINT "Satz"; N0; " , f:"; YS
END IF
NEXT
END IF
END IF
END IF
GOTO Schleife
Tausch: ' Parametersätze N2 und N3 austauschen
FOR NI = 0 TO NP
YH = Y0(N2, NI): Y0(N2, NI) = Y0(N3, NI): Y0(N3, NI) = YH
NEXT
RETURN
FQS: ' Fehlerwert YS für Parametersatz Nr. N0 berechnen
YS = 0
FOR NI = 1 TO NP: YP(NI) = Y0(N0, NI): NEXT
' Hier abhängig von YP(1) bis YP(NP) den Funktionswert in YS berechnen
' Einfaches Beispiel: ein Kreisgraben um (1,0) mit Radius 2
' YP(1) dient als x-Koordinate, YP(2) als y-Koordinate
z = SQR((YP(1) - 1) * (YP(1) - 1) + YP(2) * YP(2))
' geneigte Flaeche dazu
YS = (z - 2) * (z - 2) - .1 * YP(2) - .11 * YP(1)
Y0(N0, 0) = YS
RETURN
' Einfaches Beispiel: Anfangswerte der Parameter in DATA-Zeilen
DATA 2, 1.2, 1.4, 0, 0.2
[Bearbeiten] Grafische Darstellung eines Beispiellaufs
Das Bild zeigt das Ergebnis eines Programmlaufs mit dem beigefügten Beispiel. Die roten und blauen Linien stellen die Gefällelinien für Täler bzw. Berge dar. Es handelt sich um einen Kreisgraben in einer schrägen Ebene, es interessiert hier das lokale Minimum innerhalb des Kreisgrabens. Die Simplex-Iteration findet das Minimum an der Kreuzungsstelle der roten Linien. In x- und y-Richtung reicht die Grafik von 0 bis 4.
[Bearbeiten] Literatur
- Nelder, J. A. & Mead, R. A: A Simplex Method for Function Minimization. Computer Journal, 1965, 7, 308-313
- Lagarias, J. C.; Reeds, J. A.; Wright, M. H. & Wright, P. E.: Convergence Properties of the Nelder-Mead Simplex Method in low Dimensions. SIAM Journal on Optimization, 1998, 9, 112-147 [1]
