Algorithmen zur Optimierung mit Populationen: Algorithmus des Mind Evolutionary Computation (MEC)
128
0
Inhalt
1. Einführung
2. Der Algorithmus
3. Testergebnisse
1. Einführung
Die evolutionäre Berechnung ist ein Teilbereich der Computational Intelligence, des maschinellen Lernens und der künstlichen Intelligenz. Es findet breite Anwendung bei Optimierungsproblemen, Roboterdesign, der Erstellung von Entscheidungsbäumen, der Abstimmung von Datenanalysealgorithmen, dem Training neuronaler Netze und der Abstimmung von Hyperparametern. Anstatt klassische numerische Methoden zu verwenden, nutzt das evolutionäre Rechnen die Inspiration der biologischen Evolution, um gute Lösungen zu entwickeln. Sie sind besonders nützlich, wenn die Ableitung der Fitnessfunktion nicht bekannt ist oder wenn die Fitnessfunktion viele lokale Extrema aufweist, die sequenzielle Methoden behindern können.
Populationsalgorithmen, die in evolutionären Berechnungen eingesetzt werden, haben bei der Lösung komplexer hochdimensionaler Probleme eine Reihe von Vorteilen gegenüber klassischen Algorithmen. Sie können effizienter suboptimale Lösungen finden, die nahe genug an der optimalen Lösung liegen, was bei praktischen Optimierungsproblemen oft akzeptabel ist.
Ein interessanter Ansatz im evolutionären Rechnen ist der 1998 von Chengai und seinen Mitautoren vorgeschlagene Algorithmus Mind Evolutionary Computation (Berechnung einer Evolution des Geistes, MEC). Anders als die erwartete Modellierung des menschlichen Gehirns modelliert der MEC-Algorithmus einige Aspekte des menschlichen Verhaltens in der Gesellschaft. Bei diesem Algorithmus wird jedes Individuum als intelligenter Agent betrachtet, der in einer Gruppe von Menschen arbeitet. Bei der Entscheidungsfindung fühlt sich der Einzelne sowohl von Mitgliedern seiner Gruppe als auch von Mitgliedern anderer Gruppen beeinflusst. Um eine hohe Position in der Gesellschaft zu erreichen, muss der Einzelne von den erfolgreichsten Personen seiner Gruppe lernen. Damit seine Gruppe erfolgreicher ist als andere Gruppen, müssen alle Individuen im Wettbewerb zwischen den Gruppen nach dem gleichen Prinzip vorgehen. Ein wichtiger Aspekt des MEC-Algorithmus ist der Austausch von Informationen zwischen Einzelpersonen innerhalb einer Gruppe und zwischen Gruppen. Dies spiegelt die Notwendigkeit eines kontinuierlichen und freien Informationsaustauschs für die erfolgreiche Entwicklung einer Gesellschaft intelligenter Menschen wider.
MEC-Algorithmen setzen das vorgestellte Konzept mit Hilfe lokaler Wettbewerbs- und Dissimilationsoperationen um, die für die lokale bzw. globale Suche zuständig sind. Nachrichtentafeln (Message Boards) werden vom Algorithmus verwendet, um Informationen über die Evolutionsgeschichte der Population zu speichern. Auf der Grundlage dieser Informationen wird der Optimierungsprozess gesteuert.
2. Der Algorithmus
Der MEC-Algorithmus kann als ein Mehrpopulationsalgorithmus interpretiert werden, der aus führenden und nachlaufenden Gruppen besteht. Es wird angenommen, dass die Anzahl der Agenten in jeder Gruppe gleich ist. Jede Gruppe hat ihre eigene, lokale Nachrichtentafel, und es gibt auch eine gemeinsame globale Nachrichtentafel für die gesamte Multipopulation.
Die ursprüngliche Version des MEC-Algorithmus, bekannt als Simple MEC (SMEC), verwendet Gruppeninitialisierung, lokalen Wettbewerb und Dissimilationsoperationen.
Die Initialisierungsoperation erstellt Gruppen und platziert sie im Suchbereich. Für jede Gruppe wird ein Zufallsvektor erzeugt, der mit dem Individuum der Gruppe identifiziert wird. Dann werden die Anfangskoordinaten der verbleibenden Agenten der Gruppe bestimmt, indem sie nach dem Gesetz der Normalverteilung zufällig um das Individuum der Gruppe herum angeordnet werden.
Die lokale Wettbewerbsoperation führt eine lokale Suche nach der maximalen Fitnessfunktion jeder Gruppe durch. Für jede Gruppe werden die Informationen über den aktuellen Gewinner von der Nachrichtentafel abgelesen. Dann werden die neuen Koordinaten der verbleibenden Agenten in der Gruppe bestimmt und nach dem Zufallsprinzip um den Gewinner herum platziert, wobei das Gesetz der Normalverteilung gilt. Die neuen Konten der Gruppenagenten werden berechnet, und es wird ein neuer Gruppensieger mit dem höchsten Kontostand ermittelt. Informationen über den neuen Gewinner werden auf der Nachrichtentafel der Gruppe veröffentlicht.
Die Dissimilationsoperation steuert die globale Suche. Zunächst werden die Konten aller Gruppen aus dem Schwarzen Brett gelesen. Diese Konten werden dann miteinander verglichen. Ist die Punktzahl der führenden Gruppe geringer als die einer der hinteren Gruppen, so nimmt letztere den Platz des Führenden ein, und die führende Gruppe wird zur hinteren Gruppe. Wenn die Punktzahl einer Gruppe niedriger ist als die aller nachfolgenden Gruppen, wird die Gruppe aus der Grundgesamtheit entfernt. Anstelle von gelöschten Gruppen werden neue Gruppen mit der Initialisierungsoperation initialisiert.
Der MEC-Algorithmus ist also ein Mehrpopulationsalgorithmus, der Initialisierungs-, lokale Konkurrenz- und Dissimilationsoperationen umfasst.
Oben wurde eine allgemeine Beschreibung des einfachen MEC-Algorithmus von den Entwicklern des Algorithmus gegeben. Eine solche Beschreibung erschwert meines Erachtens das Verständnis der Grundsätze, die der Suchstrategie in einem mehrdimensionalen Raum zugrunde liegen. Infolgedessen stellen sich viele Fragen, z. B. „Was ist eine Nachrichtentafel und wie unterscheidet es sich von den Merkmalen bestimmter Personen in einer Gruppe?“ und andere Fragen.
Es wurde bereits gesagt, dass der Algorithmus die menschliche Gesellschaft und die Interaktion zwischen ihren Mitgliedern modelliert. Die einfachste und klarste Art, sich den Begriff „Idee“ vorzustellen, ist, dass es sich um eine wissenschaftliche, künstlerische, literarische oder andere Idee handeln kann. In der Gesellschaft gibt es immer dominante und alternative Ideen. Im Gegensatz zu den Autoren werde ich die Ideen in Bezug auf die Gruppen nicht in „führend“ und „zurückbleibend“ einteilen. Wie wir weiter unten sehen werden, bringt dies dem Algorithmus einige Vorteile gegenüber seiner Grundversion. Da jede Idee mindestens eine These enthält (eine These ist ein optimierter Parameter der Fitnessfunktion), kann eine Idee ideologische Zweige haben, so wie es in der Wissenschaft verschiedene wissenschaftliche Theorien und Bewegungen gibt. Abbildung 1 zeigt schematisch die mit i1, i2 usw. bezeichneten Ideen. Jede Idee kann innerhalb der durch die Denkkraft (ein externer Parameter des Algorithmus) festgelegten Grenzen Verzweigungen erzeugen. Je weiter die Verzweigung von der Idee entfernt ist, desto unwahrscheinlicher ist sie (die Wahrscheinlichkeit und die Grenzen der ideologischen Verzweigungen werden als expandierende konzentrische Kreise dargestellt). Wenn sich die Idee als konsistenter erwiesen hat (der Wert der Fitnessfunktion ist besser) als ihre ideologische Mutter, dann ersetzt dieser Zweig die Mutteridee (die neue Idee als Ergebnis des ideologischen Zweigs ist in der Abbildung als i5 dargestellt). Aus der Abbildung geht hervor, dass es keine Beschränkungen für die Überschreitung ideologischer Grenzen gibt, was bedeutet, dass die Entstehung ideologischer Zweige mit denselben Thesen möglich ist.
Bild 1. Die Ideen i1, i2, i3, i4, ihre Grenzen, die Überschneidungen der Grenzen und das Entstehen einer neuen Idee i5 als Ergebnis der Verzweigung der Idee i1
Die Ideenverzweigung führt zu einem lokalen Wettbewerb innerhalb jeder Idee und bietet eine Suche in der Nähe des lokalen Extremums. Die vielen Verzweigungen aller Ideen stellen eine Multipopulation dar, während eine einzelne Idee und ihre Verzweigungen eine einzelne Population darstellen. Jede Idee speichert nur ihre Thesen und ihren praktischen Wert, und das Nutzerprogramm bezieht sich auf ideologische Zweige und nicht auf die Ideen selbst.
Um eine globale Suche zu gewährleisten, muss sichergestellt werden, dass neue Ideen entstehen, die über die aktuellen Ideen in der Population hinausgehen, da die Ideen sonst in lokalen Extremen stecken bleiben und sich kein besserer Wert der Fitnessfunktion ergibt. Der Prozess der Dissimilation (Zerstörung) ist für diesen Zweck vorgesehen. Für den Austausch von Ideen zwischen der dominanten Gruppe (grüne Farbe) und der alternativen Gruppe (blaue Farbe) wird ein etwas anderes Schema verwendet als im ursprünglichen Algorithmus. Nach der getrennten Sortierung der Ideen in jeder Gruppe entfernen wir die schlechteste aus der dominanten Gruppe und ersetzen sie durch die beste aus der alternativen Gruppe, um so einen ideologischen Austausch zu gewährleisten. Auf den freien Platz in der alternativen Gruppe setzen wir eine neue Idee, die aus den Zusammenfassungen zufällig ausgewählter Ideen aus der dominanten Gruppe (mit Ausnahme der letzten) zusammengestellt wird. Um für Variabilität zu sorgen, kann dieser Aktion eine Zufallskomponente hinzugefügt werden, die ich für mögliche weitere Experimente von Forschern von Optimierungsalgorithmen offen lasse. Die Auswahl von Abstrakten aus den Ideen der dominanten Gruppe erhöht die kombinatorischen Fähigkeiten des Algorithmus. Abbildung 2 zeigt ein Schema für die Ersetzung einer Idee aus einer alternativen Gruppe und die Schaffung einer neuen Idee.
Bild 2. Ersetzen einer Idee aus einer alternativen Gruppe und Schaffung einer neuen Idee
Schreiben wir den MEC-Pseudocode, um das weitere Schreiben des Algorithmuscodes zu vereinfachen:
1.1 Im Falle des ersten Durchlaufs des Algorithmus
1.1.1 Bilde nach dem Zufallsprinzip zwei Gruppen von Ideen entsprechend dem Bereich der Ideen (dominante und alternative)
1.2 Im Falle des zweiten und weiterer Durchläufe des Algorithmus
1.2.1 Damit eine dominante Idee nach dem Levy'schen Gesetz* Verzweigungen hervorbringt, ist eine der Verzweigungen das Ergebnis einer Kombination von Thesen aus den dominanten Ideen.
1.2.2 Eine alternative Idee ist, dass alle Zweige nach dem Levy'schen Gesetz* erzeugt werden.
2 Berechne den Wert der ideologischen Zweige
3.1 Wenn es einen besseren ideologischen Zweig gibt, ersetze die entsprechende Idee
3.2 Sortiere die dominante und die alternative Gruppe getrennt
3.3 Ersetze die schlechteste Idee der dominanten Gruppe durch eine bessere Idee der alternativen Gruppe
3.4 Erstelle anstelle einer leeren Idee in einer alternativen Gruppe eine neue Idee, die auf Elementen der dominanten Gruppe** basiert (alle außer der letzten ersetzten Idee)
* - anstelle der vom Autor vorgeschlagenen Normalverteilung
** - anstelle der vom Autor vorgeschlagenen Thesen
Aus dem Pseudocode ist ersichtlich, dass der ursprüngliche Algorithmus geändert wurde.
Erstens verwenden wir anstelle des von den Autoren des Algorithmus vorgeschlagenen Normalverteilungsgesetzes das Levy-Fluggesetz, was die Forschungs- und Verfeinerungsmöglichkeiten des Algorithmus erhöht hat. Es ist zu beachten, dass das Levy'sche Fluggesetz die Effizienz der einzelnen Optimierungsalgorithmen nicht immer verbessern kann, wenn wir versuchen, es anstelle der Normal- oder Gleichverteilung zu verwenden. Dies ist vor allem auf die Besonderheiten der Suchstrategie des Algorithmus zurückzuführen. Im vorigen Artikel haben wir uns zum Beispiel den Algorithmus des gemischten Froschsprungs (shuffled frog-leaping) angesehen. Ich habe versucht, anstelle der Normalverteilung das Levy'sche Fluggesetz in Froschsprüngen zu verwenden, was jedoch keine spürbaren Verbesserungen der Suchleistung brachte.
Zweitens sieht der ursprüngliche Algorithmus keine kombinatorischen Mechanismen für die Suchstrategie vor. Versuchen wir herauszufinden, warum dies äußerst wichtig ist. Stellen Sie sich zum Beispiel mehrere Körbe mit Aluminiumkugeln (leicht) und einer Goldkugel (schwer) vor. Unsere Aufgabe ist es, Kugeln in einem leeren Korb zu sammeln, sodass sie alle golden sind. Dabei dürfen wir entweder die chemische Zusammensetzung jeder neuen Kugel im Korb sanft verändern, wobei nicht bekannt ist, ob sich dadurch die Masse erhöht, oder wir nehmen einfach zufällig eine Kugel, die in einem der Körbe liegt. Wir wissen, dass eine der Kugeln Gold sein muss, und wir können nur den gesamten Korb wiegen und nicht die einzelnen Kugeln. Sobald wir einen vollen Korb haben, müssen wir ihn wiegen, und die Herausforderung besteht darin, das Gewicht des Korbs zu maximieren. Dieses Problem zeigt, dass wir durch einfache Kombination einen Korb voller goldener Kugeln in viel weniger Schritten sammeln können.
Kommen wir nun zur Beschreibung des Algorithmus-Codes.
Die elementare logische Einheit des Algorithmus ist die Idee, und sie wird auch einen ideologischen Zweig darstellen. Die Struktur S_Idea eignet sich hervorragend für die Beschreibung einer Idee. Dies ist ein Objekt, das Informationen über die Koordinaten und die Eignung einer Idee enthält. Die Struktur verfügt über die Methode Init, um die Fitness mit einem negativen Wert von DBL_MAX zu initialisieren.
//—————————————————————————————————————————————————————————————————————————————— struct S_Idea { void Init (int size) { ArrayResize (c, size); f = -DBL_MAX; } double c []; //coordinates double f; //fitness }; //——————————————————————————————————————————————————————————————————————————————
In der Klasse C_AO_MEC wird der MEC-Algorithmus beschrieben. Es enthält eine Reihe von Variablen und Methoden für die Arbeit mit diesen Variablen.
Klassenvariablen:
- cB: Array mit den besten Koordinaten
- fB: Wert der Fitnessfunktion für die besten Koordinaten
- idBr: Array mit ideologischen Zweigen
- rangeMax: Array mit den maximalen Suchwerten
- rangeMin: Array mit den minimalen Suchwerten
- rangeStep: Array mit Suchschritten
- leadIdeolGroup: Array, das eine führende ideologische Gruppe enthält
- alteIdeolGroup: Array, das eine alternative ideologische Gruppe enthält
- tempIdeolGroup: Array, das eine temporäre ideologische Gruppe enthält
- coordinatesNumber: Anzahl der Koordinaten
- populationSize: Größe der Bevölkerung
- ideasNumber: Anzahl der Ideen
- thoughtPower: Macht der Gedanken
- ideasBr: Anzahl der ideologischen Zweige
- leadIdGroupSize: Größe der führenden ideologischen Gruppe
- alteIdGroupSize: Größe der alternativen ideologischen Gruppe
- vect: Vektor für die Verwendung der Koordinateninkremente
- ind: Array von Indizes
- val: Array von Werten
- revision: Revisions-Flag
Methoden der Klasse:
- Init: Initialisierung einer Klasse mit Übergabe von Parametern
- Moving: eine Bewegung ausführen
- Revision
- Sorting: Sortieren von ideologischen Gruppen
- SeInDiSp: Berechnung des Suchintervalls
- RNDfromCI: Generierung einer Zufallszahl aus einem gegebenen Intervall
//—————————————————————————————————————————————————————————————————————————————— class C_AO_MEC { //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Idea idBr []; //ideological branches public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: void Init (const int coordinatesNumberP, //coordinates number const int populationSizeP, //population size const int ideasNumberP, //ideas number const double thoughtPowerP); //thought power public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: S_Idea leadIdeolGroup []; //leading ideological group private: S_Idea alteIdeolGroup []; //alternative ideological group private: S_Idea tempIdeolGroup []; //temporal ideological group private: int coordinatesNumber; //coordinates number private: int populationSize; //population size private: int ideasNumber; //ideas number private: double thoughtPower; //thought power private: int ideasBr; //number of ideological branches private: int leadIdGroupSize; //leading ideological group size private: int alteIdGroupSize; //alternative ideological group size private: double vect []; //vector private: int ind []; private: double val []; private: bool revision; private: void Sorting (S_Idea &ideas []); private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max); }; //——————————————————————————————————————————————————————————————————————————————
Die Initialisierungsmethode Init führt die folgenden Aktionen durch:
- Zu Beginn des Codes wird der Anfangswert des Zufallszahlengenerators festgelegt und die Variable fB auf den Mindestwert vom Typ „double“ gesetzt.
- Anschließend werden die Variablen coordinatesNumber, populationSize, ideasNumber und thoughtPower auf die Werte gesetzt, die der Funktion Init übergeben wurden.
- Die Werte von ideasBr, leadIdGroupSize und alteIdGroupSize werden auf der Grundlage der Werte von populationSize und ideasNumber berechnet.
- Die Arrays rangeMax, rangeMin, rangeStep, vect, ind, val, tempIdeolGroup und cB werden mit der Funktion ArrayResize in der Größe verändert.
- Die Objekte der Klasse Ideologie werden dann in den Arrays leadIdeolGroup und alteIdeolGroup mit Hilfe von ‚for‘-Schleifen und der Init-Funktion erstellt.
- Ideologieklassen-Objekte werden als Nächstes im idBr-Array mithilfe der ‚for‘-Schleife und der Init-Funktion erstellt.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MEC::Init (const int coordinatesNumberP, //coordinates number const int populationSizeP, //population size const int ideasNumberP, //ideas number const double thoughtPowerP) //thought power { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; revision = false; coordinatesNumber = coordinatesNumberP; populationSize = populationSizeP; ideasNumber = ideasNumberP; thoughtPower = thoughtPowerP; ideasBr = populationSize / ideasNumber; leadIdGroupSize = ideasNumber / 2; alteIdGroupSize = ideasNumber - leadIdGroupSize; ArrayResize (rangeMax, coordinatesNumber); ArrayResize (rangeMin, coordinatesNumber); ArrayResize (rangeStep, coordinatesNumber); ArrayResize (vect, coordinatesNumber); ArrayResize (ind, alteIdGroupSize, alteIdGroupSize); ArrayResize (val, alteIdGroupSize, alteIdGroupSize); ArrayResize (tempIdeolGroup, alteIdGroupSize, alteIdGroupSize); ArrayResize (cB, coordinatesNumber); ArrayResize (leadIdeolGroup, leadIdGroupSize); for (int i = 0; i < leadIdGroupSize; i++) leadIdeolGroup [i].Init (coordinatesNumber); ArrayResize (alteIdeolGroup, alteIdGroupSize); for (int i = 0; i < alteIdGroupSize; i++) alteIdeolGroup [i].Init (coordinatesNumber); ArrayResize (idBr, populationSize); for (int i = 0; i < populationSize; i++) idBr [i].Init (coordinatesNumber); } //——————————————————————————————————————————————————————————————————————————————
Die Methode der Schaffung von Moving (beweglichen) ideologischen Zweigen entspricht der Kernlogik der MEC-Suchstrategie. Ein Teil des Codes wird nur bei der ersten Iteration des Algorithmus ausgeführt, der Rest des Codes wird bei jeder Iteration ausgeführt.
In der ersten Iteration ist es notwendig, einen Vektor zu initialisieren, der mit Werten gefüllt wird, die auf der Grundlage der Reichweite und der Denkkraft berechnet werden (dies ist das Inkrement während der Verzweigung), und Ideen in zwei Gruppen zu erstellen - dominante und alternative. Dazu werden wir die Ideen beider Gruppen (sie sind gleichwertig) mit gleicher Wahrscheinlichkeit über das gesamte Suchfeld streuen.
//============================================================================ if (!revision) { fB = -DBL_MAX; int cnt = 0; for (int c = 0; c < coordinatesNumber; c++) vect [c] = (rangeMax [c] - rangeMin [c]) * thoughtPower; //-------------------------------------------------------------------------- for (int i = 0; i < leadIdGroupSize; i++) { for (int c = 0; c < coordinatesNumber; c++) { coord = RNDfromCI (rangeMin [c], rangeMax [c]); leadIdeolGroup [i].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]); } leadIdeolGroup [i].f = -DBL_MAX; } //-------------------------------------------------------------------------- for (int i = 0; i < alteIdGroupSize; i++) { for (int c = 0; c < coordinatesNumber; c++) { coord = RNDfromCI (rangeMin [c], rangeMax [c]); alteIdeolGroup [i].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]); } alteIdeolGroup [i].f = -DBL_MAX; } revision = true; }
Außerdem werden wir in der ersten und den folgenden Iterationen ideologische Zweige erzeugen, da wir die Ideen selbst bereits geschaffen haben. Wir interessieren uns gerade für die ideologischen Zweige, die wir mit Hilfe der Fitnessfunktion bewerten können.
Die wichtigste Operation zur Schaffung eines Zweiges ist die Aufgabe, sich zu den abstrakten Ideen nach dem Levy'schen Fluggesetz mit Normalisierung durch den Koeffizienten der Denkkraft zu bewegen. Wir tun dies für alle Ideen der alternativen Gruppe und für alle Ideen der dominanten Gruppe, mit Ausnahme der letzten Idee, gemäß der Gleichung:
coord = leadIdeolGroup [i].c [c] + r1 * vect [c] * pow (r2, -2.0);
Für die letzte Idee der dominanten Gruppe wählen wir zufällig eine Idee aus dieser Gruppe aus und nehmen die These des entsprechenden Indexes:
r1 = RNDfromCI (0.0, leadIdGroupSize - 1); idBr [cnt].c [c] = leadIdeolGroup [(int)r1].c [c];
Im Folgenden finden Sie den vollständigen Code zur Erstellung von ideologischen Zweigen für beide Gruppen:
//---------------------------------------------------------------------------- for (int i = 0; i < leadIdGroupSize; i++) { for (int b = 0; b < ideasBr; b++) { if (b < ideasBr -1) { for (int c = 0; c < coordinatesNumber; c++) { r1 = RNDfromCI (0.0, 1.0); r1 = r1 > 0.5 ? 1.0 : -1.0; r2 = RNDfromCI (1.0, 20.0); coord = leadIdeolGroup [i].c [c] + r1 * vect [c] * pow (r2, -2.0); idBr [cnt].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]); } } else { for (int c = 0; c < coordinatesNumber; c++) { r1 = RNDfromCI (0.0, leadIdGroupSize - 1); idBr [cnt].c [c] = leadIdeolGroup [(int)r1].c [c]; } } cnt++; } } //---------------------------------------------------------------------------- for (int i = 0; i < alteIdGroupSize; i++) { for (int b = 0; b < ideasBr; b++) { for (int c = 0; c < coordinatesNumber; c++) { r1 = RNDfromCI (0.0, 1.0); r1 = r1 > 0.5 ? 1.0 : -1.0; r2 = RNDfromCI (1.0, 20.0); coord = alteIdeolGroup [i].c [c] + r1 * vect [c] * pow (r2, -2.0); idBr [cnt].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]); } cnt++; } }
Die Methode Revision dient der Überarbeitung von Ideen auf der Grundlage der Ergebnisse der Bewertung ihrer ideologischen Zweige sowie der Aktualisierung der Indikatoren für die Gesamtlösung. Der Code führt die folgenden Schritte aus:
1. Die Variablen cnt und pos werden initialisiert.
2. Ersetzen der besten Ideen: Die Suche nach dem besten ideologischen Zweig aus dem globalen Zweig (idBr) erfolgt in der Schleife für jeden Anführer in der Anführer-Gruppe (leadIdeolGroup). Für jeden Zweig wird geprüft, ob der Wert der Fitnessfunktion (f) größer ist als der Wert des aktuellen Leiters, dann wird die Position (pos) gleich dem aktuellen Index (cnt) gesetzt. Wenn eine bessere Idee gefunden wird, werden der Funktionswert und die Führungskoordinaten mit den Werten dieser Idee aktualisiert. Wenn der Merkmalswert der neuen Idee ebenfalls größer ist als der aktuelle beste Merkmalswert (fB), werden auch fB und die Koordinaten der besten Idee (cB) aktualisiert.
3. Dasselbe gilt für die Gruppe der Alternativlösungen (alteIdeolGroup).
4. Sortierung der Ideengruppen: Gruppen von Leitideen und alternativen Ideen werden in absteigender Reihenfolge nach dem Wert der Fitnessfunktion sortiert.
5. Ersetzen der schlechtesten Idee: Die schlechteste Idee der Leader-Gruppe (leadIdeolGroup) wird durch die beste Idee der Gruppe der Alternativlösungen (alteIdeolGroup) ersetzt.
6. Erstellung einer neuen Idee: Für jede Koordinate (c) in der Gruppe der alternativen Lösungen (alteIdeolGroup) wird eine neue Idee auf der Grundlage der Elemente der dominierenden Gruppe (leadIdeolGroup) erstellt. Der Koordinator wird nach dem Zufallsprinzip aus der dominanten Gruppe der Anführer ausgewählt.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MEC::Revision () { int cnt = 0; int pos = -1; //---------------------------------------------------------------------------- //4. If there is a better ideological branch, replace the corresponding idea for (int i = 0; i < leadIdGroupSize; i++) { pos = -1; for (int b = 0; b < ideasBr; b++) { if (idBr [cnt].f > leadIdeolGroup [i].f) pos = cnt; cnt++; } if (pos != -1) { leadIdeolGroup [i].f = idBr [pos].f; ArrayCopy (leadIdeolGroup [i].c, idBr [pos].c, 0, 0, WHOLE_ARRAY); if (idBr [pos].f > fB) { fB = idBr [pos].f; ArrayCopy (cB, idBr [pos].c, 0, 0, WHOLE_ARRAY); } } } //---------------------------------------------------------------------------- for (int i = 0; i < alteIdGroupSize; i++) { pos = -1; for (int b = 0; b < ideasBr; b++) { if (idBr [cnt].f > alteIdeolGroup [i].f) pos = cnt; cnt++; } if (pos != -1) { alteIdeolGroup [i].f = idBr [pos].f; ArrayCopy (alteIdeolGroup [i].c, idBr [pos].c, 0, 0, WHOLE_ARRAY); if (idBr [pos].f > fB) { fB = idBr [pos].f; ArrayCopy (cB, idBr [pos].c, 0, 0, WHOLE_ARRAY); } } } //---------------------------------------------------------------------------- //5. Sort two groups of ideas. Sorting (leadIdeolGroup); Sorting (alteIdeolGroup); //---------------------------------------------------------------------------- //6. Replace the worst idea of the first group with the best idea from the second group leadIdeolGroup [leadIdGroupSize - 1] = alteIdeolGroup [0]; //---------------------------------------------------------------------------- //7. Instead of an empty idea, create a new idea based on elements of the dominant group double rnd = 0.0; double coord = 0.0; for (int c = 0; c < coordinatesNumber; c++) { rnd = RNDfromCI (0.0, leadIdGroupSize - 2); alteIdeolGroup [0].c [c] = leadIdeolGroup [(int)rnd].c [c]; } } //——————————————————————————————————————————————————————————————————————————————
3. Testergebnisse
Ausdruck der Funktionsweise des Mind Evolution Algorithmus auf einem Prüfstand:
=============================
5 Rastrigin's; Func runs 10000 result: 78.73205273291103
Ergebnis: 0.97553
25 Rastrigin's; Func runs 10000 result: 58.554840607439516
Ergebnis: 0.72553
500 Rastrigin's; Func runs 10000 result: 42.32395504312925
Ergebnis: 0.52442
=============================
5 Forest's; Funktion läuft 10000 Ergebnis: 1.2024830541165685
Ergebnis: 0.68018
25 Forest's; Funktion läuft 10000 Ergebnis: 0.4588423143844061
Ergebnis: 0.25954
500 Forest's; Func runs 10000 result: 0.08756810826330522
Ergebnis: 0.04953
=============================
5 Megacity's; Func runs 10000 result: 5.279999999999999
Ergebnis: 0.44000
25 Megacity's; Func runs 10000 result: 2.048
Ergebnis: 0.17067
500 Megacity's; Func runs 10000 result: 0.4364
Ergebnis: 0.03637
=============================
All score: 3.86178
MEC mit der Testfunktion Rastrigin.
MEC mit der Testfunktion Forest.
MEC mit der Testfunktion Megacity.
Bei der Analyse der Rangliste der Optimierungsalgorithmus-Testergebnisse ist festzustellen, dass der MEC-Algorithmus eine sehr hohe Leistung erzielt und einen ehrenvollen fünften Platz einnimmt. MEC zeigt hervorragende Ergebnisse bei den Funktionen Rastrigin, Forest und Megacity, trotz der völlig unterschiedlichen Oberfläche dieser Testfunktionen. Besonders beeindruckende Ergebnisse werden mit der Funktion Megacity mit 10 Parametern erzielt. Es ist jedoch erwähnenswert, dass MEC bei Funktionen mit weniger optimierten Parametern eine noch höhere Effizienz aufweist als die anderen Teilnehmer der vergleichenden Analyse. Dies ist eher ein Nachteil.
| # | AO | Beschreibung | Rastrigin | Rastrigin final | Forest | Forest final | Megacity (diskret) | Megacity final | Final result | ||||||
| 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 | SSG | Setzen, Säen und Wachsen | 1.00000 | 1.00000 | 0.55665 | 2.55665 | 0.72740 | 0.94522 | 1.00000 | 2.67262 | 0.76364 | 0.85977 | 1.00000 | 2.62340 | 100000 |
| 2 | HS | Harmoniesuche | 0.99676 | 0.95282 | 0.48178 | 2.43136 | 1.00000 | 0.98931 | 0.44806 | 2.43736 | 1.00000 | 1.00000 | 0.41537 | 2.41537 | 92.329 |
| 3 | ACOm | Ameisen-Kolonie-Optimierung M | 0.34611 | 0.17985 | 0.17044 | 0.69640 | 0.86888 | 1.00000 | 0.77362 | 2.64249 | 1.00000 | 0.88930 | 0.05606 | 1.94536 | 65.347 |
| 4 | IWO | Optimierung mit invasiven Unkräutern | 0.95828 | 0.67083 | 0.29807 | 1.92719 | 0.70773 | 0.46349 | 0.31773 | 1.48896 | 0.80000 | 0.42067 | 0.33289 | 1.55356 | 61.104 |
| 5 | MEC | mind evolutionary computation | 0.99270 | 0.51040 | 0.22800 | 1.73110 | 0.60762 | 0.40658 | 0.25459 | 1.26880 | 0.93335 | 0.41328 | 0.26170 | 1.60833 | 56.227 |
| 6 | COAm | Kuckuck-Optimierungsalgorithmus M | 0.92400 | 0.46794 | 0.26004 | 1.65199 | 0.58378 | 0.34034 | 0.16526 | 1.08939 | 0.72727 | 0.33025 | 0.17083 | 1.22835 | 47.612 |
| 7 | FAm | Firefly-Algorithmus M | 0.59825 | 0.33980 | 0.17135 | 1.10941 | 0.51073 | 0.42299 | 0.49790 | 1.43161 | 0.34545 | 0.28044 | 0.35258 | 0.97847 | 41.537 |
| 8 | ABC | Künstliches Bienenvolk (Artificial Bee Colony, ABC) | 0.78170 | 0.32715 | 0.20822 | 1.31707 | 0.53837 | 0.21455 | 0.13344 | 0.88636 | 0.56364 | 0.26569 | 0.13926 | 0.96858 | 36.849 |
| 9 | GSA | Algorithmus für die Schwerkraftsuche | 0.70167 | 0.45217 | 0.00000 | 1.15384 | 0.31660 | 0.36416 | 0.33204 | 1.01280 | 0.59395 | 0.35054 | 0.00000 | 0.94448 | 36.028 |
| 10 | BA | Fledermaus-Algorithmus | 0.40526 | 0.63761 | 0.84451 | 1.88738 | 0.20841 | 0.17477 | 0.25989 | 0.64308 | 0.29698 | 0.09963 | 0.17371 | 0.57032 | 35.888 |
| 11 | BFO | Optimierung der bakteriellen Futtersuche | 0.67203 | 0.30963 | 0.11813 | 1.09979 | 0.39702 | 0.26623 | 0.20652 | 0.86976 | 0.52122 | 0.33211 | 0.18932 | 1.04264 | 34.693 |
| 12 | EM | elektromagnetismusähnlicher Algorithmus | 0.12235 | 0.46278 | 1.00000 | 1.58513 | 0.00000 | 0.03498 | 0.34880 | 0.38377 | 0.00000 | 0.00000 | 0.10924 | 0.10924 | 22.091 |
| 13 | SFL | schlurfender Froschsprung | 0.40072 | 0.23739 | 0.26548 | 0.90360 | 0.20153 | 0.04147 | 0.02652 | 0.26952 | 0.27273 | 0.05535 | 0.06639 | 0.39446 | 15.203 |
| 14 | MA | Affen-Algorithmus | 0.33192 | 0.33451 | 0.14644 | 0.81287 | 0.10012 | 0.07891 | 0.08932 | 0.26836 | 0.21818 | 0.04243 | 0.10720 | 0.36781 | 13.603 |
| 15 | FSS | Fischschulsuche | 0.46812 | 0.25337 | 0.11302 | 0.83451 | 0.12840 | 0.05013 | 0.06516 | 0.24369 | 0.16971 | 0.04796 | 0.08283 | 0.30050 | 12.655 |
| 16 | PSO | Partikelschwarmoptimierung | 0.20449 | 0.08200 | 0.07160 | 0.35809 | 0.18895 | 0.10486 | 0.21738 | 0.51119 | 0.23636 | 0.05903 | 0.01957 | 0.31496 | 10.031 |
| 17 | RND | zufällig | 0.16826 | 0.09743 | 0.08019 | 0.34589 | 0.13496 | 0.04810 | 0.04715 | 0.23021 | 0.16971 | 0.03875 | 0.04922 | 0.25767 | 5.302 |
| 18 | GWO | Grauer-Wolf-Optimierung | 0.00000 | 0.00000 | 0.02256 | 0.02256 | 0.06570 | 0.00000 | 0.00000 | 0.06570 | 0.32727 | 0.07378 | 0.02557 | 0.42663 | 1.000 |
Zusammenfassung
Der Algorithmus Mind Evolutionary Computation (MEC) ist eine effiziente und leistungsstarke Optimierungsmethode, die auf den Prinzipien der biologischen Evolution beruht. Sie hat eine Reihe von bedeutenden Vorteilen, die sie für die Lösung komplexer Optimierungsprobleme attraktiv machen.
Der Algorithmus der Evolution des Geistes kann auf ein breites Spektrum von Problemen angewandt werden, darunter funktionale Optimierung, Suche nach optimalen Parameterwerten, maschinelles Lernen und andere. Es erfordert keine Kenntnis der analytischen Form der Zielfunktion und kann mit kontinuierlichen, diskreten oder kombinatorischen Lösungsräumen arbeiten.
MEC lässt sich leicht parallelisieren, sodass mehrere Rechenressourcen genutzt werden können, um den Optimierungsprozess zu beschleunigen. Dies ist besonders nützlich, wenn Sie mit Problemen arbeiten, die viele Berechnungen oder Iterationen erfordern.
MEC hat eine gewisse Tendenz, in lokalen Extrema stecken zu bleiben, aber dieser Nachteil manifestiert sich hauptsächlich bei diskreten und sägezahnähnlichen Funktionen. Beim Entwurf einer Fitnessfunktion kann dieser Nachteil als unbedeutend angesehen werden.
MEC ist relativ gut für Probleme geeignet, bei denen der Lösungsraum eine hohe Dimension aufweist. Der Algorithmus ist noch nicht umfassend untersucht worden und kann noch verbessert werden.
Im Allgemeinen ist der MEC-Algorithmus ein leistungsstarkes Optimierungswerkzeug, das sich durch Flexibilität, Vielseitigkeit und eine gute Ausarbeitung lokaler Extrema auszeichnet. Diese Vorteile machen sie zu einer attraktiven Wahl für die Lösung komplexer Optimierungsprobleme in verschiedenen Bereichen. Die Einfachheit der Algorithmuslogik kann besonders bei kundenspezifischen, nicht standardisierten Softwarelösungen von Nutzen sein.
Zur besseren Veranschaulichung der Vor- und Nachteile der einzelnen Algorithmen kann die obige Tabelle anhand der Farbskala in Abbildung 3 dargestellt werden.
Abb. 3. Farbabstufung der Algorithmen gemäß den einschlägigen Tests
Das Histogramm der Algorithmus-Testergebnisse finden Sie unten (auf einer Skala von 0 bis 100, je mehr, desto besser, im Archiv finden Sie ein Skript zur Berechnung der Bewertungstabelle nach der in diesem Artikel beschriebenen Methode):
Abb. 4. Histogramm der Endergebnisse der Testalgorithmen
Vor- und Nachteile des MEC:
1. Minimale Anzahl externer Parameter.
2. Hohe Effizienz bei der Lösung einer Vielzahl von Problemen.
3. Geringe Belastung der Computerressourcen.
4. Leichte Umsetzung.
Nachteile
1. Hängenbleiben bei Funktionen mit flachen horizontalen „Orten“.
Jeder Artikel verfügt über ein Archiv, das aktualisierte aktuelle Versionen der Algorithmuscodes für alle früheren Artikel enthält. Es sei jedoch darauf hingewiesen, dass ich nicht für die absolute Genauigkeit bei der Beschreibung der kanonischen Algorithmen verantwortlich bin. Ich füge oft meine eigenen Ideen und Verbesserungen hinzu, die auf meinen Erfahrungen und persönlichen Meinungen beruhen. Die in den Artikeln dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Versuche.
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/13432
Einführung in MQL5 (Teil 1): Ein Leitfaden für Einsteiger in den algorithmischen Handel
Beherrschen der Modellinterpretation: Gewinnen Sie tiefere Einblicke in Ihren Machine Learning-Modelle
Entwurfsmuster in der Softwareentwicklung und MQL5 (Teil 2): Strukturelle Muster
Neuronale Netze leicht gemacht (Teil 58): Decision Transformer (DT)
- 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.