www.wikidata.de-de.nina.az

Downhill Simplex Verfahren Das oder Nelder Mead Verfahren 1 ist im Unterschied zum Namensvetter für lineare Probleme Sim

Downhill-Simplex-Verfahren

Das Downhill-Simplex-Verfahren oder Nelder-Mead-Verfahren 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.

Es wurde von John Nelder und Roger Mead 1965 eingeführt.

Grundlagen Bearbeiten

Beispiellauf mit Rosenbrock-„Bananenfunktion“
Beispiellauf mit Himmelblau-Funktion

Als Besonderheit kommt dieser Simplex-Algorithmus ohne Ableitungen der Funktion nach den Parametern aus, welche bei manchen Problemstellungen 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 nicht extrem schnell, ist aber dafür einfach und relativ robust.

Der Algorithmus basiert auf einem Simplex, dem einfachsten Volumen im -dimensionalen Parameterraum, das aus Punkten aufgespannt wird. Im Eindimensionalen auf der Zahlengeraden ist das eine Strecke, im Zweidimensionalen ein Dreieck usw. Jeder Punkt entspricht dabei einem (Koordinaten-)Satz Parameter (bzw. Variablen), und zu jedem Punkt kann man einen Funktionswert berechnen, den man z. B. als Fehler- oder Kostenwert ansehen kann. Unter diesen 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 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, sodass das Verfahren zwar im Allgemeinen langsamer konvergiert (nämlich linear) als 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.

Algorithmus Bearbeiten

Flowchart des Downhill-Simplex Verfahrens

Das Downhill-Simplex-Verfahren findet ein lokales Optimum einer Funktion mit Variablen (Parametern). Gegeben ist eine Zielfunktion , die jedem Punkt im Lösungsraum einen Wert (Qualität der Lösung) zuordnet. sind Parameter des Algorithmus.

  1. wähle Anfangspunkte , die den Simplex bilden
  2. sortiere die Punkte nach dem Wert der Zielfunktion , so dass der beste, der zweitschlechteste und der schlechteste ist
  3. bilde von allen außer dem schlechtesten Punkt den Mittelpunkt:
  4. reflektiere den schlechtesten Punkt am Mittelpunkt:
  5. wenn besser ist als : bestimme den expandierten Punkt , ersetze durch den besseren der beiden Punkte und gehe zu Schritt 2
  6. wenn besser ist als der zweitschlechteste Punkt : ersetze durch und gehe zu Schritt 2
  7. sei der bessere der beiden Punkte . Bestimme den kontrahierten Punkt
  8. wenn besser ist als : ersetze durch und gehe zu Schritt 2
  9. komprimiere den Simplex: für jedes : ersetze durch
  10. gehe zu Schritt 2

Nach diesen Regeln wird die Iteration so lange weitergeführt, bis ein Konvergenzkriterium erfüllt ist. Der Simplex wird sich dabei in Richtung eines lokalen Optimums verlagern und sich schließlich um dieses herum zusammenziehen.

Parameter sinnvoller Bereich typischer Wert
(Reflexion)
(Expansion)
(Kontraktion)
(Komprimierung)

Die Anfangspunkte müssen so gewählt werden, dass sie einen Simplex der Dimension aufspannen und nicht alle in einer Hyperebene von kleinerer Dimension liegen, d. h. die Vektoren müssen linear unabhängig sein. Man kann z. B. einen Punkt als Startpunkt wählen und weitere ermitteln, indem man von diesem aus jeweils einen der Parameter um einen von 1 verschiedenen Faktor (falls der Parameter nicht 0 sein kann) oder einen von 0 verschiedenen Summanden erhöht. Alternativ: Man gibt für jeden Parameter zwei verschiedene Werte vor, berechnet den ersten Punkt mit allen Erstwerten und die anderen Punkte auch mit den Erstwerten, nur dass jeweils einer der Parameter durch seinen Zweitwert ersetzt wird. Oder man wählt Zufallspunkte aus dem Lösungsraum.

Grafische Darstellung eines Beispiellaufs Bearbeiten

Eine Iteration des Nelder-Mead-Algorithmus in 2D.

Das Bild zeigt das Ergebnis eines Programmlaufs. 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 - und -Richtung reicht die Grafik von 0 bis 4.

