Blood inheritance optimization (BIO)
85
0
Inhalt
Einführung
Eines Tages, als ich einer Krankenschwester bei der Entnahme von Blutproben von Patienten im Labor zusah, kam mir plötzlich ein Gedanke. Blutgruppen, dieses uralte System der Vererbung, das von Generation zu Generation nach strengen genetischen Gesetzen weitergegeben wird, erschien mir plötzlich in einem völlig neuen Licht. Was wäre, wenn diese natürlichen Eigenschaften der Vererbung im Bereich der Optimierungsalgorithmen ausgenutzt werden könnten?
Jeder von uns trägt eine einzigartige Kombination in seinen Adern, die er von seinen Eltern geerbt hat. So wie die Blutgruppen die Kompatibilität bei Transfusionen bestimmen, könnten sie bestimmen, wie die Parameter bei der Optimierung übertragen und mutiert werden. Diese Idee gefiel mir und ich beschloss, darauf zurückzukommen, wenn ich Zeit für Recherchen habe. Nach der Durchführung von Experimenten wurde der Algorithmus „Blood Inheritance Optimization“ (BIO) geboren – eine Methode, die die natürlichen Gesetze der Blutgruppenvererbung als Metapher für die Verwaltung der Evolution von Entscheidungen nutzt. In dem Algorithmus entwickelten sich die vier Blutgruppen zu vier verschiedenen Strategien für die Mutation von Parametern, und die Gesetze der Vererbung bestimmten, wie die Nachkommen die Merkmale ihrer Eltern erwerben und verändern.
Wie in der Natur ist die Blutgruppe eines Kindes nicht einfach ein Durchschnitt der Blutgruppen der Eltern, sondern unterliegt genetischen Gesetzen. In BIO werden die Parameter neuer Lösungen durch ein System von Vererbung und Mutationen gebildet. Jede Blutgruppe bringt ihre eigene Herangehensweise an die Erforschung des Lösungsraums mit sich: von der konservativen Beibehaltung der besten gefundenen Werte bis hin zu radikalen Mutationen, die neue vielversprechende Bereiche und Richtungen für die weitere Erforschung des Lösungsraums eröffnen.
In diesem Artikel möchte ich die Grundsätze des BIO-Algorithmus erläutern, der biologische Inspiration mit algorithmischer Strenge verbindet, und Testergebnisse zu Funktionen liefern, die wir bereits kennen. Lassen Sie uns das also tun.
Implementierung des Algorithmus
Machen wir uns zunächst mit der Tabelle der Vererbung der Blutgruppe der Nachkommen von den Eltern vertraut. Wie Sie sehen können, ist die Vererbung der Blutgruppe nicht einheitlich. Es gibt interessante Statistiken über die Verteilung der Blutgruppen in der WeltPopulation. Am weitesten verbreitet ist die erste Gruppe (O) – etwa 40 % der WeltPopulation sind Träger dieser Krankheit. Es folgt die zweite Gruppe (A), die von etwa 30 % der Menschen besessen wird. Die dritte Gruppe (B) kommt bei 20 % der Population vor, und die vierte Gruppe (AB) ist die seltenste – nur etwa 10 % der Menschen tragen sie in sich.
Beim Studium der Vererbungsmechanismen habe ich gelernt, dass die erste Blutgruppe im Verhältnis zu allen anderen rezessiv ist. Das bedeutet, dass Menschen mit Blutgruppe 1 nur die Blutgruppe 1 an ihre Kinder weitergeben können. Gleichzeitig weisen die zweite und dritte Gruppe eine Ko-Dominanz zueinander auf, die in ihrer Kombination zur Entstehung der vierten Gruppe führt. Aus evolutionärer Sicht ist die vierte Blutgruppe die jüngste.
Ich interessierte mich besonders für einige der einzigartigen Eigenschaften der verschiedenen Blutgruppen. So gilt beispielsweise die Blutgruppe O als „Universalspender“, da sie Menschen mit jeder Blutgruppe transfundiert werden kann. Die vierte Gruppe hingegen macht ihre Träger zu „Universalempfängern“ – sie können Blut jeder Art annehmen.
All diese Merkmale des Blutgruppensystems haben mich dazu inspiriert, entsprechende Mechanismen in meinem Algorithmus zu schaffen. Da die erste Blutgruppe die einfachste und häufigste ist, entspricht sie der Strategie, die beste im Algorithmus gefundene Lösung zu erhalten. Die Blutgruppenvererbungstabelle, in der alle möglichen Kombinationen der elterlichen Blutgruppen und die potenziellen Blutgruppen ihrer Kinder aufgeführt sind, bildet die Grundlage für die Bestimmung der „Blutgruppe“ einer neuen Lösung auf der Grundlage der „Blutgruppen“ der elterlichen Lösungen, was sich direkt auf die Art und Weise auswirkt, wie die Parameter im BIO-Algorithmus mutiert werden.
Abbildung 1. Blutgruppenvererbungstabelle
Der BIO-Algorithmus basiert auf einer recht einfachen Idee: Jede Lösung in der Population (Elternindividuen) hat ihre eigene „Blutgruppe“ (von 1 bis 4), die durch ihre Ordnungszahl in der Population bestimmt wird. Wenn wir eine neue Generation von Lösungen erstellen, wählen wir zwei „Eltern“ aus der aktuellen Population aus. Die Wahrscheinlichkeit der Wahl ist nicht linear, sondern quadratisch – das bedeutet, dass die besten Entscheidungen eine deutlich höhere Chance haben, Eltern zu werden.
Jetzt beginnt der interessanteste Teil. Ausgehend von den Blutgruppen der Eltern werden mit Hilfe einer speziellen Vererbungsmatrix (sie ist im Code der Init-Methode enthalten) die möglichen Blutgruppen für das „Kind“ – die neue Lösung – bestimmt. Dann wird für jeden Parameter dieser neuen Lösung, wenn die erste Blutgruppe gefunden wurde, der Wert der besten gefundenen Lösung genommen. Ich habe dies in Analogie zur ersten Blutgruppe als Universalspender getan. Wenn die zweite Gruppe ausgewählt wird, nehmen wir den Wert von einem der Elternteile und wenden die Potenzverteilung auf ihn an. Dies führt zu einer Tendenz, die Ränder des Parameterbereichs zu erkunden. Für die dritte Gruppe nehmen wir ebenfalls einen Wert von einem der Elternteile, verschieben ihn aber um einen zufälligen Betrag in Richtung der besten Lösung. Und bei der vierten Gruppe nehmen wir den übergeordneten Wert und spiegeln ihn relativ zu den Bereichsgrenzen, eine Art Umkehrung, die es uns ermöglicht, neue Suchbereiche zu erkunden.
Nach der Erstellung einer neuen Generation prüfen wir, ob sich bessere Lösungen als die aktuelle Gesamtlösung ergeben haben, und speichern die besten Individuen für die nächste Iteration. In Analogie zur Vererbung von Blutgruppen erforscht mein Algorithmus den Lösungsraum durch die Kombination verschiedener Mutationsstrategien für Parameter. Nachstehend finden Sie den Pseudocode des Algorithmus.
Initialisierung:
- Erstelle eine Population von Agenten der Größe popSize (Standardwert 50).
- Erstelle einer Blutgruppenvererbungsmatrix, die die möglichen Blutgruppen der Kinder auf der Grundlage der Blutgruppen der Eltern bestimmt (1,2,3,4).
- Initialisiere die Bereiche der Parameter (Min., Max., Schrittwerte).
Hauptschleife:
- Wenn dies die erste Iteration ist (Revision = false):
- Initialisiere die Positionen aller Agenten innerhalb der Parameterbereiche nach dem Zufallsprinzip
- Setze das Revisionsflag auf „true“.
- Für jeden Agenten in der Population:
- Wähle die elterlichen Agenten (Vater und Mutter) anhand einer quadratischen Wahrscheinlichkeitsverteilung
- Bestimme die Blutgruppen beider Elternteile mit der Funktion: bloodType = 1 + (population_position % 4)
- Für jeden Parameter der untergeordneten Lösung:
- Ermittele der wahrscheinlichen Blutgruppe des Kindes anhand der Vererbungsmatrix auf der Grundlage der Blutgruppen der Eltern
- Wenn das Kind die Blutgruppe 1 hat:
- Verwende die beste bekannte Lösung für diesen Parameter.
- Andernfalls:
- Wähle zufällige einen Parameterwerts entweder vom Vater oder von der Mutter
- Wende die Mutation auf der Grundlage der Blutgruppe des Kindes an:
- Typ 2: Verwende eine Potenzgesetzverteilung mit Exponent 20.
- Typ 3: Verschiebe des Parameterwerts in Richtung der besten Lösung mit einem Zufallsfaktor.
- Typ 4: Spiegel den Parameterwert über den gesamten Parameterbereich.
- Stelle sicher, dass der Parameter innerhalb des zulässigen Bereichs und der zulässigen Stufe bleibt.
Revisionsphase:
- Aktualisiere die global beste Lösung, wenn ein Agent eine bessere Eignung hat.
- Kopiere die aktuelle Population in die zweite Hälfte des erweiterten Populationsfeldes.
- Sortiere die erweiterte Population nach der Fitness.
- Bewahre die besten Agenten für die nächste Generation.
Beginnen wir mit dem Schreiben des Algorithmus-Codes. Die von C_AO abgeleitete Klasse C_AO_BIO implementiert den BIO-Algorithmus und setzt die Verwendung einer Datenstruktur zur Darstellung von Individuen (Agenten) in einer Population sowie deren Kontrolle voraus.
SetParams () – die Methode ermöglicht die Einstellung von Klassenparametern, in diesem Fall die Einstellung der Populationsgröße popSize aus dem Parameter-Array.
Init () – die Methode initialisiert den Algorithmus, indem sie die Minimal- und Maximalwerte der Parameter, den Änderungsschritt und die Anzahl der Epochen annimmt.
Moving () und Revision () – Methoden sind für die Bewegung (Evolution) von Agenten in der Population und deren Revision (Leistungsbewertung und Auswahl der Besten) verantwortlich.
S_Papa und S_Mama:
- S_Papa ist eine Struktur, die ein Array von Blutgruppen (bTypes) enthält.
- S_Mama enthält eine Reihe von vier S_Papa-Objekten, was auf das Vorhandensein von „Eltern“ zur weiteren genetischen Vermischung schließen lässt.
Diese Art der Darstellung in Form von Strukturen ermöglicht es uns, die wahrscheinliche Blutgruppe der Nachkommen direkt von den Eltern zu erhalten, indem wir die Blutgruppe der Eltern angeben, also „ma [1].pa [2].bTypes“, wobei 1 und 2 die Blutgruppen der Mutter bzw. des Vaters sind.
Die Methode GetBloodType ()liefert die Blutgruppe für einen bestimmten Erreger, während GetBloodMutation () den Mechanismus der Genmutation in Abhängigkeit von der Blutgruppe implementiert.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_BIO : public C_AO { public: //-------------------------------------------------------------------- C_AO_BIO () { ao_name = "BIO"; ao_desc = "Blood Inheritance Optimization"; ao_link = "https://www.mql5.com/en/articles/17246"; popSize = 50; // population size ArrayResize (params, 1); params [0].name = "popSize"; params [0].val = popSize; } void SetParams () { popSize = (int)params [0].val; } 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 (); private: //------------------------------------------------------------------- struct S_Papa { int bTypes []; }; struct S_Mama { S_Papa pa [4]; }; S_Mama ma [4]; S_AO_Agent p []; int GetBloodType (int ind); void GetBloodMutation (double &gene, int indGene, int bloodType); }; //——————————————————————————————————————————————————————————————————————————————
Die Init-Methode initialisiert eine Instanz der Klasse C_AO_BIO und bereitet sie auf die Arbeit vor, indem sie die Agentenpopulation und deren Eigenschaften einrichtet. Schauen wir uns nun die Umsetzung dieser Methode an.
Aufruf der Methode StandardInit – die erste Zeichenkette prüft das Ergebnis des Aufrufs der Methode, die die grundlegenden Parameter prüft/initialisiert, die für das Funktionieren des Algorithmus erforderlich sind.
Initialisierung des Agentenarrays:
- Verändert die Größe des Agentenarrays „p“ auf das Doppelte der angegebenen Populationsgröße (popSize).
- In der for-Schleife wird für jeden Agenten die Init-Methode aufgerufen, die den Agenten anhand der Koordinatenparameter initialisiert.
- Als Nächstes gibt die Methode die Größe der Arrays der Blutgruppen (bTypes) für die Strukturen S_Mama und S_Papa an.
- Für verschiedene Kombinationen (z.B. ma [0].pa [0], ma [1].pa [2] usw.) werden verschiedene Bluttypen entsprechend einer speziellen Vererbungsmatrix gesetzt, und die Größe der Arrays wird über ArrayResize festgelegt.
Die Init-Methode in der Klasse C_AO_BIO erfüllt also die wichtige Aufgabe, das Objekt für die Ausführung des Optimierungsalgorithmus vorzubereiten: Sie erstellt eine Population von Agenten, legt deren Anfangsparameter fest und definiert die Assoziationsregeln für die Blutgruppen (Vererbung). So kann man sofort die wahrscheinliche Blutgruppe der Nachkommen ermitteln und die Parameter ihres „Blutes“ für die weitere Evolution innerhalb des Algorithmus verwenden.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_BIO::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- ArrayResize (p, popSize * 2); for (int i = 0; i < popSize * 2; i++) p [i].Init (coords); //1-1 ArrayResize (ma [0].pa [0].bTypes, 1); ma [0].pa [0].bTypes [0] = 1; //2-2 ArrayResize (ma [1].pa [1].bTypes, 2); ma [1].pa [1].bTypes [0] = 1; ma [1].pa [1].bTypes [1] = 2; //3-3 ArrayResize (ma [2].pa [2].bTypes, 2); ma [2].pa [2].bTypes [0] = 1; ma [2].pa [2].bTypes [1] = 3; //1-2; 2-1 ArrayResize (ma [0].pa [1].bTypes, 2); ArrayResize (ma [1].pa [0].bTypes, 2); ma [0].pa [1].bTypes [0] = 1; ma [0].pa [1].bTypes [1] = 2; ma [1].pa [0].bTypes [0] = 1; ma [1].pa [0].bTypes [1] = 2; //1-3; 3-1 ArrayResize (ma [0].pa [2].bTypes, 2); ArrayResize (ma [2].pa [0].bTypes, 2); ma [0].pa [2].bTypes [0] = 1; ma [0].pa [2].bTypes [1] = 3; ma [2].pa [0].bTypes [0] = 1; ma [2].pa [0].bTypes [1] = 3; //1-4; 4-1 ArrayResize (ma [0].pa [3].bTypes, 2); ArrayResize (ma [3].pa [0].bTypes, 2); ma [0].pa [3].bTypes [0] = 2; ma [0].pa [3].bTypes [1] = 3; ma [3].pa [0].bTypes [0] = 2; ma [3].pa [0].bTypes [1] = 3; //2-3; 3-2 ArrayResize (ma [1].pa [2].bTypes, 4); ArrayResize (ma [2].pa [1].bTypes, 4); ma [1].pa [2].bTypes [0] = 1; ma [1].pa [2].bTypes [1] = 2; ma [1].pa [2].bTypes [2] = 3; ma [1].pa [2].bTypes [3] = 4; ma [2].pa [1].bTypes [0] = 1; ma [2].pa [1].bTypes [1] = 2; ma [2].pa [1].bTypes [2] = 3; ma [2].pa [1].bTypes [3] = 4; //2-4; 4-2; 3-4; 4-3; 4-4 ArrayResize (ma [1].pa [3].bTypes, 3); ArrayResize (ma [3].pa [1].bTypes, 3); ArrayResize (ma [2].pa [3].bTypes, 3); ArrayResize (ma [3].pa [2].bTypes, 3); ArrayResize (ma [3].pa [3].bTypes, 3); ma [1].pa [3].bTypes [0] = 2; ma [1].pa [3].bTypes [1] = 3; ma [1].pa [3].bTypes [2] = 4; ma [3].pa [1].bTypes [0] = 2; ma [3].pa [1].bTypes [1] = 3; ma [3].pa [1].bTypes [2] = 4; ma [2].pa [3].bTypes [0] = 2; ma [2].pa [3].bTypes [1] = 3; ma [2].pa [3].bTypes [2] = 4; ma [3].pa [2].bTypes [0] = 2; ma [3].pa [2].bTypes [1] = 3; ma [3].pa [2].bTypes [2] = 4; ma [3].pa [3].bTypes [0] = 2; ma [3].pa [3].bTypes [1] = 3; ma [3].pa [3].bTypes [2] = 4; return true; } //——————————————————————————————————————————————————————————————————————————————
Die Methode Moving führt evolutionäre Schritte im Optimierungsprozess durch und wendet die Konzepte der Vererbung und Mutation auf eine Population von Agenten an. Schauen wir uns das genauer an:
Prüfung der Notwendigkeit einer Revision – der erste Teil der Methode prüft, ob die Agenten aktualisiert oder „verschoben“ werden müssen, und wenn „Überarbeitung“ „falsch“ ist, erfolgt die anfängliche Initialisierung (oder Aktualisierung) der Koordinaten der Agenten (a [i] .c [j]):
- Jeder Agent erhält Zufallswerte, die mit der Methode u.RNDfromCI im Bereich (rangeMin [j], rangeMax [j]) erzeugt werden.
- Der Wert wird dann mit u.SeInDiSp in den gewünschten Bereich gebracht, wobei der in rangeStep angegebene Schritt angewendet wird.
Wechsel zum Revisionsstatus – nach der ersten Iteration wird der Parameter „revision“ auf „true“ gesetzt, um zur nächsten Stufe zu wechseln, und die Methode schließt die Ausführung ab (Rückkehr).
Initialisierung der Variablen – zu Beginn der Methode werden die Variablen für die Zufallswerte und die Blutgruppen der Eltern initialisiert (papIND, mamIND, pBloodType, mBloodType, cBloodType und bloodIND).
Grundlegende Populationsschleife (popSize) – die Methode läuft in einer Schleife für jeden Agenten in der Population:
- Zwei Zufallsindizes für Eltern (papIND und mamIND) werden mit der Methode u.RNDprobab () erzeugt, die Zufallswahrscheinlichkeiten generiert.
- Die Funktion GetBloodType ermittelt die Blutgruppen beider Elternteile.
Schleife nach Koordinaten (coords) – innerhalb der Hauptschleife für jede Agentenkoordinate:
- Ein zufälliger Blutgruppenindex wird aus dem bTypes-Array der ausgewählten Eltern ausgewählt (basierend auf der Blutgruppe der Mutter und des Vaters).
- Wenn die ausgewählte Blutgruppe 1 ist, erhält der Agent den Wert aus cB[c]. Andernfalls kommt es zu einer Vermischung:
- Der Koordinatenwert der Agenten wird zufällig entweder vom Vater oder von der Mutter ausgewählt.
- Es wird die Funktion GetBloodMutation verwendet, die den ausgewählten Wert auf der Grundlage der Blutgruppe mutiert.
- Der Wert wird mit der Methode u.SeInDiSp angepasst, um sicherzustellen, dass er innerhalb akzeptabler Grenzen bleibt.
Die gleitende Methode ist ein zentraler Bestandteil des Algorithmus, der die Evolution einer Agentenpopulation nachbildet und sowohl eine zufällige Initialisierung als auch Mechanismen zur Mutation und Kombination von Agentenparametern auf der Grundlage der Prinzipien der Blutgruppenvererbung umfasst. Die Methode kombiniert Aspekte des Zufalls und der Vererbung, um neue Nachkommen mit unterschiedlichen Werten zu erzeugen. Damit sind die Agenten für die weitere Optimierung und Suche im Lösungsraum gerüstet.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BIO::Moving () { //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } //---------------------------------------------------------------------------- double rnd = 0.0; int papIND = 0; int mamIND = 0; int pBloodType = 0; int mBloodType = 0; int cBloodType = 0; int bloodIND = 0; for (int i = 0; i < popSize; i++) { rnd = u.RNDprobab (); rnd *= rnd; papIND = (int)u.Scale (rnd, 0.0, 1.0, 0, popSize - 1); rnd = u.RNDprobab (); rnd *= rnd; mamIND = (int)u.Scale (rnd, 0.0, 1.0, 0, popSize - 1); pBloodType = GetBloodType (papIND); mBloodType = GetBloodType (mamIND); for (int c = 0; c < coords; c++) { bloodIND = MathRand () % ArraySize (ma [mBloodType - 1].pa [pBloodType - 1].bTypes); cBloodType = ma [mBloodType - 1].pa [pBloodType - 1].bTypes [bloodIND]; if (cBloodType == 1) a [i].c [c] = cB [c]; else { if (u.RNDbool () < 0.5) a [i].c [c] = p [papIND].c [c]; else a [i].c [c] = p [mamIND].c [c]; GetBloodMutation (a [i].c [c], c, cBloodType); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode GetBloodType bestimmt die Blutgruppe anhand des übergebenen Index „ind“ – der aktuellen Position in der Population. Die Methode gleicht also Indizes mit Blutgruppen durch eine einfache arithmetische Operation mit einem Rest ab. Dies ermöglicht eine zyklische Verteilung der Blutgruppen auf die verfügbaren Indizes (0-3).
//—————————————————————————————————————————————————————————————————————————————— int C_AO_BIO::GetBloodType (int ind) { if (ind % 4 == 0) return 1; if (ind % 4 == 1) return 2; if (ind % 4 == 2) return 3; if (ind % 4 == 3) return 4; return 1; } //——————————————————————————————————————————————————————————————————————————————
Die Methode GetBloodMutation dient dazu, den Wert eines genetischen Parameters (Gens) in Abhängigkeit von seiner Blutgruppe und seinem Index zu ändern (zu mutieren).
Parameter:
- gene – Verweis auf den Genwert, der geändert werden soll.
- indGene – Genindex, der zur Ermittlung der Mutationsbereiche verwendet wird.
- bloodType – Blutgruppe, die die Mutationslogik bestimmt.
Blutgruppe 2 – PowerDistribution wird auf den Genwert angewandt, wodurch das Gen auf der Grundlage eines gegebenen Bereichs verändert wird und die Werte um diesen Bereich herum probabilistisch verteilt werden.
Blutgruppe 3 – das Gen erhöht sich um den Bruchteil der Differenz zwischen dem besten aktuellen Wert des Gens in der Population cB [indGene] und dem aktuellen Wert des Gens. Der Anteil der Vorspannung wird durch eine Zufallszahl [0,0; 1,0] bestimmt.
Andere Blutgruppe (Standard) – das Gen wird so verändert, dass sein neuer Wert symmetrisch zum angegebenen Bereich (invers) ist und zwischen rangeMin [indGene] und rangeMax [indGene] liegt.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BIO::GetBloodMutation (double &gene, int indGene, int bloodType) { switch (bloodType) { case 2: gene = u.PowerDistribution (gene, rangeMin [indGene], rangeMax [indGene], 20); return; case 3: gene += (cB [indGene] - gene) * u.RNDprobab (); return; default: { gene = rangeMax [indGene] - (gene - rangeMin [indGene]); } } } //——————————————————————————————————————————————————————————————————————————————
Die Methode Revision ist für die Aktualisierung und Sortierung der Population im BIO-Algorithmus zuständig. In der ersten for-Schleife (von 0 bis popSize) iteriert die Methode über alle Mitglieder der Population a[i]. Wenn der Wert der Fitnessfunktion „f“ des aktuellen a[i].f-Populationsmitglieds den aktuell besten Wert von fB übersteigt, wird fB mit dem neuen Wert aktualisiert, und die Koordinaten „c“ des aktuellen Populationsmitglieds werden in das Array cB kopiert. In der zweiten „for“-Schleife werden die aktuellen Mitglieder der Population a[i] an das Ende des Arrays „p“ kopiert, beginnend mit dem Index popSize. Als Nächstes wird das pT-Array erstellt. Sie ist doppelt so groß wie die aktuelle Population „popSize * 2“. Die Sortiermethode u.Sorting wird aufgerufen, um das zusammengeführte Array von „p“ zu sortieren und die Ergebnisse in pT zu speichern.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BIO::Revision () { //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { // Update the best global solution if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { p [popSize + i] = a [i]; } S_AO_Agent pT []; ArrayResize (pT, popSize * 2); u.Sorting (p, pT, popSize * 2); } //——————————————————————————————————————————————————————————————————————————————
Testergebnisse
Der Algorithmus wurde an drei verschiedenen Testfunktionen (Hilly, Forest und Megacity) mit unterschiedlichen Suchraumdimensionen (5*2, 25*2 und 500*2 Dimensionen) mit 10.000 Zielfunktionsbewertungen getestet. Das Gesamtergebnis von 53,80 % zeigt, dass BIO unter den Populationsbasierten Optimierungsalgorithmen eine durchschnittliche Position einnimmt, was für eine neue Methode recht gut ist.
=============================
5 Hilly's; Func runs: 10000; result: 0.8156790458423091
25 Hilly's; Func runs: 10000; result: 0.6533623929914842
500 Hilly's; Func runs: 10000; result: 0.3087659267627686
=============================
5 Forest's; Func runs: 10000; result: 0.8993708810337727
25 Forest's; Func runs: 10000; result: 0.6531872390668734
500 Forest's; Func runs: 10000; result: 0.21759965952460583
=============================
5 Megacity's; Func runs: 10000; result: 0.6784615384615384
25 Megacity's; Func runs: 10000; result: 0.4763076923076923
500 Megacity's; Func runs: 10000; result: 0.13901538461538585
=============================
All score: 4.84175 (53.80%)
Das einzige Problem, das bei der Visualisierung des Algorithmus auftritt, ist die bei Populationsalgorithmen übliche Tendenz, bei Problemen mit kleinen Dimensionen in lokalen Optima stecken zu bleiben.
BIO mit der Testfunktion Hilly
BIO mit der Testfunktion Forest
BIO mit der Testfunktion Megacity
Aufgrund der Testergebnisse belegt der BIO-Algorithmus Platz 20 in der Rangliste der Populationsoptimierungsalgorithmen.
| # | AO | Beschreibung | Hilly | Hilly final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | Suche über die gesamte Nachbarschaft | 0.94948 | 0.84776 | 0.43857 | 2.23581 | 1.00000 | 0.92334 | 0.39988 | 2.32323 | 0.70923 | 0.63477 | 0.23091 | 1.57491 | 6.134 | 68.15 |
| 2 | CLA | Code-Sperr-Algorithmus (joo) | 0.95345 | 0.87107 | 0.37590 | 2.20042 | 0.98942 | 0.91709 | 0.31642 | 2.22294 | 0.79692 | 0.69385 | 0.19303 | 1.68380 | 6.107 | 67.86 |
| 3 | AMOm | Optimierung der Tiermigration M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5.987 | 66,52 |
| 4 | (P+O)ES | (P+O) 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 | 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 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | (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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | MEC | Evolutionäre Berechnung des Geistes | 0.69533 | 0.53376 | 0.32661 | 1.55569 | 0.72464 | 0.33036 | 0.07198 | 1.12698 | 0.52500 | 0.22000 | 0.04198 | 0.78698 | 3.470 | 38.55 |
| 42 | CSA | Kreis-Such-Algorithmus | 0.66560 | 0.45317 | 0.29126 | 1.41003 | 0.68797 | 0.41397 | 0.20525 | 1.30719 | 0.37538 | 0.23631 | 0.10646 | 0.71815 | 3.435 | 38.17 |
| 43 | IWO | Optimierung mit invasiven Unkräutern | 0.72679 | 0.52256 | 0.33123 | 1.58058 | 0.70756 | 0.33955 | 0.07484 | 1.12196 | 0.42333 | 0.23067 | 0.04617 | 0.70017 | 3.403 | 37.81 |
| 44 | Micro-AIS | Künstliches Mikro-Immunsystem | 0.79547 | 0.51922 | 0.30861 | 1.62330 | 0.72956 | 0.36879 | 0.09398 | 1.19233 | 0.37667 | 0.15867 | 0.02802 | 0.56335 | 3.379 | 37.54 |
| 45 | COAm | Kuckuck-Optimierungsalgorithmus M | 0.75820 | 0.48652 | 0.31369 | 1.55841 | 0.74054 | 0.28051 | 0.05599 | 1.07704 | 0.50500 | 0.17467 | 0.03380 | 0.71347 | 3.349 | 37.21 |
| 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
Bei der Entwicklung und Erprobung des Algorithmus zur Optimierung der Blutvererbung (BIO) bin ich zu mehreren wichtigen Schlussfolgerungen gekommen. Zunächst einmal hat sich die Verwendung der Assoziation der Blutgruppenvererbung als erfolgreicher Ansatz erwiesen, um verschiedene Mutationsstrategien im Algorithmus zur Optimierung der Population zu organisieren. Tests mit verschiedenen Funktionen und Dimensionen haben gezeigt, dass der Algorithmus recht vielseitig ist und sowohl mit einfachen, niedrigdimensionalen Problemen als auch mit komplexeren, mehrdimensionalen Problemen effektiv arbeiten kann.
Es ist besonders wichtig, darauf hinzuweisen, dass die vorgestellte BIO-Implementierung nur eine Basisversion zur Demonstration des Konzepts darstellt. Die Schlüsselidee des Algorithmus liegt nicht so sehr in den spezifischen Mutationsoperatoren (die durch beliebige andere ersetzt werden können), sondern in der Struktur der Vererbung von Strategien zur Änderung von Parametern durch eine Analogie mit Blutgruppen. Dies eröffnet weitreichende Möglichkeiten zur Änderung und Erweiterung des Algorithmus. Jede „Blutgruppe“ kann mit beliebigen anderen Mutationsoperatoren verbunden werden, die von anderen Algorithmen übernommen oder für eine bestimmte Aufgabe erstellt werden. Darüber hinaus können wir mit der Anzahl der „Blutgruppen“ experimentieren, neue Strategien hinzufügen oder bestehende Strategien kombinieren.
Aktuelle Testergebnisse, die eine respektable Position in der Rangliste der Populationsalgorithmen zeigen (mit einer Punktzahl von etwa 54 %), weisen auf die Effizienz des Ansatzes bereits in seiner Grundimplementierung hin. Die beobachtete Tendenz, in lokalen Optima stecken zu bleiben, kann durch eine Änderung der Mutationsoperatoren oder durch neue Strategien zur Erkundung des Lösungsraums überwunden werden.
Die vielversprechendste Richtung für die Entwicklung des Algorithmus sehe ich in der Schaffung adaptiver Versionen, bei denen sich die Mutationsoperatoren für jede „Blutgruppe“ während des Optimierungsprozesses dynamisch ändern und an die Landschaft der Zielfunktion anpassen können. Es ist auch interessant, die Möglichkeit zu untersuchen, andere Vererbungsmuster als das klassische ABO-Blutgruppensystem zu verwenden, was zur Schaffung einer ganzen Familie von Algorithmen führen könnte, die auf verschiedenen biologischen Vererbungssystemen basieren.
BIO ist also nicht einfach nur ein weiterer Optimierungsalgorithmus, sondern eine flexible konzeptionelle Grundlage für die Schaffung einer Familie von Algorithmen, die durch die gemeinsame Idee der Vererbung von Lösungssuchstrategien durch die Metapher der Blutgruppen vereint sind, und eröffnet weitreichende Möglichkeiten für weitere Forschungen und Modifikationen zur Verbesserung der Effizienz des Algorithmus in verschiedenen Anwendungsbereichen.
Abbildung 2. Farbabstufung 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)
BIO Pro und Kontra:
Vorteile:
- Keine externen Parameter
- Interessante Idee zur Vererbung nach Blutgruppen
- Gute Konvergenz bei hoch- und mitteldimensionalen Funktionen
Nachteile:
- Bleibt bei niedrigdimensionalen Problemen an lokalen Extrema hängen.
Der Artikel wird von einem Archiv mit den aktuellen Versionen der Codes der Algorithmen begleitet. Der Autor des Artikels übernimmt keine Verantwortung für die absolute Richtigkeit der Beschreibung der kanonischen Algorithmen. An vielen von ihnen wurden Änderungen vorgenommen, um die Suchmöglichkeiten zu verbessern. Die in den Artikeln dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Versuche.
Programme, die im diesem Artikel verwendet werden
| # | Name | Typ | Beschreibung |
|---|---|---|---|
| 1 | #C_AO.mqh | Include | Elternklasse der Populationsoptimierung Algorithmen |
| 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 | Der einheitliche Prüfstand 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_BIO.mq5 | Skript | BIO-Prüfstand |
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/17246
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.
Neuronale Netze im Handel: Multi-Task-Lernen auf der Grundlage des ResNeXt-Modells (letzter Teil)
Entwicklung eines Expert Advisors für mehrere Währungen (Teil 23): Ordnung in den Ablauf automatischer Projektoptimierungsstufe bringen (II)
Fibonacci am Devisenmarkt (Teil I): Prüfung des Verhältnisses zwischen Preis und Zeit
Marktsimulation (Teil 09): Sockets (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.