Korallenriff-Optimierung (CRO)
28
0
Inhalt
Einführung
Bioinspirierte Algorithmen, die auf natürlichen Prozessen und Systemen beruhen, haben in den letzten Jahren bei Entwicklern große Aufmerksamkeit erlangt. Der Algorithmus Coral Reef Optimization (CRO), der ursprünglich von S. Salcedo-Sanz et al. im Jahr 2014 vorgeschlagen wurde, ist wahrscheinlich der bekannteste unter ihnen.
Der CRO-Algorithmus basiert auf der Modellierung der Prozesse der Entstehung und Entwicklung von Korallenriffen in der Natur. Zu diesen Prozessen gehören verschiedene Mechanismen der Korallenvermehrung (Broadcast Spawning, Brooding und ungeschlechtliche Vermehrung), der Wettbewerb um begrenzten Platz im Riff und das Absterben schwacher Individuen. So wie die Evolution in der Natur widerstandsfähige und anpassungsfähige Korallenriffe hervorbringt, kann man mit dem CRO-Algorithmus den Suchraum erkunden und optimale oder nahezu optimale Lösungen für verschiedene Probleme finden.
In diesem Papier stellen wir die verbesserte Version CROm des Algorithmus mit einem modifizierten Zerstörungsmechanismus vor, der auf der Verwendung des inversen Potenzgesetzes basiert, um neue Lösungen in der Nachbarschaft der besten Lösungen zu erzeugen. Der vorgeschlagene Ansatz bewahrt nicht nur die traditionellen Vorteile von CRO, wie z.B. die Explorationskapazität und ein natürliches Gleichgewicht zwischen globaler Exploration und lokaler Suche des Suchraums, sondern ergänzt sie durch einen effizienteren Mechanismus, der eine genauere Lokalisierung vielversprechender Suchbereiche und eine schnellere Konvergenz zu optimalen Lösungen ermöglicht.
Wir werden den vorgeschlagenen Algorithmus ausgiebig an einer Reihe von klassischen Optimierungs-Benchmark-Funktionen testen und seine verbesserte Leistung im Vergleich zum ursprünglichen CRO-Algorithmus und anderen modernen Metaheuristiken demonstrieren. Die experimentellen Ergebnisse zeigen, dass der vorgeschlagene Ansatz besonders effektiv für Probleme mit multimodalen Zielfunktionen und komplexen Suchlandschaften ist.
Der Artikel ist wie folgt gegliedert: Zunächst werden die grundlegenden Konzepte und Funktionsprinzipien des Standard-CRO-Algorithmus erläutert, dann werden die vorgeschlagenen Änderungen und ihre theoretische Begründung im Detail beschrieben. Es folgt eine experimentelle Bewertung des Algorithmus und eine Analyse der Ergebnisse. Abschließend werden die erzielten Ergebnisse, die Grenzen der vorgeschlagenen Methode und mögliche Richtungen für die zukünftige Forschung diskutiert.
Implementierung des Algorithmus
Die Grundidee von CRO besteht darin, Korallenkolonien zu simulieren, die sich entwickeln und um den Platz auf einem Riff konkurrieren und schließlich eine optimale Struktur bilden. Jede Koralle im Riff stellt eine potenzielle Lösung für das zu betrachtende Optimierungsproblem dar.
Das Riff wird als zweidimensionales N×M-Gitter modelliert. Jede Gitterzelle kann entweder mit einer Koralle besetzt werden oder leer bleiben. Eine Koralle ist eine kodierte Lösung für ein Optimierungsproblem. Für jede Koralle wird eine Fitnessfunktion (Gesundheit) bestimmt, die der Zielfunktion des Optimierungsproblems entspricht.
Der Parameter ρ₀ ∈ (0,1) bestimmt den anfänglichen Anteil des Riffs, der von Korallen besetzt ist, d. h. das Verhältnis der besetzten Zellen zur Gesamtzahl der Zellen zu Beginn des Algorithmus. Die Initialisierung des Riffs wird wie folgt durchgeführt:
- Zunächst werden die Riffgröße N×M und der anfängliche Belegungsgrad ρ₀ festgelegt.
- ⌊ρ₀ × N × M⌋ Riffzellen werden nach dem Zufallsprinzip ausgewählt, um die Startkorallen aufzunehmen.
- Die anfänglichen Korallen werden nach dem Zufallsprinzip innerhalb des Suchgebiets erzeugt und in die ausgewählten Zellen gesetzt.
Nach der Initialisierung des Riffs beginnt ein iterativer Prozess der Riffbildung und -entwicklung, der aus mehreren Phasen besteht:
Broadcast Spawning. Für diese Art der Vermehrung wird ein bestimmter Anteil der vorhandenen Fₑ-Korallen ausgewählt. Die ausgewählten Korallen bilden Paare und erzeugen mithilfe von Kreuzungsoperatoren Nachkommen. Jedes Paar erzeugt eine Larve unter Verwendung des Kreuzungsoperators (arithmetische Mittelwertbildung).
Brooding. Der verbleibende Anteil der Korallen (1-Fₑ) durchläuft Brooding, wobei jede Koralle durch Mutation eine Larve erzeugt. Für jede Koralle, die zum Brooding ausgewählt wird, wird mithilfe eines Mutationsoperators eine Larve erzeugt. Die Larve stellt in der Regel eine kleine Zufallsvariante der kodierten Lösung dar. Larvenansiedlung. Nachdem sich die Larven gebildet haben, versucht jede von ihnen, während der Fortpflanzungsphase ihren Platz im Riff einzunehmen. Die Ansiedlung wird nach den folgenden Regeln durchgeführt:
- Die Larve wählt zufällig eine Zelle (i, j) im Riff aus.
- Wenn die Zelle frei ist, besetzt die Larve sie.
- Wenn die Zelle besetzt ist, kann die Larve die vorhandene Koralle nur verdrängen, wenn ihre Fitness höher ist: f(Larve) > f(Ξᵢⱼ).
- Erfolgt keine Verdrängung, kann die Larve versuchen, sich an einem anderen Ort anzusiedeln (bis zu einer maximalen Anzahl von k Versuchen).
- Wenn die Larve nach k Versuchen keinen Platz findet, stirbt sie.
Ungeschlechtliche Vermehrung (Knospung). Die besten Korallen in einem Riff (Fₐ-Fraktion) können sich ungeschlechtlich vermehren und exakte Kopien ihrer selbst (Klone) erzeugen. Formal:
- Die Korallen werden nach der Fitnessfunktion sortiert.
- Die besten Fₐ × 100%-Korallen werden für die ungeschlechtliche Vermehrung ausgewählt.
- Jede ausgewählte Koralle erzeugt einen Klon, der versucht, sich nach denselben Regeln wie bei der Larvenansiedlung im Riff anzusiedeln.
Depredation (gezielte Entfernung schwacher Korallen). Am Ende jeder Iteration können die schlechtesten Korallen des Riffs mit einer Wahrscheinlichkeit von Pd absterben und in den nächsten Iterationen Platz für neue Korallen machen.
Die Riffbildung wird so lange wiederholt, bis das angegebene Abbruchkriterium erfüllt ist, z. B. das Erreichen der maximalen Anzahl von Iterationen. Nach dem Anhalten stellt die beste Koralle im Riff die gefundene Lösung für das Optimierungsproblem dar.
Abb. 1. Der CRO-Algorithmus funktioniert wie folgt:
Die Abbildung oben zeigt alle sechs Hauptstufen des Algorithmus:
- Bei der Initialisierung (ρ₀ = 0,6) wird ein zweidimensionales Gitter (Riff) angezeigt, das teilweise mit mehrfarbigen Korallen gefüllt ist, die verschiedene Lösungen darstellen.
- Beim Broadcast Spawning (Fb = 0,9) bilden die Korallen Paare und erzeugen Larven durch Kreuzung.
- Das Brooding (1-Fb = 0,1) zeigt, dass einzelne Korallen durch Mutation Larven produzieren.
- Die Larvenansiedlung (k = 3 Versuche) veranschaulicht die Suche der Larven nach einem Platz im Riff, einschließlich erfolgreicher und erfolgloser Versuche.
- Die ungeschlechtliche Vermehrung (Fa = 0,1) zeigt die besten Korallen (mit Sternen markiert), die exakte Kopien von sich selbst erzeugen.
- Depredation (Fd = 0,1, Pd = 0,05) zeigt, dass die schlechtesten Korallen aus dem Riff entfernt wurden.
Eingabe: Riffparameter (N, M, ρ₀, Fₑ, Fₐ, Fd, Pd, k)
Ausgabe: Beste Lösung gefunden
1. Initialisierung:
– Erstelle ein N×M-Riff
– Fülle ⌊ρ₀ × N × M⌋ Zellen mit beliebigen Korallen
– Berechne die Fitness der einzelnen Korallen
2. Bis das Abbruchkriterium erfüllt ist:
3. Broadcast Spawning:
– Wähle einen Anteil an Fₑ-Korallen zur Teilnahme aus
– Bilde Paare und erzeuge Larven durch Kreuzung
4. Brooding:
– Erzeuge für die übrigen Korallen (1-Fₑ) Larven durch Mutation
5. Larvenansiedlung:
– Für jede Larve:
– Versuche, eine zufällige Riffzelle zu besetzen
– Wenn diese besetzt ist, verdränge die vorhandene Koralle, wenn deine Fitness höher ist
– Wenn dies nicht gelingt, versuche es erneut (bis zu k Versuchen)
6. Ungeschlechtliche Fortpflanzung:
– Sortiere Korallen nach Fitness
– Die besten Fₐ-Korallen bilden Klone
– Die Klone versuchen, sich im Riff anzusiedeln
7. Depredation:
– Führe mit Wahrscheinlichkeit Pd eine Depredation durch
– Entferne den Anteil Fd der schlechtesten Korallen
8. Gib die besten Korallen im Riff zurück
Jetzt können wir den Algorithmus von CRO implementieren. Implementieren wir die Klasse C_AO_CRO, die den CRO-Algorithmus implementiert und von der Basisklasse C_AO abgeleitet wird.
CRO-Parameter:
Die Klasse deklariert die Parameter, die das Verhalten des Algorithmus steuern:
- popSize – Größe der Korallenpopulation.
- reefRows – Höhe des Riffs (Anzahl der Zeilen im Raster).
- reefCols – Breite des Riffs (Anzahl der Spalten im Raster).
- rho0 – anfängliche Riffbelegung. Dies ist der Prozentsatz der Riffzellen, die zu Beginn des Algorithmus von Korallen besetzt sind.
- Fb – Anteil der Korallen, die am Broadcast Spawning teilnehmen.
- Fa – Anteil der Korallen, die an der ungeschlechtlichen Vermehrung (Fragmentierung) teilnehmen.
- Fd – Anteil der Korallen, die aufgrund ihrer geringen Fitness entfernt werden müssen.
- Pd – Wahrscheinlichkeit der Zerstörung von Korallen.
- attemptsNum – Anzahl der Versuche der Larve, sich am Riff anzusiedeln.
Methoden der Klasse:
- SetParams () – Methode setzt die Werte der Algorithmusparameter auf der Grundlage der im Array „params“ gespeicherten Werte. Dies ist ein Array, das es uns ermöglicht, die Algorithmusparameter während der Ausführung dynamisch zu ändern.
- Init () – Initialisierungsmethode, die Suchbereiche für Optimierungsvariablen (rangeMinP, rangeMaxP, rangeStepP) und die Anzahl der Epochen (epochsP) entgegennimmt. Die Init-Methode führt die notwendigen Vorbereitungen für den Start des Algorithmus durch, wie die Initialisierung der Population und des Riffs.
- Moving () – Grundlogik der Iteration bzw. der Aktualisierung des Korallenbestands im Riff.
- Revision () – Überprüfen und Anpassen der Positionen der Korallen im Riff.
- InitReef () – initialisiert die Riffstruktur und bereitet sie auf die Besiedlung durch Korallen vor.
- LarvaSettling () – bestimmt, wo sich die Korallenlarven im Riff ansiedeln, um die Besiedlung des Riffs durch neue Korallen zu simulieren. Der Parameter „larva“ steht für die Korallenlarve.
- BroadcastSpawning () – Korallen geben ihre Larven ins Wasser ab.
- Brooding () – die Larven entwickeln sich im Inneren der Koralle.
- AsexualReproduction () – Korallen teilen sich und bilden neue Kolonien.
- Depredation () – die Korallen werden zerstört.
- GetReefCoordIndex () – wandelt Riffkoordinaten (Zeile und Spalte) in einen Index in einem eindimensionalen Array um.
- SortAgentsByFitness () – sortiert Korallen nach ihrer Fitness.
Private Variablen:
- totalReefSize – Gesamtgröße des Riffs (Produkt aus reefRows und reefCols).
- occupied [] – Array mit booleschen Werten, die angeben, ob jede Riffzelle von einer Koralle besetzt ist.
- reefIndices [] – Array mit Indizes, die die Indizes der Korallen (aus dem Array a [] der Basisklasse C_AO) in den belegten Riffzellen enthalten.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_CRO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_CRO () { } C_AO_CRO () { ao_name = "CRO"; ao_desc = "Coral Reef Optimization"; ao_link = "https://www.mql5.com/en/articles/17760"; popSize = 50; // population size reefRows = 20; // reef height reefCols = 20; // reef width rho0 = 0.2; // initial reef occupancy Fb = 0.99; // fraction of corals for broadcast spawning Fa = 0.01; // fraction of corals for asexual reproduction Fd = 0.8; // fraction of corals to remove Pd = 0.9; // probability of destruction attemptsNum = 20; // number of attempts for larvae to settle ArrayResize (params, 9); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "reefRows"; params [1].val = reefRows; params [2].name = "reefCols"; params [2].val = reefCols; params [3].name = "rho0"; params [3].val = rho0; params [4].name = "Fb"; params [4].val = Fb; params [5].name = "Fa"; params [5].val = Fa; params [6].name = "Fd"; params [6].val = Fd; params [7].name = "Pd"; params [7].val = Pd; params [8].name = "attemptsNum"; params [8].val = attemptsNum; } void SetParams () { popSize = (int)params [0].val; reefRows = (int)params [1].val; reefCols = (int)params [2].val; rho0 = params [3].val; Fb = params [4].val; Fa = params [5].val; Fd = params [6].val; Pd = params [7].val; attemptsNum = (int)params [8].val; } bool Init (const double &rangeMinP [], // minimum search range const double &rangeMaxP [], // maximum search range const double &rangeStepP [], // search step const int epochsP = 0); // number of epochs void Moving (); void Revision (); //---------------------------------------------------------------------------- int reefRows; // reef height int reefCols; // reef width double rho0; // initial reef occupancy double Fb; // fraction of corals for broadcast spawning double Fa; // fraction of corals for asexual reproduction double Fd; // fraction of corals to remove double Pd; // probability of destruction int attemptsNum; // number of attempts for larvae to settle private: //------------------------------------------------------------------- int totalReefSize; // total reef size bool occupied []; // flags of reef cell occupancy int reefIndices []; // agent indices in a[] corresponding to occupied cells // Auxiliary methods void InitReef (); int LarvaSettling (S_AO_Agent &larva); void BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount); void Brooding (S_AO_Agent &larvae [], int &larvaCount); void AsexualReproduction (); void Depredation (); int GetReefCoordIndex (int row, int col); void SortAgentsByFitness (int &indices [], int &count); }; //——————————————————————————————————————————————————————————————————————————————
Die Init-Methode initialisiert den CRO-Algorithmus: Sie ruft das StandardInit der Basisklasse auf, berechnet dann die Gesamtgröße des Riffs (totalReefSize), bestimmt die anfängliche Anzahl der Korallen (initialPopSize), initialisiert das Array „occupied“ und das Array „reefIndices“, ruft InitReef() auf, um die Korallen auf dem Riff zu platzieren, und gibt schließlich bei Erfolg „true“ zurück.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_CRO::Init (const double &rangeMinP [], // minimum search range const double &rangeMaxP [], // maximum search range const double &rangeStepP [], // search step const int epochsP = 0) // number of epochs { // Standard initialization of the parent class if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Calculate the reef total size totalReefSize = reefRows * reefCols; // The number of starting corals should not exceed popSize int initialPopSize = (int)MathRound (rho0 * totalReefSize); if (initialPopSize > popSize) initialPopSize = popSize; // Initialize the occupancy array and indices ArrayResize (occupied, totalReefSize); ArrayResize (reefIndices, totalReefSize); // Fill the arrays with initial values for (int i = 0; i < totalReefSize; i++) { occupied [i] = false; reefIndices [i] = -1; } // Reef initialization InitReef (); return true; } //——————————————————————————————————————————————————————————————————————————————Die Methode InitReef() der Klasse C_AO_CRO initialisiert die Anfangspopulation der Korallen auf dem Riff. Zunächst berechnen wir die Anzahl der zu initialisierenden Korallen auf der Grundlage der gegebenen Dichte (rho0) des Riffs. Diese Zahl wird durch die Populationsgröße popSize begrenzt. Dann wird für jede Koralle eine zufällige, aber freie Position auf dem Riff zugewiesen, die, sobald sie gefunden ist, als besetzt markiert wird, und die Koralle wird mit dieser Position im reefIndices-Array verknüpft. Anschließend werden für jede Koralle Koordinaten erstellt. Jede Koordinate wird innerhalb der vorgegebenen Grenzen (rangeMin, rangeMax) zufällig ausgewählt und mit der Funktion u.SeInDiSp diskretisiert, wobei der Diskretisierungsschritt (rangeStep) berücksichtigt wird. Dies gewährleistet eine gleichmäßige und kontrollierte Verteilung der Ausgangslösungen (Korallen) im Suchraum.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::InitReef () { // Number of starting corals in the reef (based on rho0) int initialCorals = (int)MathRound (rho0 * totalReefSize); // The number of starting corals should not exceed the population size if (initialCorals > popSize) initialCorals = popSize; // Initialize initialCorals random positions in the reef for (int i = 0; i < initialCorals; i++) { int pos; // Look for a free position do { pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Protection against exceeding the array size if (pos < 0) pos = 0; if (pos >= totalReefSize) pos = totalReefSize - 1; } while (occupied [pos]); // Create a new coral at the found position occupied [pos] = true; reefIndices [pos] = i; // Generate random coordinates for a new coral for (int c = 0; c < coords; c++) { double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode Moving() führt eine erste Bewertung der Korallenpopulation durch. Wenn „revision“ falsch ist, durchläuft die Methode alle Riffpositionen. Für jede belegte Position (bestimmt durch den Wert des Array-Elements „occupied“) erhält die Methode den Index der Koralle, die sich an dieser Position befindet, aus dem Array „reefIndices“. Wenn der resultierende idx-Index gültig ist, wird die Fitness dieser Koralle berechnet.
Es ist wichtig zu beachten, dass die Methode Moving() die Fitness selbst nicht direkt berechnet, sondern nur die notwendigen Informationen für die Berechnung liefert. Nach der Iteration über alle Riffpositionen setzt die Methode den Wert „revision“ auf „true“, um zu verhindern, dass die Korallenbewertungsschleife in derselben Optimierungsiteration erneut ausgeführt wird. Im Wesentlichen fungiert die Methode Moving() als Auslöser für die Berechnung der Korallenfitness, sodass die Bewertung nur einmal pro Iteration erfolgt.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Moving () { if (!revision) { // Initial assessment of all corals in the reef for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { int idx = reefIndices [i]; if (idx >= 0 && idx < popSize) { // Calculating fitness does not require using GetFitness() // since it will be evaluated in external code (in FuncTests) } } } revision = true; } } //——————————————————————————————————————————————————————————————————————————————
Die Methode Revision() aktualisiert die globale beste Lösung. Die Methode sucht nach Korallen im Riff, deren Fitness besser ist als die der derzeit besten globalen Lösung, und ersetzt sie. Anschließend wird ein Array zur Speicherung der erzeugten Larven angelegt. Die Methode leitet dann die sexuelle Fortpflanzung ein – sie ruft die Methoden BroadcastSpawning und Brooding auf, um Larven zu erzeugen. Der nächste Schritt der Methode ist die Larvenansiedlung mit der Methode LarvaSettling, um Standorte für neue Larven im Riff zu bestimmen. AsexualReproduction wird initiiert, gefolgt von der Depredation. Kurz gesagt, es aktualisiert die Lösung, erzeugt Korallenlarven, siedelt die Larven an und simuliert die Auswirkungen der Depredation.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Revision () { // Update the global best solution for (int i = 0; i < totalReefSize; i++) { if (occupied [i] && a [reefIndices [i]].f > fB) { fB = a [reefIndices [i]].f; ArrayCopy (cB, a [reefIndices [i]].c, 0, 0, WHOLE_ARRAY); } } // Form an array to store larvae S_AO_Agent larvae []; ArrayResize (larvae, totalReefSize * 2); // Allocate with reserve int larvaCount = 0; // Stage 1: Broadcast Spawning BroadcastSpawning (larvae, larvaCount); // Stage 2: Brooding Brooding (larvae, larvaCount); // Calculate the fitness function for each larva // (will be executed in external code in FuncTests) // Stage 3: Larval settlement for (int i = 0; i < larvaCount; i++) { LarvaSettling (larvae [i]); } // Stage 4: Asexual reproduction AsexualReproduction (); // Stage 5: Depredation Depredation (); } //——————————————————————————————————————————————————————————————————————————————
Die LarvaSettling-Methode simuliert den Prozess der Larvenbesiedlung eines Riffs. Sie versucht, einen geeigneten Platz für die Larve zu finden und setzt sie entweder an einer freien Stelle ab oder ersetzt eine vorhandene, aber weniger geeignete Koralle. Bei dem Versuch, sich niederzulassen, versucht die Larve, sich so oft wie möglich niederzulassen. Bei jedem Versuch wird eine zufällige Position auf dem Riff ausgewählt. Ist die gewählte Position frei (nicht von einer Koralle besetzt), sucht die Methode nach einem freien Index im Agenten-Array a[]. Wird ein freier Index gefunden, kopiert die Larve ihre Lösung (c[]-Koordinaten und f-Fitness) in die entsprechende Zelle des Agenten-Arrays.
Die Information, dass die Riffposition nun besetzt ist, wird aktualisiert, und die Methode gibt den Index der erfolgreich besetzten Position „pos“ zurück. Wenn die gewählte Position besetzt ist, vergleicht die Methode die Fitness der Larve mit der Fitness der aktuellen Koralle an dieser Position. Wenn die Larve besser ist, ersetzt sie die vorhandene Koralle, indem sie ihre Parameter in ihre Zelle im Agenten-Array kopiert, und die Methode gibt den Index „pos“ der Position zurück, an der die Ersetzung stattgefunden hat. Wenn es der Larve nach allen Versuchen nicht gelingt, sich anzusiedeln (entweder in einem unbesetzten Raum oder durch Ersetzen einer vorhandenen Koralle), gibt die Methode -1 zurück.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::LarvaSettling (S_AO_Agent &larva) { // Try to settle the larva attemptsNum times for (int attempt = 0; attempt < attemptsNum; attempt++) { // Select a random position in the reef int pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Check that the position is within the array if (pos < 0 || pos >= totalReefSize) continue; // If the position is free, populate the larva if (!occupied [pos]) { // Search for a free index in the agents array int newIndex = -1; for (int i = 0; i < popSize; i++) { bool used = false; for (int j = 0; j < totalReefSize; j++) { if (reefIndices [j] == i) { used = true; break; } } if (!used) { newIndex = i; break; } } if (newIndex != -1) { // Copy the larva's solution ArrayCopy (a [newIndex].c, larva.c, 0, 0, WHOLE_ARRAY); a [newIndex].f = larva.f; // Update information about the reef occupied [pos] = true; reefIndices [pos] = newIndex; return pos; } } // If the position is occupied, check if the larva is better than the current coral else if (occupied [pos] && reefIndices [pos] >= 0 && reefIndices [pos] < popSize && larva.f > a [reefIndices [pos]].f) { // The larva displaces the existing coral ArrayCopy (a [reefIndices [pos]].c, larva.c, 0, 0, WHOLE_ARRAY); a [reefIndices [pos]].f = larva.f; return pos; } } // If the larva failed to settle, return -1 return -1; } //——————————————————————————————————————————————————————————————————————————————
Die Methode BroadcastSpawning simuliert Broadcast Spawning. Es führt die folgenden grundlegenden Schritte aus: Es ermittelt die Koordinaten aller von Korallen besiedelten Stellen am Riff, bestimmt anhand des Fb-Parameters (Brooding Fraction) – also des Anteils der Korallen, die am Broadcast Spawning teilnehmen – die Anzahl der an der Phase des Broadcast Spawning beteiligten Korallen, mischt die Koordinaten der besiedelten Korallen und wählt anschließend Paare für das Broadcast Spawning aus. Erzeugung von Larven durch Kreuzung: Für jedes Korallenpaar wird eine neue Larve erzeugt. Die Koordinaten der Larve werden als Durchschnittswert der Koordinaten der Eltern berechnet, wobei eine kleine Zufallsmutation hinzugefügt wird. Die Kreuzung zielt darauf ab, die besten Eigenschaften der Eltern zu kombinieren, und die daraus resultierenden Larven werden dem „Larven“-Feld hinzugefügt.
Wichtige Punkte:
- Fb ist hier für den Anteil der Korallen verantwortlich, die sich am Broadcast Spawning beteiligen, während es beim Brooding für den Anteil der Korallen verantwortlich ist, die sich im Brooding befinden.
- Kreuzen und Mutation erhöhen die genetische Vielfalt einer Population.
- Ziel der Methode ist es, aus einer Kombination von Genen der Elternkorallen neue Larven für die weitere Besiedlung des Riffs zu erzeugen. Bei der Methode handelt es sich um paarweise Kreuzung.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount) { // Find all occupied positions int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Check if there are no occupied positions if (occupiedCount == 0) return; // Select the Fb share for broadcast spawning int broadcastCount = (int)MathRound (Fb * occupiedCount); if (broadcastCount <= 0) broadcastCount = 1; // At least one coral if (broadcastCount > occupiedCount) broadcastCount = occupiedCount; // Shuffle the indices for (int i = 0; i < occupiedCount; i++) { // Register the array out-of-bounds problem int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Ensure that j is within the array bounds if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // Form pairs and create offspring for (int i = 0; i < broadcastCount - 1; i += 2) { if (i + 1 < broadcastCount) // Make sure there is a second parent { int idx1 = reefIndices [occupiedIndices [i]]; int idx2 = reefIndices [occupiedIndices [i + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) { // Initialize the larva larvae [larvaCount].Init (coords); // Create a new larva as a result of crossover for (int c = 0; c < coords; c++) { // Simple crossover method: average of parents' coordinates with a small mutation double value = (a [idx1].c [c] + a [idx2].c [c]) / 2.0 + u.RNDfromCI (-0.1, 0.1) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Increase the larvae counter larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode Brooding simuliert die Larvenentwicklung von Korallen in CRO und umfasst folgende Schritte:
- Bestimme, welche Stellen am Riff von Korallen besetzt sind, und speichere die Indizes dieser Positionen.
- Berechne mit dem Parameter Fb (Brooding Fraction), wie viele Korallen sich am Brooding beteiligen werden. Die Indizes der besetzten Positionen werden für eine zufällig ausgewählte Koralle, die an der Fortpflanzung teilnimmt, neu gemischt.
- Larven erzeugen und mutieren: Für jede ausgewählte Koralle wird eine Larve erzeugt. Die Larve wird initialisiert und mutiert: Ihre Koordinaten weichen nach dem Zufallsprinzip leicht von denen der Elternkoralle ab. Mutierte Larven werden dem Array „larvae“ hinzugefügt.
Wichtige Punkte:
- Fb definiert den Anteil der Korallen, die NICHT am Broadcast Spawning teilnehmen, sondern Brooding durchlaufen.
- Die Mutation sorgt für Genvielfalt in der Larvenpopulation.
- Ziel ist es, neue, potenziell überlegene Individuen zu schaffen, die um den Platz im Riff konkurrieren.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Brooding (S_AO_Agent &larvae [], int &larvaCount) { // Find all occupied positions int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Check if there are no occupied positions if (occupiedCount == 0) return; // Number of corals for internal reproduction int broodingCount = (int)MathRound ((1.0 - Fb) * occupiedCount); if (broodingCount <= 0) broodingCount = 1; // At least one coral if (broodingCount > occupiedCount) broodingCount = occupiedCount; // Shuffle the indices for (int i = 0; i < occupiedCount; i++) { // Register the array out-of-bounds problem int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Ensure that j is within the array bounds if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // For each selected coral, create a mutated copy for (int i = 0; i < broodingCount; i++) { if (i < occupiedCount) // Check for out-of-bounds { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Initialize the larva larvae [larvaCount].Init (coords); // Create a new larva as a mutation of the original coral for (int c = 0; c < coords; c++) { // Mutation: add a small random deviation double value = a [idx].c [c] + u.RNDfromCI (-0.2, 0.2) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Increase the larvae counter larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode AsexualReproduction simuliert die ungeschlechtliche Vermehrung von Korallen durch Knospung. Die Methode führt folgende Schritte durch: Sie ermittelt die Indizes aller von Korallen besetzten Positionen auf dem Riff, sortiert die Indizes der besetzten Positionen in der Reihenfolge abnehmender Fitness, d. h. die Positionen mit den fittesten Korallen kommen zuerst. Auf der Grundlage des Parameters „Fa“ (Anteil der ungeschlechtliche Vermehrung), der den Anteil der Korallen angibt, die an der ungeschlechtlichen Vermehrung beteiligt sind, wird die Anzahl der besten Korallen bestimmt, die Klone produzieren werden. Erzeugung und Besiedlung von Klonen: Für jede ausgewählte Koralle wird eine exakte Kopie (Klon) erzeugt – eine Larve mit denselben Koordinaten und Anpassungen. Die Methode LarvaSettling wird aufgerufen, um zu versuchen, den Klon auf dem Riff anzusiedeln.
Wichtige Punkte:
- Die ungeschlechtliche Vermehrung ermöglicht es den anpassungsfähigsten Korallen, ihre Gene schnell zu verbreiten.
- Der Parameter Fa steuert die Intensität der ungeschlechtlichen Fortpflanzung.
- Die Verwendung von LarvaSettling zur Besiedlung von Klonen bedeutet, dass die Klone auf die gleiche Weise um den Platz im Riff konkurrieren sollten wie sexuell erzeugte Larven.
- Das Klonen ist in diesem Fall das exakte Kopieren des Elternteils OHNE Mutationen. Mutationen treten nur während der sexuellen Fortpflanzung auf.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::AsexualReproduction () { // Find all occupied positions and their indices int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // If there are no occupied positions, exit if (occupiedCount == 0) return; // Sort indices by fitness SortAgentsByFitness (occupiedIndices, occupiedCount); // Select the best Fa% of corals for asexual reproduction int budCount = (int)MathRound (Fa * occupiedCount); if (budCount <= 0) budCount = 1; // At least one coral if (budCount > occupiedCount) budCount = occupiedCount; // For each selected coral, create a clone and try to populate it for (int i = 0; i < budCount; i++) { if (i < occupiedCount) // Check for out-of-bounds { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Create a new larva as an exact copy of the original coral S_AO_Agent clone; clone.Init (coords); ArrayCopy (clone.c, a [idx].c, 0, 0, WHOLE_ARRAY); clone.f = a [idx].f; // Try to populate the clone LarvaSettling (clone); } } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode Depredation simuliert das Aussterben von Korallen aufgrund der Zerstörung oder anderen negativen Faktoren (z. B. Verschmutzung). In diesem Fall wird die Zerstörung mit Pd-Wahrscheinlichkeit durchgeführt. Wenn die Zufallszahl kleiner als Pd ist, wird die Zerstörung durchgeführt. Die Suche nach besetzten Positionen wird durch die Indizes aller von Korallen besetzten Riffpositionen bestimmt. Die Methode sortiert die Indizes der besetzten Positionen nach der Fitness der Korallen.
Danach wird die Reihenfolge der sortierten Indizes umgekehrt, sodass die Indizes der schwächsten Korallen am Anfang der Reihe stehen. Die Menge der zu entnehmenden Korallen wird anhand des Parameters Fd (ausgemerzter Anteil) bestimmt. Dieser Wert wird auf die nächste ganze Zahl gerundet. Die angegebene Anzahl der am wenigsten angepassten Korallen wird entfernt. Als Nächstes kommt die Riffsäuberung: Für jede zur Löschung vorgesehene Position wird die entsprechende Zelle im Array „Besetzt“ auf „false“ gesetzt, was bedeutet, dass die Position nun frei ist. Die entsprechende Zelle im Array reefIndices wird auf -1 gesetzt, was anzeigt, dass sich an dieser Position keine Koralle befindet.
//—————————————————————————————————————————————————————————————————————————————— oid C_AO_CRO::Depredation() { // Apply destruction with Pd probability if (u.RNDfromCI(0, 1) < Pd) { // Find all occupied positions and their indices int occupiedIndices[]; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied[i]) { ArrayResize(occupiedIndices, occupiedCount + 1); occupiedIndices[occupiedCount] = i; occupiedCount++; } } // If there are no occupied positions, exit if (occupiedCount == 0) return; // Sort indices by fitness SortAgentsByFitness(occupiedIndices, occupiedCount); // Reverse the array so the worst ones are first for (int i = 0; i < occupiedCount / 2; i++) { if(i < occupiedCount && (occupiedCount - 1 - i) < occupiedCount) // Check for out-of-bounds { int temp = occupiedIndices[i]; occupiedIndices[i] = occupiedIndices[occupiedCount - 1 - i]; occupiedIndices[occupiedCount - 1 - i] = temp; } } // Remove the worst Fd% corals int removeCount = (int)MathRound(Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // At least one coral if (removeCount > occupiedCount) removeCount = occupiedCount; // Overflow protection for (int i = 0; i < removeCount; i++) { if(i < occupiedCount) // Check for out-of-bounds { int pos = occupiedIndices[i]; if(pos >= 0 && pos < totalReefSize) // Additional check { occupied[pos] = false; reefIndices[pos] = -1; } } } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode GetReefCoordIndex wandelt Riffkoordinaten (Zeile und Spalte) in einen eindimensionalen Index um und nimmt „row“ und „col“ als Eingaben entgegen und gibt den entsprechenden Index in dem Array zurück, das das Riff darstellt. Zunächst prüft die Methode, ob die übergebenen Koordinaten außerhalb der Grenzen des Riffs liegen. Andernfalls wird der Index nach der Gleichung (row * reefCols + col, wobei „reefCols“ die Anzahl der Spalten des Riffs ist) berechnet. Die Methode wird verwendet, um auf Elemente in Arrays zuzugreifen, die das Riff darstellen.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::GetReefCoordIndex (int row, int col) { // Check for out-of-bounds if (row < 0 || row >= reefRows || col < 0 || col >= reefCols) return -1; // Convert a two-dimensional position to a one-dimensional index return row * reefCols + col; } //——————————————————————————————————————————————————————————————————————————————
Die Methode SortAgentsByFitness sortiert das Array „indices“ mit „count“-Elementen in absteigender Reihenfolge ihrer Fitness unter Verwendung eines Bubble-Sort-Algorithmus auf der Grundlage der Fitness-Werte, die im Array „a“ gespeichert sind, auf das über das Array „reefIndices“ zugegriffen wird. Nach Ausführung der Methode indices enthält es also Korallenindizes, sortiert von dem besten bis zum schlechtesten Fitnesswert. Zusätzliche Prüfungen sollen verhindern, dass Array-Grenzen überschritten werden.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::SortAgentsByFitness (int &indices [], int &count) { // Check for an empty array if (count <= 0) return; // Bubble sort by decreasing fitness for (int i = 0; i < count - 1; i++) { for (int j = 0; j < count - i - 1; j++) { if (j + 1 < count) // Check that j+1 is not out of bounds { int idx1 = reefIndices [indices [j]]; int idx2 = reefIndices [indices [j + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) // Check indices { if (a [idx1].f < a [idx2].f) { int temp = indices [j]; indices [j] = indices [j + 1]; indices [j + 1] = temp; } } } } } } //——————————————————————————————————————————————————————————————————————————————
Wir haben die Vorbereitung des Algorithmus abgeschlossen und alle zahlreichen Methoden beschrieben. Jetzt können wir direkt zum Testen übergehen.
Testergebnisse
Nach der Durchführung von Tests ist klar, dass der CRO-Algorithmus eher schlecht funktioniert und es notwendig ist, einige der Methoden des ursprünglichen Ansatzes zu überdenken.CRO|Coral Reef Optimization|50.0|5.0|5.0|0.4|0.9|0.1|0.1|0.01|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.365266682511984
25 Hilly's; Func runs: 10000; result: 0.270828009448956
500 Hilly's; Func runs: 10000; result: 0.2504192846772352
=============================
5 Forest's; Func runs: 10000; result: 0.23618879234608753
25 Forest's; Func runs: 10000; result: 0.19453106526100442
500 Forest's; Func runs: 10000; result: 0.1679109693993047
=============================
5 Megacity's; Func runs: 10000; result: 0.13076923076923075
25 Megacity's; Func runs: 10000; result: 0.11138461538461542
500 Megacity's; Func runs: 10000; result: 0.09366153846153921
=============================
All score: 1.82096 (20.23%)
Das erste, was mir an dem CRO-Algorithmus auffiel, war die Zerstörungsmethode. Sie muss geändert werden, um die Suche zu verbessern. Wir werden die schlechtesten Korallen im Riff durch neue ersetzen, die in der Nähe der besten Korallen (Lösungen) entstehen, und so die Suche auf vielversprechendere Gebiete lenken. Wir bestimmen die Anzahl der besten (eliteCount) und der schlechtesten (removeCount) Korallen.
Ersetzen der schlechtesten Lösungen: Für jede „Beute“ wird eine „Elite“-Koralle ausgewählt, und eine neue Koralle wird in der Nähe dieser „Elite“-Koralle erzeugt. Bei dem verbesserten Zerstörungsmechanismus wird eine umgekehrte Potenzverteilung mit dem Exponenten 10 (mit „Potenz“ = 0,1) angewendet, um Abweichungen von der besten Lösung zu erzeugen. Diese Verteilung zeichnet sich dadurch aus, dass die meisten neuen Lösungen in unmittelbarer Nähe der besten Lösung erzeugt werden, aber mit einer geringen Wahrscheinlichkeit signifikante Abweichungen auftreten können, was ein Gleichgewicht zwischen lokaler Suche (Ausbeutung) und globaler Erkundung des Lösungsraums gewährleistet. Die neuen Koordinaten sind durch den zulässigen Bereich begrenzt. Die frei gewordene Stelle im Riff wird dann von einer neuen Koralle besiedelt.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Depredation () { // Apply destruction with Pd probability if (u.RNDfromCI (0, 1) < Pd) { // Find all occupied positions and their indices int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // If there are no occupied positions, exit if (occupiedCount == 0) return; // Sort the indices by fitness (from best to worst) SortAgentsByFitness (occupiedIndices, occupiedCount); // Determine the number of best solutions used to generate new ones int eliteCount = (int)MathRound (0.1 * occupiedCount); // Use top 10% if (eliteCount <= 0) eliteCount = 1; // At least one elite solution if (eliteCount > occupiedCount) eliteCount = occupiedCount; // Determine the number of worst solutions to be replaced int removeCount = (int)MathRound (Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // At least one solution is replaced if (removeCount > occupiedCount - eliteCount) removeCount = occupiedCount - eliteCount; // Do not remove elite solutions // Remove the worst solutions and replace them with new ones in the vicinity of the best ones for (int i = 0; i < removeCount; i++) { // Index of the solution to be removed (from the end of the sorted array) int removeIndex = occupiedCount - 1 - i; if (removeIndex < 0 || removeIndex >= occupiedCount) continue; int posToRemove = occupiedIndices [removeIndex]; if (posToRemove < 0 || posToRemove >= totalReefSize) continue; // Choose one of the elite solutions double power = 0.1; // Power distribution parameter double r = u.RNDfromCI (0, 1); int eliteIdx = (int)(eliteCount); if (eliteIdx >= eliteCount) eliteIdx = eliteCount - 1; int posBest = occupiedIndices [eliteIdx]; if (posBest < 0 || posBest >= totalReefSize) continue; int bestAgentIdx = reefIndices [posBest]; if (bestAgentIdx < 0 || bestAgentIdx >= popSize) continue; // Free up space for a new solution occupied [posToRemove] = false; // Generate a new solution in the neighborhood of the selected elite solution int newAgentIdx = reefIndices [posToRemove]; // Use the same agent index if (newAgentIdx >= 0 && newAgentIdx < popSize) { // Generation via power-law distribution around the best solution for (int c = 0; c < coords; c++) { // Determine the search radius (can be adapted depending on progress) double radius = 0.7 * (rangeMax [c] - rangeMin [c]); // 10% of the range // Generate a value using a power law double sign = u.RNDfromCI (0, 1) < 0.5 ? -1.0 : 1.0; // Random sign double deviation = sign * radius * MathPow (u.RNDfromCI (0, 1), 1.0 / power); // New value in the neighborhood of the best one double newValue = a [bestAgentIdx].c [c] + deviation; // Limit the value to an acceptable range a [newAgentIdx].c [c] = u.SeInDiSp (newValue, rangeMin [c], rangeMax [c], rangeStep [c]); } // Populate the new solution into the reef occupied [posToRemove] = true; reefIndices [posToRemove] = newAgentIdx; } } } } //——————————————————————————————————————————————————————————————————————————————
Nachdem die Änderungen vorgenommen wurden, können wir nun den CROm-Algorithmus testen. Wie Sie aus den nachstehenden Ergebnissen ersehen können, hat der Algorithmus seine Leistung erheblich verbessert.
CROm|Coral Reef Optimization M|50.0|20.0|20.0|0.2|0.99|0.01|0.8|0.9|20.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7851210159578113
25 Hilly's; Func runs: 10000; result: 0.4603296933002806
500 Hilly's; Func runs: 10000; result: 0.25958379129490083
=============================
5 Forest's; Func runs: 10000; result: 0.8668751980437325
25 Forest's; Func runs: 10000; result: 0.3529695710837671
500 Forest's; Func runs: 10000; result: 0.16267582083006701
=============================
5 Megacity's; Func runs: 10000; result: 0.6323076923076923
25 Megacity's; Func runs: 10000; result: 0.2673846153846154
500 Megacity's; Func runs: 10000; result: 0.10733846153846247
=============================
All score: 3.89459 (43.27%)
Die Visualisierung des Algorithmus ist nicht besonders erwähnenswert. Bei der Megacity-Testfunktion hat der Algorithmus etwas mehr Mühe, mit diskreten Aufgaben fertig zu werden.
CROm mit der Testfunktion Hilly
CROm mit der Testfunktion Forest
CROm mit der Testfunktion Megacity
Auf der Grundlage der Testergebnisse liegt der CROm-Algorithmus in der Rangliste der populationsbasierten Optimierungsalgorithmen auf Platz 42.
| # | AO | Beschreibung | Hilly | Hilly Finale | Forest | Forest Finale | Megacity (discrete) | Megacity Finale | Finale Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | Suche über die gesamte Nachbarschaft | 0.94948 | 0.84776 | 0.43857 | 2.23581 | 1.00000 | 0.92334 | 0.39988 | 2.32323 | 0.70923 | 0.63477 | 0.23091 | 1.57491 | 6.134 | 68.15 |
| 2 | CLA | Code-Sperr-Algorithmus (joo) | 0.95345 | 0.87107 | 0.37590 | 2.20042 | 0.98942 | 0.91709 | 0.31642 | 2.22294 | 0.79692 | 0.69385 | 0.19303 | 1.68380 | 6.107 | 67.86 |
| 3 | AMOm | Optimierung der Tiermigration M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5.987 | 66,52 |
| 4 | (P+O)ES | (P+O) Entwicklungsstrategien | 0.92256 | 0.88101 | 0.40021 | 2.20379 | 0.97750 | 0.87490 | 0.31945 | 2.17185 | 0.67385 | 0.62985 | 0.18634 | 1.49003 | 5.866 | 65.17 |
| 5 | CTA | Kometenschweif-Algorithmus (joo) | 0.95346 | 0.86319 | 0.27770 | 2.09435 | 0.99794 | 0.85740 | 0.33949 | 2.19484 | 0.88769 | 0.56431 | 0.10512 | 1.55712 | 5.846 | 64.96 |
| 6 | TETA | Zeit-Evolutions-Reise-Algorithmus (Joo) | 0.91362 | 0.82349 | 0.31990 | 2.05701 | 0.97096 | 0.89532 | 0.29324 | 2.15952 | 0.73462 | 0.68569 | 0.16021 | 1.58052 | 5.797 | 64.41 |
| 7 | SDSm | stochastische Diffusionssuche M | 0.93066 | 0.85445 | 0.39476 | 2.17988 | 0.99983 | 0.89244 | 0.19619 | 2.08846 | 0.72333 | 0.61100 | 0.10670 | 1.44103 | 5.709 | 63.44 |
| 8 | BOAm | Billard-Optimierungsalgorithmus M | 0.95757 | 0.82599 | 0.25235 | 2.03590 | 1.00000 | 0.90036 | 0.30502 | 2.20538 | 0.73538 | 0.52523 | 0.09563 | 1.35625 | 5.598 | 62.19 |
| 9 | AAm | Algorithmus für das Bogenschießen M | 0.91744 | 0.70876 | 0.42160 | 2.04780 | 0.92527 | 0.75802 | 0.35328 | 2.03657 | 0.67385 | 0.55200 | 0.23738 | 1.46323 | 5.548 | 61.64 |
| 10 | ESG | Entwicklung sozialer Gruppen (joo) | 0.99906 | 0.79654 | 0.35056 | 2.14616 | 1.00000 | 0.82863 | 0.13102 | 1.95965 | 0.82333 | 0.55300 | 0.04725 | 1.42358 | 5.529 | 61.44 |
| 11 | SIA | Simuliertes isotropes Glühen (Joo) | 0.95784 | 0.84264 | 0.41465 | 2.21513 | 0.98239 | 0.79586 | 0.20507 | 1.98332 | 0.68667 | 0.49300 | 0.09053 | 1.27020 | 5.469 | 60.76 |
| 12 | ACS | künstliche, kooperative Suche | 0.75547 | 0.74744 | 0.30407 | 1.80698 | 1.00000 | 0.88861 | 0.22413 | 2.11274 | 0.69077 | 0.48185 | 0.13322 | 1.30583 | 5.226 | 58.06 |
| 13 | DA | dialektischer Algorithmus | 0.86183 | 0.70033 | 0.33724 | 1.89940 | 0.98163 | 0.72772 | 0.28718 | 1.99653 | 0.70308 | 0.45292 | 0.16367 | 1.31967 | 5.216 | 57.95 |
| 14 | BHAm | Algorithmus für schwarze Löcher M | 0.75236 | 0.76675 | 0.34583 | 1.86493 | 0.93593 | 0.80152 | 0.27177 | 2.00923 | 0.65077 | 0.51646 | 0.15472 | 1.32195 | 5.196 | 57.73 |
| 15 | ASO | Anarchische Gesellschaftsoptimierung | 0,84872 | 0,74646 | 0,31465 | 1,90983 | 0,96148 | 0,79150 | 0,23803 | 1,99101 | 0,57077 | 0,54062 | 0,16614 | 1,27752 | 5.178 | 57,54 |
| 16 | RFO | Optimierung des Royal Flush (joo) | 0.83361 | 0.73742 | 0.34629 | 1.91733 | 0.89424 | 0.73824 | 0.24098 | 1.87346 | 0.63154 | 0.50292 | 0.16421 | 1.29867 | 5.089 | 56.55 |
| 17 | AOSm | Suche nach atomaren Orbitalen M | 0.80232 | 0.70449 | 0.31021 | 1.81702 | 0.85660 | 0.69451 | 0.21996 | 1.77107 | 0.74615 | 0.52862 | 0.14358 | 1.41835 | 5.006 | 55.63 |
| 18 | TSEA | Schildkrötenpanzer-Evolutionsalgorithmus (joo) | 0.96798 | 0.64480 | 0.29672 | 1.90949 | 0.99449 | 0.61981 | 0.22708 | 1.84139 | 0.69077 | 0.42646 | 0.13598 | 1.25322 | 5.004 | 55.60 |
| 19 | DE | differentielle Evolution | 0.95044 | 0.61674 | 0.30308 | 1.87026 | 0.95317 | 0.78896 | 0.16652 | 1.90865 | 0.78667 | 0.36033 | 0.02953 | 1.17653 | 4.955 | 55.06 |
| 20 | SRA | Algorithmus für erfolgreiche Gastronomen (joo) | 0.96883 | 0.63455 | 0.29217 | 1.89555 | 0.94637 | 0.55506 | 0.19124 | 1.69267 | 0.74923 | 0.44031 | 0.12526 | 1.31480 | 4.903 | 54.48 |
| 21 | CRO | Optimierung chemischer Reaktionen | 0.94629 | 0.66112 | 0.29853 | 1.90593 | 0.87906 | 0.58422 | 0.21146 | 1.67473 | 0.75846 | 0.42646 | 0.12686 | 1.31178 | 4.892 | 54.36 |
| 22 | BIO | Optimierung der Blutvererbung (joo) | 0.81568 | 0.65336 | 0.30877 | 1.77781 | 0.89937 | 0.65319 | 0.21760 | 1.77016 | 0.67846 | 0.47631 | 0.13902 | 1.29378 | 4.842 | 53.80 |
| 23 | BSA | Vogelschwarm-Algorithmus | 0.89306 | 0.64900 | 0.26250 | 1.80455 | 0.92420 | 0.71121 | 0.24939 | 1.88479 | 0.69385 | 0.32615 | 0.10012 | 1.12012 | 4.809 | 53.44 |
| 24 | HS | Harmoniesuche | 0.86509 | 0.68782 | 0.32527 | 1.87818 | 0.99999 | 0.68002 | 0.09590 | 1.77592 | 0.62000 | 0.42267 | 0.05458 | 1.09725 | 4.751 | 52.79 |
| 25 | SSG | Setzen, Säen und Wachsen | 0.77839 | 0.64925 | 0.39543 | 1.82308 | 0.85973 | 0.62467 | 0.17429 | 1.65869 | 0.64667 | 0.44133 | 0.10598 | 1.19398 | 4.676 | 51.95 |
| 26 | BCOm | Optimierung mit der bakteriellen Chemotaxis M | 0.75953 | 0.62268 | 0.31483 | 1.69704 | 0.89378 | 0.61339 | 0.22542 | 1.73259 | 0.65385 | 0.42092 | 0.14435 | 1.21912 | 4.649 | 51.65 |
| 27 | ABO | Optimierung des afrikanischen Büffels | 0.83337 | 0.62247 | 0.29964 | 1.75548 | 0.92170 | 0.58618 | 0.19723 | 1.70511 | 0.61000 | 0.43154 | 0.13225 | 1.17378 | 4.634 | 51.49 |
| 28 | (PO)ES | (PO) Entwicklungsstrategien | 0.79025 | 0.62647 | 0.42935 | 1.84606 | 0.87616 | 0.60943 | 0.19591 | 1.68151 | 0.59000 | 0.37933 | 0.11322 | 1.08255 | 4.610 | 51.22 |
| 29 | TSm | Tabu-Suche M | 0.87795 | 0.61431 | 0.29104 | 1.78330 | 0.92885 | 0.51844 | 0.19054 | 1.63783 | 0.61077 | 0.38215 | 0.12157 | 1.11449 | 4.536 | 50.40 |
| 30 | BSO | Brainstorming-Optimierung | 0.93736 | 0.57616 | 0.29688 | 1.81041 | 0.93131 | 0.55866 | 0.23537 | 1.72534 | 0.55231 | 0.29077 | 0.11914 | 0.96222 | 4.498 | 49.98 |
| 31 | WOAm | Wal-Optimierungsalgorithmus M | 0.84521 | 0.56298 | 0.26263 | 1.67081 | 0.93100 | 0.52278 | 0.16365 | 1.61743 | 0.66308 | 0.41138 | 0.11357 | 1.18803 | 4.476 | 49.74 |
| 32 | AEFA | Algorithmus für künstliche elektrische Felder | 0.87700 | 0.61753 | 0.25235 | 1.74688 | 0.92729 | 0.72698 | 0.18064 | 1.83490 | 0.66615 | 0.11631 | 0.09508 | 0.87754 | 4.459 | 49.55 |
| 33 | AEO | Algorithmus zur Optimierung auf der Grundlage künstlicher Ökosysteme | 0.91380 | 0.46713 | 0.26470 | 1.64563 | 0.90223 | 0.43705 | 0.21400 | 1.55327 | 0.66154 | 0.30800 | 0.28563 | 1.25517 | 4.454 | 49.49 |
| 34 | ACOm | Ameisen-Kolonie-Optimierung M | 0.88190 | 0.66127 | 0.30377 | 1.84693 | 0.85873 | 0.58680 | 0.15051 | 1.59604 | 0.59667 | 0.37333 | 0.02472 | 0.99472 | 4.438 | 49.31 |
| 35 | BFO-GA | Optimierung der bakteriellen Futtersuche — ga | 0.89150 | 0.55111 | 0.31529 | 1.75790 | 0.96982 | 0.39612 | 0.06305 | 1.42899 | 0.72667 | 0.27500 | 0.03525 | 1.03692 | 4.224 | 46.93 |
| 36 | SOA | einfacher Optimierungsalgorithmus | 0.91520 | 0.46976 | 0.27089 | 1.65585 | 0.89675 | 0.37401 | 0.16984 | 1.44060 | 0.69538 | 0.28031 | 0.10852 | 1.08422 | 4.181 | 46.45 |
| 37 | ABHA | Algorithmus für künstliche Bienenstöcke | 0.84131 | 0.54227 | 0.26304 | 1.64663 | 0.87858 | 0.47779 | 0.17181 | 1.52818 | 0.50923 | 0.33877 | 0.10397 | 0.95197 | 4.127 | 45.85 |
| 38 | ACMO | Optimierung atmosphärischer Wolkenmodelle | 0.90321 | 0.48546 | 0.30403 | 1.69270 | 0.80268 | 0.37857 | 0.19178 | 1.37303 | 0.62308 | 0.24400 | 0.10795 | 0.97503 | 4.041 | 44.90 |
| 39 | ADAMm | adaptive Momentabschätzung M | 0.88635 | 0.44766 | 0.26613 | 1.60014 | 0.84497 | 0.38493 | 0.16889 | 1.39880 | 0.66154 | 0.27046 | 0.10594 | 1.03794 | 4.037 | 44.85 |
| 40 | CGO | Chaos Game Optimization | 0.57256 | 0.37158 | 0.32018 | 1.26432 | 0.61176 | 0.61931 | 0.62161 | 1.85267 | 0.37538 | 0.21923 | 0.19028 | 0.78490 | 3.902 | 43.35 |
| 41 | ATAm | Algorithmus für künstliche Stämme M | 0.71771 | 0.55304 | 0.25235 | 1.52310 | 0.82491 | 0.55904 | 0.20473 | 1.58867 | 0.44000 | 0.18615 | 0.09411 | 0.72026 | 3.832 | 42.58 |
| 42 | CROm | Korallenriff-Optimierung M | 0.78512 | 0.46032 | 0.25958 | 1.50502 | 0.86688 | 0.35297 | 0.16267 | 1.38252 | 0.63231 | 0.26738 | 0.10734 | 1.00703 | 3.895 | 43.27 |
| 43 | CFO | Schwerkraftoptimierung | 0.60961 | 0.54958 | 0.27831 | 1.43750 | 0.63418 | 0.46833 | 0.22541 | 1.32792 | 0.57231 | 0.23477 | 0.09586 | 0.90294 | 3.668 | 40.76 |
| 44 | ASHA | Algorithmus für künstliches Duschen | 0.89686 | 0.40433 | 0.25617 | 1.55737 | 0.80360 | 0.35526 | 0.19160 | 1.35046 | 0.47692 | 0.18123 | 0.09774 | 0.75589 | 3.664 | 40.71 |
| 45 | ASBO | Optimierung des adaptiven Sozialverhaltens | 0.76331 | 0.49253 | 0.32619 | 1.58202 | 0.79546 | 0.40035 | 0.26097 | 1.45677 | 0.26462 | 0.17169 | 0.18200 | 0.61831 | 3.657 | 40.63 |
| RW | Neuroboids Optimierungsalgorithmus 2(joo) | 0.48754 | 0.32159 | 0.25781 | 1.06694 | 0.37554 | 0.21944 | 0.15877 | 0.75375 | 0.27969 | 0.14917 | 0.09847 | 0.52734 | 2.348 | 26.09 | |
Zusammenfassung
Lebende Korallenriffe sind fein abgestimmte Systeme, die ständig ein Gleichgewicht zwischen Stabilität und Variabilität, zwischen der Erhaltung bewährter Überlebensstrategien und dem Experimentieren mit neuen Strategien aufrechterhalten. Ein modifizierter Mechanismus der Depredation, bei dem neue Lösungen in der Nähe der besten Lösungen entstehen, ahmt den natürlichen Prozess des ökologischen Erfolgs in Korallenriffen nach.
In der Natur tauchen nach dem Absterben einiger Kolonien nicht zufällige Arten in den frei gewordenen Bereichen des Riffs auf, sondern diejenigen, die sich am erfolgreichsten an die örtlichen Umweltbedingungen angepasst haben. Darüber hinaus ist die Überlebensrate neuer Kolonien in der Umgebung erfolgreicher bestehender Kolonien höher, was sich direkt im Algorithmus widerspiegelt, indem neue Lösungen in der Nähe von Elitelösungen erzeugt werden. Dies gewährleistet die ständige Erkundung vielversprechender Bereiche des Suchraums und sorgt für eine konstante Populationsgröße.
Durch die Implementierung eines inversen Potenzgesetzes (mit Exponent 10, wobei die Potenz = 0,1 ist) können Abweichungen von der besten Lösung erzeugt werden. Diese Verteilung konzentriert die meisten neuen Lösungen in der Nähe der besten mit seltenen signifikanten Abweichungen und bietet ein optimales Gleichgewicht zwischen lokaler Ausbeutung und globaler Erkundung.
Die Vergrößerung des Suchradius auf 70 % des machbaren Bereichs ermöglicht es dem Algorithmus, größere Bereiche des Lösungsraums zu erkunden.
Die Verwendung ausschließlich der besten Lösungen (Elite) als Grundlage für die Generierung neuer Lösungen beschleunigt die Konvergenz zu optimalen Bereichen und verbessert die Qualität der resultierenden Lösungen, während eine Vielzahl von Operatoren, die zentrale Aspekte der Korallenentwicklung simulieren – wie Broadcast Spawningen und Brooding, Larvenansiedlung sowie asexuelle Fortpflanzung –, bei der Entwicklung anderer populationsbasierter Optimierungsmethoden eingesetzt werden können.
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 CROm:
Vorteile:
- Interessante Idee.
- Vielversprechende Entwicklung.
- Stabile Ergebnisse.
Nachteile:
- Schwächere Ergebnisse bei diskreten Funktionen.
- Eine große Anzahl von externen Parametern.
Dem Artikel ist ein Archiv mit den aktuellen Versionen des 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 Versuche.
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 den Prüfstand |
| 5 | Utilities.mqh | Include | Bibliothek mit Hilfsfunktionen |
| 6 | CalculationTestResults.mqh | Include | Skript zur Berechnung der Ergebnisse in der Vergleichstabelle |
| 7 | Testing AOs.mq5 | Skript | Die einheitliche Testumgebung für alle Algorithmen zur Populationsoptimierung |
| 8 | Simple use of population optimization algorithms.mq5 | Skript | Ein einfaches Beispiel für die Verwendung von Algorithmen zur Populationsoptimierung ohne Visualisierung |
| 9 | Test_AO_CROm.mq5 | Skript | CROm-Testumgebung |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/17760
Warnung: Alle Rechte sind von MetaQuotes Ltd. vorbehalten. Kopieren oder Vervielfältigen untersagt.
Dieser Artikel wurde von einem Nutzer der Website verfasst und gibt dessen persönliche Meinung wieder. MetaQuotes Ltd übernimmt keine Verantwortung für die Richtigkeit der dargestellten Informationen oder für Folgen, die sich aus der Anwendung der beschriebenen Lösungen, Strategien oder Empfehlungen ergeben.
Von der Grundstufe bis zur Mittelstufe: Struktur (IV)
Neuronale Netze im Trading: Adaptive Erkennung von Marktanomalien (DADA)
Neuronale Netze im Trading: Adaptive Erkennung von Marktanomalien (Abschlussteil)
Von der Grundstufe bis zur Mittelstufe: Struktur (III)
- 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.