Erweiterungen für Notfälle Bearbeiten

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.

Erweiterung zum Kurvenfitten Bearbeiten

Will man nicht eine einzelne analytische Funktion von Parametern (Koordinaten) optimieren, sondern eine Theoriefunktion an eine Messkurve anpassen, ist nur ein kleiner zusätzlicher Schritt notwendig: Als zu optimierende Funktion verwendet man oft die Fehlerquadratsumme, also die Summe aus den Quadraten der Differenzen aus den einzelnen Messwerten (Kurvenpunkten) und den Theoriefunktionswerten an denselben Stellen, wobei letztere einerseits von der -Koordinate der Messkurve abhängen und zusätzlich von den Parametern. Ob man aus der Fehlerquadratsumme noch die Wurzel zieht, ist für das Simplex-Verfahren irrelevant. Siehe hierzu auch Methode der kleinsten Quadrate.

Jedoch ist das Downhill-Simplex-Verfahren sehr flexibel (anders als etwa der Levenberg-Marquardt-Algorithmus), man kann also je nach Situation auch andere Funktionen zur Optimierung verwenden:

  • Die Daten haben eine starke Streuung: Statt der Summe der quadrierten Abweichung minimiert man die Summe der Beträge der Abweichungen. Ausreißer beeinflussen das Ergebnis weniger.
  • Kurvenanpassung arbeitet normalerweise mit der Annahme, dass der Fehler der abhängigen Variable unabhängig von der zugehörigen unabhängigen Variable ist (Homoskedastizität). In manchen Fällen ist jedoch eine Funktion von . Diese Situation tritt insbesondere dann auf, wenn sich und über mehrere Größenordnungen erstrecken. Würde man in solchen Fällen die Fehlerquadratsumme minimieren, bekäme man eine gute Anpassung bei großen -Werten, aber eine sehr schlechte bei kleinen, die zur Fehlerquadratsumme kaum beitragen. In solchen Fällen minimiert man , also die Summe der quadrierten relativen Abweichungen .

Beispielimplementierung Bearbeiten

Pseudocode (C-ähnlich): 

