Backtracking-Suchalgorithmus (BSA)
10
0
Inhalt
Einführung
Im endlosen Labyrinth der Möglichkeiten, in dem jede Abzweigung entweder zum Triumph oder in eine Sackgasse führen kann, hinterlässt der kluge Reisende unsichtbare Spuren – etwas Vergängliches und doch Zuverlässigeres: die Erinnerung an die zurückgelegten Wege. Dieser Gedanke (in die Vergangenheit blicken, um die Zukunft zu sehen) bildet den Kern des Optimierungsalgorithmus. Jeder Schritt ins Unbekannte erfolgt unter Berücksichtigung vergangener Erfahrungen, wobei die Geschichte zum Kompass und die Erinnerung zur Landkarte wird.
In diesem Artikel werde ich mich mit einem Algorithmus befassen, den ich aufgrund seines Suchkonzepts sehr interessant fand. Der Backtracking-Suchalgorithmus (BSA) ist ein neuer evolutionärer Algorithmus (EA) zur Lösung realwertiger numerischer Optimierungsprobleme, der 2013 von Pinar Civicioglu vorgeschlagen wurde. Es handelt sich um eine Methode zur Ermittlung der besten Lösung, die „aus früheren Erfahrungen lernen“ kann.
Implementierung des Algorithmus
BSA basiert auf dem Prinzip evolutionärer Algorithmen, weist jedoch einzigartige Merkmale auf und nutzt zwei Populationen:- aktuelle Population (P) – eine sich aktiv entwickelnde Population
- historische Population (oldP) – eine zufällig ausgewählte Population aus früheren Generationen
BSA nutzt eine Strategie mit zufälligen Mutationen, die für jedes Individuum nur eine gerichtete Lösung erzeugt. Mutationsformel:
Mutant = P + F × (oldP - P)
wobei F der Amplitudenfaktor ist, der die Schrittweite der Suche bestimmt.
Der BSA-Crossover-Prozess umfasst zwei Schritte. Der erste Schritt nutzt „mixrate“. Beim zweiten Schritt darf in jedem Testvektor nur eine zufällig ausgewählte Koordinate verändert werden. Stellen Sie sich vor, Sie und Ihre Freunde (das ist unsere Population) sind auf der Suche nach der besten Pizzeria der Stadt.
Ausgangssituation:
- Sie haben 10 Freunde (Populationsgröße),
- Jeder beginnt, in einem beliebigen Stadtteil zu suchen,
- Jeder hat ein Smartphone mit einer Karte seiner vergangenen Reisen (historisches Gedächtnis).
Tag 1: Alle gingen in die Stadt. Der erste Freund fand eine Pizzeria mit einer Bewertung von 7/10, der zweite Freund fand eine Pizzeria mit einer Bewertung von 5/10, der dritte entdeckte eine Pizzeria mit einer Bewertung von 8/10 … und so weiter.
Tag 2: Nutzung der gesammelten Erfahrungen.
Schritt 1: „Erinnerungen an die Vergangenheit“ (Selection-I). Algorithmus: „Lass uns eine Münze werfen!“ Wenn die Münze auf Kopf fällt, dann „Erinnere dich daran, wo jeder gestern war“ (Historie aktualisieren); wenn sie auf Zahl fällt, „Verwende alte Erinnerungen“ (nicht aktualisieren), dann „Mische die Erinnerungen“ (wie ein Kartenspiel).
Schritt 2: „Folge der Spur“ (Mutation). Jeder Freund denkt: „Wo bin ich gerade? (aktuelle Position) und wo war ich zuvor? (frühere Position).“ Dann lautet die Bewegungsformel: Neue Position = Aktuelle Position + Zufallswert × (Alte Position – Aktuelle Position). Beispiel: Der erste Freund befindet sich jetzt in der Straße A, Nr. 10, sein „Geist aus der Vergangenheit“ war in der Straße B, Nr. 20, Zufallsschritt = 2. Neue Position = A.,10 + 2 × (B.,20 - A.,10) = Bewegung in Richtung B-Straße, aber doppelt so weit!
„Kurskorrektur“ (Crossover). Der Algorithmus wirft eine Münze und wählt eine Strategie aus. Strategie A: „Teilweise Änderung“. Der erste Freund wollte zu einer bestimmten Adresse gehen, aber der Algorithmus sagt: „Ändere nur die Straße, lass das Haus so, wie es war.“ Ergebnis: Okay, wir ändern die Straße, behalten aber das Haus. Strategie B: „Minimale Änderung“. Der erste Freund wollte zu einer bestimmten Adresse gehen, aber der Algorithmus sagt: „Bleib am alten Ort, aber ändere nur die Hausnummer.“ Ergebnis: Okay, wir ändern die Hausnummer.
„Gesamtergebnis prüfen“ (Selection-II). Freund 1 ist an einen neuen Ort gezogen:
- Wenn die neue Pizzeria besser ist (Bewertung 9/10): „Super, ich bleibe hier!“
- Ist sie schlechter (Bewertung 4/10): „Nein, ich komme zurück!“
Die folgende Abbildung veranschaulicht die Funktionsweise des Algorithmus.
Abb. 1. Phasen des BSA-Algorithmus
Diese Abbildung zeigt, wie der BSA-Algorithmus in einem zweidimensionalen Raum nach einer optimalen Lösung sucht. Stellen Sie sich vor, Sie betrachten eine topografische Karte von oben, wobei es darum geht, den höchsten Punkt (rot in der Mitte) zu finden.
Die Abbildung ist in drei Felder unterteilt, die die Historie der Suche zeigen: Iteration 1 – Initialisierung mit Zufallswerten. Das quadratische Suchfeld mit Konturlinien (wie auf einer topografischen Karte) weist in der Mitte einen roten Punkt auf, der das globale Optimum (die beste Lösung) darstellt, und vier blaue Punkte (P1, P2, P3, P4) sind die anfänglichen Zufallspositionen der „Suchagenten“. Der Algorithmus platziert vier Agenten zufällig im gesamten Suchraum. Zu diesem Zeitpunkt gilt oldP = P (die historische Population entspricht der aktuellen), und dies ist der Ausgangspunkt der Suche.
Iteration 2 – Mutationsschritt. Blaue Punkte stellen die aktuellen Positionen der Agenten dar, grüne, durchsichtige Punkte sind Positionen aus dem historischen Speicher (gemischt), rote Pfeile zeigen die Entwicklung des Suchprozesses während der Mutation an.
Schlüsselelemente: Die roten Pfeile veranschaulichen die Funktionsweise der Mutationsformel: M = P + F × (oldP - P). Jeder Agent bewegt sich im Verhältnis zu seinem „historischen Gegenstück“. Manche Pfeile zeigen auf historische Positionen, andere weg von ihnen (abhängig vom F-Zeichen). Formel im roten Kasten: F = 3 × randn(); M = P + F × (oldP - P). Dies ist die Schlüsselformel für die BSA-Mutation.
Iteration 3 – nach Crossover und Selektion. Lila Punkte kennzeichnen neue Positionen nach dem Crossover (Versuchspopulation), durchscheinende blaue Punkte zeigen frühere Positionen (zum Vergleich), und grüne Pfeile markieren ausschließlich Verbesserungen (d. h. Fälle, in denen die neue Position besser ist als die alte). Crossover: Der Algorithmus kombinierte Informationen aus der mutierten und der aktuellen Population. Bei der Greedy-Selektion wurden nur jene Änderungen beibehalten, die die Lösung verbesserten. Die Population hat sich dem Optimum angenähert (roter Mittelpunkt).
Zusammenfassung des BSA-Prozesses: Der gesamte Algorithmuszyklus als Abfolge farbiger Kreise:- Init (blau) – zufälliger Start
- Select-I (grün) – Speicheraktualisierung mit einer Wahrscheinlichkeit von 50 %
- Mutieren (rot) – Anwendung der Mutationsformel
- Crossover (lila) – Kombination verschiedener Lösungen
- Bewerten (orange) – Fitnessberechnung
- Select-II (türkis) – eine Greedy-Selektion der Besten
Der gepunktete Pfeil zeigt an, dass der Vorgang so lange wiederholt wird, bis eine Konvergenz erreicht ist. Dieses Bild verdeutlicht, warum BSA so effektiv ist: Es „merkt“ sich, wo es bereits gewesen ist, und nutzt diese Informationen, um intelligenter zu suchen als bei einem einfachen Zufallsspaziergang.
Nun können wir uns dem BSA-Pseudocode zuwenden.
Arbeitsvorbereitung
Ausgangsparameter:
- Populationsgröße festlegen
- Crossover-Parameter mixrate festlegen
- Erstelle leere Container für:
- aktuelle Population
- historische Population
- mutierte Population
- Versuchspopulation
- Crossover-Karten für jedes Individuum
Initialisierung:
- Ordne alle Individuen der historischen Population zufällig im Suchraum an
- Berücksichtige die Diskretisierung, wenn der Schritt angegeben ist
- Setze das Flag für „selection required“ auf „Nein“
Die Hauptschleife des Algorithmus
SCHRITT 1: Erster Start
Wenn dies die erste Iteration ist:
- Verteile die aktuelle Population zufällig
- Koordinaten diskretisieren
- Markiere, dass die Initialisierung abgeschlossen ist
- Beende den Schritt und warte auf die Berechnung der Fitness
SCHRITT 2: Greedy-Selektion (falls erforderlich)
Wenn das Flag „selection required“ gesetzt ist:
- Vergleiche für jeden Agenten:
- Wenn die neue Lösung schlechter ist als die gespeicherte, geben wir die alten Koordinaten und die Fitness zurück
- Wenn es besser ist, behalten wir das neue.
- Flag der Selektion zurücksetzen
SCHRITT 3: Den aktuellen Zustand speichern
Für jeden einzelnen Agenten:
- Aktuellen Fitnesswert speichern
- Speichern Sie die Kopie der aktuellen Koordinaten
SCHRITT 4: Das historische Gedächtnis aktualisieren (Selection-I)
- Wirf eine Münze (50 % Wahrscheinlichkeit)
- Wenn die Münze auf Kopf fällt:
- Die gesamte aktuelle Population in den historischen Speicher kopieren
- Fitness sichern
- Mische die historische Population wie ein Kartenspiel:
- Gehe von dem letzten Agenten zum ersten
- Wähle für jedes Element eine zufällige Position für den Austausch aus
- Vertausche
SCHRITT 5: Mutation
- Erzeuge einen Bewegungsfaktor F aus einer Normalverteilung
- Durchschnitt = 0, Bereich von -3 bis +3
- Wie der Wurf eines Würfels, aber mit einer Glockenkurve
- Für jeden Agenten und jede Koordinate:
- Neue Position = Aktuell + F × (Historisch – Aktuell)
- Wenn F positiv ist → Bewegung zur historischen Position
- Wenn F negativ ist → Bewegung weg von der historischen Position
SCHRITT 6: Crossover
- Kopiere die mutierte Population in die Versuchspopulation
- Wirf eine gewichtete Münze (40 % / 60 %)
Wenn der 40-%-Zweig ausgewählt wird (Strategie 1):
Für jedes Individuum:
- Bestimme, wie viele Koordinaten geändert werden sollen (von 0 bis alle, unter Verwendung von mixrate)
- Wähle die Koordinaten zufällig aus
- Nimm für die ausgewählten Koordinaten Werte aus der aktuellen Population
- Übernimm alle übrigen Koordinaten der Mutanten
Wenn das Ergebnis 60 % beträgt (Strategie 2):
Für jeden einzelnen Agenten:
- Wähle nur eine zufällige Koordinate aus
- Ersetze sie durch den Wert aus der aktuellen Population
- Alle übrigen Koordinaten bleiben unverändert aus der mutierten Population.
SCHRITT 7: Kontrolle der Begrenzung
Für jeden einzelnen Agenten der Versuchspopulation:
- Überprüfe jede Koordinate
- Wenn die Grenzen überschritten werden:
- Wirf eine Münze (50:50)
- Bei „Kopf“ → generiere einen neuen Zufallswert innerhalb der Grenzen
- Bei „Zahl“ → platziere an der nächstgelegenen Grenze
- Diskretisierung anwenden, wenn der Schritt angegeben ist
SCHRITT 8: Bereite die Bewertung vor
- Kopiere die Versuchspopulation zur Auswertung in die Hauptpopulation
- Setze das Flag „selection required“ auf „Ja“
- Die Kontrolle an die Fitnessberechnung übergeben
Nach der Berechnung der Fitness
- Finde den Agenten mit der besten Fitness
- Wenn ein besserer Wert als der bisher globale Bestwert gefunden wird:
- aktualisiere den globalen Bestwert
- die Koordinaten der besten Lösung speichern
Wiederholung
Kehre zu SCHRITT 2 zurück und fahre fort, bis:
- Konvergenz erreicht ist
- oder die Iterationsgrenze überschritten wird
Nachdem wir nun die wichtigsten Punkte verstanden haben, fangen wir damit an, den Algorithmus zu programmieren. Die Klasse C_AO_BSA_Backtracking wird eine Implementierung des BSA-Backtracking-Algorithmus zur Lösung von Optimierungsproblemen darstellen. Sie wird die Basisklasse C_AO erben, die eine gemeinsame Schnittstelle für Optimierungsalgorithmen definiert.
Hauptmerkmale und Zweck:
Optimierungsparameter:- popSize – die Populationsgröße, also die Anzahl der „Agenten“ oder „Lösungen“, die der Algorithmus gleichzeitig berücksichtigt.
- mixrate – ein Crossover-Parameter, der den Grad der „Vermischung“ von Informationen zwischen Agenten bei der Erzeugung neuer Lösungen steuert.
- Der Klassenkonstruktor initialisiert die Basisparameter und fügt „popSize“ und „mixrate“ dem Array „params“ hinzu, das zur Steuerung der Algorithmusparameter dient.
- Mit der Methode „SetParams“ können Sie die internen Parameter des Algorithmus anhand der Werte aus dem Array „params“ aktualisieren. Außerdem umfasst es grundlegende Prüfungen der Gültigkeit der Werte.
- Init – für die Ersteinrichtung des Algorithmus, einschließlich der Festlegung der Variablenbereiche (Mindest-, Höchstwerte und Schrittweiten) sowie der Anzahl der Optimierungsiterationen.
- Moving – bezeichnet die Hauptiteration des Algorithmus, die dafür zuständig ist, auf der Grundlage der aktuellen Population neue „Kandidaten“ oder „Moving“-Lösungen zu generieren.
- Revision – bewertet die generierten Lösungen und aktualisiert das aktuell beste Ergebnis.
- oldP – ein Array, das die „historische“ oder frühere Population von Agenten darstellt.
- M – ein Array für die durch die Mutation entstandene Population.
- T – ein Array für die Versuchspopulation, das vor dem Treffen von Entscheidungen zum Vergleich mit der aktuellen Population herangezogen wird.
- F – Amplitudenfaktor für Mutationen, der das Ausmaß der Veränderung bei einer Mutation beeinflusst.
- needSelection – Flag, das angibt, dass die zweite Stufe der Selektion durchgeführt werden muss.
- prevFitness – Array zur Speicherung der Fitnesswerte der Agenten aus der vorherigen Iteration.
- S_Map – Hilfsstruktur, die eine binäre Maske enthält und während des Crossover-Prozesses verwendet wird, um zu bestimmen, welche Variablen der Agenten aus verschiedenen Elternteilen „gemischt“ werden.
- map – ein Array dieser binären Masken, eine für jeden Agenten.
- SelectionI – die erste Phase der Selektion, in der die Agenten für die Entwicklung neuer Lösungen bestimmt werden.
- Mutation – Wende die Mutationsoperation auf die ausgewählten Agenten an.
- Crossover – Führe einen Crossover-Vorgang (Kombination) zwischen Agenten durch, um neue „Test“-Lösungen zu erstellen.
- BoundaryControl – Überprüft, ob die Werte der Agentenparameter innerhalb der festgelegten Grenzen (Mindest- und Höchstwerte) bleiben.
- ShufflePopulation – Methode zum zufälligen Mischen einer Population.
Somit implementiert die Klasse C_AO_BSA_Backtracking einen evolutionären Optimierungsalgorithmus, der die Konzepte Population, Mutation und Crossover sowie BSA-spezifische Mechanismen wie Backtracking nutzt, um Optimierungsprobleme zu lösen.
//———————————————————————————————————————————————————————————————————— class C_AO_BSA_Backtracking : public C_AO { public: //---------------------------------------------------------- ~C_AO_BSA_Backtracking () { } C_AO_BSA_Backtracking () { ao_name = "BSA"; ao_desc = "Backtracking Search Algorithm"; ao_link = "https://www.mql5.com/en/articles/18568"; popSize = 10; // population size mixrate = 1.0; // crossover parameter ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "mixrate"; params [1].val = mixrate; } void SetParams () { popSize = (int)params [0].val; mixrate = params [1].val; // Check the parameters validity //if (popSize < 2) popSize = 2; if (mixrate < 0.0) mixrate = 0.0; if (mixrate > 1.0) mixrate = 1.0; } bool Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0); // number of epochs void Moving (); void Revision (); //------------------------------------------------------------------ double mixrate; // crossover parameter private: //--------------------------------------------------------- S_AO_Agent oldP []; // historical population S_AO_Agent M []; // mutant population (Mutant) S_AO_Agent T []; // trial population (Trial) double F; // amplitude factor for mutation bool needSelection; // flag for the necessity of executing Selection-II double prevFitness []; // array for storing previous fitness // Auxiliary structures for crossover struct S_Map { int val []; // binary map for crossover void Init (int size) { ArrayResize (val, size); ArrayInitialize (val, 0); } }; S_Map map []; // array of binary maps for each agent // Algorithm methods void SelectionI (); void Mutation (); void Crossover (); void BoundaryControl (S_AO_Agent &agent); void ShufflePopulation (S_AO_Agent &pop []); }; //————————————————————————————————————————————————————————————————————
Die Methode „Init“ ist dafür zuständig, den Algorithmus vor Beginn der Optimierung für den Betrieb vorzubereiten. Zunächst wird die grundlegende Initialisierungsfunktion aufgerufen, die die grundlegenden Parameter für die Wertebereiche der Variablen festlegt (Mindest- und Höchstwerte sowie Schrittweite). Wenn dieser grundlegende Schritt fehlschlägt, bricht die Methode ab und gibt einen Fehler zurück.
Anschließend werden die für den BSA-Algorithmus spezifischen internen Datenstrukturen zugewiesen und vorbereitet. Insbesondere werden Populations-Arrays erstellt und auf die erforderliche Größe gebracht: die historische Population oldP, die mutierte Population M, die Versuchspopulation T sowie ein Array mit binären Masken für den Crossover „map“ und das Array prevFitness zur Speicherung der vorherigen Fitnesswerte jedes Agenten. Das Flag für die Notwendigkeit einer zusätzlichen Selektion ist zunächst auf „false“ gesetzt.
Anschließend werden für jeden Agenten in der Population Initialisierungsmethoden aufgerufen, die die internen Strukturen der einzelnen Agenten entsprechend der Anzahl der Aufgabenparameter vorbereiten.
Anschließend wird die historische Population mit Anfangswerten gefüllt. Für jeden Agenten und jeden Parameter in seiner Menge wird ein Zufallswert innerhalb eines vorgegebenen Bereichs generiert; anschließend wird dieser Wert entsprechend einer vorgegebenen Änderungsschrittweite angepasst. Wenn alle diese Schritte erfolgreich abgeschlossen wurden, gibt die Methode einen Wert zurück, der anzeigt, dass das Algorithmusobjekt erfolgreich initialisiert wurde und für die weitere Optimierung bereit ist.
//———————————————————————————————————————————————————————————————————— //--- Initialization bool C_AO_BSA_Backtracking::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Initialize additional BSA structures ArrayResize (oldP, popSize); ArrayResize (M, popSize); ArrayResize (T, popSize); ArrayResize (map, popSize); ArrayResize (prevFitness, popSize); needSelection = false; for (int i = 0; i < popSize; i++) { oldP [i].Init (coords); M [i].Init (coords); T [i].Init (coords); map [i].Init (coords); } // Initialize oldP historical population for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { oldP [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); oldP [p].c [c] = u.SeInDiSp (oldP [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } return true; } //————————————————————————————————————————————————————————————————————
Die Moving-Methode beschreibt den Hauptschritt des BSA-Optimierungsalgorithmus und ist für die Erzeugung neuer Lösungskandidaten in der Population verantwortlich. Beim ersten Aufruf der Methode, wenn das Flag „revision“ auf „false“ gesetzt ist, wird die aktive Population „a“ zunächst initialisiert. Für jeden Agenten in der Population und für jeden seiner Parameter wird ein Zufallswert innerhalb eines vorgegebenen Bereichs (Minimum und Maximum) generiert. Dieser Zufallswert wird dann entsprechend der festgelegten Schrittweite angepasst. Nach der Initialisierung wird das Flag „revision“ auf „true“ gesetzt (damit dieser Block bei nachfolgenden Aufrufen nicht ausgeführt wird), und das Flag „needSelection“ wird zurückgesetzt. Die Methode wird beendet.
Durchführung der Greedy-Selektion (Selection-II) (wird bei Bedarf durchgeführt): Wenn needSelection den Wert „true“ hat, bedeutet dies, dass im vorherigen Schritt eine neue Population generiert wurde und nun deren Fitness mit der Fitness der vorherigen Lösungen verglichen werden muss. Die Iteration wird für jeden Agenten in der Population durchgeführt. Der aktuelle Fitnesswert des Agenten „a[i].f“ (der für die „Versuchs“-Lösung berechnet wurde) wird mit seiner im Schritt zuvor ermittelten Fitness, die in prevFitness[i] gespeichert ist, verglichen. Wenn sich die „Test“-Lösung a [i] als schlechter als die vorherige erwiesen hat, werden die Koordinatenwerte des aktuellen Agenten „a [i].c“ aus „a [i].cP“ (den Koordinaten des Agenten im vorherigen Schritt) wiederhergestellt, und seine „a [i].f“-Fitness wird ebenfalls auf prevFitness [i] zurückgesetzt. Dadurch wird sichergestellt, dass sich der Zustand der Population nicht verschlechtert. Nachdem die Selektion abgeschlossen ist, wird das Flag „needSelection“ zurückgesetzt.
Grundlegende Schritte des BSA-Algorithmus (nach der Initialisierung oder Selektion): Vor der Erzeugung neuer Lösungen werden die aktuellen Fitnesswerte aller Agenten aus „a“ in prevFitness für die spätere Verwendung in Selection-II gespeichert und die aktuellen Koordinaten der Agenten aus „a [i].c“ werden in „a [i].cP“ kopiert, um ein Zurücksetzen zu ermöglichen, falls sich die neuen Lösungen als schlechter erweisen sollten.
Die interne Methode „SelectionI“ wird aufgerufen. Dieser Schritt dient der Selektion oder Vorbereitung der Operation „archive“ oldP, die für die Mutation verwendet wird. Die interne Methode „Mutation“ wird aufgerufen. In diesem Schritt wird auf der Grundlage der aktiven und/oder archivierten Populationen eine „mutierte“ Population M erzeugt. Die interne Methode „Crossover“ wird aufgerufen. In diesem Schritt wird die M-mutierte Population mit der derzeit aktiven „a“-Population vermischt, wodurch eine „Test“-Population T entsteht.
Die Koordinaten der Agenten aus der generierten T-Versuchspopulation werden in die aktive „a“-Population kopiert. Nun enthält „a“ neue „Test“-Lösungen, deren Fitness berechnet werden muss. Das Flag „needSelection“ ist auf „true“ gesetzt. Dies bedeutet, dass beim nächsten Aufruf von „Moving“ (nachdem die Fitness der neuen Lösungen in „a“ berechnet wurde) eine Greedy-Selektion (Selection-II) durchgeführt werden sollte.
Die Methode Moving umfasst somit eine vollständige Iteration oder „Epoche“ des BSA-Algorithmus, einschließlich Initialisierung, Selektion, Mutation, Crossover und Vorbereitung für den Ergebnisvergleich.
//———————————————————————————————————————————————————————————————————— //--- The main step of the algorithm void C_AO_BSA_Backtracking::Moving () { // Initial population setup if (!revision) { for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { a [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; needSelection = false; return; } // If you want to perform greedy selection after calculating fitness if (needSelection) { // Selection-II: Greedy selection for (int i = 0; i < popSize; i++) { // If the current solution (from T) is worse than the previous one, return the previous one if (a [i].f < prevFitness [i]) { ArrayCopy (a [i].c, a [i].cP, 0, 0, WHOLE_ARRAY); a [i].f = prevFitness [i]; } } needSelection = false; } //--- BSA basic steps: // Save current fitness before generating a new population for (int i = 0; i < popSize; i++) { prevFitness [i] = a [i].f; ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY); } // 1. Selection-I SelectionI (); // 2. Mutation Mutation (); // 3. Crossover Crossover (); // 4. Copy the trial population T into the 'a' main population to calculate fitness for (int i = 0; i < popSize; i++) { ArrayCopy (a [i].c, T [i].c, 0, 0, WHOLE_ARRAY); } // Set the flag to execute Selection-II after calculating fitness needSelection = true; } //————————————————————————————————————————————————————————————————————
Die Methode „SelectionI“ implementiert die erste Selektionsstufe des BSA-Algorithmus und ist für die Selektion der historischen Population zuständig, die anschließend für die Mutation verwendet wird.
Probabilistische Aktualisierung der historischen Population: Mit einer Wahrscheinlichkeit von 50 % (oder, einfacher ausgedrückt, mit gleicher Wahrscheinlichkeit) wird die historische Population „oldP“ durch die aktuelle Population „a“ aktualisiert. Wird eine Zufallszahl generiert, die kleiner als ein vorgegebener Schwellenwert (0,5) ist, werden der Inhalt („c“, Koordinaten) jedes Agenten aus der aktuellen Population „a“ auf den entsprechenden Agenten in der historischen Population „oldP“ kopiert, und auch die Fitness „f“ des Agenten wird kopiert.
Historische Populationsdaten mischen: Unabhängig davon, ob die historische Population im vorherigen Schritt aktualisiert wurde oder nicht, wird die Methode ShufflePopulation(oldP) aufgerufen, um die Agenten in der historischen Population neu zu mischen. Dies geschieht, um Zufälligkeit in die Mutation einzubringen. Durch das Mischen wird sichergestellt, dass die Agenten in der historischen Population in zufälliger Reihenfolge ausgewählt werden und nicht in der Reihenfolge, in der sie ursprünglich angeordnet waren.
Somit aktualisiert „SelectionI“ entweder die historische Population mit aktuellen Lösungsvorschlägen oder behält ihren vorherigen Zustand bei; in beiden Fällen werden anschließend die Agenten in der historischen Population neu gemischt, was eine Diversifizierung der Suche während der anschließenden Mutation ermöglicht.
//———————————————————————————————————————————————————————————————————— //--- Selection-I: select a historical population void C_AO_BSA_Backtracking::SelectionI () { // Update the historical population with a 50% probability if (u.RNDprobab () < 0.5) // equivalent to if (a < b) where a,b ~ U(0,1) { // Copy the current population to the historical one for (int i = 0; i < popSize; i++) { ArrayCopy (oldP [i].c, a [i].c, 0, 0, WHOLE_ARRAY); oldP [i].f = a [i].f; } } // Shuffle the historical population ShufflePopulation (oldP); } //————————————————————————————————————————————————————————————————————
Die Methode „ShufflePopulation“ dient dazu, Elemente in einer gegebenen Population von Agenten (dargestellt durch die Struktur „S_AO_Agent“) zufällig zu mischen. Die Funktion nimmt ein Array von pop[]-Agenten als Eingabe entgegen und führt eine In-Place-Mischung durch, d. h., sie ändert die Reihenfolge der Elemente direkt im übergebenen Array.
Mischalgorithmus: Die Methode nutzt den Fisher-Yates-Shuffle-Algorithmus, um Elemente in einer Population zufällig zu mischen; der Algorithmus stellt sicher, dass jede Permutation (Reihenfolge) der Elemente die gleiche Wahrscheinlichkeit aufweist.
Die „for“-Schleife beginnt beim letzten Element des Arrays (popSize - 1) und läuft in umgekehrter Reihenfolge bis zum zweiten Element (Index 1). Das erste Element (Index 0) muss nicht gemischt werden, da es zu diesem Zeitpunkt im Ablauf des Algorithmus bereits „verschoben“ worden ist. Für jedes Element mit dem Index i wird ein zufälliger Index j im Bereich von 0 bis einschließlich i ausgewählt. Dies geschieht mithilfe der Funktion u.RNDminusOne(i+1), die eine zufällige Ganzzahl im angegebenen Bereich zurückgibt (einschließlich „0“ und ohne „i+1“).
Elemente mit den Indizes i und j werden vertauscht. Zu diesem Zweck wird die temporäre Variable „temp“ vom Typ S_AO_Agent verwendet. Da S_AO_Agent das Array „c“ (Koordinaten) enthält, wird das Array kopiert. Der f-Fitness-Wert wird ebenfalls kopiert. Die Koordinaten- und Fitnesswerte des Elements pop[i] werden in der temporären Variablen temp gespeichert, und die Koordinaten- und Fitnesswerte des Elements pop[j] werden in pop[i] kopiert. Die in „temp“ gespeicherten Werte (die ursprünglichen Werte von pop[i]) werden in pop[j] kopiert. Daher ist die Reihenfolge der Elemente im Array pop[] nach Abschluss der Schleife zufällig.
//———————————————————————————————————————————————————————————————————— //--- Shuffle population void C_AO_BSA_Backtracking::ShufflePopulation (S_AO_Agent &pop []) { for (int i = popSize - 1; i > 0; i--) { int j = u.RNDminusOne (i + 1); // Swap i and j elements S_AO_Agent temp; temp.Init (coords); ArrayCopy (temp.c, pop [i].c, 0, 0, WHOLE_ARRAY); temp.f = pop [i].f; ArrayCopy (pop [i].c, pop [j].c, 0, 0, WHOLE_ARRAY); pop [i].f = pop [j].f; ArrayCopy (pop [j].c, temp.c, 0, 0, WHOLE_ARRAY); pop [j].f = temp.f; } } //————————————————————————————————————————————————————————————————————
Die Mutationsmethode ist für die Erzeugung der mutierten Population zuständig, was einen entscheidenden Schritt im BSA-Algorithmus darstellt. Sie basiert auf der Differenz zwischen der aktuellen und der historischen Population.
Zunächst wird ein zufälliger Amplitudenfaktor F generiert, der den Einfluss der historischen Population auf die aktuelle Population bestimmt. Anschließend wird für jeden Agenten in der Population und für jede Koordinate innerhalb dieses Agenten ein neuer Wert für die Koordinate in der mutierten Population berechnet. Dies geschieht, indem man zur aktuellen Koordinate das Produkt aus dem F-Amplitudenfaktor und der Differenz zwischen der entsprechenden Koordinate in der historischen Population und der aktuellen Koordinate addiert. So entsteht eine mutierte Population, indem die aktuelle Population in die durch die historische Population vorgegebene Richtung verschoben wird, wobei die Amplitude vom F-Faktor abhängt.
//———————————————————————————————————————————————————————————————————— //--- Mutation: generation of a mutant population void C_AO_BSA_Backtracking::Mutation () { // Generate the amplitude factor F = u.GaussDistribution (0.0, -3.0, 3.0, 2); // Apply mutation: M = P + F * (oldP - P) for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { M [i].c [j] = a [i].c [j] + F * (oldP [i].c [j] - a [i].c [j]); } } } //————————————————————————————————————————————————————————————————————
Die Crossover-Methode dient dazu, auf der Grundlage der aktuellen mutierten Population unter Verwendung der gewählten Crossover-Strategie eine Versuchspopulation zu bilden. Dieser Prozess zielt darauf ab, die Eigenschaften bestehender Lösungen zu kombinieren, um optimalere Optionen zu finden.
Zunächst wird eine Versuchspopulation aus der mutierten Population kopiert, um eine Grundlage für weitere Modifikationen zu schaffen. Dann muss eine Entscheidung über die Kreuzungsstrategie getroffen werden: Mit einer Wahrscheinlichkeit von 40 % wird die erste Strategie gewählt, andernfalls die zweite.
Wird die erste Option gewählt, wird die Strategie „mixrate“ umgesetzt. In diesem Fall wird für jeden Agenten die Anzahl der Elemente (innerhalb der Koordinaten) bestimmt, die vom aktuellen Agenten übernommen werden, wobei der angegebene Koeffizient „mixrate“ berücksichtigt wird. Diese Elemente werden nach dem Zufallsprinzip ausgewählt, ohne Wiederholungen. Anschließend werden die entsprechenden Koordinaten aus der aktuellen Lösung von den ausgewählten Indizes in den Agenten der Versuchspopulation kopiert.
Wird die zweite Strategie gewählt, wird für jeden Agenten ein Zufallselement (Koordinate) ausgewählt, und in der Versuchspopulation wird dieses Element an der entsprechenden Position durch seinen Wert aus der aktuellen Lösung ersetzt.
Nach Abschluss des Crossover-Schritts wird für jeden Agenten in der Versuchspopulation eine Bereichsprüfung durchgeführt, um sicherzustellen, dass alle Entscheidungen gültig sind und die Bereichsanforderungen erfüllen.
//———————————————————————————————————————————————————————————————————— //--- Crossover: trial population generation void C_AO_BSA_Backtracking::Crossover () { // Initialize the trial population as a copy of the mutant one for (int i = 0; i < popSize; i++) { ArrayCopy (T [i].c, M [i].c, 0, 0, WHOLE_ARRAY); } // Select a crossover strategy if (u.RNDprobab () < 0.4) { //--- STRATEGY 1: Using mixrate for (int i = 0; i < popSize; i++) { // Reset the map ArrayInitialize (map [i].val, 0); // Define the number of elements for the crossover int numElements = (int)MathCeil (mixrate * u.RNDprobab () * coords); // Generate unique indices for the crossover for (int n = 0; n < numElements; n++) { int idx; do { idx = u.RNDminusOne (coords); } while (map [i].val [idx] == 1); // until we find an unused index map [i].val [idx] = 1; } // Apply crossover for (int j = 0; j < coords; j++) { if (map [i].val [j] == 1) { T [i].c [j] = a [i].c [j]; } } } } else { //--- STRATEGY 2: Mutation of only one element for (int i = 0; i < popSize; i++) { // Select one random element int randomIndex = u.RNDminusOne (coords); T [i].c [randomIndex] = a [i].c [randomIndex]; } } // Boundary control for all agents in the trial population for (int i = 0; i < popSize; i++) { BoundaryControl (T [i]); } } //————————————————————————————————————————————————————————————————————
Die Methode „BoundaryControl“ dient dazu, die Parameterwerte des Agenten zu überprüfen und anzupassen, um sicherzustellen, dass sie innerhalb akzeptabler Grenzen bleiben, sowie die Entscheidungen in das gewünschte diskrete Format zu konvertieren.
Für jede Komponente der Koordinaten des Agenten wird eine Überprüfung durchgeführt: Liegt der Wert außerhalb der festgelegten Mindest- oder Höchstgrenzen, wird dieser Wert gemäß der gewählten Strategie verarbeitet. Wird die Wahrscheinlichkeit zufällig auf einen Wert unter 50 % festgelegt, erfolgt eine zufällige Neuberechnung eines Wertes innerhalb des zulässigen Bereichs. Andernfalls wird der Wert auf den nächstgelegenen Grenzwert gesetzt – entweder auf das Minimum oder das Maximum.
Anschließend wird jeder Koordinatenwert diskretisiert – das heißt, er wird in den nächstgelegenen zulässigen Wert umgewandelt, der dem festgelegten Bereich und der Diskretisierungsschrittweite entspricht. Dadurch wird sichergestellt, dass die Lösung die Anforderungen an Datentyp und Wertebereich erfüllt.
//———————————————————————————————————————————————————————————————————— //--- Boundary control void C_AO_BSA_Backtracking::BoundaryControl (S_AO_Agent &agent) { for (int j = 0; j < coords; j++) { if (agent.c [j] < rangeMin [j] || agent.c [j] > rangeMax [j]) { // Select a boundary handling strategy if (u.RNDprobab () < 0.5) { // Random regeneration agent.c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); } else { // Set to the boundary if (agent.c [j] < rangeMin [j]) agent.c [j] = rangeMin [j]; else agent.c [j] = rangeMax [j]; } } // Discretization agent.c [j] = u.SeInDiSp (agent.c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } //————————————————————————————————————————————————————————————————————
Die Methode Revision ist dafür zuständig, die beste Lösung aus der aktuellen Population auszuwählen und zu aktualisieren. Es durchläuft alle Lösungen und sucht dabei nach derjenigen mit dem höchsten Wert der Bewertungsfunktion (Fitness). Wird eine solche Lösung gefunden, wird sie als derzeit bestes Ergebnis gespeichert, und ihre Koordinaten werden in ein separates Array kopiert, das dazu dient, die aktuell beste Lösung zu speichern. Das Verfahren ermöglicht somit eine kontinuierliche Verfolgung und Aktualisierung der während der Algorithmus-Iterationen ermittelten optimalen Lösung.
//———————————————————————————————————————————————————————————————————— //--- Selection-II and updating the best solution void C_AO_BSA_Backtracking::Revision () { int bestIND = -1; for (int i = 0; i < popSize; i++) { // Update the global best solution if (a [i].f > fB) { fB = a [i].f; bestIND = i; } } // Copy the coordinates of the best solution if (bestIND != -1) { ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY); } } //————————————————————————————————————————————————————————————————————
Die Methode GaussDistribution generiert eine Zufallszahl mit einer gaußschen (Normal-)Verteilung, deren Mittelwert auf einem vorgegebenen Eingabewert liegt und die auf einen bestimmten Bereich begrenzt ist. Dabei wird das Box-Muller-Verfahren zur Erzeugung normalverteilter Zufallsvariablen verwendet.
Zunächst erzeugt es zwei gleichverteilte Zufallsvariablen. Anschließend wird auf der Grundlage dieser Werte eine normalverteilte Standardzufallsvariable berechnet, mit deren Hilfe eine Gauß-Verteilung ermittelt werden kann.
Die Methode prüft dann, ob der erzeugte Wert innerhalb des durch den Sigma-Parameter definierten Abweichungsbereichs liegt. Liegt der erzeugte Wert außerhalb dieser Grenzen, wird die Methode erneut rekursiv aufgerufen, um einen neuen Wert zu erzeugen, bis dieser innerhalb des zulässigen Bereichs liegt.
Schließlich wird die erzeugte normalverteilte Varianz so skaliert, dass sie im Verhältnis zum Eingabewert „In“ in den vorgegebenen Ausgabebereich (von outMin bis outMax) passt. Dadurch können wir die Verteilung an Ihre gewünschten Parameter anpassen und skalieren. Das Ergebnis ist eine nach einer Gauß-Verteilung verteilte Zahl mit dem Mittelpunkt bei In, die jedoch den Einschränkungen hinsichtlich des minimalen und maximalen Ausgabewerts unterliegt.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_Utilities :: GaussDistribution (const double In, const double outMin, const double outMax, const double sigma) { double logN = 0.0; double u1 = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0); double u2 = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0); logN = u1 <= 0.0 ? 0.000000000000001 : u1; double z0 = sqrt (-2 * log (logN)) * cos (2 * M_PI * u2); double sigmaN = sigma > 8.583864105157389 ? 8.583864105157389 : sigma; // If z0 is outside the range [-sigmaN, sigmaN], generate anew if (z0 >= sigmaN || z0 <= -sigmaN) { return GaussDistribution(In, outMin, outMax, sigma); // Recursive call } if (z0 >= 0.0) z0 = Scale (z0, 0.0, sigmaN, 0.0, outMax - In, false); else z0 = -Scale (fabs (z0), 0.0, sigmaN, 0.0, In - outMin, false); return In + z0; } //——————————————————————————————————————————————————————————————————————————————
Testergebnisse
Der BSA-Algorithmus liefert sehr gute Ergebnisse.
=============================
5 Hilly's; Func runs: 10000; result: 0.9730917210619289
25 Hilly's; Func runs: 10000; result: 0.5453406317593932
500 Hilly's; Func runs: 10000; result: 0.2909827609772065
=============================
5 Forest's; Func runs: 10000; result: 0.9999986842258451
25 Forest's; Func runs: 10000; result: 0.5854340780208712
500 Forest's; Func runs: 10000; result: 0.21747482800959225
=============================
5 Megacity's; Func runs: 10000; result: 0.8476923076923077
25 Megacity's; Func runs: 10000; result: 0.3695384615384615
500 Megacity's; Func runs: 10000; result: 0.12978461538461658
=============================
All score: 4.95934 (55.10%)
Bei der Visualisierung des BSA-Algorithmus ist eine deutliche Streuung der Resultate bei Funktionen kleiner und mittlerer Dimension zu erkennen; mit steigenden Parametern für die Populationsgröße nimmt die Streuung jedoch ab, doch für eine bessere Konvergenz ist es notwendig, die Anzahl der Iterationen zu erhöhen.
BSA mit der Testfunktion Hilly
BSA mit der Testfunktion Forest
BSA mit der Testfunktion Megacity
Der BSA-Algorithmus belegt Platz 20 in der Rangliste der populationsbasierten Optimierungsalgorithmen.
| # | AO | Beschreibung | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | Suche über die gesamte Nachbarschaft | 0.94948 | 0.84776 | 0.43857 | 2.23581 | 1.00000 | 0.92334 | 0.39988 | 2.32323 | 0.70923 | 0.63477 | 0.23091 | 1.57491 | 6.134 | 68.15 |
| 2 | CLA | Code-Lock-Algorithmus (joo) | 0.95345 | 0.87107 | 0.37590 | 2.20042 | 0.98942 | 0.91709 | 0.31642 | 2.22294 | 0.79692 | 0.69385 | 0.19303 | 1.68380 | 6.107 | 67.86 |
| 3 | AMOm | Optimierung der Tiermigration M | 0.90358 | 0.84317 | 0.46284 | 2.20959 | 0.99001 | 0.92436 | 0.46598 | 2.38034 | 0.56769 | 0.59132 | 0.23773 | 1.39675 | 5.987 | 66.52 |
| 4 | (P+O)ES | (P+O) Entwicklungsstrategien | 0.92256 | 0.88101 | 0.40021 | 2.20379 | 0.97750 | 0.87490 | 0.31945 | 2.17185 | 0.67385 | 0.62985 | 0.18634 | 1.49003 | 5.866 | 65.17 |
| 5 | CTA | Kometenschweif-Algorithmus (joo) | 0.95346 | 0.86319 | 0.27770 | 2.09435 | 0.99794 | 0.85740 | 0.33949 | 2.19484 | 0.88769 | 0.56431 | 0.10512 | 1.55712 | 5.846 | 64.96 |
| 6 | TETA | Zeit-Evolutions-Reise-Algorithmus (Joo) | 0.91362 | 0.82349 | 0.31990 | 2.05701 | 0.97096 | 0.89532 | 0.29324 | 2.15952 | 0.73462 | 0.68569 | 0.16021 | 1.58052 | 5.797 | 64.41 |
| 7 | SDSm | stochastische Diffusionssuche M | 0.93066 | 0.85445 | 0.39476 | 2.17988 | 0.99983 | 0.89244 | 0.19619 | 2.08846 | 0.72333 | 0.61100 | 0.10670 | 1.44103 | 5.709 | 63.44 |
| 8 | BOAm | Billard-Optimierungsalgorithmus M | 0.95757 | 0.82599 | 0.25235 | 2.03590 | 1.00000 | 0.90036 | 0.30502 | 2.20538 | 0.73538 | 0.52523 | 0.09563 | 1.35625 | 5.598 | 62.19 |
| 9 | AAm | Algorithmus für das Bogenschießen M | 0.91744 | 0.70876 | 0.42160 | 2.04780 | 0.92527 | 0.75802 | 0.35328 | 2.03657 | 0.67385 | 0.55200 | 0.23738 | 1.46323 | 5.548 | 61.64 |
| 10 | ESG | Entwicklung sozialer Gruppen (joo) | 0.99906 | 0.79654 | 0.35056 | 2.14616 | 1.00000 | 0.82863 | 0.13102 | 1.95965 | 0.82333 | 0.55300 | 0.04725 | 1.42358 | 5.529 | 61.44 |
| 11 | SIA | Simuliertes isotropes Glühen (Joo) | 0.95784 | 0.84264 | 0.41465 | 2.21513 | 0.98239 | 0.79586 | 0.20507 | 1.98332 | 0.68667 | 0.49300 | 0.09053 | 1.27020 | 5.469 | 60.76 |
| 12 | BBO | biogeografisch basierte Optimierung | 0.94912 | 0.69456 | 0.35031 | 1.99399 | 0.93820 | 0.67365 | 0.25682 | 1.86867 | 0.74615 | 0.48277 | 0.17369 | 1.40261 | 5.265 | 58.50 |
| 13 | ACS | künstliche, kooperative Suche | 0.75547 | 0.74744 | 0.30407 | 1.80698 | 1.00000 | 0.88861 | 0.22413 | 2.11274 | 0.69077 | 0.48185 | 0.13322 | 1.30583 | 5.226 | 58.06 |
| 14 | DA | dialektischer Algorithmus | 0.86183 | 0.70033 | 0.33724 | 1.89940 | 0.98163 | 0.72772 | 0.28718 | 1.99653 | 0.70308 | 0.45292 | 0.16367 | 1.31967 | 5.216 | 57.95 |
| 15 | BHAm | Algorithmus für schwarze Löcher M | 0.75236 | 0.76675 | 0.34583 | 1.86493 | 0.93593 | 0.80152 | 0.27177 | 2.00923 | 0.65077 | 0.51646 | 0.15472 | 1.32195 | 5.196 | 57.73 |
| 16 | ASO | Anarchische Gesellschaftsoptimierung | 0.84872 | 0.74646 | 0.31465 | 1.90983 | 0.96148 | 0.79150 | 0.23803 | 1.99101 | 0.57077 | 0.54062 | 0.16614 | 1.27752 | 5.178 | 57.54 |
| 17 | RFO | Optimierung des Royal Flush (joo) | 0.83361 | 0.73742 | 0.34629 | 1.91733 | 0.89424 | 0.73824 | 0.24098 | 1.87346 | 0.63154 | 0.50292 | 0.16421 | 1.29867 | 5.089 | 56.55 |
| 18 | AOSm | Suche nach atomaren Orbitalen M | 0.80232 | 0.70449 | 0.31021 | 1.81702 | 0.85660 | 0.69451 | 0.21996 | 1.77107 | 0.74615 | 0.52862 | 0.14358 | 1.41835 | 5.006 | 55.63 |
| 19 | TSEA | Schildkrötenpanzer-Evolutionsalgorithmus (joo) | 0.96798 | 0.64480 | 0.29672 | 1.90949 | 0.99449 | 0.61981 | 0.22708 | 1.84139 | 0.69077 | 0.42646 | 0.13598 | 1.25322 | 5.004 | 55.60 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | (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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
| 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
BSA stellt einen Kompromiss zwischen einfacher Implementierung und Sucheffizienz dar und nimmt einen stabilen Platz im Mittelfeld der Rangliste der populationsbasierten Optimierungsalgorithmen ein. Sein Hauptvorteil ist das interessante Konzept des historischen Gedächtnisses, das es dem Algorithmus ermöglicht, eine vorzeitige Konvergenz zu vermeiden, ohne das Rechenschema zu verkomplizieren. Im Gegensatz zu vielen modernen Metaheuristiken, die mit Parametern und komplexen Operatoren überladen sind, erfordert BSA nur einen minimalen Satz an Einstellungen, was es zu einer attraktiven Wahl für Praktiker macht, die keine Zeit mit der Feinabstimmung externer Parameter verbringen möchten.
Der einzige wichtige Parameter (Mixrate) ist intuitiv und erfordert kein tiefgreifendes Verständnis der internen Funktionsweise des Algorithmus. Gleichzeitig zeigt BSA stabile Ergebnisse bei einer breiten Palette von Problemen – von einfachen unimodalen Funktionen bis hin zu komplexen Landschaften mit mehreren Extrema und zahlreichen lokalen Optima. Der Algorithmus erhebt zwar keinen Anspruch darauf, in puncto Konvergenzgeschwindigkeit oder Lösungsgenauigkeit unübertroffen zu sein, doch seine Zuverlässigkeit und Vorhersehbarkeit machen ihn zu einem bewährten Arbeitstier. Besonders wertvoll ist, dass BSA bei wachsender Population nur in geringem Maße anfällig für Stagnation ist – der Mechanismus der zufälligen Erneuerung der historischen Population sorgt selbst in den späten Phasen der Suche für einen konstanten Zufluss an Vielfalt.
Seine Platzierung im Mittelfeld der Rangliste ist kein Zeichen von Mittelmäßigkeit, sondern vielmehr ein Beweis für seine Vielseitigkeit und Praxistauglichkeit, da die Lösung realer Probleme nicht immer das komplexeste und modernste Werkzeug erfordert. Manchmal reicht ein robuster Algorithmus mit klarer Funktionslogik aus, der ohne fachmännische Feinabstimmung gute Ergebnisse liefert, und BSA füllt diese Nische erfolgreich aus.
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 der BSA:
Vorteile:
- Gute Konvergenz bei allen getesteten Funktionen.
- Abgesehen von der Populationsgröße gibt es nur einen weiteren externen Parameter.
Nachteile:
- Es besteht eine gewisse Tendenz, bei Problemen mit geringer Dimension und kleinen Populationen hängen zu bleiben.
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_BSA.mq5 | Skript | BSA-Testumgebung |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/18568
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.
Analyse von Kurs-Zeit-Lücken in MQL5 (Teil I): Entwicklung eines einfachen Indikators
Untersuchung von Conformal Prediction bei Finanzzeitreihen
Eine alternative Log-datei mit der Verwendung der HTML und CSS
Ermittlung fairer Wechselkurse anhand von KKP- und IWF-Daten
- 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.