J
http://de.wikipedia.org/wiki/Downhill-Simplex-Verfahren
wiki hat dazu was interessantes.
// 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 Promille
// 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+2 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 0..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