// Deklarationen 
// Benutzervorgaben, -eingaben int NP= ... ; // Anzahl der Parameter, die in FQS() eingehen, // auch "Dimension des Parameterraums" 
double ParP[NP]={ ... }; // primärer Parametersatz double ParS[NP]={ ... }; // sekundärer Parametersatz, gibt Schwankungsbreite vor 
double FQS(int pf) // Zu minimierende Funktion, hängt { // von den Parametern Par0[pf][...] ab. ... // Muss je nach Problemstellung erstellt werden. // So schreiben, dass sie für den Parametersatz Nr. pf } // berechnet und am Schluss in Par0[pf][0] (s. u.) // abgespeichert wird. 
// Ende Benutzervorgaben 
// Initialisierung 
// Simplex-Parameter double NA = 1, NB = .5, NC = 2; // Alpha, Beta, Gamma 
// Parametersätze, NP+1 Stück für den Simplex selbst, plus 3 weitere double Par0[NP+4][NP+1]; // darin 1. Index: 0..NP die (NP+1) Parametersätze des Simplex, // dabei auf 0 immer der schlechteste Punkt des Simplex, // auf 1 immer der beste Punkt des Simplex // NP+1 Punkt P*, s. u. // NP+2 Punkt P**, s. u. // NP+3 Mittelpunkt P-Quer des Simplex, s. u. // darin 2. Index: 0 Fehlerwert für diesen Satz // 1..NP einzelne Parameterwerte dieses Satzes 
// Initialisierung 
// Simplex aus Primär- und Sekundärwerten Parametersätze 0 bis NP mit Primärwerten belegen; In Parametersätzen 1 bis NP (i) jeweils Parameter Nr. i mit Sekundärwert belegen; 
// Berechnung der Anfangs-Fehlersummen für Parametersätze 0 bis NP: feh=FQS(i); // speichert Ergebnis in Par0[i][0], s. o. 
// Schleife für Iteration, Hauptschleife bool fertig = false; while (!fertig) NT++; // Simplex-Schritt Nr. NT 
 // schlechtesten und besten Punkt ermitteln (höchster bzw. niedrigster Fehlerwert) Werte fmin und fmax auf Fehlerwert von Satz Nr. 0 vorbelegen; für alle Parametersätze von 1 bis NP: wenn Fehler für Satz Nr. i größer als fmax: noch schlechterer Punkt, fmax auf diesen Wert, Punkt mit Nr. 0 tauschen wenn Fehler für Satz Nr. i kleiner als fmin: noch besserer Punkt, fmin auf diesen Wert, Punkt mit Nr. 1 tauschen 
 // Konvergenzabfrage, sind wir fertig? // Dies muss auch je nach Problem individuell erstellt werden, // hier als Beispiel die Bedingung, dass alle Parameter nur noch um 1 ‰ // schwanken. 
 fertig = true; für alle Parameter in allen Parametersätzen von 0 bis NP: wenn nur für einen Parameter die relative Abweichung des Wertes zwischen schlechtestem und bestem Punkt größer als 0.001, dann: fertig=false; // doch noch nicht fertig 
 //Wenn fertig, dann beende mit bestem Punkt Par0[1][1..3] als Ergebnis des Algorithmus 
 // Mittelpunkt P-QUER des Simplex nach Index NP+3 Mittelwerte über Sätze 1 bis NP (also ohne schlechtesten Punkt Nr. 0!) bilden und als Satz Nr. NP+3 speichern; 
 // Punkt P* durch Reflexion des schlechtesten Punkts // am Mittelpunkt P-QUER (mit Nelder/Mead-Parameter alpha=NA) nach Index NP+1 innerhalb eines Parametersatzes: Par0[NP+1][i]=(1 + NA) * Par0[NP+3][i] - NA * Par0[0][i]; fs=Par0[NP+1][0]=FQS(NP+1); // und Fehler berechnen 
 // Fallunterscheidung, ob Verbesserung erreicht wenn fs<fmin // neuer Punkt P* im Vergleich zu bisher bestem / // ja, besser! | // weiteren Schritt zu Punkt P** in dieselbe Richtung nach Index NP+2 | // (mit Nelder/Mead-Parameter gamma=NC) | innerhalb eines Parametersatzes: | Par0[NP+2][i]=(1 + NC) * Par0[NP+1][i] - NC * Par0[NP+3][i]; | fs=Par0[NP+2][0]=FQS(NP+2); // und Fehler berechnen | | wenn fs>=fmin // wieder Vergleich mit bisher bestem Punkt | / // keine weitere Verbesserung: P** verwerfen, P* nach Index 0, | | // also bisher schlechtesten Wert durch neuen (etwas besseren) ersetzen | \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren; | else // von fs>=fmin | / // ja, auch eine Verbesserung! | | // auch besser als P* ? | | wenn fs>Par0[NP+1][0] | | / // nein, P* weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen | | \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren; | | else // von fs>Par0[NP+1][0] | | / // ja, P** weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen \ \ \ Parametersatz Nr. NP+2 nach Nr. 0 kopieren; 
 else // von fs<fmin / // nicht besser als bisher bester, nun prüfen, ob P* wenigstens überhaupt eine Verbesserung | wenn fs von P* für wenigstens einen der Punkte 2..NP kleiner ist, dann: | / // ja, besser als mindestens einer, mit P* den bisher schlechtesten Punkt auf Index 0 ersetzen | \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren; | else // von fs von P* | / // nein, weiterhin schlechter als die anderen Punkte | | // Zusatzprüfung: sogar schlechter als bisher schlechtester Punkt fmax? | | wenn fs>fmax // schlechter als bisher schlechtester? | | // ja, erstmal nichts tun | | else // von fs>fmax | | / // nein, also wenigstens bisher schlechtesten Punkt damit ersetzen | \ \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren; | // neuer Punkt P** durch Kontraktion zwischen bisher schlechtestem Punkt (Index 0) | // und P-QUER (Index NP+3) nach Index NP+2 (mit Nelder/Mead-Parameter beta=NB) | innerhalb eines Parametersatzes: | Par0[NP+2][i]= NB * Par0[0][i] + (1 - NB) * Par0[NP+3][i]; | fs=Par0[NP+2][0]=FQS(NP+2); // und Fehler berechnen | // P** besser als bisher schlechtester Punkt? | wenn fs<fmax // besser als bisher schlechtester? | / // ja, bisher schlechtesten durch P** ersetzen | \ Parametersatz Nr. NP+2 nach Nr. 0 kopieren; | else // von fs<fmax | / // nein, keinerlei Verbesserung, Notfall | | // folgt allgemeine Kompression um Faktor 2 um den bisher besten Punkt herum | | für alle Parametersätze außer Nr. 1 (bisher bester): // also j=0 und 2..NP | | innerhalb eines Parametersatzes j: | | Par0[j][i]=(Par0[j][i] + Par0[1][i]) / 2; \ \ fs=Par0[j][0]=FQS(j); // und Fehler berechnen // Schleifenende

