Optimierungsmethoden der ALGLIB-Bibliothek (Teil I)
25
1
Inhalt
- Einführung
- Optimierungsmethoden der ALGLIB-Bibliothek:
Einführung
Das MetaTrader 5-Terminal wird standardmäßig mit der Bibliothek ALGLIB ausgeliefert, einem leistungsstarken Tool für numerische Analysen, das für Entwickler von Handelssystemen nützlich sein kann. Die ALGLIB-Bibliothek bietet dem Nutzer eine breite Palette von numerischen Analysemethoden, darunter:
- Lineare Algebra - Lösen von linearen Gleichungssystemen, Berechnung von Eigenwerten und Vektoren, Matrixzerlegung.
- Optimierung - Methoden der ein- und mehrdimensionalen Optimierung.
- Interpolation und Approximation - Polynom- und Spline-Interpolation, Approximation von Funktionen mit Methoden der kleinsten Quadrate.
- Numerische Integration und Differenzierung - Integrationsmethoden (Trapezoide, Simpson, usw.), numerische Differenzierung.
- Numerische Methoden zur Lösung von Differentialgleichungen - gewöhnliche Differentialgleichungen und numerische Methoden.
- Statistische Methoden - Parameterschätzung, Regressionsanalyse, Erzeugung von Zufallszahlen.
- Fourier-Analyse: schnelle Fourier-Transformation.
Die in ALGLIB vorgestellten deterministischen Optimierungsmethoden basieren auf verschiedenen Variationen des Gradientenabstiegs und erlauben die Verwendung sowohl analytischer als auch numerischer Ansätze. In diesem Artikel werden wir uns auf numerische Methoden konzentrieren, da sie für die praktischen Aufgaben von Händlern am besten geeignet sind.
Es ist wichtig zu beachten, dass viele Probleme im Finanzsektor diskreter Natur sind, da die Preisdaten als einzelne Punkte dargestellt werden. Daher sind wir besonders an Methoden interessiert, die eine numerische Darstellung von Gradienten verwenden. Der Nutzer braucht den Gradienten nicht zu berechnen - diese Aufgabe wird von Optimierungsmethoden übernommen.
Die Beherrschung von ALGLIB-Optimierungsmethoden ist in der Regel schwierig, weil die Namen der Methoden und die Reihenfolge, in der auf sie zugegriffen wird, nicht einheitlich sind. Das Hauptziel dieses Artikels ist es, die Informationslücken über die Bibliothek zu schließen und einfache Anwendungsbeispiele zu liefern. Definieren wir zunächst die grundlegenden Begriffe und Konzepte, um besser zu verstehen, wofür diese Methoden gedacht sind.
Bei der Optimierung geht es darum, unter gegebenen Bedingungen und Einschränkungen die beste Lösung zu finden. Die Suche impliziert das Vorhandensein von mindestens zwei Optionen zur Lösung des Problems, von denen die beste ausgewählt werden muss.
Ein Optimierungsproblem ist ein Problem, bei dem es darum geht, die beste Lösung (Maximum oder Minimum) aus einer Reihe möglicher Optionen zu finden, die bestimmte Bedingungen erfüllen. Die Hauptelemente des Optimierungsproblems:
- Zielfunktion (Fitnessfunktion). Dies ist die Funktion, die maximiert oder minimiert werden muss. Zum Beispiel die Maximierung des Gewinns oder die Minimierung der Kosten (Gewinn oder Kosten sind die Optimierungskriterien).
- Variablen. Diese Parameter können geändert werden, um das beste Ergebnis zu erzielen.
- Restriktionen. Dies sind die Bedingungen, die bei der Suche nach der optimalen Lösung erfüllt sein müssen.
Die Zielfunktion kann eine beliebige, vom Nutzer festgelegte Funktion sein, die die Eingaben (die optimiert werden sollen) annimmt und einen Wert erzeugt, der als Optimierungskriterium dient. Die Zielfunktion kann zum Beispiel das Testen eines Handelssystems anhand historischer Daten sein, wobei die Funktionsparameter die Einstellungen des Handelssystems sind und der Ausgabewert die erforderliche Qualität des Betriebs darstellt.
Arten von Einschränkungen:
- Boundary Constraints (Box Constraints) - Einschränkungen für die Werte von Variablen, z. B. kann die Variable „x“ nur im Bereich von 1 bis 3 liegen.
- Lineare Gleichheitsbedingung - Bedingungen, unter denen ein Ausdruck mit Variablen genau gleich einer bestimmten Zahl sein muss. Zum Beispiel ist (x + y = 5) eine lineare Gleichheit.
- Lineare Ungleichheitsbedingung - Bedingungen, unter denen ein Ausdruck mit Variablen kleiner als oder gleich (oder größer als oder gleich) einer Zahl sein muss. Zum Beispiel: (x - y >= 1).
In den folgenden Beispielen werden wir nur die Randbedingungen berücksichtigen. In diesem Artikel werden daher wirksame Techniken und ein einfacher Weg zur Nutzung von ALGLIB-Optimierungsmethoden anhand einfacher Beispiele aufgezeigt.
Als Beispiel für ein Optimierungsproblem wird eine einfache Zielfunktion verwendet, die maximiert werden muss. Es handelt sich um eine glatte monotone Funktion mit einem einzigen Maximum - ein umgekehrtes Paraboloid. Die Werte dieser Funktion liegen im Bereich [0; 1], unabhängig von der Anzahl der Argumente, die zum Bereich [-10; 10] gehören.
//—————————————————————————————————————————————————————————————————————————————— //Paraboloid, F(Xn) ∈ [0.0; 1.0], X ∈ [-10.0; 10.0], maximization double ObjectiveFunction (double &x []) { double sum = 0.0; for (int i = 0; i < ArraySize (x); i++) { if (x [i] < -10.0 || x [i] > 10.0) return 0.0; sum += (-x [i] * x [i] + 100.0) * 0.01; } return sum /= ArraySize (x); } //——————————————————————————————————————————————————————————————————————————————
BLEIC (Boundary, Linear Equality-Inequality Constraints)
BLEIC (Boundary, Linear Equality-Inequality Constraints) ist die Bezeichnung für eine Familie von Methoden, die zur Lösung von Optimierungsproblemen mit Gleichheiten und Ungleichheiten verwendet werden. Der Name der Methode leitet sich von der Klassifizierung der Zwänge ab, die sie in aktive und inaktive Zwänge an der aktuellen Stelle unterteilt. Die Methode reduziert ein Problem mit Nebenbedingungen in Form von Gleichheiten und Ungleichheiten auf eine Folge von Teilproblemen, die nur durch Gleichheiten begrenzt sind. Aktive Ungleichheiten werden als Gleichheiten behandelt, inaktive Ungleichheiten werden vorübergehend ignoriert (obwohl wir sie weiterhin beobachten). Informell ausgedrückt, bewegt sich der aktuelle Punkt entlang der durchführbaren Menge, wobei er an den Grenzen „klebt“ oder sich von ihnen „löst“.
1. Was bewirkt es? Sie sucht nach dem Minimum oder Maximum einer Funktion (z. B. nach dem höchsten Gewinn oder den niedrigsten Kosten), wobei verschiedene Einschränkungen berücksichtigt werden:
- Grenzen der Variablenwerte (z. B. kann der Preis nicht negativ sein)
- Gleichheit (z.B. die Summe der Gewichte in einem Portfolio sollte 100% betragen)
- Ungleichheit (z. B. das Risiko darf ein bestimmtes Niveau nicht überschreiten)
2. Wie funktioniert das? Der Speicherplatz ist begrenzt, d.h. es werden nicht alle Zwischenberechnungen gespeichert, sondern nur die wichtigsten. Nähert sich schrittweise einer Lösung an:
- Bewertet die aktuelle Situation
- Bestimmt die Richtung der Bewegung
- Macht einen Schritt in diese Richtung
- Prüft, ob Einschränkungen verletzt werden
- Passt die Bewegung bei Bedarf an
3. Merkmale:
- Die Funktion sollte „glatt“ sein (ohne scharfe Sprünge)
- Findet ein lokales Minimum anstelle eines globalen Minimums
- Empfindlich gegenüber anfänglicher Annäherung (Ausgangspunkt)
Ein einfaches Beispiel: Stellen Sie sich vor, Sie suchen einen Platz für den Bau eines Hauses auf einem Grundstück. Es gibt Einschränkungen: Das Haus muss eine bestimmte Größe haben (Gleichheit), darf nicht näher als X Meter von der Grundstücksgrenze entfernt sein (Ungleichheit) und muss sich innerhalb der Grundstücksgrenze befinden (Randbedingungen). Sie wollen, dass die Ansicht die beste ist (Zielfunktion). BLEIC wird das imaginäre Haus schrittweise auf dem Gelände „verschieben“, wobei alle Einschränkungen beachtet werden, bis der beste Standort für die Aussicht gefunden ist. Weitere Einzelheiten hierzu sowie zu den folgenden Algorithmen finden Sie auf der Bibliotheksseite des Autors.
Um die BLEIC-Methode und den Rest der ALGLIB-Bibliothek zu verwenden, müssen wir die Datei einschließen (die Bibliothek wird mit dem MetaTrader 5-Terminal geliefert, der Nutzer muss nichts zusätzlich installieren).
#include <Math\Alglib\alglib.mqh> Lassen Sie uns ein Skript entwickeln - ein Beispiel für effektives Arbeiten mit ALGLIB-Methoden. Ich werde die wichtigsten Schritte hervorheben, die für die Arbeit mit ALGLIB-Methoden typisch sind. Identische Codeblöcke werden ebenfalls in der entsprechenden Farbe hervorgehoben.
1. Festlegen der Randbedingungen des Problems, wie die Anzahl der Starts der Fitnessfunktion (Zielfunktion), die Bereiche der zu optimierenden Parameter und deren Schritt. Für die ALGLIB-Methoden müssen die Startwerte der optimierten Parameter „x“ (die Methoden sind deterministisch und die Ergebnisse hängen vollständig von den Anfangswerten ab, daher werden wir die Zufallszahlengenerierung im Bereich der Problemparameter anwenden) sowie die Skala „s“ (die Methoden reagieren empfindlich auf die Skala der Parameter im Verhältnis zueinander, in diesem Fall setzen wir die Skala auf „1“) festgelegt werden.
2. Deklarieren der Objekte, die für das Funktionieren des Algorithmus erforderlich sind.
3. Festlegen der externen Parameter des Algorithmus fest (Einstellungen).
4. Initialisierung des Algorithmus durch Übergabe der Bereiche und Schritte der zu optimierenden Parameter sowie der externen Parameter des Algorithmus an die Methode.
5. Durchführen der Optimierung.
6. Erhalten Sie die Optimierungsergebnisse zur weiteren Verwendung.
Denken Sie daran, dass der Nutzer keine Möglichkeit hat, den Optimierungsprozess zu beeinflussen oder ihn zu stoppen. Die Methode führt alle Operationen unabhängig voneinander aus und ruft die Fitnessfunktion innerhalb ihres Prozesses auf. Der Algorithmus kann die Fitnessfunktion beliebig oft aufrufen (es gibt keine Möglichkeit, diesen Stopp-Parameter für die BLEIC-Methode festzulegen), und der Nutzer kann nur die maximal zulässige Anzahl von Aufrufen selbst kontrollieren, indem er einen Versuch erzwingt, der Methode einen Stopp-Befehl zu übergeben.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Initialization of optimization parameters--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Create and initialize arrays for range bounds--------------------- double rangeMin [], rangeMax [], rangeStep; ArrayResize (rangeMin, params); ArrayResize (rangeMax, params); for (int i = 0; i < params; i++) { rangeMin [i] = -10; rangeMax [i] = 10; } rangeStep = DBL_EPSILON; double x []; double s []; ArrayResize (x, params); ArrayResize (s, params); ArrayInitialize (s, 1); // Generate random initial parameter values in given ranges---- for (int i = 0; i < params; i++) { x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0); } // Create objects for optimization------------------------------------------ C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinBLEICReportShell rep; // Set the parameters of the BLEIC optimization algorithm--------------------------- double diffStep = 0.00001; double epsg = 1e-16; double epsf = 1e-16; double epsi = 0.00001; CAlglib::MinBLEICCreateF (x, diffStep, fFunc.state); CAlglib::MinBLEICSetBC (fFunc.state, rangeMin, rangeMax); CAlglib::MinBLEICSetInnerCond (fFunc.state, epsg, epsf, rangeStep); CAlglib::MinBLEICSetOuterCond (fFunc.state, rangeStep, epsi); CAlglib::MinBLEICOptimize (fFunc.state, fFunc, frep, 0, obj); CAlglib::MinBLEICResults (fFunc.state, x, rep); // Output of optimization results----------------------------------------------- Print ("BLEIC, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
Da die Methode die Fitnessfunktion selbst aufruft (und nicht vom Nutzerprogramm aus), muss der Aufruf der Fitnessfunktion in einer Klasse verpackt werden, die von einer übergeordneten Klasse in der ALGLIB erbt (diese übergeordneten Klassen sind für verschiedene Methoden unterschiedlich). Deklarieren wir die Wrapper-Klasse als C_OptimizedFunction und legen die folgenden Methoden in der Klasse fest:
1. Func () ist eine virtuelle Methode, die in abgeleiteten Klassen außer Kraft gesetzt wird.2. Init () - Initialisierung der Klassenparameter. Innerhalb der Methode:
- Die Variablen für die Anzahl der Durchläufe und den besten Wert der Funktion werden initialisiert.
- Die Arrays c und cB sind für die Speicherung von Koordinaten reserviert.
Variablen:
- state - Objekt vom Typ CMinBLEICStateShell, das für die BLEIC-Methode spezifisch ist, wird beim Aufruf statischer Methoden des Algorithmus und beim Aufruf der Stopp-Methode verwendet.
- numberLaunches - aktuelle Anzahl der Starts (notwendig, um eine unkontrollierte oder zu lange Ausführung der Fitnessfunktion zu verhindern).
- maxNumbLaunchesAllowed - maximal zulässige Anzahl von Starts.
- fB - bester gefundener Wert der Fitnessfunktion.
- c [] - Array der aktuellen Koordinaten.
- cB [] - Array zum Speichern der besten Suchkoordinaten.
//—————————————————————————————————————————————————————————————————————————————— // Class for function optimization, inherits from CNDimensional_Func class C_OptimizedFunction : public CNDimensional_Func { public: C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // A virtual function to contain the function being optimized-------- virtual void Func (CRowDouble &x, double &func, CObject &obj); // Initialization of optimization parameters--------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinBLEICStateShell state; // State int numberLaunches; // Launch counter double fB; // Best found value of the objective function (maximum) double cB []; // Coordinates of the point with the best function value private: //------------------------------------------------------------------- double c []; // Array for storing current coordinates int maxNumbLaunchesAllowed; // Maximum number of function calls allowed }; //——————————————————————————————————————————————————————————————————————————————
Die Methode Func der C_OptimizedFunction ist für den Zugriff auf die Fitnessfunktion des Nutzers vorgesehen. Sie nimmt als Argumente den Vektor x (eine der Varianten der optimierten Parameter des Problems, die von der Optimierungsmethode vorgeschlagen werden), das Argument func, um den berechneten Wert der zurückgegebenen Fitnessfunktion zu akzeptieren, und das Objekt obj (dessen Zweck mir unklar ist, vielleicht ist es für die Fähigkeit reserviert, zusätzliche Informationen an/von der Methode zu übergeben). Die wichtigsten Etappen der Methode:
1. Der Zähler numberLaunches wird erhöht. Ihr Ziel ist es, die Anzahl der Methodenaufrufe von Func zu verfolgen.
2. Wenn die Anzahl der Starts den zulässigen Wert von maxNumbLaunchesAllowed überschreitet, setzt die Funktion den Wert func in DBL_MAX (den Maximalwert vom Typ „double“, die Methoden von ALGLIB sind darauf ausgelegt, Funktionen zu minimieren, dieser Wert bedeutet die schlechtestmögliche Lösung). Dann rufen wir die Funktion MinBLEICRequestTermination auf. Es signalisiert der Methode BLEIC, die Optimierung zu beenden.
3. In der nächsten Schleife werden die Werte aus dem Vektor x in das Array c kopiert. Dies ist notwendig, um diese Werte an die Fitnessfunktion des Nutzers weiterzugeben.
4. Die Funktion ObjectiveFunction wird aufgerufen. Sie berechnet den Wert der Zielfunktion für die aktuellen Werte im Array c. Das Ergebnis wird in ffVal gespeichert, während der Wert von func auf den negativen Wert von ffVal gesetzt wird (wir optimieren ein invertiertes Paraboloid, das maximiert werden muss, und BLEIC minimiert die Funktion, also drehen wir den Wert um).
5. Wenn der aktuelle Wert von ffVal den vorhergehenden besten Wert von fB übersteigt, wird fB aktualisiert und das Array cB kopiert den aktuellen Zustand von c. Dies ermöglicht es uns, den besten gefundenen Wert der Zielfunktion mit den entsprechenden Parametern zu verfolgen und bei Bedarf später darauf zurückzugreifen.
Die Funktion Func implementiert einen Aufruf einer nutzerdefinierten Fitnessfunktion und verfolgt, wie oft diese Funktion aufgerufen wurde, wobei die besten Ergebnisse aktualisiert werden. Sie steuert auch die Stoppbedingungen, wenn die Anzahl der Starts einen festgelegten Grenzwert überschreitet.
//—————————————————————————————————————————————————————————————————————————————— // Implementation of the function to be optimized void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj) { // Increase the function launch counter and limitation control---------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { func = DBL_MAX; CAlglib::MinBLEICRequestTermination (state); return; } // Copy input coordinates to internal array------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Calculate objective function value---------------------------------------- double ffVal = ObjectiveFunction (c); func = -ffVal; // Update the best solution found-------------------------------------- if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Nachdem wir das Testskript mit dem Algorithmus von BLEIC zur Optimierung der Parabelfunktion ausgeführt haben, erhalten wir das folgende Ergebnis im Ausdruck:
BLEIC, bestes Ergebnis: 0.6861786206145579, Anzahl der Funktionsstarts: 84022
Es ist erwähnenswert, dass der Algorithmus trotz der Aufforderung, die Optimierung mit der Methode MinBLEICRequestTermination zu beenden, den Prozess fortsetzte und weitere 74.022 Mal versuchte, auf die Fitnessfunktion zuzugreifen, wodurch die Grenze von 10.000 Durchläufen überschritten wurde.
Versuchen wir nun, BLEIC nicht einzuengen und lassen wir es nach eigenem Ermessen handeln. Die Ergebnisse waren wie folgt:
BLEIC, bestes Ergebnis: 1.0, Anzahl der Funktionsstarts: 72017
Wie wir sehen, ist BLEIC in der Lage, vollständig auf die Parabelfunktion zu konvergieren, aber in diesem Fall ist es unmöglich, die erforderliche Anzahl von Durchläufen der Zielfunktion im Voraus zu schätzen. Wir werden zu einem späteren Zeitpunkt umfassende Tests durchführen und die Ergebnisse auswerten.
Der Schritt der Differenzierung ist ein wichtiger Bestandteil des Algorithmus. Wenn wir z. B. einen sehr kleinen Schritt verwenden, z. B. 1e-16 anstelle von 0,00001, dann bleibt der Algorithmus vorzeitig stehen, mit folgendem Ergebnis:
BLEIC, bestes Ergebnis: 0.6615878186651468, Anzahl der Funktionsstarts: 4002
L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno)
Der Algorithmus L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno) ist ein effizientes Optimierungsverfahren, das speziell für die Lösung großer Probleme entwickelt wurde, bei denen die Anzahl der Variablen 1.000 übersteigt. Es handelt sich um eine Quasi-Newton-Methode, die einen begrenzten Speicherplatz zur Speicherung von Informationen über die Krümmung der Funktion verwendet, sodass die vollständige Hessische Matrix nicht explizit gespeichert und berechnet werden muss.
Das Prinzip des Algorithmus besteht darin, dass er ein quadratisches Modell der zu optimierenden Funktion unter Verwendung der letzten M Wertepaare und Gradienten konstruiert und verfeinert. Typischerweise ist M eine moderate Zahl, von 3 bis 10, was die Rechenkosten erheblich auf O(N-M) Operationen reduziert. Bei jeder Iteration berechnet der Algorithmus den Gradienten am aktuellen Punkt, bestimmt die Suchrichtung anhand der gespeicherten Vektoren und führt eine lineare Suche zur Bestimmung der Schrittlänge durch. Führt ein Schritt der Methode Quasi-Newton nicht zu einer ausreichenden Abnahme des Funktionswerts oder des Gradienten, erfolgt eine wiederholte Richtungsanpassung.
Das Hauptmerkmal von L-BFGS ist die positive Definitheit der approximativen Hessian, die garantiert, dass die Richtung des Verfahrens Quasi-Newton immer die Richtung des Abstiegs ist, unabhängig von der Krümmung der Funktion.
Die Funktionsweise des LBFGS in einfachen Worten:
1. Der Grundgedanke: Der Algorithmus versucht, das Minimum der Funktion zu finden, indem er sich allmählich dorthin „herabsenkt“, während er ein vereinfachtes (quadratisches) Modell der Funktion aufbaut, das er ständig verfeinert.
2. Wie genau wird das bewerkstelligt? Es merkt sich die letzten M Schritte (normalerweise 310 Schritte) und speichert bei jedem Schritt zwei Dinge:
- wo wir waren (Bedeutung)
- wohin wir uns bewegen können (Gefälle)
Auf der Grundlage dieser Daten konstruiert der Algorithmus eine Annäherung an die Funktionskrümmung (die Hess'sche Matrix) und verwendet diese Annäherung, um den nächsten Schritt zu bestimmen.
3. Merkmale: Er bewegt sich immer „nach unten“ (in Richtung abnehmender Funktionswert), geht sparsam mit dem Speicher um (speichert nur die letzten M Schritte) und arbeitet schnell (der Aufwand ist proportional zur Problemgröße × M).
4. Praktisches Beispiel. Stellen Sie sich vor, Sie gehen im Nebel einen Berg hinunter:
- Sie können nur die Richtung des Abstiegs am aktuellen Punkt bestimmen.
- Sie können sich an die letzten Schritte erinnern und daran, wie sich die Steigung verändert hat.
- Auf der Grundlage dieser Informationen können Sie vorhersagen, wo Sie am besten den nächsten Schritt setzen sollten.
5. Einschränkungen:
- Er kann bei sehr komplexen „Landschaften“ langsamer arbeiten.
- Er kann zusätzliche Konfiguration zur Verbesserung der Leistung erfordern.
Anders als bei der Methode BLEIC können Sie bei L-BFGS die Anzahl der Durchläufe der Zielfunktion direkt festlegen, aber es gibt keine Möglichkeit, Randbedingungen für die zu optimierenden Parameter anzugeben. Der Wert M ist im nachstehenden Beispiel auf „1“ eingestellt, die Verwendung anderer Werte führte nicht zu merklichen Veränderungen in der Leistung und im Verhalten des Algorithmus.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Initialization of optimization parameters--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Create and initialize arrays for search range bounds-------------- double rangeMin [], rangeMax [], rangeStep; ArrayResize (rangeMin, params); ArrayResize (rangeMax, params); for (int i = 0; i < params; i++) { rangeMin [i] = -10; rangeMax [i] = 10; } rangeStep = DBL_EPSILON; double x []; double s []; ArrayResize (x, params); ArrayResize (s, params); ArrayInitialize (s, 1); // Generate random initial parameter values in given ranges----- for (int i = 0; i < params; i++) { x [i] = rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0); } // Create objects for optimization------------------------------------------- C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinLBFGSReportShell rep; // Set the parameters of the L-BFGS optimization algorithm--------------------------- double diffStep = 0.00001; double epsg = 1e-16; double epsf = 1e-16; CAlglib::MinLBFGSCreateF (1, x, diffStep, fFunc.state); CAlglib::MinLBFGSSetCond (fFunc.state, epsg, epsf, rangeStep, numbTestFuncRuns); CAlglib::MinLBFGSSetScale (fFunc.state, s); CAlglib::MinLBFGSOptimize (fFunc.state, fFunc, frep, 0, obj); CAlglib::MinLBFGSResults (fFunc.state, x, rep); //---------------------------------------------------------------------------- Print ("L-BFGS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
In L-BFGS wird der Variablentyp „state“ durch CMinLBFGSStateShell festgelegt.
//—————————————————————————————————————————————————————————————————————————————— // Class for function optimization, inherits from CNDimensional_Func class C_OptimizedFunction : public CNDimensional_Func { public: //-------------------------------------------------------------------- C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // A virtual function to contain the function being optimized--------- virtual void Func (CRowDouble &x, double &func, CObject &obj); // Initialization of optimization parameters---------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinLBFGSStateShell state; // State int numberLaunches; // Launch counter double fB; // Best found value of the objective function (maximum) double cB []; // Coordinates of the point with the best function value private: //------------------------------------------------------------------- double c []; // Array for storing current coordinates int maxNumbLaunchesAllowed; // Maximum number of function calls allowed }; //——————————————————————————————————————————————————————————————————————————————
Mit dem Befehl MinLBFGSRequestTermination wird der Abbruch des Optimierungsprozesses angefordert.
//—————————————————————————————————————————————————————————————————————————————— // Implementation of the function to be optimized void C_OptimizedFunction::Func (CRowDouble &x, double &func, CObject &obj) { //Increase the function launch counter and limitation control------------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { func = DBL_MAX; CAlglib::MinLBFGSRequestTermination (state); return; } // Copy input coordinates to internal array------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Calculate objective function value---------------------------------------- double ffVal = ObjectiveFunction (c); func = -ffVal; // Update the best solution found-------------------------------------- if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Nachdem wir das Testskript mit dem Algorithmus L-BFGS zur Optimierung der Parabelfunktion ausgeführt haben, erhalten wir das folgende Ergebnis im Ausdruck:
L-BFGS, bestes Ergebnis: 0.6743844728276278, Anzahl der Funktionsstarts: 24006
Es ist sehr wahrscheinlich, dass der Parameter für die maximale Anzahl von Durchläufen der Zielfunktion nicht funktioniert, weil der Algorithmus tatsächlich mehr als zweimal mehr Durchläufe durchgeführt hat.
Lassen Sie es nun die Optimierung ohne Beschränkung der Anzahl der Durchläufe durchführen:
L-BFGS, bestes Ergebnis: 1.0, Anzahl der Funktionsstarts: 52013
Wie BLEIC ist auch L-BFGS in der Lage, vollständig auf die Parabelfunktion zu konvergieren, aber die Anzahl der Starts wird unkontrollierbar. Bei der Überprüfung des nächsten Algorithmus werden wir zeigen, dass dies ein wirklich großes Problem sein kann, wenn diese Nuance nicht berücksichtigt wird.
Für L-BFGS ist auch der Differenzierungsschritt wichtig. Wenn Sie einen sehr kleinen Schritt von 1e-16 verwenden, bleibt der Algorithmus nicht mehr vorzeitig bei diesem Ergebnis stecken:
L-BFGS, bestes Ergebnis: 0.6746423814003036, Anzahl der Funktionsstarts: 4001
NS (Nonsmooth Nonconvex Optimization Subject to box / linear / nonlinear - Nonsmooth Constraints)
NS (Nonsmooth Nonconvex Optimization Subject to box/linear/nonlinear - Nonsmooth Constraints) ist ein nicht-glatter nicht-konvexer Optimierungsalgorithmus zur Lösung von Problemen, bei denen die Zielfunktion nicht glatt und konvex ist. Dies bedeutet, dass die Funktion scharfe Änderungen, Winkel oder andere Merkmale aufweisen kann. Die Hauptmerkmale solcher Probleme sind, dass die Zielfunktion Unstetigkeiten oder abrupte Änderungen enthalten kann, die eine Analyse mit gradientenbasierten Methoden erschweren.
Zu den Grundsätzen des Algorithmus gehört die Gradientenschätzung, bei der ein Gradienten-Sampling-Verfahren zum Einsatz kommt, bei dem der Gradient an mehreren zufälligen Punkten um die aktuelle Lösung herum geschätzt wird. Dies hilft, Probleme im Zusammenhang mit den Besonderheiten der Funktion zu vermeiden. Auf der Grundlage der erhaltenen Gradientenschätzungen wird ein begrenztes quadratisches Programmierproblem (QP) gebildet. Die Lösung ermöglicht es uns, die Richtung zu bestimmen, in die wir gehen müssen, um die aktuelle Lösung zu verbessern. Der Algorithmus arbeitet iterativ und aktualisiert die aktuelle Lösung bei jeder Iteration auf der Grundlage der berechneten Gradienten und der Lösung des QP-Problems.
Betrachten wir einmal, was diese Beschreibung der Optimierung in einfachen Worten bedeutet:
1. NONSMOOTH (nicht-glatte Optimierung):
- Die Funktion kann Brüche oder „Risse“ aufweisen
- Keine Voraussetzung für kontinuierliche Differenzierbarkeit
- Es kann zu scharfen Übergängen und Sprüngen kommen.
2. NONCONVEX (nicht-konvex):
- Die Funktion kann mehrere lokale Minima und Maxima haben
- Die „Landschaft“ der Funktion kann aus „Hügeln“ und „Tälern“ bestehen
3. Constraint-Typen (CONSTRAINTS): BOX, LINEAR, NONLINEAR-NONSMOOTH (wie oben beschrieben).
Die Besonderheit dieser Methode besteht darin, dass die Parameter für den Löser AGS (Adaptive Gradient Sampling Method) spezifiziert und eingestellt werden müssen. Dieser Solver wurde entwickelt, um nicht-glatte Probleme mit Randbedingungen, linearen und nicht-linearen Nebenbedingungen zu lösen. Der AGS-Löser verfügt über mehrere wichtige Funktionen: spezielle Behandlung von Nebenbedingungen, Variablenskalierung (zur Behandlung schlecht skalierbarer Probleme) und integrierte Unterstützung für numerische Differenzierung.
Die wichtigste Einschränkung des AGS-Lösers ist, dass er nicht für hochdimensionale Probleme ausgelegt ist. Ein Schritt von AGS erfordert ungefähr 2-N Gradientenauswertungen an zufällig ausgewählten Punkten (im Vergleich dazu erfordert L-BFGS O(1) Auswertungen pro Schritt). In der Regel benötigen er O(N) Iterationen, um zu konvergieren, was zu O(N²) Gradientenschätzungen pro Optimierungssitzung führt.
Im Gegensatz zu den vorherigen Methoden erfordert NS die Verwendung des Typs CRowDouble für Randbedingungsvariablen anstelle des Typs double und Anfangswerte der optimierten Parameter des Problems. Außerdem müssen die Parameter für den AGS-Solver angegeben werden.
//—————————————————————————————————————————————————————————————————————————————— void OnStart () { // Initialization of optimization parameters--------------------------------------- int numbTestFuncRuns = 10000; int params = 1000; // Additionally, you need to specify -------------- CRowDouble rangeMin, rangeMax; rangeMin.Resize (params); rangeMax.Resize (params); double rangeStep; for (int i = 0; i < params; i++) { rangeMin.Set (i, -10); rangeMax.Set (i, 10); } rangeStep = DBL_EPSILON; CRowDouble x, s; x.Resize (params); s.Resize (params); s.Fill (1); // Generate random initial parameter values in given ranges---- for (int i = 0; i < params; i++) { x.Set (i, rangeMin [i] + ((rangeMax [i] - rangeMin [i]) * rand () / 32767.0)); } // Create objects for optimization------------------------------------------ C_OptimizedFunction fFunc; fFunc.Init (params, numbTestFuncRuns); CObject obj; CNDimensional_Rep frep; CMinNSReport rep; // Set the parameters of the NS optimization algorithm------------------------------ double diffStep = 0.00001; double radius = 0.8; double rho = 50.0; CAlglib::MinNSCreateF (x, diffStep, fFunc.state); CAlglib::MinNSSetBC (fFunc.state, rangeMin, rangeMax); CAlglib::MinNSSetScale (fFunc.state, s); CAlglib::MinNSSetCond (fFunc.state, rangeStep, numbTestFuncRuns); CAlglib::MinNSSetAlgoAGS (fFunc.state, radius, rho); CAlglib::MinNSOptimize (fFunc.state, fFunc, frep, obj); CAlglib::MinNSResults (fFunc.state, x, rep); // Output of optimization results----------------------------------------------- Print ("NS, best result: ", fFunc.fB, ", number of function launches: ", fFunc.numberLaunches); } //——————————————————————————————————————————————————————————————————————————————
Für die Methode NS muss eine Wrapper-Klasse erstellt werden, die nun von einer anderen übergeordneten Klasse, CNDimensional_FVec, abgeleitet wird. Wir müssen auch die virtuelle Methode in FVec ändern. Die Besonderheit der Methode besteht darin, dass es unmöglich ist, den Wert der Fitnessfunktion gleich DBL_MAX zurückzugeben, da die Methode in diesem Fall mit einem Fehler endet, im Gegensatz zu den vorherigen Optimierungsmethoden. Wir werden also ein zusätzliches Feld in die Klasse aufnehmen (fW), um die Worst-Case-Lösung während der Optimierung zu verfolgen.
//—————————————————————————————————————————————————————————————————————————————— // Class for function optimization, inherits from CNDimensional_FVec class C_OptimizedFunction : public CNDimensional_FVec { public: //-------------------------------------------------------------------- C_OptimizedFunction (void) { } ~C_OptimizedFunction (void) { } // A virtual function to contain the function being optimized-------- virtual void FVec (CRowDouble &x, CRowDouble &fi, CObject &obj); // Initialization of optimization parameters--------------------------------------- void Init (int coords, int maxNumberLaunchesAllowed) { numberLaunches = 0; maxNumbLaunchesAllowed = maxNumberLaunchesAllowed; fB = -DBL_MAX; fW = DBL_MAX; ArrayResize (c, coords); ArrayResize (cB, coords); } //---------------------------------------------------------------------------- CMinNSState state; // State int numberLaunches; // Launch counter double fB; // Best found value of the objective function (maximum) double fW; // Worst found value of the objective function (maximum) double cB []; // Coordinates of the point with the best function value private: //------------------------------------------------------------------- double c []; // Array for storing current coordinates int maxNumbLaunchesAllowed; // Maximum number of function calls allowed }; //——————————————————————————————————————————————————————————————————————————————
Fehlerhafte Aktionen werden in rot angezeigt. Stattdessen wird die schlechteste Lösung, die während der Optimierung gefunden wurde, zurückgegeben (mit einem Minuszeichen, da die Methode zur Minimierung dient). Und natürlich muss die Methode zum Aufrufen des Stopps der Methode in MinNSRequestTermination geändert werden.
//—————————————————————————————————————————————————————————————————————————————— void C_OptimizedFunction::FVec (CRowDouble &x, CRowDouble &fi, CObject &obj) { // Increase the function launch counter and limitation control---------------- numberLaunches++; if (numberLaunches >= maxNumbLaunchesAllowed) { //fi.Set (0, DBL_MAX); //Cannot return DBL_MAX value fi.Set (0, -fW); CAlglib::MinNSRequestTermination (state); return; } // Copy input coordinates to internal array------------------------- for (int i = 0; i < x.Size (); i++) c [i] = x [i]; // Calculate objective function value---------------------------------------- double ffVal = ObjectiveFunction (c); fi.Set (0, -ffVal); // Update the best and worst solutions found----------------------------- if (ffVal < fW) fW = ffVal; if (ffVal > fB) { fB = ffVal; ArrayCopy (cB, c); } } //——————————————————————————————————————————————————————————————————————————————
Nachdem wir das Testskript mit dem Algorithmus NS zur Optimierung der Parabelfunktion ausgeführt haben, erhalten wir das folgende Ergebnis im Ausdruck:
NS, bestes Ergebnis: 0.6605212238333136, Anzahl der Funktionsstarts: 1006503
Es scheint, dass der Parameter für die maximal zulässige Anzahl von Durchläufen der Zielfunktion auch bei NS nicht funktioniert, da der Algorithmus tatsächlich mehr als 1 Million Starts durchgeführt hat.
Versuchen wir nun, NS nicht einzuschränken und es die Optimierung ohne Beschränkung der Anzahl der Durchläufe durchführen zu lassen. Leider konnte ich nicht warten, bis das Skript zu Ende war, und musste seine Arbeit zwangsweise beenden, indem ich das Chart schloss:
Kein Ergebnis
Der Schritt der Differenzierung ist auch für NS wichtig. Wenn wir einen sehr kleinen Schritt von 1e-16 verwenden, bleibt der Algorithmus vorzeitig stehen - er bleibt stecken, ohne die für seine Arbeit vorgesehene Anzahl von Durchläufen der Zielfunktion zu nutzen, mit folgendem Ergebnis:
NS, bestes Ergebnis: 0.6784901840822722, Anzahl der Funktionsstarts: 96378
Schlussfolgerung
In diesem Artikel haben wir uns mit Optimierungsmethoden aus der Bibliothek ALGLIB vertraut gemacht. Wir haben uns die wichtigsten Merkmale dieser Methoden angesehen, deren Kenntnis nicht nur die Durchführung der Optimierung selbst ermöglicht, sondern auch dazu beiträgt, unangenehme Situationen wie eine unkontrollierte Anzahl von Aufrufen der Zielfunktion zu vermeiden.
Im nächsten, letzten Artikel über Optimierungsmethoden ALGLIB werden wir drei weitere Methoden im Detail untersuchen. Wir werden alle in Betracht gezogenen Methoden testen, was es uns ermöglichen wird, ihre Stärken und Schwächen in der praktischen Anwendung zu ermitteln, und die Ergebnisse unserer Forschung zusammenfassen. Darüber hinaus visualisieren wir traditionell die Funktionsweise von Algorithmen, um ihr charakteristisches Verhalten bei komplexen Testproblemen deutlich zu machen. So können wir besser verstehen, wie die einzelnen Methoden mit den verschiedenen Optimierungsproblemen umgehen.
Der Text des Artikels enthält vollständig funktionierende Skriptcodes für die Ausführung der Methoden von ALGLIB. Darüber hinaus finden Sie im Archiv alles, was Sie brauchen, um die besprochenen Methoden sofort zur Optimierung Ihrer Handelsstrategien und anderer Aufgaben einzusetzen. Damit ist das Ziel des Artikels - einfache und klare Beispiele für die Anwendung von Methoden zu zeigen - erreicht worden.
Mein besonderer Dank gilt Evgeniy Chernish, der mir geholfen hat, die Besonderheiten des Zugriffs auf die Bibliotheksmethoden von ALGLIB zu verstehen.
Programme, die im diesem Artikel verwendet werden
| # | Name | Typ | Beschreibung |
|---|---|---|---|
| 1 | Simple test ALGLIB BLEIC.mq5 | Skript | Testskript für die Arbeit mit BLEIC |
| 2 | Simple test ALGLIB LBFGS.mq5 | Skript | Testskript für die Arbeit mit L-BFGS |
| 3 | Simple test ALGLIB NS.mq5 | Skript | Testskript für die Arbeit mit NS |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/16133
Neuronale Netze im Handel: Der Contrastive Muster-Transformer (letzter Teil)
Entwicklung eines Expert Advisors für mehrere Währungen (Teil 19): In Python implementierte Stufen erstellen
Eine alternative Log-datei mit der Verwendung der HTML und CSS
Von der Grundstufe bis zur Mittelstufe: Union (I)
- Freie Handelsapplikationen
- Über 8.000 Signale zum Kopieren
- Wirtschaftsnachrichten für die Lage an den Finanzmärkte
Sie stimmen der Website-Richtlinie und den Nutzungsbedingungen zu.