Algorithmus der Delfin-Echoortung (DEA)
14
0
Inhalt
Einführung
Mit jedem neuen Artikel kommen wir unserem Ziel näher: einen geeigneten Algorithmus zur Lösung von Optimierungsproblemen mit unseren Handelsrobotern zu finden. Wir werden einen weiteren, von der Natur inspirierten Algorithmus untersuchen, der auf den Echoortungsfähigkeiten einiger Meerestiere basiert.
Stellen Sie sich einen Delfin vor, der in den dunklen Tiefen des Ozeans auf Beutejagd geht. Die Sicht ist praktisch gleich null, doch das hindert ihn nicht daran, erfolgreich Beute zu finden. Das Geheimnis liegt in einer erstaunlichen Fähigkeit: Der Delfin sendet eine Reihe von Klicklauten aus und gewinnt aus dem reflektierten Echo ein präzises Bild der Umgebung. Interessant ist, dass die Häufigkeit dieser Klicks variiert: Bei einer allgemeinen Suche sind Klicks selten, während sie häufiger auftreten, wenn das Ziel in der Nähe ist. Es ist diese ungewöhnliche Strategie, die die Grundlage des DEA (Dolphin Echolocation Algorithm) bildet.
In der Welt der Optimierung stehen wir oft vor einer ähnlichen Herausforderung: Wir müssen die beste Lösung in einem riesigen Raum von Möglichkeiten finden, ohne den vollständigen Überblick zu haben. Wie ein Delfin im Ozean beginnen wir mit einer umfassenden Suche und konzentrieren uns nach und nach auf die vielversprechendsten Bereiche.
Implementierung des Algorithmus
Um besser zu verstehen, wie der Algorithmus funktioniert, stellen wir uns folgende Situation vor. Sie und ihre Freunde suchen an einem großen Strand mit Metalldetektoren nach Gold. Zu Beginn der Suche ist es sinnvoll, sich über das gesamte Gebiet zu verteilen – so ist die Wahrscheinlichkeit größer, dass man auf etwas Interessantes stößt. Sobald jedoch einer von Ihnen ein starkes Signal empfängt, informiert er die anderen, und nach und nach konzentriert sich das gesamte Team auf vielversprechende Bereiche/Positionen. Am Ende der Suche graben alle in der Nähe des stärksten Signals. Das ist der Kern des Delfin-Echoortungsalgorithmus.
In dem Algorithmus übernehmen Suchagenten – Punkte im Lösungsraum – die Rolle der Delfine. Jeder dieser Delfine steht für eine mögliche Lösung des Problems. Wenn wir beispielsweise das Minimum einer einfachen Funktion y = x² suchen, könnte sich ein Delfin am Punkt x = -3 (wo y = 9) befinden, ein anderer am Punkt x = 1 (wo y = 1), und der dritte landet zufällig am Punkt x = 0 (wo y = 0) – das ist dann unser Spitzenkandidat.
Aber wie tauschen Delfine Informationen aus? An dieser Stelle kommt der sogenannte effektive Echoortungsradius, der mit Re bezeichnet wird, ins Spiel. Überlegen Sie, wie weit sich das Licht einer Taschenlampe ausbreitet. Bei Re = 1 haben wir einen schmalen Lichtstrahl, der nur die unmittelbare Umgebung ausleuchtet. Bei Re = 3 breitet sich das Licht weiter aus und deckt einen größeren Bereich ab. Bei Re = 5 oder höher verhält sich die Suche eher wie ein Flutlicht. Im Zusammenhang mit dem Algorithmus bedeutet dies, dass sich Informationen über eine gute Lösung auf benachbarte Bereiche ausbreiten und die Stärke dieses Einflusses mit zunehmender Entfernung abnimmt.
All diese Informationen werden in Form einer Karte der Erfolgsaussichten zusammengefasst, die der Algorithmus als akkumulierte Fitness (AF) bezeichnet. Stellen Sie sich eine Heatmap einer Stadt vor, auf der Bereiche hoher Aktivität angezeigt werden. In unserem Fall sind aktive Zonen Gebiete, in denen Delfine gute Beute gefunden haben. Je erfolgreicher die Funde in einem bestimmten Gebiet sind, desto heißer wird es und zieht andere Delfine an.
Der Algorithmus ist jedoch intelligenter, als die Suche einfach nur auf einen Ort zu konzentrieren. Er verwendet einen Parameter namens vorgegebene Wahrscheinlichkeit (Predetermined Probability, PP), der das Gleichgewicht zwischen der Exploration neuer Gebiete und der Exploitation bereits gefundener guter Stellen steuert. Zu Beginn, wenn der PP-Wert niedrig ist (etwa 0,1), probiert der Algorithmus verschiedene Ansätze aus; wenn der PP-Wert dann bei etwa 0,5 liegt, stützt er sich stärker auf bewährte Verfahren, und wenn sich der PP-Wert der 1 nähert, wendet er nur noch die effektivsten Methoden an.
Schauen wir uns ein konkretes Beispiel an, wie der Algorithmus funktioniert. Nehmen wir an, wir suchen den höchsten Punkt in einer hügeligen Gegend. Zu Beginn der Suche sind unsere Delfine zufällig über das gesamte Gebiet verteilt – einige im Tal, andere an den Hängen und wieder andere haben das Glück, auf einem Hügel zu stehen. Nachdem der Algorithmus die Höhe jeder Position ausgewertet hat, stellt er fest, dass der Delfin ganz oben den besten Platz gefunden hat. Nun geschieht etwas Interessantes: Die Umgebung dieses glücklichen Delfins wird für die anderen attraktiver, aber – und das ist der entscheidende Punkt – genau der Ort, an dem sich der Anführer befindet, wird vorübergehend auf Null gesetzt. Dies zwingt andere Delfine dazu, die umliegenden Gebiete zu erkunden, anstatt sich an einem Ort zu versammeln. Dieser Ansatz hilft dabei, eine vorzeitige Konvergenz zu vermeiden und andere potenziell gute Lösungen zu finden.
Während der Algorithmus läuft, verändert sich das Bild. Bei Iteration 50 lässt sich beobachten, dass sich die Delfine allmählich in hügeligen Gebieten ansammeln, dabei aber weiterhin eine gewisse Vielfalt aufweisen. Bei der 100. Iteration konzentrieren sich die meisten bereits auf die höchsten Punkte des Geländes; am Ende konzentrieren sich alle Delfine im Bereich des globalen Maximums. Die Effizienz des Algorithmus hängt von der korrekten Konfiguration der Parameter ab.
Die Wahl des effektiven Re-Radius ist wichtig, um ein Gleichgewicht zwischen lokaler und globaler Suche herzustellen. Bei Re = 1 erhalten wir eine sehr präzise, aber eng fokussierte Suche – als würden wir mit einer Lupe nach einer Nadel im Heuhaufen suchen. Wenn man den Re-Wert auf 3–4 erhöht, erhält man einen ausgewogenen Ansatz, ähnlich wie beim Suchen mit einer Taschenlampe. Und wenn Re größer als 5 ist, funktioniert der Algorithmus wie ein Scheinwerfer: Er deckt größere Bereiche ab, verliert dabei jedoch an Genauigkeit.
Der Parameter Power bestimmt, wie abrupt der Algorithmus von der Exploration zur Exploitation wechselt. Bei Power = 1 verläuft dieser Übergang sanft und allmählich. Ein Power-Wert von 2 (empfohlen) führt zu einem ausgeprägteren Übergang, während Werte ab 3 einen noch schärferen Übergang bewirken, was für bestimmte Aufgaben nützlich sein kann.
Die Anfangswahrscheinlichkeit von PP1 bestimmt das anfängliche Gleichgewicht zwischen Exploration und Exploitation. Ein niedriger Wert (0,05) bedeutet eine intensive Exploration des Raums, der Standardwert von 0,1 sorgt für ein gutes Gleichgewicht, und ein hoher Wert (0,5) führt zu einer schnellen Fokussierung auf die gefundenen Lösungen.
Der Hauptvorteil von DEA liegt in seiner Anpassungsfähigkeit – der Algorithmus passt das Gleichgewicht zwischen der Exploration neuer Gebiete und der intensiveren Suche in vielversprechenden Bereichen automatisch an. Dennoch ist es relativ einfach und erfordert lediglich die Konfiguration von vier Einstellungen. Der Mechanismus der Informationsweitergabe durch die akkumulierte Fitness ermöglicht eine effiziente Exploitation des Wissens über den Suchraum, und das Nullsetzen der AF-Werte an den besten Positionen hilft, ein Feststecken in lokalen Optima zu vermeiden.
Natürlich hat der Algorithmus einige Einschränkungen. Es ist zusätzlicher Speicherplatz erforderlich, um die akkumulierte Fitness aller Alternativen zu speichern, was bei sehr großen Suchräumen ein Problem darstellen kann. Und vielleicht noch etwas: Die Effizienz des Algorithmus hängt von der richtigen Wahl des effektiven Echoortungsradius Re ab. Nachfolgend finden Sie eine schematische Darstellung der Funktionsweise des Algorithmus.
Abb. 1. Der DEA-Algorithmus in Aktion
Die wichtigsten Schritte des DEA-Algorithmus sind in der Abbildung dargestellt:
- Erste Exploration – Delfine (Suchagenten) an zufälligen Positionen mit einem Echoortungsradius von Re.
- Verteilung der akkumulierten Fitness (AF) – wie sich die AF um die Positionen der Delfine herum ansammelt.
- Der Konvergenzprozess besteht aus drei Teilphasen, die den Übergang von der Exploration zur Exploitation verdeutlichen.
Die Abbildung veranschaulicht, wie Delfine mithilfe der Echoortung das Optimum finden, wie Informationen durch die akkumulierte Fitness weitergegeben werden, wie der Parameter Re die Suchbreite beeinflusst und wie PP das Gleichgewicht zwischen Exploration und Exploitation steuert. Schlüsselbegriffe – Formeln für PP (vorgegebene Wahrscheinlichkeit) und AF. Algorithmus-Flussdiagramm – grundlegende Schritte in einem Zyklus. Einfluss des Re-Parameters – Darstellung von engem, mittlerem und großem Einflussradius.
Die Farbcodierung in der Abbildung: Blau – normale Delfine, Rot – die beste Lösung, blaue Farbverläufe – akkumulierte Fitnesswerte, Grau – Suchraum.
Da wir nun einen Überblick über den Algorithmus haben, können wir damit fortfahren, einen detaillierten Pseudocode zu schreiben.
Eingaben:
- Anzahl der Delfine (Suchagenten)
- Effektiver Echoortungsradius
- Grad der Konvergenzkurve
- Anfängliche vorgegebene Wahrscheinlichkeit
- Grenzen des Suchraums und Diskretisierungsschritt für jede Dimension
Initialisierung:
Erzeugen des Alternativenraums:
- Erzeuge für jede Dimension des Suchraums eine Menge möglicher Alternativen
- Wenn eine Schrittweite angegeben ist, erstelle Alternativen mit diesem Schritt, von minimal bis maximal
- Wenn kein Schritt angegeben ist, werden 500 gleichmäßig verteilte Alternativen generiert
- Überprüfe den effektiven Echoortungsradius: Er sollte ein Viertel der Anzahl der Alternativen nicht überschreiten
Anfängliche Platzierung der Delfine:
- Platziere alle Delfine zufällig im Suchraum
- Berechne für jeden Delfin die Qualität seiner Position (Fitness)
- Setze die akkumulierte Fitness für alle Alternativen auf Null.
Grundlegende Optimierungsschleife:
Wiederhole dies für eine bestimmte Anzahl von Iterationen:
Phase 1. Berechnung der vorgegebenen Wahrscheinlichkeit
Berechne die Wahrscheinlichkeit, dass die beste Position bei der aktuellen Iteration beibehalten wird. Zu Beginn des Prozesses entspricht diese Wahrscheinlichkeit dem Ausgangswert und steigt dann gemäß einer Potenzfunktion allmählich an, bis sie am Ende der Optimierung den Wert 1 erreicht.
Phase 2. Berechnung des dynamischen Anpassungskoeffizienten
Berechne den Koeffizienten, der das Gleichgewicht zwischen lokaler und globaler Suche bestimmt. Der Koeffizient entspricht dem Verhältnis der Differenz zwischen der besten und der schlechtesten Lösung zur Summe der Abweichungen aller Lösungen von der besten Lösung. Wenn die Population heterogen ist, ist der Koeffizient hoch; wenn sie konvergiert, ist er niedrig.
Phase 3. Akkumulation von Fitness-Informationen
Für jeden Delfin:
- Die Fitness relativ zum aktuellen Bereich in der Population normieren
- Ermittle für jede Koordinate die nächstgelegene Alternative zur Position des Delfins
- Informationen über die Qualität innerhalb des Echoortungsradius dieser Alternative verteilen
- Die Stärke des Einflusses nimmt linear mit der Entfernung vom Zentrum ab
- Reflexion an den Grenzen des Raums anwenden, um Informationen zu erhalten
- Füge allen akkumulierten Fitnesswerten einen kleinen Wert hinzu, um Wahrscheinlichkeiten von null zu vermeiden
Schritt 4. Zurücksetzen der Informationen für die beste Position
Finde den Delfin mit der besten Lösung und setze die akkumulierte Fitness für die Alternativen, die seinen Koordinaten entsprechen, auf null zurück. Dadurch wird verhindert, dass sich die Suche zu sehr auf einen Punkt konzentriert.
Schritt 5. Neue Positionen auswählen
Für jeden Delfin und jede seiner Koordinaten:
- Wenn dies der beste Delfin ist und die Position mit einer entsprechenden Wahrscheinlichkeit beibehalten wird, bleibt die Koordinate unverändert.
- Andernfalls, wenn Informationen zur Fitness vorliegen, wähle unter Berücksichtigung dieser Informationen mithilfe der Roulette-Methode eine neue Alternative aus
- Falls die gesammelten Informationen fehlen oder unzureichend sind:
- mit einer Wahrscheinlichkeit, die dem dynamischen Koeffizienten entspricht, eine lokale Suche innerhalb des Echoortungsradius durchführen
- Andernfalls führe eine globale Suche auf Basis einer zufälligen Alternative aus.
- Suchraum-Einschränkungen und Diskretisierung anwenden
Schritt 6. Bewertung neuer Stellen
Berechne die Qualität der Lösung für jeden Delfin an seiner neuen Position.
Schritt 7. Aktualisierung globaler Informationen
Aktualisiere die besten und schlechtesten Werte in der Population. Wenn eine Lösung gefunden wird, die besser ist als das derzeitige globale Optimum, sollten wir sie beibehalten.
Beendigung:
Nachdem alle Iterationen abgeschlossen sind, gib die gefundene beste Lösung und deren Qualität zurück.
Kommen wir nun zur Umsetzung von DEA.
Schreiben wir die Struktur S_Alternative. Sie speichert Informationen über eine Alternative im Entscheidungsprozess zur Optimierung und enthält den Wert (den diese Alternative charakterisierenden Wert, eine Bewertung der Effektivität und der AF) – die akkumulierte Fitness für diese Alternative; dies ist erforderlich, um die Qualität der Alternative zu bewerten, wenn ein iterativer Prozess angewendet werden muss.
//———————————————————————————————————————————————————————————————————— struct S_Alternative { double value; // alternative value double AF; // accumulated fitness for this alternative }; //————————————————————————————————————————————————————————————————————
Die Struktur S_Coordinate dient dazu, eine Reihe von Alternativen darzustellen, die einer bestimmten Koordinate zugeordnet sind. alt ist ein Array von Alternativen, von denen jede einer Koordinate entspricht. count ist eine Variable, die die aktuelle Anzahl der tatsächlich im Array alt gespeicherten Alternativen angibt.
//———————————————————————————————————————————————————————————————————— struct S_Coordinate { S_Alternative alt []; // array of alternatives for a given coordinate int count; // number of alternatives }; //————————————————————————————————————————————————————————————————————
Als Nächstes wenden wir uns der Beschreibung der Klasse zu, die den Optimierungsalgorithmus (DEA) direkt implementiert. Die Klasse C_AO_DEA ist eine Unterklasse der Basisklasse C_AO. Beim Erstellen eines Klassenobjekts werden die wichtigsten Parameter des Algorithmus initialisiert:
- popSize – initialisiert die Populationsgröße (Anzahl der Delfine oder Positionen).
- Re – Anfangswert des effektiven Echoortungsradius.
- Power – Grad der Konvergenzkurve.
- PP1 – initialisiert den Konvergenzfaktor für die erste Iteration.
Die Methode SetParams dient dazu, die internen Parameter des Algorithmus anhand der im Array params gespeicherten Werte zu aktualisieren. Nach dem Auslesen der Werte für popSize, Re, Power und PP1 wird eine Validierungsprüfung durchgeführt.
Methoden:
- Init dient zur Initialisierung des Algorithmus und akzeptiert Minimal- und Maximalwerte sowie Schrittweiten für jeden Parameter sowie die Gesamtzahl der Epochen (Iterationen).
- Moving ist dafür zuständig, die Delfine im Suchraum zu verschieben; dies ist Teil der Hauptoptimierungsschleife.
- Die Methode Revision aktualisiert nach der Bewegung die Informationen über die Population, insbesondere über die besten und schlechtesten Lösungen.
Die folgenden Felder werden intern zur Ausführung des Algorithmus verwendet und sind von außerhalb der Klasse nicht zugänglich.
- PP ist eine Gleitkommazahl, die eine vorgegebene Wahrscheinlichkeit für die aktuelle Iteration darstellt und für stochastische Entscheidungen verwendet wird; currentEpoch ist ein Wert, der die aktuelle Epoche (Iteration) des Algorithmus angibt.
- totalEpochs ist ein Wert, der die Gesamtzahl der geplanten Epochen speichert.
- coeffA ist ein dynamischer Koeffizient, der zur Auswahl von Positionen verwendet wird.
- coordData ist ein Array von Strukturen, wobei jede S_Coordinate ein Array von Alternativen und deren Anzahl für eine bestimmte Koordinate enthält.
- Mit CalculatePP wird der PP-Wert (vorgegebene Wahrscheinlichkeit) bei der aktuellen Iteration berechnet.
- CalculateAccumulativeFitness berechnet die akkumulierte Fitness für jede Alternative.
- ResetAFforBestLocation setzt die akkumulierten Fitnesswerte für die besten Positionen zurück.
- SelectNextLocations wählt anhand des aktuellen Zustands die nächsten Positionen für die Delfine aus.
- FindNearestAlternative ermittelt anhand der angegebenen Koordinaten und des angegebenen Werts die nächstgelegene Alternative.
- CalculateCoefficientA berechnet den dynamischen Koeffizienten coeffA.
Im Allgemeinen ist die Klasse C_AO_DEA einsatzbereit, um Lösungen im mehrdimensionalen Raum zu finden. Die Klasse bietet öffentliche Methoden zur Initialisierung und zur Durchführung der wichtigsten Optimierungsschritte sowie private Methoden und Daten, die die interne Logik des Algorithmus umsetzen.
//———————————————————————————————————————————————————————————————————— class C_AO_DEA : public C_AO { public: //---------------------------------------------------------- ~C_AO_DEA () { } C_AO_DEA () { ao_name = "DEA"; ao_desc = "Dolphin Echolocation Algorithm"; ao_link = "https://www.mql5.com/en/articles/18495"; popSize = 100; // NL - number of locations (dolphins) Re = 2; // effective search radius Power = 2.0; // convergence curve power PP1 = 1.0; // first iteration convergence factor ArrayResize (params, 4); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "Re"; params [1].val = Re; params [2].name = "Power"; params [2].val = Power; params [3].name = "PP1"; params [3].val = PP1; } void SetParams () { popSize = (int)params [0].val; Re = (int)params [1].val; Power = params [2].val; PP1 = params [3].val; // Check the parameters validity if (Re < 0) Re = 0; if (PP1 < 0.0) PP1 = 0.0; if (PP1 > 1.0) PP1 = 1.0; if (Power < 0.1) Power = 0.1; } bool Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0); // number of epochs void Moving (); void Revision (); //------------------------------------------------------------------ int Re; // effective search radius double Power; // convergence curve power double PP1; // first iteration convergence factor private: //--------------------------------------------------------- double PP; // predefined probability for the current iteration int currentEpoch; // current epoch int totalEpochs; // total number of epochs double coeffA; // dynamic coefficient used to select positions S_Coordinate coordData []; // coordinate data (alternatives and AF) void CalculatePP (); void CalculateAccumulativeFitness (); void ResetAFforBestLocation (); void SelectNextLocations (); int FindNearestAlternative (int coord, double value); void CalculateCoefficientA (); }; //————————————————————————————————————————————————————————————————————
Die Methode Init der Klasse C_AO_DEA initialisiert den Algorithmus (DEA). Als Eingabewerte werden die Minimal- und Maximalwerte jeder Variablen, die Schrittweite für die Änderung jeder Variablen sowie die Gesamtzahl der zu optimierenden Epochen benötigt. Die Methode ruft zunächst die Basismethode StandardInit auf, um die Standardinitialisierung der gemeinsamen Parameter des Algorithmus durchzuführen, und gibt false zurück, falls diese Initialisierung fehlschlägt. Anschließend werden die Variablen initialisiert, die die aktuelle und die Gesamtzahl der Epochen der Algorithmusausführung erfassen.
Anschließend wird die Datenstruktur coordData angelegt, um Informationen zu jeder Koordinate (Variablen) des Suchraums zu speichern. Für jede Koordinate wird die Anzahl der möglichen alternativen Werte ermittelt. Wird für eine Koordinate ein Schrittwert angegeben, wird die Anzahl der Alternativen anhand der Grenzen und des Schrittwerts berechnet. Wenn der Schritt nicht angegeben wird (d. h. gleich null ist), wird davon ausgegangen, dass die Koordinate kontinuierlich ist, und es wird eine feste Anzahl von Alternativen festgelegt.
Anschließend wird der Parameter Re (effektiver Echoortungsradius) überprüft und gegebenenfalls so angepasst, dass er für jede Koordinate ein Viertel der Anzahl der Alternativen nicht überschreitet. Anschließend wird Speicherplatz reserviert, um für jede Koordinate alternative Werte zu speichern.
Schließlich füllt die Schleife für jede Koordinate ein Array mit alternativen Werten und verteilt diese gleichmäßig zwischen dem Minimal- und dem Maximalwert. Wenn ein Schritt angegeben wird, werden alternative Werte unter Verwendung dieses Schritts berechnet. Wenn der Schritt nicht angegeben wird, wird der Bereich zwischen den angegebenen Grenzen diskretisiert. Außerdem wird für jede Alternative der zugehörige AF-Wert (akkumulierte Fitness) auf Null gesetzt. Wenn alle Initialisierungsschritte erfolgreich abgeschlossen wurden, gibt die Methode true zurück.
//———————————————————————————————————————————————————————————————————— //--- Initialization bool C_AO_DEA::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ currentEpoch = 0; totalEpochs = epochsP; // Initialize the data structure for coordinates ArrayResize (coordData, coords); // Create alternatives for each coordinate for (int c = 0; c < coords; c++) { if (rangeStep [c] != 0) { coordData [c].count = (int)((rangeMax [c] - rangeMin [c]) / rangeStep [c]) + 1; } else { coordData [c].count = 500; } // Check that Re is not too large for the number of alternatives if (Re > coordData [c].count / 4) Re = coordData [c].count / 4; ArrayResize (coordData [c].alt, coordData [c].count); // Fill in the alternatives for (int i = 0; i < coordData [c].count; i++) { if (rangeStep [c] != 0) { coordData [c].alt [i].value = rangeMin [c] + i * rangeStep [c]; } else { coordData [c].alt [i].value = rangeMin [c] + (rangeMax [c] - rangeMin [c]) * i / (coordData [c].count - 1); } coordData [c].alt [i].AF = 0.0; } } return true; } //————————————————————————————————————————————————————————————————————
Die Moving-Methode implementiert einen Hauptschritt des Algorithmus (DEA), der einer bestimmten Iteration des Optimierungsprozesses entspricht. Wenn dies die erste Iteration ist, die anhand des Flags revision erkannt wird, erfolgt eine anfängliche zufällige Zuordnung der Populationskoordinaten. Für jeden Abschnitt (Populationselement) und für jede Variable im Bereich werden Zufallswerte zugewiesen. Diese Werte werden unter Berücksichtigung der Randbedingungen und der Änderungsschritte angepasst, um akzeptable Lösungen zu gewährleisten. Danach wird das Flag gesetzt, die Initialisierung ist abgeschlossen, und die Methode verlässt diese Schleife.
Sobald die Initialisierung abgeschlossen ist, wird der Zähler für die aktuelle Epoche (Iteration) um eins erhöht. Anschließend werden die wichtigsten Schritte des Algorithmus ausgeführt: Für jede Lösung in der aktuellen Population werden Fitnesswerte ermittelt, die angeben, wie gut sie zur Aufgabenstellung passen. Der Koeffizient a wird berechnet. Anhand der Qualitätsindikatoren wird eine zusammengefasste Fitnessbewertung jeder Lösung bestimmt und der AF-Index dafür neu berechnet, wodurch die Suche auf den Bereich der besten Lösungen konzentriert werden kann. Auf der Grundlage aktueller Informationen und berechneter Koeffizienten werden die nächsten Positionen ausgewählt, um die Lösungsvorschläge im Suchraum zu aktualisieren und zu verschieben.
Im Allgemeinen führt die Moving-Methode einen Iterationszyklus des DEA-Algorithmus durch und führt dabei nacheinander die wichtigsten Schritte der Aktualisierung und Optimierung von Lösungen im Rahmen der Suche nach dem Optimum durch.
//———————————————————————————————————————————————————————————————————— //--- The main step of the algorithm (according to Algorithm 1) void C_AO_DEA::Moving () { // Initial setup if (!revision) { for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { a [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); a [p].cB [c] = a [p].c [c]; } } revision = true; return; } // Increase the epoch counter currentEpoch++; // Steps of the DEA algorithm according to Algorithm 1: // 1. Calculate PP for the current iteration CalculatePP (); // 2. We calculate the 'a' dynamic coefficient CalculateCoefficientA (); // 3. Calculate accumulated fitness CalculateAccumulativeFitness (); // 4. Find the best location and reset AF for it ResetAFforBestLocation (); // 5. Select the next positions SelectNextLocations (); } //————————————————————————————————————————————————————————————————————
Die Methode CalculatePP berechnet die vorgegebene Wahrscheinlichkeit (PP), die im Entscheidungsprozess des Algorithmus verwendet wird. Wenn die Gesamtzahl der Epochen (Iterationen) gleich eins oder kleiner ist, wird die Wahrscheinlichkeit auf einen vorgegebenen Anfangswert (PP1) gesetzt. In diesem Fall sind keine weiteren Berechnungen erforderlich, und der Vorgang wird beendet.
Ist die Anzahl der Epochen größer als eins, wird der PP-Wert anhand einer vorgegebenen Formel berechnet, die die aktuelle Epoche berücksichtigt und folgende Logik beinhaltet: Die Potenz, die eine Funktion der aktuellen Epoche hoch der Potenz (Power) ist, wird berechnet, und davon wird eins abgezogen; analog dazu wird die Potenz für die Gesamtzahl der Epochen berechnet.
Der PP-Wert wird anhand einer Formel aktualisiert, die sich unter Berücksichtigung des aktuellen Fortschritts über mehrere Epochen hinweg schrittweise dem Wert 1 annähert. Konkret wird ein Anteil, der proportional zum Fortschritt ist und um den Wert der Parameter degree, Power und totalEpochs bereinigt wurde, zum ursprünglichen PP1-Wert addiert. Ist der Gesamt-Exponent ungleich Null, wird eine Division durchgeführt, um die aktuelle Wahrscheinlichkeit zu ermitteln; andernfalls bleibt der Wert gleich dem ursprünglichen PP1.
Letztendlich passt die Methode den Wahrscheinlichkeitswert während der Ausführung des Algorithmus dynamisch an und sorgt so im Verlauf der Epochen für ein Gleichgewicht zwischen den anfänglichen und den progressiveren Werten.
//———————————————————————————————————————————————————————————————————— //--- Calculate the predetermined probability (according to the formula 5) void C_AO_DEA::CalculatePP () { if (totalEpochs <= 1) { PP = PP1; return; } // PP = PP1 + (1 - PP1) * ((Loop^Power - 1) / (LoopsNumber^Power - 1)) double iterPower = MathPow ((double)currentEpoch, Power) - 1.0; double totalPower = MathPow ((double)totalEpochs, Power) - 1.0; if (totalPower != 0) { PP = PP1 + (1.0 - PP1) * iterPower / totalPower; } else { PP = PP1; } } //————————————————————————————————————————————————————————————————————
CalculateCoefficientA berechnet den dynamischen Koeffizienten a, der zur Steuerung des Suchvorgangs verwendet wird. Die Methode durchläuft die gesamte aktuelle Lösungsmenge und berechnet für jede Lösung die Differenz zwischen der maximal möglichen fB-Fitness und der aktuellen Fitness der jeweiligen Lösung (a[i].f). Diese Unterschiede summieren sich.
Nach der Summierung der Werte ergibt sich der Koeffizient a als Quotient aus der Differenz zwischen fB und der minimalen Fitness fW und der resultierenden Summe. Dadurch können wir einen dynamischen Koeffizienten definieren, der sich je nach dem aktuellen Zustand der Population anpasst und dazu beiträgt, das Gleichgewicht zwischen Konvergenz und Exploration des Suchraums herzustellen.Diese Methode erzeugt somit einen Skalierungsparameter, der die Fitnessverteilung der Lösungen berücksichtigt und deren Aktualisierungs- und Bewegungsstrategie in den nachfolgenden Iterationen des Algorithmus beeinflusst.
//———————————————————————————————————————————————————————————————————— //--- Calculate the dynamic 'a' coefficient void C_AO_DEA::CalculateCoefficientA () { double sumFitness = 0.0; for (int i = 0; i < popSize; i++) { sumFitness += fB - a [i].f; } coeffA = (fB - fW) / sumFitness; } //————————————————————————————————————————————————————————————————————
Die Methode FindNearestAlternative dient dazu, die nächstgelegene Alternative zu einem bestimmten Wert innerhalb einer bestimmten Koordinate zu finden, und benötigt zwei Argumente: den Koordinatenindex coord und den Wert value, für den wir die nächstgelegene Alternative suchen. Die Anfangswerte für nearest (der Index der nächstgelegenen Alternative) und minDist (der Mindestabstand) werden initialisiert und festgelegt.
Die Schleife durchläuft alle Alternativen, die mit der angegebenen Koordinate verknüpft sind. Für jede Alternative wird der Abstand zwischen dem angegebenen Wert und dem Wert der Alternative (coordData[coord].alt[i].value) berechnet, und wenn der berechnete Abstand kleiner ist als der aktuelle Mindestabstand (minDist), wird minDist mit dem neuen, kleineren Abstandswert aktualisiert und nearest mit dem Index der aktuellen Alternative.
Nachdem die Schleife durchlaufen wurde, wird der Index der Alternative zurückgegeben, die innerhalb der angegebenen Koordinate dem angegebenen Wert am nächsten lag. Auf diese Weise ermittelt das Verfahren, welche der verfügbaren Alternativen für die angegebene Koordinate dem vorgegebenen reellen Wert am nächsten liegt.
//———————————————————————————————————————————————————————————————————— //--- Search for the closest alternative int C_AO_DEA::FindNearestAlternative (int coord, double value) { int nearest = 0; double minDist = DBL_MAX; for (int i = 0; i < coordData [coord].count; i++) { double dist = MathAbs (value - coordData [coord].alt [i].value); if (dist < minDist) { minDist = dist; nearest = i; } } return nearest; } //————————————————————————————————————————————————————————————————————
Die Methode CalculateAccumulativeFitness dient dazu, die akkumulierte Fitness (AF) für Alternativen gemäß Algorithmus 2 zu berechnen. Vor Beginn der Berechnungen werden alle akkumulierten Fitnesswerte für jede Alternative in jeder Koordinate gelöscht und auf Null gesetzt. Es wird der Fitnessbereich der aktuellen Lösungsmenge ermittelt, berechnet als Differenz zwischen der maximal möglichen Fitness (fB) und der minimalen Fitness (fW).
Anschließend wird für jeden Agenten (Delfin) seine Fitness relativ zum Suchbereich normiert, und für jede Suchkoordinate wird die nächstgelegene Alternative ermittelt; innerhalb des effektiven Echoortungsradius Re um diese Alternative wird die akkumulierte Fitness für die Alternative aktualisiert, wobei die reflektierenden Eigenschaften der Grenzen berücksichtigt werden. Dies geschieht durch eine gewichtete Summierung der Beiträge, wobei die Gewichte auf der Grundlage der Entfernung zur nächstgelegenen Alternative (unter Berücksichtigung reflektierender Grenzen) gebildet werden und einen Koeffizienten enthalten, der mit dem aktuellen effektiven Echoortungsradius Re verknüpft ist.
Im Rahmen des Verfahrens werden für jede Alternative in jeder Koordinate akkumulierte Fitnesswerte gebildet, wobei der Beitrag benachbarter Alternativen berücksichtigt wird.
//———————————————————————————————————————————————————————————————————— //--- Calculate the accumulated fitness (according to Algorithm 2) void C_AO_DEA::CalculateAccumulativeFitness () { // Clear the accumulated fitness for all alternatives for (int c = 0; c < coords; c++) { for (int i = 0; i < coordData [c].count; i++) { coordData [c].alt [i].AF = 0.0; } } double rangeFF = fB - fW; if (rangeFF == 0.0) rangeFF = DBL_EPSILON; // For each agent (dolphin) for (int i = 0; i < popSize; i++) { // Normalize 'fitness' for this agent double normalizedFitness = (a [i].f - fW) / rangeFF; for (int c = 0; c < coords; c++) { // Find the closest alternative for the current coordinate int nearestAlt = FindNearestAlternative (c, a [i].c [c]); // Update the accumulated fitness in Re radius // According to Algorithm 2: AF(A+k)j = (1/Re) * (Re - |k|) * fitness(i) + AF(A+k)j for (int k = -Re; k <= Re; k++) { int altIndex = nearestAlt + k; // Boundary check taking into account reflection (reflective characteristic) if (altIndex < 0) { altIndex = -altIndex; // reflection from the lower border } else if (altIndex >= coordData [c].count) { altIndex = 2 * (coordData [c].count - 1) - altIndex; // reflection from the upper border } if (altIndex >= 0 && altIndex < coordData [c].count) { double weight = (1.0 / (double)(Re + 1)) * (Re - MathAbs (k) + 1); coordData [c].alt [altIndex].AF += weight * normalizedFitness; } } } } // Add a small epsilon value to all AFs to avoid zero probabilities double epsilon = 0.0001; for (int c = 0; c < coords; c++) { for (int i = 0; i < coordData [c].count; i++) { coordData [c].alt [i].AF += epsilon; } } } //————————————————————————————————————————————————————————————————————
Die Methode ResetAFforBestLocation dient dazu, die akkumulierte Fitness (AF) für Alternativen zurückzusetzen, die der Position der besten Lösung (des Agenten) in der Population entspricht. Zunächst ermittelt das Verfahren den Index der besten Lösung (des besten Agenten) in der aktuellen Population. Es durchläuft alle Lösungen und ermittelt dabei die Lösung mit dem höchsten Fitnesswert. Der Index der Lösung mit der höchsten Fitness wird in der Variablen bestIndex gespeichert.
Für jede c-Koordinate der besten Lösung ermittelt die Methode mithilfe der Funktion FindNearestAlternative die nächstgelegene Alternative zum Koordinatenwert der besten Lösung an dieser Koordinate; existiert die gefundene Alternative (d. h., liegt ihr Index innerhalb des zulässigen Bereichs), wird der akkumulierte Fitnesswert AF für diese bestimmte Alternative auf Null zurückgesetzt.
Daher setzt das Verfahren den AF nur für jene Alternativen zurück, die den Koordinaten der besten Lösung am ehesten entsprechen. Dies geschieht, um den Einfluss dieser Alternativen auf nachfolgende Phasen der Suche zu verringern und so möglicherweise die Exploration anderer Bereiche des Suchraums zu fördern.
Infolgedessen wird die Fitness jener Koordinaten, die am besten zur besten Lösung passen, auf Null gesetzt, um die Suche nach anderen, möglicherweise noch besseren Lösungen anzuregen.
//———————————————————————————————————————————————————————————————————— //--- Reset AF for the best location (according to Algorithm 3) void C_AO_DEA::ResetAFforBestLocation () { // Find the index of the best solution int bestIndex = 0; double bestFitness = a [0].f; // Search for a solution with maximum fitness (since we always maximize normalized fitness) for (int i = 1; i < popSize; i++) { if (a [i].f > bestFitness) { bestFitness = a [i].f; bestIndex = i; } } // Reset AF for ALL alternatives corresponding to the coordinates of the best solution for (int c = 0; c < coords; c++) { // Find the closest alternative to the coordinate of the best solution int nearestAlt = FindNearestAlternative (c, a [bestIndex].c [c]); // Reset AF only for this alternative if (nearestAlt >= 0 && nearestAlt < coordData [c].count) { coordData [c].alt [nearestAlt].AF = 0.0; } } } //————————————————————————————————————————————————————————————————————
Die Methode SelectNextLocations dient dazu, für jede Lösung in der Population (für jeden Delfin) die nächste Position auf der Grundlage probabilistischer Überlegungen auszuwählen, wobei sowohl die akkumulierte Fitness (AF) als auch die Strategie zur Beibehaltung der besten Position berücksichtigt werden. Die Methode ermittelt zunächst anhand des Fitnesswerts die beste Lösung in der aktuellen Population. Der Index der besten Lösung wird zur späteren Verwendung gespeichert.
Für jede Lösung und jede ihrer Koordinaten wird die folgende Abfolge von Schritten durchgeführt: Ist die aktuelle Lösung die beste und liegt die Zufallszahl unter der PP-Wahrscheinlichkeit, so bleibt die aktuelle Koordinate dieser Lösung unverändert. Dadurch bleibt die bisher beste Lösung erhalten. Sollte die aktuelle Lösung jedoch nicht die beste sein oder sollte die Position unter PP nicht beibehalten werden, werden alle AF-Werte für die Alternativen an der aktuellen Koordinate addiert. Ist die Gesamt-AF-Summe größer als ein kleiner Wert (Epsilon), was auf das Vorhandensein von Fitnesswerten ungleich Null hindeutet, wird ein Roulette-Verfahren durchgeführt: Es wird eine Zufallszahl ausgewählt, die proportional zur AF-Summe ist, und die Lösungskoordinate wird auf der Grundlage der kumulativen AF-Summe der Alternativen bestimmt, wodurch sich Lösungen zu Orten mit höherer Fitness bewegen können.
Wenn die Summe von AF nahe Null liegt (alle Werte von AF sind sehr klein), wird eine lokale Suche durchgeführt, sofern die Zufallszahl kleiner ist als der dynamische Koeffizient coeffA. In diesem Fall wird ein zufälliger Versatz (-Re...+Re) relativ zum aktuellen Wert ausgewählt, und die Koordinate wird mit dem nächstgelegenen Wert aktualisiert. Grenzen werden berücksichtigt.
Globale Suche (Zufallsauswahl), wenn die Zufallszahl größer als coeffA ist. In diesem Fall wird eine völlig zufällige Alternative für die Koordinate ausgewählt. Am Ende der Methode wird der ermittelte Koordinatenwert auf den zulässigen Bereich (rangeMin, rangeMax) begrenzt und mit dem angegebenen Schritt rangeStep diskretisiert, um sicherzustellen, dass der Wert innerhalb des zulässigen Bereichs liegt und den zulässigen Werten entspricht.
Durch diese Methode werden die Koordinaten jeder Lösung unter Berücksichtigung der Wahrscheinlichkeitsgewichte aktualisiert, die auf der akkumulierten Fitness, der PP-Strategie (Preserve the Best) sowie der dynamischen lokalen und globalen Suche basieren. Dies ermöglicht es dem Algorithmus, den Suchraum effektiv zu durchsuchen und optimale Lösungen zu finden.
//———————————————————————————————————————————————————————————————————— //--- Select next positions based on probabilities void C_AO_DEA::SelectNextLocations () { // First we find the index of the best solution int bestIndex = 0; double bestFitness = a [0].f; for (int i = 1; i < popSize; i++) { if (a [i].f > bestFitness) { bestFitness = a [i].f; bestIndex = i; } } for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { // For the best agent, apply PP if (i == bestIndex && u.RNDprobab () < PP) { // Save the current value of the coordinate of the best solution with PP probability continue; } // Select based on accumulated fitness double totalAF = 0.0; for (int alt = 0; alt < coordData [c].count; alt++) { totalAF += coordData [c].alt [alt].AF; } if (totalAF > DBL_EPSILON) // Check that there are non-zero AFs { // Choose an alternative based on roulette double rnd = u.RNDprobab () * totalAF; double cumSum = 0.0; for (int alt = 0; alt < coordData [c].count; alt++) { cumSum += coordData [c].alt [alt].AF; if (cumSum >= rnd) { a [i].c [c] = coordData [c].alt [alt].value; break; } } } else { // If all AFs are almost zero, use random selection // with the dynamic coeffA coefficient for the local search probability if (u.RNDprobab () < coeffA) // Use the dynamic coefficient { // Local search - stay close to the current position int currentAlt = FindNearestAlternative (c, a [i].c [c]); int shift = u.RNDminusOne (2 * Re + 1) - Re; // random offset within Re int newAlt = currentAlt + shift; // Check boundaries if (newAlt < 0) newAlt = 0; if (newAlt >= coordData [c].count) newAlt = coordData [c].count - 1; a [i].c [c] = coordData [c].alt [newAlt].value; } else { // Global search - completely random selection int randAlt = u.RNDminusOne (coordData [c].count); a [i].c [c] = coordData [c].alt [randAlt].value; } } // Bounds checking and discretization a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //————————————————————————————————————————————————————————————————————
Die Revisionsmethode dient dazu, Informationen über die besten und schlechtesten Lösungen in der aktuellen Population zu aktualisieren. Der Index der besten Lösung wird festgelegt, und der Variablen, die die beste Fitness speichert, wird der Wert der schlechtesten der aktuellen Lösung zugewiesen. Dadurch wird ein Ausgangszustand für die Suche nach neuen Extremwerten geschaffen. Alle Lösungen in der aktuellen Population werden durchsucht: Die Lösung mit dem höchsten Fitnesswert (die beste Lösung) wird ermittelt. Der Wert wird gespeichert, und der zugehörige Index wird aktualisiert. Wir suchen auch nach der Lösung mit dem niedrigsten Fitnesswert (der schlechtesten Lösung). Wurde eine wirklich optimale Lösung gefunden, werden deren Koordinaten in ein spezielles Array oder eine Variable kopiert, die dazu dient, die aktuell beste Lösung zu speichern.
Durch die Ausführung der Methode sind die Koordinaten der besten und schlechtesten Lösung in der Population zum aktuellen Zeitpunkt genau bekannt. Dadurch kann der Algorithmus die Suchdynamik verfolgen und diese Daten bei der Entscheidungsfindung nutzen, um bessere optimale Lösungen zu finden.
//———————————————————————————————————————————————————————————————————— //--- Update the best solution void C_AO_DEA::Revision () { int bestIND = -1; fW = fB; // Find the best and worst solutions in the current population for (int i = 0; i < popSize; i++) { // Update the best solution if (a [i].f > fB) { fB = a [i].f; bestIND = i; } // Update the worst solution if (a [i].f < fW) { fW = a [i].f; } } // Copy the coordinates of the best solution if (bestIND != -1) { ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY); } } //————————————————————————————————————————————————————————————————————
Testergebnisse
Schauen wir uns nun die Ergebnisse an. Es fällt sofort auf, dass der Algorithmus verschiedene Arten von Aufgaben gut und schnell bewältigt.
DEA|Algorithmus zur Echoortung bei Delfinen|100,0|2,0|2,0|1,0|
=============================5 Hilly's; Func runs: 10000; result: 0.7599517883429889
25 Hilly's; Func runs: 10000; result: 0.6757192867862007
500 Hilly's; Func runs: 10000; result: 0.34170057553968197
=============================
5 Forest's; Func runs: 10000; result: 0.8958173952258406
25 Forest's; Func runs: 10000; result: 0.6422393144820473
500 Forest's; Func runs: 10000; result: 0.23940903266305935
=============================
5 Megacity's; Func runs: 10000; result: 0.6153846153846154
25 Megacity's; Func runs: 10000; result: 0.4403076923076923
500 Megacity's; Func runs: 10000; result: 0.15115384615384736
=============================
All score: 4.76168 (52.91%)
Die Visualisierung zeigt eine Streuung der Ergebnisse für niedrigdimensionale Funktionen (grün) und gute Ergebnisse für mitteldimensionale Funktionen (blau).
DEA mit der Testfunktion Hilly
DEA mit der Testfunktion Forest
DEA mit der Testfunktion Megacity
Aufgrund seiner Ergebnisse belegt der DEA-Algorithmus Platz 25 in der Rangliste.
| # | 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 | BBO | biogeografisch basierte Optimierung | 0.94912 | 0.69456 | 0.35031 | 1.99399 | 0.93820 | 0.67365 | 0.25682 | 1.86867 | 0.74615 | 0.48277 | 0.17369 | 1.40261 | 5.265 | 58.50 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | DEA | Algorithmus zur Echoortung bei Delfinen | 0.75995 | 0.67572 | 0.34171 | 1.77738 | 0.89582 | 0.64223 | 0.23941 | 1.77746 | 0.61538 | 0.44031 | 0.15115 | 1.20684 | 4.762 | 52.91 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | (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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | CMAES | Anpassung der Kovarianzmatrix mittels Evolutionsstrategie | 0.76258 | 0.72089 | 0.00000 | 1.48347 | 0.82056 | 0.79616 | 0.00000 | 1.61672 | 0.75846 | 0.49077 | 0.00000 | 1.24923 | 4.349 | 48.33 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
| RW | Random Walk | 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
Die Hauptvorteile des Algorithmus sind: adaptive Suchsteuerung: Die vorgegebene Wahrscheinlichkeit steigt allmählich an, wodurch sich das Gleichgewicht von der Exploration hin zur Exploitation verlagert; dynamische Anpassung; kollektives Gedächtnis: Die akkumulierte Fitness bewahrt und verbreitet Informationen über vielversprechende Bereiche; Diversitätsmechanismus: Das Zurücksetzen der Informationen für die besten Positionen regt die Exploration neuer Bereiche an.
Die Stärke des Algorithmus liegt in seiner Anpassungsfähigkeit. Der dynamische Koeffizient sorgt dafür, dass der Algorithmus auf den Zustand der Population reagiert und sich an den Rhythmus der Aufgabe anpasst. Wenn die Delfine über den Suchraum verteilt sind, fördert der Algorithmus die lokale Exploration. Wenn sie beginnen, sich auf ein Ziel zu konzentrieren, lenkt er sie in neue Bereiche des Suchraums und bewahrt sie davor, sich in der Illusion eines lokalen Erfolgs zu verlieren.
Die akkumulierte Fitness ist das kollektive Gedächtnis des Schwarms, in dem jede Entdeckung ein Echo im Lösungsraum hinterlässt. Im Gegensatz zur einfachen Anhäufung kann der Algorithmus jedoch vergessen – das Zurücksetzen der besten Positionen auf Null führt paradoxerweise zu noch besseren Entdeckungen.
Das ist nicht nur eine Metapher – es ist eine Philosophie der Optimierung, bei der jeder Klick des Echolokators Informationen über den Raum der Möglichkeiten enthält.
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 DEA:
Vorteile:
- Gute Konvergenz bei Funktionen mittlerer und hoher Dimension.
- Geringe Anzahl von externen Parametern.
Nachteile:
- Es besteht eine gewisse Tendenz, sich auf niedrigdimensionale Probleme zu versteifen.
- Hoher Ressourcenbedarf bei hochdimensionalen 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_DEA.mq5 | Skript | DEA-Testumgebung |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/18495
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.
Bewertung der Qualität des Forex-Spread-Tradings anhand saisonaler Faktoren in MetaTrader 5
IWF-Daten mit Python herunterladen
Ermittlung fairer Wechselkurse anhand von KKP- und IWF-Daten
Entwicklung eines Toolkits für die Price-Action-Analyse (Teil 29): Boom and Crash Interceptor EA
- 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.