Literatur Bearbeiten

Einzelnachweise Bearbeiten

  1. Nelder, Mead A simplex method for function minimization, Computer Journal, Band 7, 1965, S. 308–313
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Downhill Simplex Verfahren oder Nelder Mead Verfahren 1 ist im Unterschied zum Namensvetter fur lineare Probleme Simplex Algorithmus eine Methode zur Optimierung nichtlinearer Funktionen von mehreren Parametern Er fallt in die Kategorie der Hillclimbing oder Downhill Suchverfahren Angewendet werden kann er z B auch beim Kurvenfitten Es wurde von John Nelder und Roger Mead 1965 eingefuhrt Inhaltsverzeichnis 1 Grundlagen 2 Algorithmus 3 Grafische Darstellung eines Beispiellaufs 4 Erweiterungen fur Notfalle 5 Erweiterung zum Kurvenfitten 6 Beispielimplementierung 7 Literatur 8 EinzelnachweiseGrundlagen Bearbeiten nbsp Beispiellauf mit Rosenbrock Bananenfunktion nbsp Beispiellauf mit Himmelblau FunktionAls Besonderheit kommt dieser Simplex Algorithmus ohne Ableitungen der Funktion nach den Parametern aus welche bei manchen Problemstellungen nicht mit vertretbarem Aufwand berechenbar sind Durch sinnvolle Vergleiche der Funktionswerte mehrerer Punkte im Parameterraum wird ahnlich wie bei einer Regula falsi mit Schrittweitensteuerung die Tendenz der Werte und der Gradient Richtung Optimum angenahert Das Verfahren konvergiert nicht extrem schnell ist aber dafur einfach und relativ robust Der Algorithmus basiert auf einem Simplex dem einfachsten Volumen im N displaystyle N nbsp dimensionalen Parameterraum das aus N 1 displaystyle N 1 nbsp Punkten aufgespannt wird Im Eindimensionalen auf der Zahlengeraden ist das eine Strecke im Zweidimensionalen ein Dreieck usw Jeder Punkt entspricht dabei einem Koordinaten Satz Parameter bzw Variablen und zu jedem Punkt kann man einen Funktionswert berechnen den man z B als Fehler oder Kostenwert ansehen kann Unter diesen N 1 displaystyle N 1 nbsp Punkten ermittelt man dann den schlechtesten und den besten Von einem Iterationsschritt zum nachsten wird normalerweise der schlechteste dieser Punkte durch einen neuen ersetzt der hoffentlich besser ist Den besten Punkt behalt man als bisher beste Losung immer bei Bei einer Visualisierung im Zweidimensionalen mit Hohenlinien fur die zu optimierende Funktion sieht man in den Bildern rechts ein Dreieck das sich zielstrebig dem Optimum nahert indem es sich um eine seiner Seiten klappt sich streckt oder in der Nahe des Optimums um dieses zusammenzieht Siehe auch die Abbildung ganz unten Ohne Ableitungen entfallen diverse Fallen wie pathologisches Verhalten dieser Ableitungen bei Unstetigkeiten sodass das Verfahren zwar im Allgemeinen langsamer konvergiert namlich linear als Optimierungsverfahren mit Ableitungen aber wesentlich robuster arbeitet Die moglichen Fallen beim Simplex Verfahren sind ahnlich wie bei den meisten Optimierungsverfahren unverhoffte lokale Nebenminima bzw optima auf die konvergiert werden kann oder dass das Verfahren sich fur einen oder mehrere Parameter zu fruh auf einen konstanten Wert zusammenzieht Algorithmus Bearbeiten nbsp Flowchart des Downhill Simplex VerfahrensDas Downhill Simplex Verfahren findet ein lokales Optimum einer Funktion mit N displaystyle N nbsp Variablen Parametern Gegeben ist eine Zielfunktion f R N R displaystyle f mathbb R N rightarrow mathbb R nbsp die jedem Punkt im Losungsraum einen Wert Qualitat der Losung zuordnet a g b s R displaystyle alpha gamma beta sigma in mathbb R nbsp sind Parameter des Algorithmus wahle N 1 displaystyle N 1 nbsp Anfangspunkte x 0 x 1 x N R N displaystyle x 0 x 1 cdots x N in mathbb R N nbsp die den Simplex bilden sortiere die Punkte nach dem Wert der Zielfunktion f displaystyle f nbsp so dass x 0 displaystyle x 0 nbsp der beste x N 1 displaystyle x N 1 nbsp der zweitschlechteste und x N displaystyle x N nbsp der schlechteste ist bilde von allen ausser dem schlechtesten Punkt den Mittelpunkt m 1 N i 0 N 1 x i displaystyle m frac 1 N sum nolimits i 0 N 1 x i nbsp reflektiere den schlechtesten Punkt am Mittelpunkt r m a m x N displaystyle r m alpha m x N nbsp wenn r displaystyle r nbsp besser ist als x 0 displaystyle x 0 nbsp bestimme den expandierten Punkt e r g r m displaystyle e r gamma r m nbsp ersetze x N displaystyle x N nbsp durch den besseren der beiden Punkte e r displaystyle e r nbsp und gehe zu Schritt 2 wenn r displaystyle r nbsp besser ist als der zweitschlechteste Punkt x N 1 displaystyle x N 1 nbsp ersetze x N displaystyle x N nbsp durch r displaystyle r nbsp und gehe zu Schritt 2 sei h displaystyle h nbsp der bessere der beiden Punkte x N r displaystyle x N r nbsp Bestimme den kontrahierten Punkt c h b m h displaystyle c h beta m h nbsp wenn c displaystyle c nbsp besser ist als x N displaystyle x N nbsp ersetze x N displaystyle x N nbsp durch c displaystyle c nbsp und gehe zu Schritt 2 komprimiere den Simplex fur jedes i 1 N displaystyle i in 1 cdots N nbsp ersetze x i displaystyle x i nbsp durch x i s x 0 x i displaystyle x i sigma x 0 x i nbsp gehe zu Schritt 2Nach diesen Regeln wird die Iteration so lange weitergefuhrt bis ein Konvergenzkriterium erfullt ist Der Simplex wird sich dabei in Richtung eines lokalen Optimums verlagern und sich schliesslich um dieses herum zusammenziehen Parameter sinnvoller Bereich typischer Werta displaystyle alpha nbsp Reflexion a gt 0 displaystyle alpha gt 0 nbsp a 1 displaystyle alpha 1 nbsp g displaystyle gamma nbsp Expansion g gt 0 displaystyle gamma gt 0 nbsp g 1 displaystyle gamma 1 nbsp b displaystyle beta nbsp Kontraktion 0 lt b lt 1 displaystyle 0 lt beta lt 1 nbsp b 0 5 displaystyle beta 0 5 nbsp s displaystyle sigma nbsp Komprimierung 0 lt s lt 1 displaystyle 0 lt sigma lt 1 nbsp s 0 5 displaystyle sigma 0 5 nbsp Die N 1 displaystyle N 1 nbsp Anfangspunkte mussen so gewahlt werden dass sie einen Simplex der Dimension N displaystyle N nbsp aufspannen und nicht alle in einer Hyperebene von kleinerer Dimension liegen d h die Vektoren x 1 x 0 x 2 x 0 x N x 0 displaystyle x 1 x 0 x 2 x 0 x N x 0 nbsp mussen linear unabhangig sein Man kann z B einen Punkt als Startpunkt wahlen und N displaystyle N nbsp weitere ermitteln indem man von diesem aus jeweils einen der Parameter um einen von 1 verschiedenen Faktor falls der Parameter nicht 0 sein kann oder einen von 0 verschiedenen Summanden erhoht Alternativ Man gibt fur jeden Parameter zwei verschiedene Werte vor berechnet den ersten Punkt mit allen Erstwerten und die anderen N displaystyle N nbsp Punkte auch mit den Erstwerten nur dass jeweils einer der Parameter durch seinen Zweitwert ersetzt wird Oder man wahlt Zufallspunkte aus dem Losungsraum Grafische Darstellung eines Beispiellaufs Bearbeiten nbsp Eine Iteration des Nelder Mead Algorithmus in 2D nbsp Das Bild zeigt das Ergebnis eines Programmlaufs Die roten und blauen Linien stellen die Gefallelinien fur Taler bzw Berge dar Es handelt sich um einen Kreisgraben in einer schragen Ebene es interessiert hier das lokale Minimum innerhalb des Kreisgrabens Die Simplex Iteration findet das Minimum an der Kreuzungsstelle der roten Linien In x displaystyle x nbsp und y displaystyle y nbsp Richtung reicht die Grafik von 0 bis 4 Erweiterungen fur Notfalle BearbeitenWie bei anderen Verfahren besteht immer die Gefahr dass auf ein Nebenoptimum konvergiert wird Diese Gefahr kann man durch mehrere Massnahmen 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 zusatzlichen Simplex Punkte durch Zufallswerte noch mehr flexibilisiert Statt solche Massnahmen nach einer festen Anzahl von Schritten zu ergreifen kann man den Zeitpunkt auch vom aktuellen Stand der Iteration abhangig machen Dazu muss das Problem naturlich besser bekannt sein dass man sich dessen auch sicher sein kann Alternativ kann man sogar den Zeitpunkt der Neuansetzung per Zufallszahl variabel gestalten Eine zusatzliche Sicherheitsabfrage konnte den Fall abfangen dass sich nur einer der Parameter vorzeitig festgelaufen hat dann konnte man ihm eine Spezialbehandlung zukommen lassen All diese Varianten erfordern eine intensive Beschaftigung mit dem jeweiligen konkreten Problem es gibt leider keine allgemein gultigen Kochrezepte dafur Erweiterung zum Kurvenfitten BearbeitenWill man nicht eine einzelne analytische Funktion von N displaystyle N nbsp Parametern Koordinaten optimieren sondern eine Theoriefunktion an eine Messkurve anpassen ist nur ein kleiner zusatzlicher Schritt notwendig Als zu optimierende Funktion verwendet man oft die Fehlerquadratsumme also die Summe aus den Quadraten der Differenzen aus den einzelnen Messwerten Kurvenpunkten und den Theoriefunktionswerten an denselben Stellen wobei letztere einerseits von der x displaystyle x nbsp Koordinate der Messkurve abhangen und zusatzlich von den N displaystyle N nbsp Parametern Ob man aus der Fehlerquadratsumme noch die Wurzel zieht ist fur das Simplex Verfahren irrelevant Siehe hierzu auch Methode der kleinsten Quadrate Jedoch ist das Downhill Simplex Verfahren sehr flexibel anders als etwa der Levenberg Marquardt Algorithmus man kann also je nach Situation auch andere Funktionen zur Optimierung verwenden Die Daten haben eine starke Streuung Statt der Summe der quadrierten Abweichung minimiert man die Summe der Betrage der Abweichungen Ausreisser beeinflussen das Ergebnis weniger Kurvenanpassung arbeitet normalerweise mit der Annahme dass der Fehler der abhangigen Variable D y y c a l c y o b s displaystyle Delta y y calc y obs nbsp unabhangig von der zugehorigen unabhangigen Variable ist Homoskedastizitat In manchen Fallen ist jedoch D y displaystyle Delta y nbsp eine Funktion von x displaystyle x nbsp Diese Situation tritt insbesondere dann auf wenn sich x displaystyle x nbsp und y displaystyle y nbsp uber mehrere Grossenordnungen erstrecken Wurde man in solchen Fallen die Fehlerquadratsumme minimieren bekame man eine gute Anpassung bei grossen x y displaystyle x y nbsp Werten aber eine sehr schlechte bei kleinen die zur Fehlerquadratsumme kaum beitragen In solchen Fallen minimiert man x 2 displaystyle chi 2 nbsp also die Summe der quadrierten relativen Abweichungen S D y y 2 displaystyle Sigma Delta y y 2 nbsp Beispielimplementierung BearbeitenPseudocode C ahnlich Deklarationen Benutzervorgaben eingaben int NP Anzahl der Parameter die in FQS eingehen auch Dimension des Parameterraums double ParP NP primarer Parametersatz double ParS NP sekundarer Parametersatz gibt Schwankungsbreite vor double FQS int pf Zu minimierende Funktion hangt von den Parametern Par0 pf ab Muss je nach Problemstellung erstellt werden So schreiben dass sie fur den Parametersatz Nr pf berechnet und am Schluss in Par0 pf 0 s u abgespeichert wird Ende Benutzervorgaben Initialisierung Simplex Parameter double NA 1 NB 5 NC 2 Alpha Beta Gamma Parametersatze NP 1 Stuck fur den Simplex selbst plus 3 weitere double Par0 NP 4 NP 1 darin 1 Index 0 NP die NP 1 Parametersatze des Simplex dabei auf 0 immer der schlechteste Punkt des Simplex auf 1 immer der beste Punkt des Simplex NP 1 Punkt P s u NP 2 Punkt P s u NP 3 Mittelpunkt P Quer des Simplex s u darin 2 Index 0 Fehlerwert fur diesen Satz 1 NP einzelne Parameterwerte dieses Satzes Initialisierung Simplex aus Primar und Sekundarwerten Parametersatze 0 bis NP mit Primarwerten belegen In Parametersatzen 1 bis NP i jeweils Parameter Nr i mit Sekundarwert belegen Berechnung der Anfangs Fehlersummen fur Parametersatze 0 bis NP feh FQS i speichert Ergebnis in Par0 i 0 s o Schleife fur Iteration Hauptschleife bool fertig false while fertig NT Simplex Schritt Nr NT schlechtesten und besten Punkt ermitteln hochster bzw niedrigster Fehlerwert Werte fmin und fmax auf Fehlerwert von Satz Nr 0 vorbelegen fur alle Parametersatze von 1 bis NP wenn Fehler fur Satz Nr i grosser als fmax noch schlechterer Punkt fmax auf diesen Wert Punkt mit Nr 0 tauschen wenn Fehler fur Satz Nr i kleiner als fmin noch besserer Punkt fmin auf diesen Wert Punkt mit Nr 1 tauschen Konvergenzabfrage sind wir fertig Dies muss auch je nach Problem individuell erstellt werden hier als Beispiel die Bedingung dass alle Parameter nur noch um 1 schwanken fertig true fur alle Parameter in allen Parametersatzen von 0 bis NP wenn nur fur einen Parameter die relative Abweichung des Wertes zwischen schlechtestem und bestem Punkt grosser als 0 001 dann fertig false doch noch nicht fertig Wenn fertig dann beende mit bestem Punkt Par0 1 1 3 als Ergebnis des Algorithmus Mittelpunkt P QUER des Simplex nach Index NP 3 Mittelwerte uber Satze 1 bis NP also ohne schlechtesten Punkt Nr 0 bilden und als Satz Nr NP 3 speichern Punkt P durch Reflexion des schlechtesten Punkts am Mittelpunkt P QUER mit Nelder Mead Parameter alpha NA nach Index NP 1 innerhalb eines Parametersatzes Par0 NP 1 i 1 NA Par0 NP 3 i NA Par0 0 i fs Par0 NP 1 0 FQS NP 1 und Fehler berechnen Fallunterscheidung ob Verbesserung erreicht wenn fs lt fmin neuer Punkt P im Vergleich zu bisher bestem ja besser weiteren Schritt zu Punkt P in dieselbe Richtung nach Index NP 2 mit Nelder Mead Parameter gamma NC innerhalb eines Parametersatzes Par0 NP 2 i 1 NC Par0 NP 1 i NC Par0 NP 3 i fs Par0 NP 2 0 FQS NP 2 und Fehler berechnen wenn fs gt fmin wieder Vergleich mit bisher bestem Punkt keine weitere Verbesserung P verwerfen P nach Index 0 also bisher schlechtesten Wert durch neuen etwas besseren ersetzen Parametersatz Nr NP 1 nach Nr 0 kopieren else von fs gt fmin ja auch eine Verbesserung auch besser als P wenn fs gt Par0 NP 1 0 nein P weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen Parametersatz Nr NP 1 nach Nr 0 kopieren else von fs gt Par0 NP 1 0 ja P weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen Parametersatz Nr NP 2 nach Nr 0 kopieren else von fs lt fmin nicht besser als bisher bester nun prufen ob P wenigstens uberhaupt eine Verbesserung wenn fs von P fur wenigstens einen der Punkte 2 NP kleiner ist dann ja besser als mindestens einer mit P den bisher schlechtesten Punkt auf Index 0 ersetzen Parametersatz Nr NP 1 nach Nr 0 kopieren else von fs von P nein weiterhin schlechter als die anderen Punkte Zusatzprufung sogar schlechter als bisher schlechtester Punkt fmax wenn fs gt fmax schlechter als bisher schlechtester ja erstmal nichts tun else von fs gt fmax nein also wenigstens bisher schlechtesten Punkt damit ersetzen Parametersatz Nr NP 1 nach Nr 0 kopieren neuer Punkt P durch Kontraktion zwischen bisher schlechtestem Punkt Index 0 und P QUER Index NP 3 nach Index NP 2 mit Nelder Mead Parameter beta NB innerhalb eines Parametersatzes Par0 NP 2 i NB Par0 0 i 1 NB Par0 NP 3 i fs Par0 NP 2 0 FQS NP 2 und Fehler berechnen P besser als bisher schlechtester Punkt wenn fs lt fmax besser als bisher schlechtester ja bisher schlechtesten durch P ersetzen Parametersatz Nr NP 2 nach Nr 0 kopieren else von fs lt fmax nein keinerlei Verbesserung Notfall folgt allgemeine Kompression um Faktor 2 um den bisher besten Punkt herum fur alle Parametersatze ausser Nr 1 bisher bester also j 0 und 2 NP innerhalb eines Parametersatzes j Par0 j i Par0 j i Par0 1 i 2 fs Par0 j 0 FQS j und Fehler berechnen SchleifenendeLiteratur BearbeitenJohn Ashworth Nelder Roger Mead A Simplex Method for Function Minimization Computer Journal 1965 7 308 313 Originaltext als PDF Datei 543 kB William H Press Saul A Teukolsky William T Vetterling Brian P Flannery Numerical Recipes in C Foundation Books 2007 ISBN 978 81 85618 16 6 Jeffrey C Lagarias James A Reeds Margaret H Wright Paul E Wright Convergence Properties of the Nelder Mead Simplex Method in Low Dimensions In SIAM Journal on Optimization Band 9 Nr 1 1998 S 112 147 doi 10 1137 S1052623496303470 Larry Nazareth Paul Tseng Gilding the Lily A variant of the Nelder Mead algorithm based on Golden Section Search Computational Optimization and Applications Bd 22 2002 Nr 1 S 133 144 Sasa Singer Sanja Singer Efficient implementation of the Nelder Mead search algorithm Applied Numerical Analysis and Computational Mathematics Bd 1 2004 Nr 2 S 524 534 Zusammenfassung Marco A Luersen Rodolphe Le Riche Globalized Nelder Mead method for engineering optimization Computers and Structures 82 2004 S 2251 2260 Andrej Prsa Tomaz Zwitter Introducing adapted Nelder amp Mead s downhill simplex method to a fully automated analysis of eclipsing binaries In C Turon K S O Flaherty M A C Perryman Hrsg The Three Dimensional Universe with Gaia ESA SP 576 Proc Gaia Sympos 2004 ESA Publications Division Nordwijk 2005 S 611 614 David Byatt Ian Coope Chris Price 40 years of the Nelder Mead algorithm PDF Datei 3 46 MB Fuchang Gao Lixing Han Implementing the Nelder Mead simplex algorithm with adaptive parameters Computational Optimization and Applications 51 2012 Nr 1 S 259 277 Jeffrey C Lagarias Bjorn Poonen Margaret H Wright Convergence of the restricted Nelder Mead algorithm in two dimensions SIAM J Optimization 22 2012 Nr 2 S 501 532Einzelnachweise Bearbeiten Nelder Mead A simplex method for function minimization Computer Journal Band 7 1965 S 308 313 Abgerufen von https de wikipedia org w index php title Downhill Simplex Verfahren amp oldid 235662471