Deterministische oszillatorische Suchmethode (DOS)
21
0
Inhalt
Einführung
Die Optimierungsalgorithmen werden ständig weiterentwickelt, um die grundlegenden Einschränkungen der traditionellen Methoden zu überwinden. Die meisten metaheuristischen Optimierungsalgorithmen stützen sich stark auf stochastische Prozesse und Zufallszahlen. Diese Ansätze zeigen zwar eine beeindruckende Fähigkeit, lokale Optima zu vermeiden, aber ihr nicht-deterministischer Charakter kann in Bereichen, in denen eine genaue Reproduzierbarkeit der Ergebnisse erforderlich ist, Probleme verursachen.
Der Artikel stellt die deterministische oszillatorische Suche (DOS) vor, einen neuen metaheuristischen Algorithmus, der die Vorteile traditioneller gradientenbasierter Methoden mit der Effizienz von Schwarmalgorithmen kombiniert, aber vollständig auf die Verwendung von Zufallszahlen verzichtet.
DOS wurde 2017 von Archana zur Lösung komplexer globaler Optimierungsprobleme entwickelt und basiert auf dem Konzept der oszillierenden Partikelbewegung in einem Suchraum mit einer deterministischen Verteilung der Ausgangspositionen. Das Hauptmerkmal des Algorithmus ist seine Fähigkeit, mehrdimensionale Probleme bei voller Reproduzierbarkeit zu behandeln: Bei gleichen Ausgangsbedingungen kommt der Algorithmus immer zum gleichen Ergebnis.
Im Gegensatz zu den meisten metaheuristischen Algorithmen führt DOS das Konzept der „Fitness-Steigung“ ein – einen Mechanismus, der es den Partikeln ermöglicht, zu beurteilen, ob ihre aktuelle Richtung die Lösung verbessert, und ihre Suchstrategie anzupassen. Die Partikel können sich in einem von drei Steigungszuständen befinden: positiv (Bewegung verbessert die Lösung), negativ (Bewegung verschlechtert die Lösung) oder unbekannt.
Diese Informationen werden genutzt, um das Schwingungsverhalten der Partikel zu steuern. Wenn herkömmliche Gradientenmethoden einen Punkt erreichen, an dem alle Richtungen zu einer Verschlechterung der Zielfunktion führen, hören sie auf. DOS überwindet diese Einschränkung durch einen aktivierten Schwarmmechanismus, wenn die oszillierende Bewegung keine Verbesserung bringt. In diesem Fall beginnt das Partikel, sich in Richtung der besten bekannten globalen Lösung zu bewegen.
In diesem Artikel werden wir die mathematischen Grundlagen des DOS-Algorithmus im Detail untersuchen, seine Eigenschaften und Implementierungsmerkmale analysieren und seine Effizienz anhand einer Reihe von Testproblemen demonstrieren.
Implementierung des Algorithmus
Nun wollen wir sehen, wie der DOS-Algorithmus funktioniert. Statt eines Random Walk verwendet DOS einen systematischen Ansatz, der aus einigen einfachen Regeln besteht. DOS verlässt sich nicht auf Zufälligkeiten. Der Algorithmus beginnt mit der Platzierung mehrerer „Entdecker“ (Partikel) an verschiedenen Punkten der Landschaft. Die Platzierung ist nicht zufällig, sondern wird durch eine spezielle Gleichung bestimmt, die die Region gleichmäßig abdeckt. Jeder Entdecker hat eine Ausgangsrichtung und eine Bewegungsgeschwindigkeit. Während der Entdecker sich vorwärtsbewegt, merkt er sich, ob das Gelände höher (besser) oder niedriger (schlechter) wird. Dies wird als „Steigung“ bezeichnet – eine einfache Methode, um festzustellen, ob Sie sich in die richtige Richtung bewegen.
Jetzt beginnt der Spaß. Wenn ein Entdecker feststellt, dass er aufgehört hat aufzusteigen und begonnen hat abzusteigen (seine Fitness hat sich verschlechtert), hört er nicht einfach auf oder kehrt um. Stattdessen prallt er gewissermaßen zurück – er dreht sich um und setzt seine Bewegung in die entgegengesetzte Richtung fort, allerdings mit einer geringeren Geschwindigkeit (der Hälfte seiner vorherigen Geschwindigkeit). Es ist wie ein Tennisball, der an einer Wand abprallt, nur mit weniger Energie.
Dieses Abprallen erzeugt eine oszillierende Bewegung, daher der Name des Algorithmus. Mit jedem Rückprall lokalisiert der Entdecker das Extremum genauer. Was aber, wenn der Entdecker in der Falle sitzt – ein kleiner Hügel, um den herum alles tiefer wird, und dieses Extremum nicht der höchste Punkt in der Region ist? Hier verwendet DOS eine andere Technik. Wenn der Entdecker versucht, sich in verschiedene Richtungen zu bewegen, aber überall auf einen Abstieg stößt, schaltet er in einen anderen Modus: dem „Schwärmen“. In diesem Modus bewegt er sich auf den besten Punkt zu, der bislang von allen Entdeckern (Partikeln) gefunden wurde.
Anders als bei der zufälligen Suche oder bei Versuch und Irrtum wird bei DOS der Lösungsraum systematisch erkundet, wobei Informationen über die Richtung der Verbesserung und die kollektive Erfahrung aller Entdecker genutzt werden. Gleichzeitig sind keine komplexen Ableitungsberechnungen oder die Speicherung einer umfangreichen Suchhistorie erforderlich. So findet DOS Schritt für Schritt unter Anwendung einfacher Bewegungs-, Reflexions- und Schwarmregeln optimale Lösungen für komplexe Probleme.
Die folgende Abbildung zeigt die folgenden Hauptaspekte des Algorithmus: einen zweidimensionalen Suchraum mit einem globalen Optimum und mehreren lokalen Optima, dargestellt durch Konturlinien, sowie einen Pfad vom Ausgangspunkt zum globalen Optimum, der das charakteristische Verhalten des DOS-Algorithmus veranschaulicht:
- die deterministische Ausgangsposition des Partikels,
- oszillierende (Zickzack-)Bewegung bei der Erkundung des Raums,
- eine anpassungsfähige Bewegung in Richtung des globalen Optimums.
Die wichtigsten Bestandteile des Algorithmus sind: deterministische Partikelinitialisierung, die Verwendung des Konzepts der Fitness-Steigung, oszillierende Bewegung und ein Schwarmmechanismus (Bewegung in Richtung der besten bekannten Lösung).
Der Steigungszustand kann sein:
- positiv (+1) – die aktuelle Bewegung verbessert die Fitness,
- negativ (-1) – die aktuelle Bewegung verschlechtert die Fitness,
- unbekannt (0) – Zustand während der Initialisierung oder nach einem Strategiewechsel.
Abb. 1. Funktionsweise des Algorithmus
Die Abbildung zeigt deutlich, wie DOS die Eigenschaften klassischer Gradientenmethoden (lokale Suche durch Oszillationen) mit den Fähigkeiten von Schwarmalgorithmen kombiniert und dabei ein vollständig deterministisches Verhalten beibehält. Nachdem die Funktionsprinzipien geklärt sind, können wir nun mit dem Schreiben des Pseudocodes des Algorithmus beginnen.
Schritt 1: Erste Vorbereitung
- Erstellen von Arrays zum Speichern von Positionen, Geschwindigkeiten, früheren Fitnesswerten und Steigungen für jedes Partikel
- Initialisierung der besten gefundenen Lösung mit dem kleinstmöglichen Fitnesswert
Schritt 2: Deterministische Partikelinitialisierung
- Für jedes Partikel:
- im Suchraum mithilfe einer deterministischen Gleichung so positionieren, dass eine gleichmäßige Abdeckung gewährleistet ist,
- die Anfangsgeschwindigkeit auf Null setzen,
- die anfängliche Steigung auf „unbekannt“ (0) setzen,
- den vorherigen Fitnesswert auf den kleinstmöglichen Wert setzen.
Schritt 3: Die Hauptschleife der Optimierung
- Wiederholen, bis die maximale Anzahl an Iterationen erreicht ist. Teil 1: Partikelbewegung
- Für jedes Partikel:
- den aktuellen Fitnesswert als vorherigen speichern
- die Position durch Addition der aktuellen Geschwindigkeit aktualisieren
- liegt die neue Position außerhalb der Suchgrenzen, sie auf die zulässigen Grenzen beschränken
- Für jedes Partikel:
- Berechnung des neuen Fitnesswerts
- Aktualisieren die beste Lösung, wenn die Fitness besser ist als die beste gefundene Lösung
- wenn die Steigung „unbekannt“ (0) ist:
- Setzen der Steigung auf „positiv“ (1), wenn die neue Fitness besser ist als die vorherige
- Setzen der Steigung auf „negativ“ (-1), wenn die neue Fitness schlechter ist als die vorherige
- Belassen der Steigung als „unbekannt“, wenn sich die Fitness nicht geändert hat
- wenn die Steigung „positiv“ (1) ist:
- wenn die neue Fitness schlechter ist als die vorherige:
- Ändern der Bewegungsrichtung in die entgegengesetzte Richtung
- Halbieren der Geschwindigkeit
- Setzen der Steigung auf „negativ“ (-1)
- wenn die neue Fitness schlechter ist als die vorherige:
- wenn die Steigung „negativ“ (-1) ist:
- wenn die neue Fitness schlechter ist als die vorherige:
- Anwenden des Schwarmmechanismus: zur aktuellen Geschwindigkeit den Vektor zur besten Lösung hinzufügen, multipliziert mit dem Bewegungsfaktor
- Setzen der Steigung auf „unbekannt“ (0)
- wenn die neue Fitness schlechter ist als die vorherige:
- Prüfen, ob die Geschwindigkeit Null oder nahe Null ist:
- wenn die Geschwindigkeit fast Null ist:
- Festlegen der Geschwindigkeit in Richtung der besten gefundenen Lösung multipliziert mit dem Bewegungsfaktor
- Setzen der Steigung auf „unbekannt“ (0)
- wenn die Geschwindigkeit fast Null ist:
- Für jedes Partikel:
Schritt 4: Abschluss
- Rückgabe der besten gefundenen Lösung und ihres Fitnesswerts
Jetzt können wir mit dem Schreiben des Codes für den DOS-Algorithmus beginnen. Erstellen wir eine Struktur, um den Partikelzustand während der Optimierung zu speichern. Diese Struktur enthält ein Feld zur Definition der Steigung der Geschwindigkeit (positiv, negativ oder undefiniert) und ein Array von Geschwindigkeitskomponenten nach Dimensionen, die eine bequeme Speicherung und Verarbeitung von Partikelbewegungsparametern ermöglichen.
Zur Initialisierung der Struktur wird eine Methode bereitgestellt, die die Steigung auf einen Standardwert setzt und ein Geschwindigkeits-Array einer bestimmten Größe erstellt, das mit Nullen gefüllt wird, um einen korrekten Ausgangszustand vor Beginn der Arbeit zu gewährleisten.
Zusätzlich wurde eine Geschwindigkeitsprüfung auf Null implementiert – eine Methode, die alle Geschwindigkeitskomponenten prüft und „true“ zurückgibt, wenn sie alle bei der angegebenen Genauigkeit praktisch Null sind, oder „false“ andernfalls. Auf diese Weise lässt sich feststellen, ob das Partikel einen stabilen Zustand erreicht hat oder sich weiter bewegen muss.
// Structure for storing particle velocity struct S_DOS_Velocity { int slope; // Particle slope (-1: negative, 0: unknown, 1: positive) double v []; // Velocity components for each dimension void Init (int dims) { slope = 0; ArrayResize (v, dims); ArrayInitialize (v, 0.0); // Quick initialization of the entire array to zeros } // Check for zero velocity bool IsZero (double epsilon = 1e-10) { for (int i = 0; i < ArraySize (v); i++) if (MathAbs (v [i]) > epsilon) return false; return true; } }; //——————————————————————————————————————————————————————————————————————————————
Die Klasse C_AO_DOS wird die Implementierung des Algorithmus darstellen. Sie erbt die Funktionalität von der Basisklasse C_AO und fügt eine spezifische Logik für die DOS-Methode hinzu. Die wichtigsten Merkmale der Klasse: Der Konstruktor initialisiert die Standardparameter, einschließlich der Populationsgröße und des Faktors der Bewegung in Richtung der besten Lösung, und erstellt ein Array von Parametern. Die Methode SetParams() ermöglicht, Parameter wie popSize und movementFactor zu setzen und zu überprüfen, und zwar vorbehaltlich von Beschränkungen. Die Methode Init() ist für die Vorbereitung der Anfangsbedingungen zuständig: Suchbereiche, Änderungsschritte und die Anzahl der Iterationen.
Logik der Partikelbewegung, Methoden:- Moving () implementiert den grundlegenden Mechanismus zur Bewegung von Partikeln im Suchraum, basierend auf aktuellen Geschwindigkeiten und Bewertungen.
- Revision () wird verwendet, um Positionen oder Geschwindigkeiten nach jedem Schritt anzupassen.
Innerhalb der Klasse ist die Struktur „S_DOS_Velocity velocities“ definiert, die die Geschwindigkeitskomponenten jedes Partikels in allen Dimensionen speichert und Methoden zur Initialisierung sowie zur Überprüfung der Nullgeschwindigkeit enthält.
Interne Methoden:- InitializeParticles() und ProcessParticleMovement() sind Hilfsfunktionen zur Initialisierung und Aktualisierung von Partikelpositionen. Sie liefern algorithmische Logik.
Insgesamt implementiert die Klasse einen strukturierten Ansatz für die DOS-Methode, bei dem jeder Parameter und jede Variable der gezielten Exploration des Lösungsraums mithilfe von Partikelpositionen, Geschwindigkeiten und Suchrichtungen dient.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_DOS : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_DOS () { } C_AO_DOS () { ao_name = "DOS"; ao_desc = "Deterministic Oscillatory Search"; ao_link = "https://www.mql5.com/en/articles/18154"; // Set default parameters popSize = 30; // population size movementFactor = 0.95; // movement factor towards the best solution // Create and initialize the parameters array ArrayResize (params, 2); params [0].name = "Population Size"; params [0].val = popSize; params [1].name = "Movement Factor"; params [1].val = movementFactor; } void SetParams () { // Set parameter values with validation popSize = (int)MathMax (5, params [0].val); // Minimum 5 particles for efficiency movementFactor = MathMax (0.1, MathMin (1.0, params [1].val)); // Limit from 0.1 to 1.0 } bool Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0); void Moving (); void Revision (); //---------------------------------------------------------------------------- double movementFactor; // movement factor towards the best solution S_DOS_Velocity velocities []; // Array of particle velocity structures private: //------------------------------------------------------------------- void InitializeParticles (); void ProcessParticleMovement (int particleIndex); }; //——————————————————————————————————————————————————————————————————————————————
Die Init-Methode ist für die Vorbereitung des Algorithmus auf die Ausführung zuständig. Zunächst wird die Basisinitialisierungsmethode aufgerufen, die die anfänglichen Suchbereiche und Schritte einrichtet, die für die Ausführung erforderlich sind. Nach erfolgreicher Grundinitialisierung wird Speicher für Arrays zugewiesen, in denen Informationen über Partikelgeschwindigkeiten gespeichert werden.
Für jedes Element der Population werden die Anfangsgeschwindigkeiten in allen Dimensionen berechnet, um die Anfangsdynamik der Partikelbewegung zu bestimmen. Schließlich wird eine Methode aufgerufen, die die Partikel auf eine bestimmte deterministische Weise in ihre Ausgangspositionen bringt und ihre Startpunkte im Suchraum festlegt.
Das Ergebnis dieser Methode ist eine vorbereitete Population von Partikeln mit bestimmten Anfangsbedingungen, die bereit ist, den iterativen Suchprozess zu beginnen.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_DOS::Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0) // number of epochs { // Standard C_AO initialization if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Allocating memory for arrays ArrayResize (velocities, popSize); // Initialize the velocities for each dimension for (int i = 0; i < popSize; i++) velocities [i].Init (coords); // Initialize particle positions deterministically InitializeParticles (); return true; } //——————————————————————————————————————————————————————————————————————————————
Die Methode Moving implementiert die Bewegung von Partikeln im Suchraum des DOS-Algorithmus und bearbeitet nacheinander jedes Partikel in der Population, wobei sie vom ersten bis zum letzten durchlaufen wird. Für jedes Partikel wird sein aktueller Fitnessfunktionswert „f“ gespeichert. Dies ist für den späteren Vergleich und die Feststellung einer Verbesserung oder Verschlechterung der Position des Partikels erforderlich.
Für jede Koordinate (Dimension) des Partikels wird ein neuer Wert berechnet, indem die entsprechende Geschwindigkeitskomponente zur aktuellen Koordinate addiert wird. Neue Koordinaten werden je nach Schritt auf die angegebenen Bereiche rangeMin[d] und rangeMax[d] begrenzt, damit die Partikel nicht über den zulässigen Suchbereich hinausgehen.
Bei der Methode Moving werden die Positionen der Partikel im Suchraum verändert, wobei die Informationen über den vorherigen Zustand erhalten bleiben und die Gültigkeit der neuen Koordinaten unter Berücksichtigung von Einschränkungen und Diskretisierung sichergestellt wird.
//+----------------------------------------------------------------------------+ //| Basic method of particle movement | //+----------------------------------------------------------------------------+ void C_AO_DOS::Moving () { // Handle all particles for (int i = 0; i < popSize; i++) { // Save the fitness value a [i].fP = a [i].f; // Calculate new coordinates based on velocity for (int d = 0; d < coords; d++) { // Update position a [i].c [d] += velocities [i].v [d]; // Round to the nearest acceptable step a [i].c [d] = u.SeInDiSp (a [i].c [d], rangeMin [d], rangeMax [d], rangeStep [d]); } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode Revision ist für die Aktualisierung der Informationen über die besten Lösungen und die Behandlung der Partikelbewegungen während der Suche zuständig. Die Methode verarbeitet nacheinander alle Partikel in der Population. Für jedes dieser Partikel wird geprüft, ob die aktuelle Lösung des Partikels den global besten Fitnesswert fB verbessert. Wenn ja, wird das beste Gesamtergebnis aktualisiert und die entsprechenden Koordinaten werden gespeichert. Für jedes Partikel wird eine eigene Methode aufgerufen, die für die Neuberechnung und Anpassung seiner Position auf der Grundlage von Änderungen der Fitnessfunktion verantwortlich ist.
Das Ergebnis des Verfahrens ist die Aktualisierung der besten Lösungen und die Vorbereitung des Systems auf die nächste Phase der Suche, in der sich die Partikel unter Berücksichtigung der letzten Aktualisierungen weiterbewegen können.
//+----------------------------------------------------------------------------+ //| Fitness function update method | //+----------------------------------------------------------------------------+ void C_AO_DOS::Revision () { // Handle each particle for (int i = 0; i < popSize; i++) { // Update the best solution if the current solution is better if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } // Handle particle motion based on fitness change ProcessParticleMovement (i); } } //——————————————————————————————————————————————————————————————————————————————
Die Methode ProcessParticleMovement ist für die Anpassung der Bewegung eines einzelnen Partikels im Suchraum auf der Grundlage von Änderungen seiner Fitnessfunktion und der aktuellen Richtungen zuständig. Wenn der Index ungültig ist, wird die Methode abgebrochen. Um den Zugriff zu beschleunigen, werden das aktuelle Fitness-Partikel, der vorherige Fitness-Wert und die aktuelle Bewegungssteigung gespeichert. Anhand der Differenz zwischen der aktuellen und der vorherigen Fitness sowie der aktuellen Steigung entscheidet der Algorithmus, in welche Richtung sich das Partikel bewegen soll:
- die Steigung unbekannt ist, wird ihre Richtung (positiv, negativ oder undefiniert) auf der Grundlage der Veränderung der Fitness bestimmt;
- war die Steigung positiv, aber die Fitness hat sich verschlechtert, wird die Steigung negativ, und die Geschwindigkeiten entlang aller Achsen werden halbiert, was zu einer Änderung der Bewegungsrichtung beiträgt;
- war die Steigung negativ und die Fitness hat sich verschlechtert, kommt es zum „Schwarmmodus“ – einer Bewegung in Richtung des globalen Optimums, bei der die Geschwindigkeiten entlang der Achsen in Richtung der besten Lösung zunehmen.
Wenn die Geschwindigkeiten in allen Richtungen gleich Null sind, wird die Bewegung in Richtung des globalen Optimums eingeleitet, indem die Geschwindigkeit auf der Grundlage der Differenz zwischen den aktuellen Koordinaten und den Koordinaten der global besten Lösung unter Berücksichtigung des Bewegungsverhältnisses festgelegt wird. Dadurch werden die Richtung und die Größe der Geschwindigkeit je nach Situation angepasst, sodass das Partikel angemessen auf Veränderungen der Fitness reagieren und „lernen“ kann, sich in die optimale Richtung zu bewegen.
Das ultimative Ziel der Methode ist es, eine dynamische und adaptive Bewegung der Partikel zu ermöglichen, wobei Änderungen in ihren lokalen und globalen Lösungen für eine effiziente Suche nach dem Optimum berücksichtigt werden.
//+----------------------------------------------------------------------------+ //| Handle particle motion after fitness update | //+----------------------------------------------------------------------------+ void C_AO_DOS::ProcessParticleMovement (int particleIndex) { // Local variables for access optimization double currentFitness = a [particleIndex].f; double previousFitness = a [particleIndex].fP; int currentSlope = velocities [particleIndex].slope; // Comparison of fitnesses to determine the movement direction double fitnessDiff = currentFitness - previousFitness; // Handle a slope according to the current state if (currentSlope == 0) // Unknown slope { // Determine the slope based on the change in fitness velocities [particleIndex].slope = (fitnessDiff > 0) ? 1 : (fitnessDiff < 0) ? -1 : 0; } else if (currentSlope == 1 && fitnessDiff < 0) // Positive slope and deterioration of fitness { // Change direction and decrease velocity for (int d = 0; d < coords; d++) velocities [particleIndex].v [d] *= -0.5; // Optimized form of division by 2 velocities [particleIndex].slope = -1; // Change the slope to negative } else if (currentSlope == -1 && fitnessDiff < 0) // Negative slope and fitness degradation { // Apply the swarming mechanism - movement towards the global optimum for (int d = 0; d < coords; d++) velocities [particleIndex].v [d] += (cB [d] - a [particleIndex].c [d]) * movementFactor; velocities [particleIndex].slope = 0; // Reset the slope as unknown } // Check for zero velocity using the structure method if (velocities [particleIndex].IsZero ()) { // Initialize the velocity by moving towards the global optimum for (int d = 0; d < coords; d++) velocities [particleIndex].v [d] = (cB [d] - a [particleIndex].c [d]) * movementFactor; // Reset the slope velocities [particleIndex].slope = 0; } } //——————————————————————————————————————————————————————————————————————————————
Testergebnisse
Schauen wir uns nun die Ergebnisse an. Es zeigt sich, dass der Algorithmus, der auf einem Gradientenverfahren mit eingebautem Schwarm-Effekt basiert, die Aufgaben besser bewältigt als herkömmliche Gradientenverfahren.
=============================
5 Hilly's; Func runs: 10000; result: 0.3422040822277234
25 Hilly's; Func runs: 10000; result: 0.3421751631202356
500 Hilly's; Func runs: 10000; result: 0.3421605659711745
=============================
5 Forest's; Func runs: 10000; result: 0.5708601371368296
25 Forest's; Func runs: 10000; result: 0.34628707444514434
500 Forest's; Func runs: 10000; result: 0.32879379664917996
=============================
5 Megacity's; Func runs: 10000; result: 0.19999999999999998
25 Megacity's; Func runs: 10000; result: 0.20923076923076928
500 Megacity's; Func runs: 10000; result: 0.23076923076922945
=============================
All score: 2.91248 (32.36%)
Die Visualisierung zeigt eine große Streuung in den Ergebnissen für niedrigdimensionale Funktionen.
DOS mit der Testfunktion Hilly
DOS auf der Testfunktion Forest
DOS mit der Testfunktion Megacity
In der Bewertungstabelle des Algorithmus der Populationsoptimierung wird DOS zu Informationszwecken aufgeführt.
| # | AO | Beschreibung | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | Suche über die gesamte Nachbarschaft | 0.94948 | 0.84776 | 0.43857 | 2.23581 | 1.00000 | 0.92334 | 0.39988 | 2.32323 | 0.70923 | 0.63477 | 0.23091 | 1.57491 | 6.134 | 68.15 |
| 2 | CLA | Code-Lock-Algorithmus (joo) | 0.95345 | 0.87107 | 0.37590 | 2.20042 | 0.98942 | 0.91709 | 0.31642 | 2.22294 | 0.79692 | 0.69385 | 0.19303 | 1.68380 | 6.107 | 67.86 |
| 3 | AMOm | Optimierung der Tiermigration M | 0.90358 | 0.84317 | 0.46284 | 2.20959 | 0.99001 | 0.92436 | 0.46598 | 2.38034 | 0.56769 | 0.59132 | 0.23773 | 1.39675 | 5.987 | 66.52 |
| 4 | (P+O)ES | (P+O) Entwicklungsstrategien | 0.92256 | 0.88101 | 0.40021 | 2.20379 | 0.97750 | 0.87490 | 0.31945 | 2.17185 | 0.67385 | 0.62985 | 0.18634 | 1.49003 | 5.866 | 65.17 |
| 5 | CTA | Kometenschweif-Algorithmus (joo) | 0.95346 | 0.86319 | 0.27770 | 2.09435 | 0.99794 | 0.85740 | 0.33949 | 2.19484 | 0.88769 | 0.56431 | 0.10512 | 1.55712 | 5.846 | 64.96 |
| 6 | TETA | Zeit-Evolutions-Reise-Algorithmus (Joo) | 0.91362 | 0.82349 | 0.31990 | 2.05701 | 0.97096 | 0.89532 | 0.29324 | 2.15952 | 0.73462 | 0.68569 | 0.16021 | 1.58052 | 5.797 | 64.41 |
| 7 | SDSm | stochastische Diffusionssuche M | 0.93066 | 0.85445 | 0.39476 | 2.17988 | 0.99983 | 0.89244 | 0.19619 | 2.08846 | 0.72333 | 0.61100 | 0.10670 | 1.44103 | 5.709 | 63.44 |
| 8 | BOAm | Billard-Optimierungsalgorithmus M | 0.95757 | 0.82599 | 0.25235 | 2.03590 | 1.00000 | 0.90036 | 0.30502 | 2.20538 | 0.73538 | 0.52523 | 0.09563 | 1.35625 | 5.598 | 62.19 |
| 9 | AAm | Algorithmus für das Bogenschießen M | 0.91744 | 0.70876 | 0.42160 | 2.04780 | 0.92527 | 0.75802 | 0.35328 | 2.03657 | 0.67385 | 0.55200 | 0.23738 | 1.46323 | 5.548 | 61.64 |
| 10 | ESG | Entwicklung sozialer Gruppen (joo) | 0.99906 | 0.79654 | 0.35056 | 2.14616 | 1.00000 | 0.82863 | 0.13102 | 1.95965 | 0.82333 | 0.55300 | 0.04725 | 1.42358 | 5.529 | 61.44 |
| 11 | SIA | Simuliertes isotropes Glühen (Joo) | 0.95784 | 0.84264 | 0.41465 | 2.21513 | 0.98239 | 0.79586 | 0.20507 | 1.98332 | 0.68667 | 0.49300 | 0.09053 | 1.27020 | 5.469 | 60.76 |
| 12 | ACS | künstliche, kooperative Suche | 0.75547 | 0.74744 | 0.30407 | 1.80698 | 1.00000 | 0.88861 | 0.22413 | 2.11274 | 0.69077 | 0.48185 | 0.13322 | 1.30583 | 5.226 | 58.06 |
| 13 | DA | dialektischer Algorithmus | 0.86183 | 0.70033 | 0.33724 | 1.89940 | 0.98163 | 0.72772 | 0.28718 | 1.99653 | 0.70308 | 0.45292 | 0.16367 | 1.31967 | 5.216 | 57.95 |
| 14 | BHAm | Algorithmus für schwarze Löcher M | 0.75236 | 0.76675 | 0.34583 | 1.86493 | 0.93593 | 0.80152 | 0.27177 | 2.00923 | 0.65077 | 0.51646 | 0.15472 | 1.32195 | 5.196 | 57.73 |
| 15 | ASO | Anarchische Gesellschaftsoptimierung | 0.84872 | 0.74646 | 0.31465 | 1.90983 | 0.96148 | 0.79150 | 0.23803 | 1.99101 | 0.57077 | 0.54062 | 0.16614 | 1.27752 | 5.178 | 57.54 |
| 16 | RFO | Optimierung des Royal Flush (joo) | 0.83361 | 0.73742 | 0.34629 | 1.91733 | 0.89424 | 0.73824 | 0.24098 | 1.87346 | 0.63154 | 0.50292 | 0.16421 | 1.29867 | 5.089 | 56.55 |
| 17 | AOSm | Suche nach atomaren Orbitalen M | 0.80232 | 0.70449 | 0.31021 | 1.81702 | 0.85660 | 0.69451 | 0.21996 | 1.77107 | 0.74615 | 0.52862 | 0.14358 | 1.41835 | 5.006 | 55.63 |
| 18 | TSEA | Schildkrötenpanzer-Evolutionsalgorithmus (joo) | 0.96798 | 0.64480 | 0.29672 | 1.90949 | 0.99449 | 0.61981 | 0.22708 | 1.84139 | 0.69077 | 0.42646 | 0.13598 | 1.25322 | 5.004 | 55.60 |
| 19 | DE | differentielle Evolution | 0.95044 | 0.61674 | 0.30308 | 1.87026 | 0.95317 | 0.78896 | 0.16652 | 1.90865 | 0.78667 | 0.36033 | 0.02953 | 1.17653 | 4.955 | 55.06 |
| 20 | SRA | Algorithmus für erfolgreiche Gastronomen (joo) | 0.96883 | 0.63455 | 0.29217 | 1.89555 | 0.94637 | 0.55506 | 0.19124 | 1.69267 | 0.74923 | 0.44031 | 0.12526 | 1.31480 | 4.903 | 54.48 |
| 21 | CRO | Optimierung chemischer Reaktionen | 0.94629 | 0.66112 | 0.29853 | 1.90593 | 0.87906 | 0.58422 | 0.21146 | 1.67473 | 0.75846 | 0.42646 | 0.12686 | 1.31178 | 4.892 | 54.36 |
| 22 | BIO | Optimierung der Blutvererbung (joo) | 0.81568 | 0.65336 | 0.30877 | 1.77781 | 0.89937 | 0.65319 | 0.21760 | 1.77016 | 0.67846 | 0.47631 | 0.13902 | 1.29378 | 4.842 | 53.80 |
| 23 | BSA | Vogelschwarm-Algorithmus | 0.89306 | 0.64900 | 0.26250 | 1.80455 | 0.92420 | 0.71121 | 0.24939 | 1.88479 | 0.69385 | 0.32615 | 0.10012 | 1.12012 | 4.809 | 53.44 |
| 24 | HS | Harmoniesuche | 0.86509 | 0.68782 | 0.32527 | 1.87818 | 0.99999 | 0.68002 | 0.09590 | 1.77592 | 0.62000 | 0.42267 | 0.05458 | 1.09725 | 4.751 | 52.79 |
| 25 | SSG | Setzen, Säen und Wachsen | 0.77839 | 0.64925 | 0.39543 | 1.82308 | 0.85973 | 0.62467 | 0.17429 | 1.65869 | 0.64667 | 0.44133 | 0.10598 | 1.19398 | 4.676 | 51.95 |
| 26 | BCOm | Optimierung mit der bakteriellen Chemotaxis M | 0.75953 | 0.62268 | 0.31483 | 1.69704 | 0.89378 | 0.61339 | 0.22542 | 1.73259 | 0.65385 | 0.42092 | 0.14435 | 1.21912 | 4.649 | 51.65 |
| 27 | ABO | Optimierung des afrikanischen Büffels | 0.83337 | 0.62247 | 0.29964 | 1.75548 | 0.92170 | 0.58618 | 0.19723 | 1.70511 | 0.61000 | 0.43154 | 0.13225 | 1.17378 | 4.634 | 51.49 |
| 28 | (PO)ES | (PO) Entwicklungsstrategien | 0.79025 | 0.62647 | 0.42935 | 1.84606 | 0.87616 | 0.60943 | 0.19591 | 1.68151 | 0.59000 | 0.37933 | 0.11322 | 1.08255 | 4.610 | 51.22 |
| 29 | FBA | Fraktal-basierter Algorithmus | 0.79000 | 0.65134 | 0.28965 | 1.73099 | 0.87158 | 0.56823 | 0.18877 | 1.62858 | 0.61077 | 0.46062 | 0.12398 | 1.19537 | 4.555 | 50.61 |
| 30 | TSm | Tabu-Suche M | 0.87795 | 0.61431 | 0.29104 | 1.78330 | 0.92885 | 0.51844 | 0.19054 | 1.63783 | 0.61077 | 0.38215 | 0.12157 | 1.11449 | 4.536 | 50.40 |
| 31 | BSO | Brainstorming-Optimierung | 0.93736 | 0.57616 | 0.29688 | 1.81041 | 0.93131 | 0.55866 | 0.23537 | 1.72534 | 0.55231 | 0.29077 | 0.11914 | 0.96222 | 4.498 | 49.98 |
| 32 | WOAm | Wal-Optimierungsalgorithmus M | 0.84521 | 0.56298 | 0.26263 | 1.67081 | 0.93100 | 0.52278 | 0.16365 | 1.61743 | 0.66308 | 0.41138 | 0.11357 | 1.18803 | 4.476 | 49.74 |
| 33 | AEFA | Algorithmus für künstliche elektrische Felder | 0.87700 | 0.61753 | 0.25235 | 1.74688 | 0.92729 | 0.72698 | 0.18064 | 1.83490 | 0.66615 | 0.11631 | 0.09508 | 0.87754 | 4.459 | 49.55 |
| 34 | AEO | Algorithmus zur Optimierung auf der Grundlage künstlicher Ökosysteme | 0.91380 | 0.46713 | 0.26470 | 1.64563 | 0.90223 | 0.43705 | 0.21400 | 1.55327 | 0.66154 | 0.30800 | 0.28563 | 1.25517 | 4.454 | 49.49 |
| 35 | CAm | Kamel-Algorithmus M | 0.78684 | 0.56042 | 0.35133 | 1.69859 | 0.82772 | 0.56041 | 0.24336 | 1.63149 | 0.64846 | 0.33092 | 0.13418 | 1.11356 | 4.444 | 49.37 |
| 36 | ACOm | Ameisen-Kolonie-Optimierung M | 0.88190 | 0.66127 | 0.30377 | 1.84693 | 0.85873 | 0.58680 | 0.15051 | 1.59604 | 0.59667 | 0.37333 | 0.02472 | 0.99472 | 4.438 | 49.31 |
| 37 | BFO-GA | Optimierung der bakteriellen Futtersuche — ga | 0.89150 | 0.55111 | 0.31529 | 1.75790 | 0.96982 | 0.39612 | 0.06305 | 1.42899 | 0.72667 | 0.27500 | 0.03525 | 1.03692 | 4.224 | 46.93 |
| 38 | SOA | einfacher Optimierungsalgorithmus | 0.91520 | 0.46976 | 0.27089 | 1.65585 | 0.89675 | 0.37401 | 0.16984 | 1.44060 | 0.69538 | 0.28031 | 0.10852 | 1.08422 | 4.181 | 46.45 |
| 39 | ABHA | Algorithmus für künstliche Bienenstöcke | 0.84131 | 0.54227 | 0.26304 | 1.64663 | 0.87858 | 0.47779 | 0.17181 | 1.52818 | 0.50923 | 0.33877 | 0.10397 | 0.95197 | 4.127 | 45.85 |
| 40 | ACMO | Optimierung atmosphärischer Wolkenmodelle | 0.90321 | 0.48546 | 0.30403 | 1.69270 | 0.80268 | 0.37857 | 0.19178 | 1.37303 | 0.62308 | 0.24400 | 0.10795 | 0.97503 | 4.041 | 44.90 |
| 41 | ADAMm | adaptive Momentabschätzung M | 0.88635 | 0.44766 | 0.26613 | 1.60014 | 0.84497 | 0.38493 | 0.16889 | 1.39880 | 0.66154 | 0.27046 | 0.10594 | 1.03794 | 4.037 | 44.85 |
| 42 | CGO | Chaos Game Optimization | 0.57256 | 0.37158 | 0.32018 | 1.26432 | 0.61176 | 0.61931 | 0.62161 | 1.85267 | 0.37538 | 0.21923 | 0.19028 | 0.78490 | 3.902 | 43.35 |
| 43 | ATAm | Algorithmus für künstliche Stämme M | 0.71771 | 0.55304 | 0.25235 | 1.52310 | 0.82491 | 0.55904 | 0.20473 | 1.58867 | 0.44000 | 0.18615 | 0.09411 | 0.72026 | 3.832 | 42.58 |
| 44 | CROm | Korallenriff-Optimierung M | 0.78512 | 0.46032 | 0.25958 | 1.50502 | 0.86688 | 0.35297 | 0.16267 | 1.38252 | 0.63231 | 0.26738 | 0.10734 | 1.00703 | 3.895 | 43.27 |
| 45 | CFO | Schwerkraftoptimierung | 0.60961 | 0.54958 | 0.27831 | 1.43750 | 0.63418 | 0.46833 | 0.22541 | 1.32792 | 0.57231 | 0.23477 | 0.09586 | 0.90294 | 3.668 | 40.76 |
| DOS | deterministische oszillatorische Suche | 0.34220 | 0.34218 | 0.34216 | 1.02654 | 0.57086 | 0.34629 | 0.32879 | 1.24594 | 0.20000 | 0.20923 | 0.23077 | 0.64000 | 2.912 | 32.36 | |
| RW | Neuroboids Optimierungsalgorithmus 2(joo) | 0.48754 | 0.32159 | 0.25781 | 1.06694 | 0.37554 | 0.21944 | 0.15877 | 0.75375 | 0.27969 | 0.14917 | 0.09847 | 0.52734 | 2.348 | 26.09 | |
Zusammenfassung
Der Algorithmus erfordert nur wenige Konfigurationsparameter (Populationsgröße und Bewegungsfaktor), was seine Anwendung vereinfacht und das Risiko einer Fehlkonfiguration verringert.
Das dreistufige Steigungssystem (positiv, negativ, unbekannt) gewährleistet ein adaptives Verhalten der Partikel in Abhängigkeit von der Qualität der aktuellen Suchrichtung. Dies ist die wichtigste Innovation des Algorithmus. Da es keine komplexen mathematischen Operationen gibt, ist es rechnerisch effizient.
Die Hauptstärke des Algorithmus liegt in der Kombination der Effizienz von Schwarmalgorithmen mit der Zuverlässigkeit und Reproduzierbarkeit deterministischer Methoden, obwohl deterministische Methoden im Allgemeinen stochastischen Methoden unterlegen sind, aber für die Lösung bestimmter Probleme sind solche Methoden gerechtfertigt.
Abbildung 2. Farbskala der Algorithmen nach den entsprechenden Tests
Abbildung 3. Histogramm der Algorithmus-Testergebnisse (Skala von 0 bis 100, je höher, desto besser, wobei 100 das maximal mögliche theoretische Ergebnis ist; im Archiv befindet sich ein Skript zur Berechnung der Bewertungstabelle)
Vor- und Nachteile von DOS:
Vorteile:
- Schnell.
- Sehr einfache Implementierung.
Nachteile:
- Streuung der Ergebnisse bei niedrigdimensionalen Funktionen.
Dem Artikel ist ein Archiv mit den aktuellen Versionen der Algorithmuscodes beigefügt. Der Autor des Artikels übernimmt keine Verantwortung für die absolute Richtigkeit der Beschreibung der kanonischen Algorithmen. An vielen von ihnen wurden Änderungen vorgenommen, um die Suchmöglichkeiten zu verbessern. Die in den Artikeln dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Experimente.
Programme, die in diesem Artikel verwendet werden
| # | Name | Typ | Beschreibung |
|---|---|---|---|
| 1 | #C_AO.mqh | Include | Übergeordnete Klasse von Populationsoptimierungsalgorithmen |
| 2 | #C_AO_enum.mqh | Include | Enumeration der Algorithmen zur Populationsoptimierung |
| 3 | TestFunctions.mqh | Include | Bibliothek mit Testfunktionen |
| 4 | TestStandFunctions.mqh | Include | Bibliothek mit Funktionen für die Testumgebung |
| 5 | Utilities.mqh | Include | Bibliothek mit Hilfsfunktionen |
| 6 | CalculationTestResults.mqh | Include | Skript zur Berechnung der Ergebnisse in der Vergleichstabelle |
| 7 | Testing AOs.mq5 | Skript | Die einheitliche Testumgebung für alle Algorithmen zur Populationsoptimierung |
| 8 | Simple use of population optimization algorithms.mq5 | Skript | Ein einfaches Beispiel für die Verwendung von Algorithmen zur Populationsoptimierung ohne Visualisierung |
| 9 | Test_AO_DOS.mq5 | Skript | DOS-Testumgebung |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/18154
Warnung: Alle Rechte sind von MetaQuotes Ltd. vorbehalten. Kopieren oder Vervielfältigen untersagt.
Dieser Artikel wurde von einem Nutzer der Website verfasst und gibt dessen persönliche Meinung wieder. MetaQuotes Ltd übernimmt keine Verantwortung für die Richtigkeit der dargestellten Informationen oder für Folgen, die sich aus der Anwendung der beschriebenen Lösungen, Strategien oder Empfehlungen ergeben.
Von der CPU zur GPU in MQL5: Ein praktisches OpenCL-Framework zur Beschleunigung von Analysen, Optimierungen und Mustererkennung
Arbitragehandel im Forex-Markt: Ein Matrix-Handelssystem mit Rückkehr zum fairen Wert mit Risikokontrolle
Auf Markov-Ketten basierendes Matrix-Prognosemodell
MetaTrader 5 und der MQL5-Wirtschaftskalender: Wie sich News in ein reproduzierbares Handelssystem umwandeln lassen
- 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.