Battle Royale Optimizer (BRO)
33
1
Inhalt
Einführung
In der metaheuristischen Optimierung, bei der Algorithmen häufig von natürlichen Prozessen, physikalischen Phänomenen und evolutionären Mechanismen inspiriert werden, ist eine grundlegend neue Inspirationsquelle aufgetaucht – Videospiele. Battle Royale Optimizer (BRO), entwickelt von Taymaz Rahkar Farshi, ist ein innovativer Optimierungsalgorithmus, der auf der Mechanik beliebter Battle Royale-Spiele wie PlayerUnknown's Battlegrounds (PUBG) basiert.
Der BRO-Algorithmus eröffnet eine neue Kategorie spielbasierter Optimierungsmethoden. Damit ergänzt er die etablierte Dreiteilung der Optimierungsverfahren, einschließlich der evolutionären Algorithmen, der Algorithmen der Schwarmintelligenz und der auf physikalischen Phänomenen basierenden Algorithmen, die zu der breiten Gruppe der populationsbasierten Optimierungsalgorithmen gehören. Im Gegensatz zu den Algorithmen der Schwarmintelligenz, bei denen die Agenten zusammenarbeiten, um ein gemeinsames Ziel zu erreichen, konkurrieren bei BRO die Individuen miteinander, um zu überleben und die beste Position im Suchraum zu besetzen.
Ein wesentliches Merkmal von BRO ist der einzigartige Mechanismus des Wettbewerbs und der Schadenszählung für Lösungen. Jede Lösung wird mit dem nächstgelegenen Nachbarn verglichen, und der Verlierer erleidet einen Schaden, während der Gewinner wieder bei null beginnt. Lösungen, die zu viel Schaden angehäuft haben, werden aus der Population entfernt und durch neue, zufällige Lösungen ersetzt, ähnlich wie Spieler in PUBG aus einem Match ausscheiden, nachdem sie kritischen Schaden erlitten haben. Dies bietet einen Mechanismus zur Erkundung des Suchraums.
Implementierung des Algorithmus
Der Battle Royale Optimizer (BRO) lässt sich bildlich als virtuelle Welt darstellen, in der viele Spieler auf einem Schlachtfeld landen und nur einer überleben kann. Das ist das Grundprinzip dieses Spielmodells. Übertragen wir dieses Konzept nun auf Optimierungsprobleme.
Zu Beginn des Algorithmus erstellen wir eine Population von Lösungen, die zufällig über den Suchraum verteilt sind. Jede Lösung ist ein einzigartiger „Spieler“, der eine bestimmte Position und die Qualität (Fitness) dieser Position hat. Dann beginnt der eigentliche Wettbewerbszyklus, bei dem jede Lösung mit dem nächstgelegenen Nachbarn verglichen wird, ähnlich wie Spieler, die in einer Schlacht gegeneinander antreten.
Wenn zwei Lösungen „aufeinandertreffen“, werden sie auf ihre Qualität hin verglichen. Die beste Lösung geht als Sieger hervor und erhält keinen Schaden, während die schlechteste Lösung zum Verlierer erklärt wird und einen Schadenspunkt erhält. Dieser Schadenszähler ist ein Schlüsselmerkmal des Algorithmus. Die unterlegene Lösung erleidet nicht nur Schaden, sie versucht auch, ihre Position zu verbessern, indem sie sich der besten bekannten Lösung in der Population annähert. Diese Bewegung simuliert den Wunsch zu überleben, indem man einen sichereren und vorteilhafteren Ort findet.
Wenn eine Lösung zu viel Schaden anhäuft (einen bestimmten Schwellenwert überschreitet), wird sie „aus dem Spiel genommen“ – aus der Population entfernt und durch eine neue Zufallslösung ersetzt. Es ist so, als ob ein Spieler in einem Battle Royale ausscheidet und im nächsten Spiel ein neuer Spieler auftaucht. Dieser Mechanismus gewährleistet eine ständige Erneuerung der Population und fördert die Vielfalt der Lösungen.
In regelmäßigen Abständen verkleinert der Algorithmus den Suchraum – analog zu einem schrumpfenden Spielfeld in einem Battle Royale, das die Spieler zwingt, enger zusammenzurücken. Die Suchgrenzen verengen sich um die beste gefundene Lösung, was die Population dazu zwingt, sich auf vielversprechendere Gebiete zu konzentrieren.
Dank dieses Ansatzes schafft der BRO-Algorithmus ein Gleichgewicht zwischen der Erkundung neuer Bereiche und der Nutzung bereits gefundener guter Lösungen. Unterlegene Lösungen werden in Richtung besserer Lösungen verschoben, um den Trend zur Verbesserung aufrechtzuerhalten, während Lösungen mit zu hohem Schaden durch neue Zufallslösungen ersetzt werden. Gleichzeitig wird durch die periodische Verkleinerung der Grenzen die lokale Suche nach vielversprechenden Lösungen intensiviert.
Abbildung 1. BRO-Algorithmus in Aktion
Diese Abbildung zeigt die Hauptkomponenten des Battle Royale Optimizer (BRO)-Algorithmus. Der Suchraum wird als 2D-Region mit Konturen dargestellt, die die Optimierungsfunktion symbolisieren (hellere Regionen stehen für bessere Lösungen). Die globale beste Lösung ist mit einem roten Stern in der Mitte des höchsten „Berges“ gekennzeichnet. Die siegreichen Lösungen sind mit grünen Punkten markiert – das sind Lösungen, die keinen Schaden haben (Gewinner im Vergleich zu ihren Nachbarn). Unterlegene Lösungen werden durch gelbe (mit 1 Schaden) und orangefarbene (mit 2 Schaden) Punkte dargestellt. Neue Zufallslösungen werden durch blaue Punkte dargestellt, die erscheinen, wenn eine Lösung zu viel Schaden anhäuft. Unterlegene Lösungen werden in Richtung der besten Lösung verschoben (durch die gestrichelten Pfeile dargestellt). Die Verkleinerung des Suchraums wird durch das orange gepunktete Kästchen in der Mitte der besten Lösung dargestellt.
Die wichtigsten Phasen des Algorithmus sind die Initialisierung, der Vergleich mit den Nachbarn, die Bewegung in Richtung einer besseren Lösung und die Verkleinerung des Suchraums.Die Lösungen im BRO-Algorithmus konkurrieren miteinander, und die Verlierer werden „beschädigt“. Lösungen mit zu großem Schaden werden durch neue, zufällige Lösungen ersetzt. Da das Prinzip des Algorithmus nun klar ist, können wir mit dem Schreiben von Pseudocode fortfahren.
Initialisierung:
- Erstelle eine Population von popSize
- Setze für jede Lösung den Schadenszähler auf 0
- Lege den maximalen Schadensschwellenwert maxDamage fest
- Bestimme die Anzahl der Epochen
- Berechne die Anfangsdeltas für die periodische Verkleinerung des Suchraums
Grundlegender Algorithmus:
- Erstellen der Ausgangspopulation:
- Für jede Lösung in der Population:
- Generiere Zufallskoordinaten innerhalb eines bestimmten Suchraums
- Für jede Lösung in der Population:
- Für jede Epoche:
- Aktualisiere die beste globale Lösung, sobald eine bessere Lösung gefunden wird
- Trage die „Kämpfe“ zwischen Lösungen aus:
- Für jede Lösung in der Population:
- Suche nach dem nächsten Nachbarn (Lösung mit minimalem Abstand)
- Vergleiche die Qualität der aktuellen Lösung mit der ihrer Nachbarn:
- Wenn die derzeitige Lösung besser ist:
- Setze den Schadenszähler der aktuellen Lösung zurück
- Erhöhe den Schadenszähler des Nachbarn
- Der Verlierer (Nachbar) bewegt sich in Richtung der besten Lösung
- ansonsten:
- Erhöhe den Schadenszähler der aktuellen Lösung
- Setze den Schadenszähler des Nachbarn zurück
- Der Verlierer (aktuelle Lösung) bewegt sich in Richtung der besten Lösung
- Wenn die derzeitige Lösung besser ist:
- Für jede Lösung in der Population:
- Behandeln der stark beschädigten Lösungen:
- Für jede Lösung in der Population:
- Wenn der Schadenszähler ≥ maxDamage :
- Setze den Schadenszähler zurück
- Ersetze die Lösung durch eine neue zufällige Lösung
- Wenn der Schadenszähler ≥ maxDamage :
- Für jede Lösung in der Population:
- Periodische Verkleinerung des Suchraums:
- Wenn die aktuelle Epochennummer durch delta teilbar ist:
- Berechne die Standardabweichungen der Koordinaten für die gesamte Population
- Grenze den Suchraum um die beste Lösung herum ein
- Aktualisiere Delta
- Wenn die aktuelle Epochennummer durch delta teilbar ist:
- Rückgabe der besten gefundenen Lösung
Der Algorithmus verwendet die folgenden Gleichungen:
- Berechne den anfänglichen Delta-Wert, um den Suchraum einzugrenzen: delta = ⌊epochs / log₁₀(epochs)⌋
- Berechne den euklidischen Abstand zwischen den Lösungen: distance = √(∑(a[idx1][c] – a[idx2][c])²)
- Verschiebe eine unterlegene Lösung hin zu einer global besseren Lösung: a[i][c] = a[i][c] + r × (cB[c] – a[i][c])
- Berechne den Durchschnittswert für jede Koordinate: mean[c] = (∑a[i][c]) / popSize
- Berechne die Standardabweichung für jede Koordinate: sdValues[c] = √(∑(a[i][c] – mean[c])² / popSize)
- Gleichungen zur Verkleinerung des Suchraums: newMin[c] = cB[c] – sdValues[c] newMax[c] = cB[c] + sdValues[c]
- Aktualisiere den Parameter Delta nach Verkleinerung des Raums: delta = delta + ⌊delta / 2⌉
Der Autor schlägt die folgende Gleichung vor, um den Suchraum periodisch einzugrenzen: Δ (delta) = maxEpochs / log₁₀(maxEpochs). Das Schaubild ist unten abgebildet:
Abbildung 2. Abhängigkeit des Parameters Delta von der Anzahl der Epochen
Der Graph von delta = epochs/log₁₀(epochs) ist für die Funktionsweise des BRO-Algorithmus wichtig, da er bestimmt, nach wie vielen Iterationen der Suchraum eingegrenzt wird. Wie aus dem Diagramm ersichtlich ist, steigt der Delta-Wert mit der Anzahl der Epochen, jedoch nicht so schnell wie die Epochen selbst, was auf die Division durch den Logarithmus zurückzuführen ist. Dadurch entsteht eine nichtlineare Beziehung, die folgende Vorteile bietet: In den frühen Phasen der Optimierung (mit einer geringen Anzahl von Epochen) tritt die Verkleinerung relativ häufig auf, was dem Algorithmus hilft, sich schnell auf vielversprechende Bereiche zu konzentrieren, und in den späteren Phasen (mit einer großen Anzahl von Epochen) tritt die Verengung weniger häufig auf, was eine gründlichere Erkundung bereits identifizierter vielversprechender Bereiche ermöglicht.
In meinen Experimenten habe ich die Gleichung für den Delta-Parameter geändert, indem ich den Logarithmus zweimal angewendet habe. Diese Version hat besser abgeschnitten.
// Calculate the initial delta to narrow the search space delta = (int)MathFloor(epochs / MathLog(MathLog(epochs)));
Kommen wir nun zur Codierung. Wir werden eine nutzerdefinierte Klasse (C_AO_BRO) implementieren, die von der Basisklasse (C_AO) erbt, d.h. sie erbt alle öffentlichen und geschützten Mitglieder der Klasse C_AO und kann deren Verhalten überschreiben. Diese Klasse wird die Implementierung des Optimierungsalgorithmus auf der Grundlage des Battle Royale-Konzepts sein.
1. Öffentliche Klassenmitglieder:
- popSize – legt die Größe der Population fest.
- maxDamage – legt die maximale Schadensschwelle fest, d. h. wie viele „Treffer“ die Lösung verkraften kann, bevor sie eliminiert wird.
- SetParams () – Die Methode SetParams() aktualisiert die popSize- und maxDamage-Werte auf der Grundlage der im params-Array gespeicherten Werte, sodass Sie die Algorithmusparameter zur Laufzeit ändern können.
- Init () – Methode zur Initialisierung des Algorithmus. Akzeptierte Parameter:
- rangeMinP [] – Mindestwerte des Suchbereichs für jede Variable.
- rangeMaxP [] – maximale Suchbereichswerte.
- rangeStepP [] – Suchschritt für jede Variable.
- epochsP – Anzahl der Epochen (Iterationen) des Algorithmus. Der Standardwert ist 0.
- Moving () – grundlegende Logik des Verschiebens oder Aktualisierens von Lösungen im Suchraum.
- Revision () – Logik der Revision aktueller Lösungen; hier wird der „Schaden“, der durch jede Lösung entsteht, bewertet.
- maxDamage – öffentliches Mitglied, das den maximalen Schadensschwellenwert speichert.
2. Private Felder der Klasse:
- delta – Intervall für die Verkleinerung des Suchraums. Dient zur Anpassung der Suchschrittgröße während der Optimierung.
- damages [] – die Schadenszähler für jede Lösung in der Population.
- epoch – aktuelle Epoche des Algorithmus (Iterationsnummer).
- epochs – maximale Anzahl von Epochen (Iterationen) des Algorithmus.
3. Hilfsmethoden:
- FindNearestNeighbor () – findet den nächstgelegenen Nachbarn für eine Lösung bei einem bestimmten Index. Wird für Wechselwirkungen zwischen Lösungen verwendet.
- CalculateDistance () – Abstand zwischen zwei Lösungen, die durch ihre Indizes identifiziert werden.
- CalculateStandardDeviations () – berechnet die Standardabweichungen der Lösungswerte der Population, die zur Schätzung der Populationsvielfalt und zur Anpassung der Suchparameter verwendet werden.
- ShrinkSearchSpace () – Methode schränkt den Suchraum ein. Dies ist eine Standardtechnik zur Konvergenz eines Algorithmus zu einer optimalen Lösung.
Allgemeine Idee:
C_AO_BRO ist eine Klasse mit dem Algorithmus des Battle Royale Optimizer, und die Grundidee des Algorithmus ist, kurz gesagt, wie folgt:
- Initialisierung – eine Population von Zufallslösungen wird in einem bestimmten Suchraum erstellt.
- Bewertung – jede Lösung wird anhand einer Zielfunktion (Fitnessfunktion) bewertet.
- Battle Royale – Lösungen „konkurrieren“ miteinander (werden anhand der Werte der Zielfunktion verglichen).
- Schaden – einige Lösungen erhalten abhängig vom Ausgang der „Kämpfe“ Schadenspunkte.
- Eliminierung – Lösungen, deren „Schadenswert“ größer als maxDamage ist, werden aus der Population entfernt.
- Erneuerung/Ersatz – entfernte Lösungen werden durch neue Zufallslösungen ersetzt.
- Verkleinerung des Suchraums – Der Suchraum kann eingegrenzt werden, um sich auf die vielversprechendsten Bereiche zu konzentrieren.
- Wiederholung – die Schritte 2-7 werden für eine bestimmte Anzahl von Epochen wiederholt.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_BRO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_BRO () { } C_AO_BRO () { ao_name = "BRO"; ao_desc = "Battle Royale Optimizer"; ao_link = "https://www.mql5.com/en/articles/17688"; popSize = 100; // population size maxDamage = 3; // maximum damage threshold ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "maxDamage"; params [1].val = maxDamage; } void SetParams () { popSize = (int)params [0].val; maxDamage = (int)params [1].val; } bool Init (constdouble &rangeMinP [],// minimum search range const double &rangeMaxP [], // maximum search range const double &rangeStepP [], // search step const int epochsP = 0); // number of epochs void Moving (); void Revision (); //---------------------------------------------------------------------------- int maxDamage; // maximum damage threshold private: //------------------------------------------------------------------- int delta; // interval for shrinking the search space int damages []; // amount of damage for each solution int epoch; // current epoch int epochs; // maximum number of epochs // Auxiliary methods int FindNearestNeighbor (int index); double CalculateDistance (int idx1, int idx2); void CalculateStandardDeviations (double &sdValues []); void ShrinkSearchSpace (); }; //——————————————————————————————————————————————————————————————————————————————
Die Methode Init() initialisiert den BRO-Algorithmus, indem sie StandardInit() zur Standardinitialisierung unter Verwendung der übergebenen Suchbereiche und Schritte aufruft. Wenn StandardInit „false“ zurückgibt, gibt die Methode Init() ebenfalls „false“ zurück, was einen Initialisierungsfehler signalisiert. Sie initialisiert das Array „damages“, indem es Speicher für jede Lösung in der Population popSize zuweist und die anfängliche „damage“-Zahl jeder Lösung auf 0 setzt. Die Gesamtzahl der „Epochen“ wird eingestellt und die aktuelle „Epoche“ wird auf 0 zurückgesetzt.
Der „Delta“-Wert wird auf der Grundlage der Gesamtzahl der Epochen berechnet, sodass der Suchraum schrittweise eingegrenzt wird. Ist „delta“ kleiner oder gleich 0, wird der Wert auf 1 gesetzt. Im Allgemeinen bereitet diese Methode den Algorithmus für den Betrieb vor, indem sie seine grundlegenden Parameter und Datenstrukturen initialisiert.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_BRO::Init (const double &rangeMinP [], // minimum search range const double &rangeMaxP [], // maximum search range const double &rangeStepP [], // search step const int epochsP = 0) // number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Initialize damage counters for each solution ArrayResize (damages, popSize); ArrayInitialize (damages, 0); // Set epochs epochs = epochsP; epoch = 0; // Calculate the initial 'delta' to narrow the search space delta = (int)MathFloor (epochs / MathLog10 (epochs)); if (delta <= 0) delta = 1; return true; } //——————————————————————————————————————————————————————————————————————————————
Die Methode Moving() implementiert die Logik für die Initialisierung der Lösungspopulation, wobei jede Koordinate jeder Lösung zufällig zwischen den angegebenen Minimal- und Maximalbereichen rangeMin und rangeMax erzeugt und mit einem bestimmten rangeStep diskretisiert wird. Die Methode gewährleistet, dass die Population nur einmal initialisiert wird.
/—————————————————————————————————————————————————————————————————————————————— void C_AO_BRO::Moving () { if (!revision) { // Initialize the population with random decisions for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; } } //——————————————————————————————————————————————————————————————————————————————
Die Methode Revision() ist ein wichtiger Schritt im BRO-Optimierungsalgorithmus. Bei jeder Iteration der Methode wird die beste Lösung aktualisiert: Wenn eine Lösung in der aktuellen Population besser ist als die derzeit beste globale Lösung, wird die beste globale Lösung aktualisiert.
Die Methode vergleicht Lösungen mit ihren Nachbarn: Für jede Lösung wird ein nächster Nachbar in der Population gefunden. Dann werden ihre Funktionswerte verglichen. Die beste Lösung des Paares wird „belohnt“, indem ihr Schadenszähler zurückgesetzt wird, während der Schadenszähler der schlechtesten Lösung steigt. Die schlechteste Lösung des Paares wird in Richtung der global besten Lösung verschoben.
Als Nächstes werden die „beschädigten“ Lösungen ersetzt: Wenn eine Lösung genug „Schaden“ angesammelt hat (den maxDamage-Wert erreicht hat), wird sie durch eine neue, zufällig generierte Lösung ersetzt. In regelmäßigen Abständen wird der Suchraum in Abhängigkeit von der „Delta“-Variablen eingegrenzt. Dieser Vorgang wird über mehrere Iterationen des Algorithmus wiederholt. Durch den Vergleich mit Nachbarn werden Lösungen in günstigere Bereiche des Suchraums verschoben.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BRO::Revision () { epoch++; // Update the global best solution for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } // Compare each solution with its nearest neighbor and update damage counters for (int i = 0; i < popSize; i++) { int neighbor = FindNearestNeighbor (i); if (neighbor != -1) { if (a [i].f >= a [neighbor].f) { // Solution i wins damages [i] = 0; damages [neighbor]++; // The loser (neighbor) moves toward the best solution for (int c = 0; c < coords; c++) { double r = u.RNDfromCI (0, 1); a [neighbor].c [c] = a [neighbor].c [c] + r * (cB [c] - a [neighbor].c [c]); a [neighbor].c [c] = u.SeInDiSp (a [neighbor].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } else { // Solution i loses damages [i]++; damages [neighbor] = 0; // The loser (i) moves to the best solution for (int c = 0; c < coords; c++) { double r = u.RNDfromCI (0, 1); a [i].c [c] = a [i].c [c] + r * (cB [c] - a [i].c [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } } // Check if any solution has reached maximum damage and replace it for (int i = 0; i < popSize; i++) { if (damages [i] >= maxDamage) { // Reset the damage counter damages [i] = 0; // Generate a new random solution for (int c = 0; c < coords; c++) { double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]); } } } // Periodic narrowing of the search space if (epochs > 0 && epoch % delta == 0) { ShrinkSearchSpace (); // Update delta delta = delta + (int)MathRound (delta / 2); } } //——————————————————————————————————————————————————————————————————————————————
Die Methode FindNearestNeighbor() findet den Index des nächsten Nachbarn für die Lösung mit „index“ in der Population. Sie durchläuft alle Lösungen, berechnet den Abstand zu jeder von ihnen (mit Ausnahme der „Index“-Lösung selbst) und gibt den Index der Lösung mit dem geringsten Abstand zurück. Wenn der nächste Nachbar nicht gefunden werden konnte (z. B. weil es nur eine Lösung in der Population gibt), wird -1 zurückgegeben. Kurz gesagt, die Methode findet den nächsten Nachbarn für eine bestimmte Lösung.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_BRO::FindNearestNeighbor (int index) { double minDistance = DBL_MAX; int nearestIndex = -1; for (int i = 0; i < popSize; i++) { if (i == index) continue; double distance = CalculateDistance (index, i); if (distance < minDistance) { minDistance = distance; nearestIndex = i; } } return nearestIndex; } //——————————————————————————————————————————————————————————————————————————————
Die Methode CalculateDistance() berechnet den euklidischen Abstand zwischen zwei Lösungen in der Population anhand ihrer Indizes idx1 und idx2. Zunächst wird die Variable distanceSum auf Null initialisiert. Diese Variable akkumuliert die Summe der Quadrate der Koordinatendifferenzen. Die „for“-Schleife iteriert über alle Lösungskoordinaten. Bei jeder Iteration der Schleife wird die Differenz zwischen den entsprechenden Koordinaten der Lösungen idx1 und idx2 berechnet. Das Quadrat dieser Differenz wird zu distanceSum addiert.
Nach Beendigung der Schleife gibt die Methode die Quadratwurzel von distanceSum zurück, d. h. den euklidischen Abstand zwischen den beiden Lösungen. Letztendlich liefert die Methode einen numerischen Wert, der den „Abstand“ zwischen zwei Lösungen im Suchraum wiedergibt. Je größer dieser Wert ist, desto weiter liegen die Lösungen auseinander.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_BRO::CalculateDistance (int idx1, int idx2) { double distanceSum = 0.0; for (int c = 0; c < coords; c++) { double diff = a [idx1].c [c] - a [idx2].c [c]; distanceSum += diff * diff; } return MathSqrt (distanceSum); } //——————————————————————————————————————————————————————————————————————————————
Die Methode CalculateStandardDeviations() berechnet die Standardabweichung für jede Lösungskoordinate in der Population und speichert die Ergebnisse in dem Array sdValues. Die Größe des Eingabefeldes sdValues wird so angepasst, dass es die Standardabweichung für jede der „coords“-Koordinaten speichern kann. Anschließend wird in der Schleife über jede Lösungskoordinate iteriert und die Standardabweichung berechnet. Die Methode setzt die Summe der quadratischen Abweichungen für die aktuelle Koordinate zurück und setzt dann auch ihren Mittelwert zurück. Die Schleife summiert die Werte der aktuellen Koordinate c für alle Lösungen in der Population. Dann wird der Durchschnittswert der Koordinate berechnet.
Berechnung der Summe der quadrierten Abweichungen: Die Schleife iteriert über alle Lösungen in der Population und berechnet die Summe der quadratischen Abweichungen vom Mittelwert für die aktuelle Koordinate. Sie berechnet die Differenz zwischen dem Wert der Koordinate c für die Lösung i und ihrem Mittelwert. Das Quadrat der Differenz wird zur Summe der Abweichungsquadrate addiert. Die Standardabweichung wird berechnet als die Quadratwurzel aus der Summe der Abweichungsquadrate der Abweichungen, geteilt durch die Population. Das Ergebnis wird in dem entsprechenden Element des Arrays sdValues gespeichert.
Letztendlich berechnet die Methode ein Maß für die Streuung der Werte für jede Lösungskoordinate in der Population und speichert es in dem übergebenen Array sdValues. Die Standardabweichung zeigt, wie stark die Koordinatenwerte um den Mittelwert schwanken.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BRO::CalculateStandardDeviations (double &sdValues []) { ArrayResize (sdValues, coords); for (int c = 0; c < coords; c++) { double sum = 0.0; double mean = 0.0; // Calculate the average for (int i = 0; i < popSize; i++) mean += a [i].c [c]; mean /= popSize; // Calculate the sum of squared deviations for (int i = 0; i < popSize; i++) { double diff = a [i].c [c] - mean; sum += diff * diff; } sdValues [c] = MathSqrt (sum / popSize); } } //——————————————————————————————————————————————————————————————————————————————
Die Methode ShrinkSearchSpace() verkleinert den Suchraum auf der Grundlage der Standardabweichungen der Koordinaten und des Standorts der besten gefundenen Lösung. Bildlich gesprochen konzentriert sich die Suche auf einen vielversprechenden Bereich, für den es bereits eine gute Lösung gibt.
Zunächst werden die Standardabweichungen berechnet. Dies geschieht durch den Aufruf der Methode CalculateStandardDeviations(), die die Standardabweichungen für jede Lösungskoordinate in der Population berechnet und in dem Array sdValues speichert. Dies gibt an, wie stark die Werte der einzelnen Koordinaten in der Population variieren. Berechnung der neuen Grenzen: Neue Grenzen werden um die beste gefundene Lösung zentriert, und ihre Breite wird durch die Standardabweichung bestimmt. Wenn die Standardabweichung klein ist, wird die Suche auf die beste Lösung eingegrenzt. Wenn die Standardabweichung groß ist, bleibt die Suche breiter. Gültigkeitsprüfung: Die Suche geht nicht über den ursprünglich machbaren Lösungsraum hinaus.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BRO::ShrinkSearchSpace () { double sdValues []; CalculateStandardDeviations (sdValues); for (int c = 0; c < coords; c++) { // The new boundaries are centered around the best solution with a standard deviation width double newMin = cB [c] - sdValues [c]; double newMax = cB [c] + sdValues [c]; // Make sure the new bounds are within the original constraints if (newMin < rangeMin [c]) newMin = rangeMin [c]; if (newMax > rangeMax [c]) newMax = rangeMax [c]; // Update the boundaries rangeMin [c] = newMin; rangeMax [c] = newMax; } } //——————————————————————————————————————————————————————————————————————————————
Testergebnisse
Nach der Durchführung von Tests ist klar, dass der Algorithmus bei Hilly- und Forest-Funktionen recht gut funktioniert, bei der diskreten Megacity-Funktion sind die Konvergenzraten jedoch viel schwächer.
BRO|Battle Royale Optimizer|50.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7494493002235458
25 Hilly's; Func runs: 10000; result: 0.4983307394255448
500 Hilly's; Func runs: 10000; result: 0.27994639979348446
=============================
5 Forest's; Func runs: 10000; result: 0.6962444245506945
25 Forest's; Func runs: 10000; result: 0.3845619185097379
500 Forest's; Func runs: 10000; result: 0.20427058729050862
=============================
5 Megacity's; Func runs: 10000; result: 0.3815384615384616
25 Megacity's; Func runs: 10000; result: 0.21107692307692308
500 Megacity's; Func runs: 10000; result: 0.10607692307692404
=============================
All score: 3.51150 (39.02%)
Die Visualisierung zeigt die Streuung der Ergebniswerte und schwächere Suchmöglichkeiten bei der letzten diskreten Megacity-Funktion.
BRO mit der Testfunktion Hilly
BRO mit der Testfunktion Forest
BRO mit der Testfunktion Megacity
Auf der Grundlage der Testergebnisse belegt der BRO-Algorithmus den letzten Platz in der Rangliste der populationsbasierten Optimierungsalgorithmen.
| # | 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-Sperr-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) Evolutionsstrategien | 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) Evolutionsstrategien | 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 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | ASHA | Algorithmus für künstliches Duschen | 0.89686 | 0.40433 | 0.25617 | 1.55737 | 0.80360 | 0.35526 | 0.19160 | 1.35046 | 0.47692 | 0.18123 | 0.09774 | 0.75589 | 3.664 | 40.71 |
| 44 | ASBO | Optimierung des adaptiven Sozialverhaltens | 0.76331 | 0.49253 | 0.32619 | 1.58202 | 0.79546 | 0.40035 | 0.26097 | 1.45677 | 0.26462 | 0.17169 | 0.18200 | 0.61831 | 3.657 | 40.63 |
| 45 | BRO | Battle Royale Optimizer | 0.74945 | 0.49833 | 0.27995 | 1.52773 | 0.69624 | 0.38456 | 0.20427 | 1.28507 | 0.38154 | 0.21108 | 0.10608 | 0.69870 | 3.512 | 39.02 |
| 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 BRO-Algorithmus zeigt einen interessanten Ansatz für die metaheuristische Optimierung, der den Weg zu „spielbasierten“ Methoden mit der Battle-Royale-Metapher eröffnet, bei denen Lösungen gegeneinander antreten. Die Stärken des Algorithmus sind die konzeptionelle Einfachheit, die Intuitivität, die relativ einfache Implementierung, die automatische Verkleinerung des Suchraums auf der Grundlage statistischer Merkmale der Population und die Verwendung des Konzepts des nächsten Nachbarn für lokale Wettbewerbe. Der BRO-Algorithmus ist eine vielversprechende Optimierungsmethode, deren Potenzial noch lange nicht ausgeschöpft ist.
Abbildung 3. Farbabstufung der Algorithmen nach den entsprechenden Tests
Abbildung 4. 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)
BRO Vor- und Nachteile:
Vorteile:
- Interessante Idee.
- Einfache Umsetzung.
- Vielversprechende Entwicklung.
Nachteile:
- Schwache Ergebnisse bei diskreten Funktionen.
Der Artikel wird von einem Archiv mit den aktuellen Versionen der Codes der Algorithmen begleitet. 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 Versuche.
In diesem Artikel verwendete Programme
| # | 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 den Prüfstand |
| 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_BRO.mq5 | Skript | BRO-Testumgebung |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/17688
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 Grundstufe bis zur Mittelstufe: Struktur (III)
Pair-Trading: Algorithmischer Handel mit automatischer Optimierung auf Basis von Z-Score-Differenzen
Neuronale Netze im Trading: Adaptive Erkennung von Marktanomalien (DADA)
Neuronale Netze im Trading: Duales Clustering multivariater Zeitreihen (Abschlussteil)
- 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.