Extremaloptimierung (EO)
30
0
Inhalt
Einführung
Viele reale Probleme, insbesondere Handelsaufgaben, sind durch komplexe diskrete Zielfunktionslandschaften mit mehreren lokalen Extrema, Unstetigkeiten und nicht differenzierbaren Bereichen gekennzeichnet, wodurch klassische gradientenbasierte Methoden nicht anwendbar sind. Zahlreiche metaheuristische Algorithmen wurden entwickelt, um solche Probleme zu lösen, und jeder Ansatz hat seine eigenen Vor- und Nachteile bei der Ausbalancierung von Exploration und Exploitation des Suchraums.
Extremaloptimierung (EO) ist ein metaheuristischer Optimierungsalgorithmus, der vom Bak-Sneppen-Modell inspiriert ist. Der Algorithmus wurde 1999 von Stefan Boettcher und Allon Percus als eine Methode entwickelt, die vom Konzept der selbstorganisierten Kritikalität inspiriert ist, wonach sich komplexe Systeme auf natürliche Weise in Richtung eines kritischen Zustands entwickeln, in dem lawinenartige Veränderungen unterschiedlicher Skalen auftreten. Eine populationsbasierte Variante von EO wurde für die kontinuierliche Optimierung mithilfe iterativer Aktualisierungen auf Populationsebene entwickelt.
Implementierung des Algorithmus
Das Bak-Sneppen-Modell wurde entwickelt, um die Evolution von Ökosystemen zu beschreiben und das Phänomen der selbstorganisierten Kritikalität zu demonstrieren. Dies ist ein einfaches Koevolutionsmodell, das zeigt, wie lokale Interaktionen zu globalen kritischen Ereignissen führen können.
Prinzipien des Bak-Sneppen-Modells
Ökosystem von Arten:
- N Arten sind in einer Kette (oder auf einem Gitter) angeordnet
- Jeder Art i wird ein Fitnesswert fi ∈ [0,1] zugewiesen
- Fitness repräsentiert die Anpassungsfähigkeit einer Art an ihre Umgebung.
Dynamik der Evolution
Bei jedem Zeitschritt: 1. Ermittle die Art mit der geringsten Fitness: fmin = min{fi} 2. Ersetze die Fitness dieser Art und ihrer Nachbarn durch neue Zufallswerte 3. Wiederhole den VorgangSelbstorganisierte Kritikalität
- Das System organisiert sich selbst in einen kritischen Zustand
- Es stellt sich ein Schwellenwert von fc ≈ 0,67 ein
- Arten mit einer Fitness < fc sterben in lawinenartigen Ereignissen aus
- Lawinengrößen folgen einem Potenzgesetz
In Abwesenheit externer Steuerung organisiert sich das System selbst: Auf lange Phasen relativer Stagnation folgen plötzlich lawinenartige Veränderungen unterschiedlicher Größenordnung. Die Größen der Lawinen folgen einem Potenzgesetz: P(s) ~ s^(-τ), wobei die Lebensdauern von Arten einem Potenzgesetz in Abwesenheit einer charakteristischen Skala gehorchen. Veränderungen bei einer Art wirken sich auf benachbarte Arten aus. Globale Dynamiken entstehen aus lokalen Interaktionen.
Boettcher und Percus adaptierten die Prinzipien des Bak-Sneppen-Modells, um einen Optimierungsalgorithmus zu erstellen. Anstatt das Beste zu verbessern, verbessern wir das Schlechteste. Die Konzentration auf die schlechtesten Elemente ist kontraintuitiv, aber effektiv, um aus lokalen Optima auszubrechen. Im Bak-Sneppen-Modell erfolgt die Evolution durch ein punktuiertes Gleichgewicht – lange Perioden der Stasis, die durch plötzliche Veränderungen unterbrochen werden. EO nutzt dieses Prinzip: Wenn nur schlechte Komponenten geändert werden und das Ändern einer Komponente die Lösung drastisch verbessert, kann die Verbesserung einer Komponente andere Komponenten schlecht machen.
Extremaloptimierung wendet die Prinzipien der selbstorganisierten Kritikalität – ursprünglich in Ökosystemmodellen untersucht – auf die Optimierung an. Die entscheidende Innovation ist die Nutzung der natürlichen Tendenz komplexer Systeme zur Selbstorganisation, um die Exploration und Exploitation des Suchraums automatisch auszubalancieren. Wir werden diese Behauptung an praktischen Problemen testen. Lassen Sie uns nun den Algorithmus in Pseudocode skizzieren.
Initialisierung:
- Erstelle eine Population aus popSize Agenten
- Initialisiere die Parameter
- Erstelle die Arrays für das Ranking von Agenten und Komponenten
Erster Durchlauf (Initialisierung der Population):
- Für jeden Agenten in der Population:
- Für jede Komponente (Koordinaten):
- Weise einen Zufallswert innerhalb des zulässigen Bereichs zu
- Wende eine Diskretisierung an, falls erforderlich
- Für jede Komponente (Koordinaten):
Grundlegende Optimierungsschleife:
Führe für jeden Agenten in der Population aus:
- Agenten-Ranking:
- Erstelle eine Liste aller Agenten mit ihrer Fitness
- Sortiere die Agenten nach ihrer Fitness (die schlechtesten zuerst bei Maximierung)
- Wähle einen Zielagenten:
- Verwende die Potenzgesetz-Verteilung P(n) ∝ n^(-τ)
- Wähle einen Rang gemäß dieser Verteilung
- Definiere den Agenten mit dem gewählten Rang als Zielagenten
- Komponenten-Ranking des Zielagenten:
- Berechne die Fitness für jede Komponente:
- Fitness = 1 - (normalisierte Abweichung vom besten bekannten Wert)
- Sortiere die Komponenten nach der Fitness (die schlechtesten zuerst)
- Berechne die Fitness für jede Komponente:
- Komponentenauswahl und Mutation:
- Verwende eine Potenzgesetz-Verteilung, um den Komponentenrang zu wählen
- Ersetze die gewählte Komponente durch einen neuen Zufallswert
- Prüfe die Grenzen und wende eine Diskretisierung an
Ergebnisaktualisierung:
- Sortiere die gesamte Population nach der Fitness (die besten am Anfang)
- Aktualisiere die global beste Lösung, wenn eine Verbesserung gefunden wird
Implementieren wir den Algorithmus nun im Code. Wir schreiben eine Klasse, die die Implementierung des EO-Algorithmus darstellt, basierend auf der Optimierungsmethode unter Verwendung des Prinzips der Entfernung der schlechtesten Elemente, um bessere Lösungen zu finden. Die Klasse erbt von der Basisklasse C_AO und enthält zusätzlich algorithmusspezifische Parameter und Methoden. Konstruktor und Destruktor: Initialisierung der Parameter beziehungsweise Freigabe der Ressourcen. Wichtigste Parameter
- popSize – Populationsgröße, Anzahl der Agenten in der Population;
- tau – Potenzgesetzverteilung, die die Wahrscheinlichkeiten für die Auswahl von Elementen bestimmt;
- greedyStart – Anteil der Agenten mit greedy-basierter Initialisierung
- eliteUpdate – Anteil der Agenten, die pro Iteration am Update teilnehmen.
- SetParams – aktuelle Parameterwerte aus dem Array extrahieren und anwenden;
- Init – Population unter Berücksichtigung der Parameterbereiche und der Anzahl der Epochen initialisieren;
- Moving – einen Schritt des Algorithmus ausführen und den Zustand der Population aktualisieren;
- Revision – Bewertungen aktualisieren oder auf die nächste Stufe vorbereiten.
- RankedComponent – Struktur zum Speichern des Rankings von Agentenkomponenten nach ihrer Qualität (Fitness);
- RankedAgent – Struktur zum Speichern des Rankings der Agenten selbst gemäß ihrer Gesamtfitness.
- compRanks und agentRanks – Arrays von Strukturen zum Speichern sortierter Komponenten und Agenten;
- tau, greedyStart, eliteUpdate steuern das Verhalten des Algorithmus
- ApplyExtremalOptimization – grundlegender Mechanismus zur Auswahl und Aktualisierung von Elementen basierend auf ihren Rängen unter Berücksichtigung der Potenzgesetzverteilung.
- CalculateComponentFitness – berechnet die Fitness der Agentenkomponente.
- SelectRankByPowerLaw – wählt den Rang einer Komponente oder eines Agenten unter Verwendung einer Potenzgesetzverteilung aus, was eine Fokussierung auf die schlechtesten Elemente ermöglicht.
Die Klasse ist für die Anwendung des Extremaloptimierungsalgorithmus vorgesehen, insbesondere bei Problemen, die die Suche nach einer qualitativ hochwertigen Lösung durch sukzessive Eliminierung der am schlechtesten angepassten Komponenten in der Population erfordern.
//———————————————————————————————————————————————————————————————————— //--- Initialization bool C_AO_EO::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ ArrayResize (compRanks, coords); ArrayResize (agentRanks, popSize); return true; } //————————————————————————————————————————————————————————————————————
Die Initialisierungsmethode der EO-Klasse ist für die Vorbereitung der Anfangsbedingungen für den weiteren Ablauf verantwortlich. Sie akzeptiert Parameter für die minimalen und maximalen Wertebereiche der Variablen sowie Schrittweiten für deren Änderung und bei Bedarf die Anzahl der Epochen (Iterationen).
Die Methode ruft zuerst das Standard-Initialisierungsverfahren auf, das grundlegende Parameter konfiguriert und gemeinsame Datenstrukturen vorbereitet. Wenn dieses Verfahren fehlschlägt, wird die Initialisierung abgebrochen.
Wenn die Initialisierung erfolgreich ist, ändert die Methode die Größe der Arrays, die zum Speichern der rangierten Komponenten und Agenten verwendet werden. Die Größe des Komponenten-Arrays wird entsprechend der Anzahl der Koordinaten oder Variablen des Problems festgelegt, und das Array der Agenten wird entsprechend der angegebenen Populationsgröße festgelegt. Sobald diese Schritte abgeschlossen sind, gibt die Methode true zurück.
//———————————————————————————————————————————————————————————————————— //--- Main loop of the algorithm void C_AO_EO::Moving () { // Initial population setup if (!revision) { int greedyCount = (int)(popSize * greedyStart); for (int i = 0; i < popSize; i++) { // Random initialization for the rest for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } // Apply Extremal Optimization --------------------------------- ApplyExtremalOptimization (); } //————————————————————————————————————————————————————————————————————
Die Methode ApplyExtremalOptimization implementiert die Hauptschleife des EO-Algorithmus zur Aktualisierung der Agentenpopulation. Ihr Ziel ist es, Lösungen durch Modifizierung von Agentenkomponenten basierend auf EO-Prinzipien zu verbessern. Die Anzahl der pro Iteration zu aktualisierenden Agenten wird unter Berücksichtigung des Parameters eliteUpdate (der Anteil der zu aktualisierenden Agenten) und der Populationsgröße bestimmt. Agenten werden basierend auf ihrer Fitness sortiert. Der Algorithmus ordnet Agenten vom schlechtesten zum besten, sodass der Algorithmus für eine Maximierung ausgelegt ist. Unter Verwendung einer Potenzgesetz-Wahrscheinlichkeitsverteilung wird der Agent ausgewählt, der geändert werden soll.
Für den ausgewählten Agenten werden seine Komponenten rangiert. Jeder Komponente wird ein Fitnesswert zugewiesen, um ihren Beitrag zur Agentenfitness zu bewerten. Die Komponenten werden basierend auf ihrer Fitness vom schlechtesten zum besten sortiert. Eine Potenzgesetz-Wahrscheinlichkeitsverteilung wird verwendet, um eine der Komponenten des Agenten zur Modifikation auszuwählen. Dies geschieht, um die Wahrscheinlichkeit zu erhöhen, dass Komponenten mit dem schlechtesten Rang ausgewählt werden.
Die ausgewählte Agentenkomponente wird durch einen Zufallswert innerhalb des zulässigen Bereichs ersetzt, der durch die Parameter rangeMin und rangeMax spezifiziert ist. Der resultierende Wert wird auf Gültigkeit geprüft, um sicherzustellen, dass er den spezifizierten Grenzen und Schrittweiten entspricht.Die Methode wiederholt diese Schritte für jeden zu aktualisierenden Agenten und implementiert die Schlüssellogik des EO-Algorithmus: Auswahl von Komponenten mit der schlechtesten Leistung und deren zufällige Ersetzung, um die Fitness der Lösungen zu verbessern.
//———————————————————————————————————————————————————————————————————— //--- Apply Extremal Optimization void C_AO_EO::ApplyExtremalOptimization () { // Number of agents to update in this iteration int numUpdates = MathMax (1, (int)(popSize * eliteUpdate)); // Update selected agents based on EO principle //for (int update = 0; update < numUpdates; update++) for (int update = 0; update < popSize; update++) { // Step 1: Select an agent to modify // Use ranking by overall fitness int targetAgent; // Rank agents by fitness (from worst to best for maximization) for (int i = 0; i < popSize; i++) { agentRanks [i].idx = i; agentRanks [i].fitness = a [i].f; } // Sort (worst first to maximize) for (int i = 0; i < popSize - 1; i++) { for (int j = i + 1; j < popSize; j++) { if (agentRanks [i].fitness > agentRanks [j].fitness) { RankedAgent temp = agentRanks [i]; agentRanks [i] = agentRanks [j]; agentRanks [j] = temp; } } } // Select an agent according to the power-law distribution int rank = SelectRankByPowerLaw (popSize); targetAgent = agentRanks [rank].idx; // Step 2: Rank the components of the selected agent for (int c = 0; c < coords; c++) { compRanks [c].agentIdx = targetAgent; compRanks [c].componentIdx = c; compRanks [c].fitness = CalculateComponentFitness (targetAgent, c); } // Sort components (worst first) for (int i = 0; i < coords - 1; i++) { for (int j = i + 1; j < coords; j++) { if (compRanks [i].fitness > compRanks [j].fitness) { RankedComponent temp = compRanks [i]; compRanks [i] = compRanks [j]; compRanks [j] = temp; } } } // Step 3: Select a component to change according to P(n) ∝ n^(-τ) int compRank = SelectRankByPowerLaw (coords); int compIdx = compRanks [compRank].componentIdx; // Step 4: Replace the selected component with a new random value // This is the key principle of EO - unconditional replacement with random a [targetAgent].c [compIdx] = u.RNDfromCI (rangeMin [compIdx], rangeMax [compIdx]); // Check boundaries a [targetAgent].c [compIdx] = u.SeInDiSp (a [targetAgent].c [compIdx], rangeMin [compIdx], rangeMax [compIdx], rangeStep [compIdx]); } } //————————————————————————————————————————————————————————————————————
Die Methode CalculateComponentFitness berechnet den Fitnesswert für eine einzelne Komponente des Agenten. Diese Funktion spielt eine wichtige Rolle im Extremal-Optimierungs-Algorithmus (EO) und bewertet den Beitrag jeder Komponente zur Fitness der Lösung. Der Algorithmus verwendet eine einfache Metrik, die auf der Berechnung der Fitness als relativer Beitrag einer Komponente zur Fitness basiert.
Anfangs wird die Fitness auf null initialisiert. Als Nächstes wird der Bereich der Komponentenwerte (range) berechnet. Wenn dieser Bereich größer als null ist, wird die normalisierte Abweichung berechnet. Die Abweichung wird als Absolutwert der Differenz zwischen dem Agentenkomponentenwert und dem Basiswert von cB berechnet, normalisiert durch den Bereich der Komponentenwerte. Die Fitness wird berechnet, indem die Abweichung von 1.0 subtrahiert wird. Dies macht die Fitness umgekehrt proportional zur Abweichung: Je kleiner die Abweichung einer Komponente vom Zielwert ist, desto höher ist ihre Fitness.
Somit gibt die Funktion einen Fitnesswert für eine bestimmte Komponente zurück, der angibt, wie gut der aktuelle Wert der Komponente mit dem Zielwert übereinstimmt, was für die weitere Rangfolge der Komponenten erforderlich ist.
//———————————————————————————————————————————————————————————————————— //--- Calculate the fitness component double C_AO_EO::CalculateComponentFitness (int agentIdx, int componentIdx) { // For the general optimization problem we use a simple metric // λi = relative contribution of the component to the fitness double fitness = 0.0; double range = rangeMax [componentIdx] - rangeMin [componentIdx]; if (range > 0) { // Normalized deviation double deviation = MathAbs (a [agentIdx].c [componentIdx] - cB [componentIdx]) / range; fitness =1.0 - deviation;// Invert so that bigger = better } return fitness; } //————————————————————————————————————————————————————————————————————
Die Methode SelectRankByPowerLaw implementiert die Auswahl der Position (Rang) eines Elements aus einer Liste basierend auf einer Wahrscheinlichkeitsverteilung nach einem Potenzgesetz. Diese Methode ist der Schlüssel zum EO-Algorithmus, da durch sie die Auswahl von Agenten und Komponenten für die Modifikation erfolgt. Die Methode nimmt maxRank als Eingabe entgegen, was den maximalen Rang des Elements definiert.
Die Methode basiert auf dem Prinzip der inversen Transformation zur Gewinnung eines Zufallswertes gemäß dem Potenzgesetz P(n) ∝ n^(-τ), wobei n der Rang des Elements ist und τ (Tau) der Parameter, der die Form der Potenzgesetzverteilung bestimmt.
Abhängig vom Wert des tau-Parameters werden zwei Szenarien realisiert:
Allgemeiner Fall (τ ≠ 1.0):
- ein Normalisierungsfaktor norm wird berechnet, der die korrekte Skalierung der Wahrscheinlichkeiten sicherstellt;
- eine Zufallszahl r im Bereich [0, 1) wird unter Verwendung von u.RNDprobab() generiert;
- die Formel der inversen Transformation wird verwendet, um den Rang basierend auf r, norm und τ zu berechnen;
- der Rang wird auf [0, maxRank - 1] begrenzt, um Array-Indexüberschreitungen zu vermeiden.
Spezialfall (τ = 1.0):
- der Normalisierungsfaktor norm wird für den Fall τ = 1.0 berechnet;
- eine spezielle Formel wird zur Berechnung des Rangs verwendet;
- der Rang wird auf den Bereich [0, maxRank - 1] begrenzt.
Als Ergebnis gibt die Methode einen ganzzahligen Rang zurück, der die ausgewählte Position des Elements in der Rangliste angibt. Diese Auswahl ist probabilistisch, das heißt, Elemente mit niedrigerem Rang (schlechter) haben eine höhere Wahrscheinlichkeit, ausgewählt zu werden, in Übereinstimmung mit den Prinzipien von EO.
//———————————————————————————————————————————————————————————————————— //--- Select a rank according to a power-law distribution int C_AO_EO::SelectRankByPowerLaw (int maxRank) { // P(n) ∝ n^(-τ), where n is a rank from 1 to maxRank // Use the inverse transformation method double r = u.RNDprobab (); if (tau != 1.0) { // General case: inverse transform for P(n) ∝ n^(-τ) double norm = (1.0 - MathPow (maxRank + 1.0, 1.0 - tau)) / (1.0 - tau); double x = r * norm; int rank = (int)MathPow ((1.0 - tau) * x + 1.0, 1.0 / (1.0 - tau)) - 1; if (rank >= maxRank) rank = maxRank - 1; if (rank < 0) rank = 0; return rank; } else { // Special case τ = 1: P(n) ∝ 1/n double norm = MathLog (maxRank + 1.0); int rank = (int)(MathExp (r * norm) - 1.0); if (rank >= maxRank) rank = maxRank - 1; if (rank < 0) rank = 0; return rank; } } //————————————————————————————————————————————————————————————————————
Die Methode Revision dient dazu, Informationen über die besten Lösungen während der Ausführung des EO-Algorithmus zu aktualisieren. Ihre Aufgabe ist es, die aktuell beste Lösung zu bestimmen und globale Variablen zu aktualisieren, die Informationen darüber speichern. Ein temporäres Array aT wird erstellt, um die sortierten Agenten zu speichern. Die a-Population von Agenten wird mithilfe der integrierten Funktion u.Sorting sortiert. Die Sortierung erfolgt zur Maximierung, das heißt, die besten Agenten (diejenigen mit dem höchsten Wert der f-Fitnessfunktion) werden am Anfang des a-Arrays (der Hauptdatenstruktur) platziert, das Informationen über die Agenten enthält, einschließlich der Werte ihrer c-Komponenten und des Wertes der f-Fitnessfunktion.
Nach der Sortierung wird geprüft, ob der Wert der f-Fitnessfunktion des besten Agenten (d. h. a[0]) größer ist als der aktuelle beste fB-Wert (der den Wert der Fitnessfunktion der bisher besten gefundenen Lösung speichert). Wenn der aktuell beste Agent besser ist als die global beste Lösung, werden die Werte der Komponenten des besten Agenten (a[0].c) in das cB-Array kopiert, das wahrscheinlich die Komponenten der besten Lösung speichert, und fB wird auf den Wert der Fitnessfunktion des besten Agenten (a[0].f) aktualisiert.
Somit aktualisiert die Funktion Revision die Informationen über die beste Lösung, bewahrt deren Komponenten sowie den Wert der Fitnessfunktion und sortiert die Population so, dass die besten Lösungen immer am Anfang des Arrays verfügbar sind.
//———————————————————————————————————————————————————————————————————— //--- Update the best solutions void C_AO_EO::Revision () { // Sort the population for MAXIMIZATION static S_AO_Agent aT []; ArrayResize (aT, popSize); // Use the built-in sorting function u.Sorting (a, aT, popSize); // Update the global best solution if (a [0].f > fB) { ArrayCopy (cB, a [0].c, 0, 0, WHOLE_ARRAY); fB = a [0].f; } } //————————————————————————————————————————————————————————————————————
Testergebnisse
Nach dem Testen zeigte der Algorithmus keine guten Ergebnisse. Daher entschied ich mich, alle ursprünglichen Methoden zu überprüfen und eine modifizierte Version zu erstellen, die auf die Verbesserung der Konvergenz des Algorithmus abzielt.EO|Extremal Optimization (Boettcher-Percus)|50.0|1.4|0.5|0.3|
=============================
5 Hilly's; Func runs: 10000; result: 0.5146369337195529
25 Hilly's; Func runs: 10000; result: 0.29089804555433085
500 Hilly's; Func runs: 10000; result: 0.25192095557138877
=============================
5 Forest's; Func runs: 10000; result: 0.367128650332966
25 Forest's; Func runs: 10000; result: 0.19477408852361866
500 Forest's; Func runs: 10000; result: 0.15367465708144543
=============================
5 Megacity's; Func runs: 10000; result: 0.2584615384615384
25 Megacity's; Func runs: 10000; result: 0.12707692307692314
500 Megacity's; Func runs: 10000; result: 0.09413846153846227
=============================
All score: 2.25271 (25.03%)
Nachfolgend finden Sie meine eigene Interpretation dieser Optimierungsmethode. Wir implementieren eine neue Klasse, die von der Basis-Optimierungsklasse erbt.
Der Konstruktor legt die Anfangsparameter des Algorithmus fest: Populationsgröße, die Anzahl der zu verbessernden schlechtesten Lösungen, die Mutationswahrscheinlichkeit sowie die Verteilungsgrade für Selektion und Mutation. Die Parameter werden zur weiteren Modifikation und Anpassung in einem Array von Strukturen gespeichert.
Die Methode SetParams aktualisiert die internen Variablen der Klasse basierend auf den Werten im Parameter-Array. Es werden Methoden deklariert, um den Algorithmus zu initialisieren, Bewegungsschritte auszuführen (Aktualisierung des Zustands) und eine Revision durchzuführen (Neubewertung von Lösungen oder Vorbereitung der nächsten Iteration). Der private Teil der Klasse speichert Variablen für die aktuelle Epoche und die Gesamtzahl der Epochen der Algorithmusausführung. Es wird eine Methode zur Mutation einer spezifischen Komponente einer Lösung in einer Population definiert, was einen wesentlichen Teil des implementierten Algorithmus darstellt.
//———————————————————————————————————————————————————————————————————— class C_AO_EOm : public C_AO { public: //---------------------------------------------------------- ~C_AO_EOm () { } C_AO_EOm () { ao_name = "EOm"; ao_desc = "Extremal Optimization M"; ao_link = "https://www.mql5.com/en/articles/18755"; popSize = 50; // Population size popRaising = 3; // Boost the worst agents mutationRate = 0.1; // Mutation probability powCh = 2.0; // Selection power-law exponent powMut = 8.0; // Mutation power-law exponent ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "popRaising"; params [1].val = popRaising; params [2].name = "mutationRate"; params [2].val = mutationRate; params [3].name = "powCh"; params [3].val = powCh; params [4].name = "powMut"; params [4].val = powMut; } void SetParams () { popSize = (int)params [0].val; popRaising = (int)params [1].val; mutationRate = params [2].val; powCh = params [3].val; powMut = params [4].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving (); void Revision (); //------------------------------------------------------------------ int popRaising; // Boost the worst agents double mutationRate; // Mutation probability double powCh; // Selection power-law exponent double powMut; // Mutation power-law exponent private: //--------------------------------------------------------- int currentEpoch; // current epoch int totalEpochs; // total number of epochs void MutateComponent (int agentIdx, int componentIdx); }; //————————————————————————————————————————————————————————————————————
Die Methode Init ist für die Initialisierung des Algorithmus zuständig. Die Funktion nimmt als Eingabe Arrays mit Minimal- und Maximalwerten sowie die Schrittweite für Optimierungsparameter entgegen, ebenso wie die Gesamtzahl der Epochen (Zyklen) des Algorithmusbetriebs.
Innerhalb der Methode wird zuerst die Funktion StandardInit aus der Basisklasse C_AO aufgerufen. Diese Funktion führt eine allgemeine Initialisierung, Speicherzuweisung oder die Einrichtung grundlegender Parameter in Bezug auf Bereiche und Schritte für Optimierungsparameter durch.
Wenn StandardInit fehlschlägt, wird auch die Funktion Init beendet und gibt false zurück. Wenn StandardInit erfolgreich ist, initialisiert die Methode die Variablen currentEpoch (aktuelle Epoche) auf 0 und totalEpochs (Gesamtzahl der Epochen) auf den im Parameter epochsP erhaltenen Wert.
Am Ende gibt die Methode true zurück, was eine erfolgreiche Initialisierung signalisiert. Somit bereitet die Methode den Algorithmus durch das Festlegen der Anfangsparameter und des Epochenzählers auf den Einsatz vor.
//———————————————————————————————————————————————————————————————————— //--- Initialization bool C_AO_EOm::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; return true; } //————————————————————————————————————————————————————————————————————
Die Methode Moving stellt den Hauptzyklus des extremalen Optimierungsalgorithmus dar. Sie ist für die Evolution der Lösungspopulation bei der Suche nach der optimalen Lösung verantwortlich. Epochen-Inkrement: der Zähler currentEpoch wird inkrementiert. Populationsinitialisierung (nur erste Epoche): Wenn das Flag revision (das die Notwendigkeit einer Neubewertung der Lösungen anzeigt) gleich false ist (d. h. im ersten Zyklus des Algorithmus), wird die Population initialisiert.
Für jeden Agenten (Lösung) in der Population wird für jede Koordinate (Lösungsparameter) ein Zufallswert in einem gegebenen Bereich (rangeMin, rangeMax) für die aktuelle Koordinate generiert. Die SeInDiSp-Diskretisierung wird verwendet, um sicherzustellen, dass die Parameterwerte den angegebenen Schritten entsprechen. Nach der Initialisierung wird revision auf true gesetzt, sodass dieser Codeblock nur einmal ausgeführt wird. Die Methode wird beendet.
Anwendung der extremalen Optimierung in nachfolgenden Epochen: ein temporäres Array aT wird erstellt, um neue (mutierte) Lösungen zu speichern. Für jeden Agenten in der Population wird die Struktur aT[i] initialisiert. Für jede Lösungskoordinate wird eine Zufallszahl generiert und mit der Potenz powCh potenziert. Dies wird verwendet, um den Ausgangsagenten auszuwählen.
Die Zufallszahl wird skaliert, um den Elternindex in der Population ind auszuwählen. Der Mutationstyp wird bestimmt: Wenn die Zufallszahl kleiner als mutationRate ist (die Mutation wird mit der Wahrscheinlichkeit mutationRate aktiviert), dann wird die Mutation gemäß dem Potenzgesetz PowerDistribution auf den Wert der Elternkoordinate angewendet. Andernfalls erfolgt eine gerichtete Bewegung in Richtung der besten Lösung unter Hinzufügung von Zufallsrauschen. Der neue Wert wird als Summe aus dem Wert der Elternkoordinate, einer Zufallszahl und der Differenz zwischen cB[c] (der gefundenen besten Koordinate) und der Elternkoordinate berechnet. Die SeInDiSp-Diskretisierung wird verwendet. Nach der Mutation werden alle Koordinaten aus dem temporären Array aT in das Hauptpopulations-Array a kopiert.
Somit implementiert die Methode einen Evolutionszyklus, bei dem die Lösungen in jedem Schritt (Epoche) mutieren (sich ändern), wobei Mechanismen der Selektion, der zufälligen Mutation und der gerichteten Suche verwendet werden, mit dem Ziel, ihre Werte zu verbessern (Minimierung oder Maximierung der Zielfunktion), um letztendlich die optimale Lösung zu finden.
//———————————————————————————————————————————————————————————————————— //--- Main loop of the algorithm void C_AO_EOm::Moving () { currentEpoch++; // Initial population setup if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } //Apply Extremal Optimization--------------------------------------- static S_AO_Agent aT []; ArrayResize (aT, popSize); for (int i = 0; i < popSize; i++) { aT [i].Init (coords); for (int c = 0; c < coords; c++) { double rnd = u.RNDprobab (); rnd = pow (rnd, powCh); int ind = (int)u.Scale (rnd, 0.0, 1.0, 0, popSize - 1); // Select the mutation type double mutType = u.RNDprobab (); if (mutType < mutationRate) { aT [i].c [c] = u.PowerDistribution (a [ind].c [c], rangeMin [c], rangeMax [c], powMut); } else { // Directed movement towards the better with noise aT [i].c [c] = a [ind].c [c] + u.RNDprobab () * (cB [c] - a [ind].c [c]); } // Check boundaries aT [i].c [c] = u.SeInDiSp (aT [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, aT [i].c); } //————————————————————————————————————————————————————————————————————
Die Methode ist für die Aktualisierung von Informationen über die besten Lösungen während des Betriebs des Algorithmus verantwortlich.
Sortierung der Population: Ein temporäres Array aT wird erstellt, um eine Kopie der Population zu speichern. Die Population a wird nach dem Wert der Zielfunktion sortiert. Die Methode u.Sorting wird für die Sortierung verwendet.
Aktualisierung der global besten Lösung: Es wird geprüft, ob der Wert der Zielfunktion f des ersten Elements der Population (d. h. der besten Lösung) besser ist als der aktuelle globale Bestwert fB. Wenn die aktuelle Lösung besser ist, wird cB aus den Koordinaten des ersten Elements a[0].c kopiert und fB mit dem Wert f der besseren Lösung aktualisiert.
Aktualisierung der schlechtesten Lösung: fW wird mit dem Funktionswert des letzten Elements der Population aktualisiert.
Anheben der schlechtesten Lösungen: In einer Schleife, die popRaising-mal ausgeführt wird, werden die schlechtesten Lösungen in der Population angehoben: Für die popRaising schlechtesten Agenten (die sich am Ende des sortierten Arrays a befinden) wird der Wert der Zielfunktion f als Zufallswert neu berechnet, der zwischen fW (dem schlechtesten aktuellen Ergebnis) und fB (dem besten aktuellen Ergebnis) liegt. Dies geschieht, um Vielfalt einzuführen oder die schlechtesten Lösungen in Richtung der besseren zu verschieben.
Neusortierung der Population: Die Population a wird mithilfe der Methode u.Sorting neu sortiert. Dies ist notwendig, um die Population nach Änderungen der f-Werte wieder in Ordnung zu bringen.
//———————————————————————————————————————————————————————————————————— //--- Update the best solutions void C_AO_EOm::Revision () { // Sort the population -------------------------------------------- static S_AO_Agent aT []; ArrayResize (aT, popSize); u.Sorting (a, aT, popSize); // Update the global best solution if (a [0].f > fB) { ArrayCopy (cB, a [0].c, 0, 0, WHOLE_ARRAY); fB = a [0].f; } fW = a [popSize - 1].f; //------------------------------------------------------------------ for (int i = 0; i < popRaising; i++) { a [popSize - 1 - i].f = u.RNDfromCI (fW, fB); } u.Sorting (a, aT, popSize); } //————————————————————————————————————————————————————————————————————
Nun verwendet der Algorithmus (der in gewissem Sinne die Ideen von EO erbt, wenn auch auf modifizierte Weise) eine Potenzverteilung, um Ausgangslösungen auszuwählen (nicht notwendigerweise schlechte).
a [popSize - 1 - i].f = u.RNDfromCI (fW, fB);Ich habe eine Funktion hinzugefügt, die in EO-Beschreibungen nicht vorkommt: Der Algorithmus gibt den schlechtesten Agenten gewissermaßen neues Potenzial, indem er ihnen eine zufällige Fitness im Bereich vom schlechtesten bis zum besten Wert in der Population zuweist. PowerDistribution für Mutation ist eine Interpretation der Power-Law-Distributionsmutation. Gezielte Bewegung in Richtung des Besseren (für mutType >= mutationRate ) – Ergänzung zur Beschleunigung der Konvergenz.
Nun können wir uns die Ergebnisse der modifizierten Version ansehen. Wir können die folgenden Ergebnisse in unsere Bewertungstabelle aufnehmen.
EOm|Extremal Optimization Mod|50.0|3.0|0.1|2.0|8.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7616651321732368
25 Hilly's; Func runs: 10000; result: 0.7724295992586084
500 Hilly's; Func runs: 10000; result: 0.3174703398632668
=============================
5 Forest's; Func runs: 10000; result: 0.9999936711143977
25 Forest's; Func runs: 10000; result: 0.7675163269928252
500 Forest's; Func runs: 10000; result: 0.23527203643380376
=============================
5 Megacity's; Func runs: 10000; result: 0.7476923076923077
25 Megacity's; Func runs: 10000; result: 0.5396923076923076
500 Megacity's; Func runs: 10000; result: 0.14249230769230903
=============================
All score: 5.28422 (58.71%)
Die Visualisierung zeigt eine große Streuung der Ergebnisse für niedrigdimensionale Funktionen (grüne Linien).
EOm mit der Testfunktion Hilly
EOm mit der Testfunktion Forest
EOm mit der Testfunktion Megacity
Nach dem Test belegt der EOm-Algorithmus den 12. Platz in unserer 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) 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 | EOm | extremal_optimization_M | 0.76166 | 0.77242 | 0.31747 | 1.85155 | 0.99999 | 0.76751 | 0.23527 | 2.00277 | 0.74769 | 0.53969 | 0.14249 | 1.42987 | 5.284 | 58.71 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | BSA | Backtracking-Suchalgorithmus | 0.97309 | 0.54534 | 0.29098 | 1.80941 | 0.99999 | 0.58543 | 0.21747 | 1.80289 | 0.84769 | 0.36953 | 0.12978 | 1.34700 | 4.959 | 55.10 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | (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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
| 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 vorgestellte kompakte modifizierte Implementierung von EOm zeigt ein interessantes Beispiel auf dem Gebiet der metaheuristischen Optimierung: eine signifikante Abweichung von theoretischen Prinzipien kann zu verbesserten praktischen Ergebnissen führen. Der Algorithmus, der unter 45 populationsbasierten Methoden den 12. Platz belegte, ist eigentlich ein Hybrid, der nur die Kernidee der Potenzgesetzverteilung aus dem ursprünglichen EO beibehält.
Der Auferstehungs-Mechanismus der schlechtesten Agenten verhindert eine vorzeitige Konvergenz, erhält die Populationsvielfalt aufrecht und schafft zusätzliche Möglichkeiten zur Exploration. Vereinfachung der Berechnungsstruktur: Der Verzicht auf eine komponentenweise Auswertung reduziert die Rechenkomplexität, und das direkte Arbeiten mit Lösungen beschleunigt die Konvergenz.
Der Erfolg der modifizierten Version von EO bestätigt ein wichtiges Prinzip beim Entwurf von Metaheuristiken: die Effizienz eines Algorithmus wird nicht durch seine Treue zur ursprünglichen Idee bestimmt, sondern durch das Gleichgewicht zwischen Exploration und Exploitation des Suchraums. Die vorgestellte Implementierung zeigt trotz ihrer Abkehr von den klassischen Prinzipien der Extremaloptimierung eine hohe Konvergenzgeschwindigkeit, wettbewerbsfähige Ergebnisse sowie eine einfache Implementierung und Konfiguration.
Dies macht EOm zu einem nützlichen Werkzeug im Arsenal der Populationsoptimierungsmethoden, insbesondere für Probleme, bei denen das Gleichgewicht zwischen Lösungsqualität und Rechenaufwand wichtig ist.
Abbildung 1. Farbskala der Algorithmen nach den entsprechenden Tests
Abbildung 2. 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 EOm:
Vorteile:
- Einfache Umsetzung
- Schnell und effizient
- Gute Ergebnisse bei diskreten Problemen
Nachteile:
- Große Streuung der Ergebnisse bei niedrigdimensionalen Funktionen
- Durchschnittliche Ergebnisse bei glatten niedrigdimensionalen Problemen
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.
Im 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 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_EOm.mq5 | Skript | EOm-Testumgebung |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/18755
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.
Die Übertragung der Trading-Signale in einem universalen Expert Advisor.
Neuronale Netze im Trading: Skill-Hierarchie für das Verhalten adaptiver Agenten (letzter Teil)
Eine alternative Log-datei mit der Verwendung der HTML und CSS
Benutzerdefinierte Symbole in MQL5: Erstellung eines 3D-Bar-Symbols
- 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.