Algorithmen zur Optimierung mit Populationen: Shuffled Frog-Leaping Algorithmus (SFL)

MetaTrader 5 — Beispiele | 15 Februar 2024, 11:32

133

Andrey Dik

Inhalt

1. Einführung
2. Der Algorithmus
3. Testergebnisse

1. Einführung

Der Shuffled-Frog-Leaping-Algorithmus (SFL) wurde von М. Eusuff und anderen Autoren im Jahr 2003 vorgeschlagen. Dieser Algorithmus kombiniert die Prinzipien des memetischen Algorithmus und des Partikelschwarm-Algorithmus, und sein Design wurde durch das Verhalten einer Gruppe von Fröschen bei der Nahrungssuche inspiriert.

Der SFL-Algorithmus wurde ursprünglich als metaheuristische Methode zur Lösung von kombinatorischen Optimierungsproblemen entwickelt. Sie basiert auf der Verwendung mathematischer Funktionen und einer fundierten heuristischen Suche.

Der SFL-Algorithmus besteht aus mehreren interagierenden virtuellen Froschpopulationen, den sogenannten Memeplexen. Virtuelle Frösche fungieren als Wirte oder Träger von Memen, wobei ein Mem eine Einheit der kulturellen Evolution darstellt. Jeder Memeplex wird einer unabhängigen lokalen Suche unterzogen, wobei eine Methode ähnlich der Partikelschwarm-Optimierung angewandt wird, bei der jedoch der Schwerpunkt auf der lokalen Suche liegt.

Um die globale Exploration zu unterstützen, werden die virtuellen Frösche in regelmäßigen Abständen neu gemischt und in neue Memeplexe umorganisiert, wobei eine dem Algorithmus „Shuffled Complex Evolution“ ähnliche Methode verwendet wird. Außerdem werden zufällige, virtuelle Frösche generiert und in der Population ersetzt, um eine zufällige Generierung von besseren Informationen zu ermöglichen.

Das Shuffled-Frog-Leaping ist eine effektive Methode zur Lösung komplexer Optimierungsprobleme. Es kann in verschiedenen Anwendungsbereichen optimale Lösungen erzielen. In diesem Artikel werden wir die Grundprinzipien und Anwendungen dieses Algorithmus sowie seine Vorteile und Grenzen erläutern.

2. Der Algorithmus

Memetik ist ein Ansatz für Modelle der evolutionären Informationsübertragung, der auf dem Konzept der Meme basiert. Meme sind Analoga von Genen und dienen als kulturelle Informationseinheiten, die durch Nachahmung, Lernen und andere Mittel zwischen Menschen verbreitet werden. Das Konzept des Mems und die Grundlagen der Memetik wurden von C.R. Dawkins im Jahr 1976 entwickelt. Meme können vertikal weitergegeben werden - von Vorgängern, Eltern, Erziehern, Büchern, kulturellen Artefakten usw. Auch eine horizontale Übertragung von Memen von Mensch zu Mensch und von Kultur zu Kultur ist möglich. Auch wenn es sich bei Memen um reine Informationen handelt, führt ihre Funktionsweise zu erheblichen Veränderungen im menschlichen Verhalten.

Memetische Algorithmen (M-Algorithmen) sind definiert als hybride metaheuristische Algorithmen zur Suchmaschinenoptimierung, die auf dem Konzept des Mems und dem neodarwinistischen Evolutionsprinzip basieren. Im Zusammenhang mit M-Algorithmen ist ein Mem eine Implementierung eines lokalen Optimierungsalgorithmus, der aktuelle Lösungen bei jeder Iteration oder nach einer bestimmten Anzahl von Iterationen verfeinert. M-Algorithmen können als Hybridisierung eines der populationsbasierten globalen Suchalgorithmen und eines oder mehrerer klassischer oder populationsbasierter lokaler Optimierungsalgorithmen betrachtet werden. Ursprünglich wurden M-Algorithmen als eine der Möglichkeiten zur Steigerung der Effizienz von genetischen Algorithmen vorgeschlagen.

Die Effizienz von M-Algorithmen hängt weitgehend von den Werten ihrer freien Parameter ab. Eine Reihe von Studien hat gezeigt, dass die Wahl der verwendeten Meme einen sehr großen Einfluss auf die Effizienz dieser Algorithmen hat. Daher nimmt dieses Problem einen der zentralen Plätze in den Arbeiten über M-Algorithmen ein.

Meme sind eine der revolutionären Ideen, die die Ähnlichkeit zwischen der Evolution der Gene und der Evolution der menschlichen Kultur nahelegen. Nach Dawkins ist ein Mem eine Einheit des kulturellen Austauschs, das Äquivalent eines Gens in der Kultur. Ein Meme kann eine Geste, ein Wort oder eine Idee sein. Jede kulturelle Informationseinheit, die durch Nachahmungslernen von Mensch zu Mensch übertragen werden kann, ist ein Mem.

Memetische Algorithmen imitieren im Gegensatz zu genetischen Algorithmen den Prozess der kulturellen Evolution. Moscatos Ansatz verwendet eine Analogie mit der Evolution von Memen. Der memetische Algorithmus besteht aus den folgenden Phasen: lokale Suche, Kooperation, Wettbewerb und Suchabbruchkriterium. Eine memetische Klasse ist eine breite Klasse von Algorithmen, die durch eine gemeinsame Idee vereint sind: die Einbeziehung des individuellen Lernens von Individuen in den genetischen Algorithmus und die Nutzung von Informationen über die Struktur des Raums möglicher Lösungen. Das Problem des Gleichgewichts zwischen Population und lokaler Suche kann als ein allgemeines Problem der Aufrechterhaltung des Gleichgewichts zwischen extensiver und intensiver Erkundung des Suchraums betrachtet werden.

Der memetische Algorithmus umfasst im Wesentlichen die folgenden Komponenten:

1. Lokale Suche. Zur Umsetzung können wir ein simuliertes Annealing und Lifting-Algorithmen verwenden.
2. Zusammenarbeit. Der Informationsaustausch zwischen den Individuen kann durch ein Verfahren erfolgen, das der Verwendung des Zwei-Punkt-Kreuzungsoperators in genetischen Algorithmen ähnelt.
3. Wettbewerb. Die Auswahl ist ähnlich wie bei genetischen Algorithmen und besteht in der Regel darin, die fittesten Individuen in der Population auszuwählen und die weniger fitten auszuschließen.
4. Endkriterium der Suche. Bei memetischen Algorithmen kann dies neben der Zählung der Iterationen und der Bewertung der Verbesserung des Ergebnisses auch die Schätzung der Vielfalt der Individuen beinhalten.

Memetische Algorithmen sind eine breite Klasse von Algorithmen, die durch die gemeinsame Idee des individuellen Lernens von Individuen und der Nutzung von Informationen über die Struktur des Raums möglicher Lösungen vereint sind.

Meme sind wie Gene Replikatoren, d. h. Objekte, die sich selbst reproduzieren können. Das Überleben und die Reproduktion von Memen hängen von der Anwesenheit eines Wirts ab, der das Mem verbreitet. Meme können sich verändern, neue Meme bilden und sich am Kampf um Ressourcen - die Köpfe der Menschen - beteiligen.

Meme werden oft zu Komplexen oder Memeplexen kombiniert, um den Kampf um die Träger zu verstärken. Memeplexe sind vergleichbar mit den symbiotischen Ansammlungen von Genen, die den genetischen Code biologischer Organismen bilden. Ein Beispiel für einen Memeplex ist die Religion. Memeplexe haben einen tiefgreifenden Einfluss auf die Gestaltung des individuellen und sozialen Verhaltens.

Gehen wir direkt zum Shuffled-Frog-Leaping-Algorithmus über. Die Hauptidee des Algorithmus besteht darin, die gesamte Froschpopulation mit einem globalen Anführer G in Meme zu unterteilen. Jedes Mem (Gruppe) hat einen Anführer L (Abbildung 1).

Frösche1

Bild 1. Eine Population von Fröschen mit einem globalen Anführer (G), aufgeteilt in Meme mit ihrem lokalen Anführer (L)

Innerhalb eines Mems neigen die Frösche dazu, sich in Richtung des lokalen Anführers zu bewegen. Die Führung wird aktualisiert, wenn sich die Position eines der Frösche verbessert. Meme sind im Suchraum nicht getrennt und können sich überschneiden. So kann ein Frosch, der sich im Gebiet eines Mems befindet, durchaus zu einem anderen gehören. Dadurch entsteht ein dynamisches Umfeld, in dem sich Frösche räumlich von einem Mem zu einem anderen bewegen können, je nachdem, wie sich ihre Position im Suchraum verändert.

Wir betrachten ein globales bedingtes Optimierungsproblem, bei dem die Fitnessfunktion maximiert werden muss. Der SFL-Algorithmus umfasst die folgenden grundlegenden Schritte.

1.0 Initialisierung des Algorithmus
1.1 Schaffung einer Anfangspopulation von Fröschen mit zufälligen Koordinaten.
1.2 Bestimmung der Fitness der einzelnen Frösche.
1.3 Bildung von Memeplexen (Teilpopulationen), Verteilung der Frösche auf die Memeplexe.

2.0 Zyklus der Suche nach der optimalen Lösung
2.1 Für jedes Memeplex:
    2.1.1 Bestimmen des besten Frosches.
    2.1.2 Bewegen der verbleibenden Frösche in Richtung des besten Frosches im Memeplex.
2.2 Wenn das Umsetzen des Frosches seine Fitness nicht verbessert:
    2.2.1 Bewegung von ihm in Richtung des global besseren Frosches.
    2.2.2 Wenn sich die Fitness dadurch nicht verbessert, muss der Frosch an eine beliebige Stelle auf dem Spielfeld gesetzt werden.

3.0 Messung der Fitness von Fröschen
3.1 Messung der Fitness für jeden Frosch in der Population.
3.2 Aktualisieren der Informationen über den besten Frosch in jedem Memeplex und in der Population als Ganzes.

4.0 Ermittlung des global besten Frosches und Aktualisierung der Memeplexe
4.1 Bestimmen des global besten Frosches für die gesamte Population.
4.2 Wenn dies der letzte Zyklus ist:
    4.2.1 Zurücksetzen des Memeplex-Zykluszählers.
    4.2.2 Generieren der Zufallsindizes der Frösche.
    4.2.3 Kopieren von Fröschen in Memeplexe unter Verwendung neuer Indizes.
    4.2.4 Bestimmen des besten Frosches in jedem Memeplex.
    4.2.5 Zurücksetzen von Fitness und Schritt der Frösche.
4.3 Wenn dies nicht der letzte Zyklus ist:
    4.3.1 Kopieren der Fitness und der Koordinaten der Frösche aus der Population in die entsprechenden Memeplex-Frösche.
    4.3.2 Bestimmen des besten Frosches in jedem Memeplex.
    4.3.3 Bestimmen der Richtung des nächsten Sprungs für jeden Frosch in Abhängigkeit von seiner Fitness.

Die Grundlage des SFL-Algorithmus ist also eine Kombination aus lokaler Suche innerhalb der einzelnen Memeplexe und globaler Suche durch Austausch von Informationen über die Positionen der besten Memeplex-Agenten.
Dieser Algorithmus ist eine Abwandlung des SFL-Algorithmus, bei dem sich der Agent in der Phase der lokalen Suche nicht genau in die Richtung des besten Agenten des entsprechenden Memeplexes bewegt, sondern in eine zufällig gestörte Richtung. Es sind sowohl sequentielle als auch parallele Hybridisierungen des Algorithmus mit vielen Populationsalgorithmen bekannt (einschließlich des Algorithmus des künstlichen Immunsystems).

Frosch2

Bild 2. Frosch springt. Wenn die vorherige Bewegung erfolglos war, wird der nächste Sprung von der gleichen Stelle aus durchgeführt.

Die logische Einheit des SFL-Optimierungsalgorithmus ist der Frosch. Sie kann durch die Struktur S_Frog beschrieben werden, die einen Agenten im Suchraum darstellt.

Die Struktur S_Frog enthält die folgenden Felder:

c - Array mit den Koordinaten der aktuellen Position des Frosches.
cPrev - Array mit den Koordinaten der vorherigen Position des Frosches.
f - Fitnessfunktion für die aktuelle Position des Frosches.
fPrev - Fitnessfunktion für die vorherige Position des Frosches.
frogStep - Nummer der Stufe, auf der sich der Frosch befindet.

//——————————————————————————————————————————————————————————————————————————————
struct S_Frog
{
  void Init (int coords)
  {
    ArrayResize (c,     coords);
    ArrayResize (cPrev, coords);
    f        = -DBL_MAX;
    fPrev    = -DBL_MAX;
    frogStep = 0;
  }
  double c     []; //coordinates
  double cPrev []; //previous coordinates
  double f;        //fitness
  double fPrev;    //previous fitness
  int    frogStep; //frog step
};
//——————————————————————————————————————————————————————————————————————————————

Die Struktur S_Memeplex beschreibt das Memeplex im Algorithmus. Sie enthält die folgenden Felder:

frogs - Array von Fröschen, die den Memeplex bilden.
fBest - bester Wert der Fitnessfunktion unter allen Fröschen im Memeplex.
cBest - Array von Koordinaten, die dem besten Wert der Fitnessfunktion im Memeplex entsprechen.

//——————————————————————————————————————————————————————————————————————————————
struct S_Memeplex
{
  S_Frog frogs [];
  double fBest;     //best fitness
  double cBest [];  //best coordinates
};
//——————————————————————————————————————————————————————————————————————————————

Die Klasse C_AO_SFL bietet Methoden zur Initialisierung des Algorithmus, zum Verschieben von Fröschen und zur Überarbeitung der Population. Sie enthält auch Hilfsmethoden zur Konvertierung von Werten und zur Erzeugung von Zufallszahlen.

Schreiben wir die SFL-Algorithmusklasse, die die folgenden Felder enthält:

cB - Array zur Speicherung der besten Koordinaten;
fB - Variable, die den Wert der Fitnessfunktion für die besten Koordinaten speichert;
frogs - Array, das alle Frösche in der Population speichert;
mems - Array zur Speicherung von Memeplexen (Gruppen von Fröschen);
rangeMax - Array, das die Höchstwerte für jede Suchkoordinate speichert;
rangeMin - Array zur Speicherung der Mindestwerte für jede Suchkoordinate;
rangeStep - Array, das die Suchschritte für jede Koordinate speichert.

Öffentliche Methoden der Klasse:

Init - Methode zur Initialisierung der Algorithmusparameter akzeptiert die folgenden Parameter:
coordinatesNumberP - Anzahl der Suchkoordinaten;
populationSizeP - Populationsgröße (Anzahl der Frösche);
numbMemsP - Anzahl der Memeplexe (Gruppen von Fröschen);
numbCyclesP - Anzahl der Zyklen im Memeplex;
frogStepsToLocalMaxP - Anzahl der Froschschritte bis zum lokalen Maximum;
movConstantP - Verschiebungskonstante (Suchschritt) der Frösche.

Moving - Methode, die die Bewegung der Frösche im Suchraum implementiert.
Revision - Methode, die eine Revision der Froschpopulation implementiert und die besten Koordinaten aktualisiert.
SeInDiSp - Hilfsmethode, die einen Wert von einem Bereich in einen anderen mit einem bestimmten Schritt umwandelt.
RNDfromCI - Hilfsmethode, die eine Zufallszahl in einem bestimmten Intervall erzeugt.

Beschreibung der privaten Klassenfelder:

coordinatesNumber - Anzahl der Suchkoordinaten;
frogsNumber - Anzahl der Frösche in der Population;
numbMems - Anzahl der Memeplexe (Gruppen von Fröschen);
numbCycles - Anzahl der Zyklen im Memeplex;
frogStepsToLocalMax - Anzahl der Froschschritte bis zum lokalen Maximum;
movConstant - Verschiebungskonstante (Suchschritt) der Frösche;
memsFrogs - Anzahl der Frösche in jedem Memeplex;
numbCyclesCNT - Zykluszähler;
vect - Array zur Speicherung eines Vektors;
indexes - Array zum Speichern von Indizes;
Revision - Flag, das die Notwendigkeit einer Populationsrevision anzeigt.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SFL
{
  //----------------------------------------------------------------------------
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates
  public: S_Frog frogs     []; //all frogs
  public: S_Memeplex mems  []; //memeplexes

  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    numbMemsP,            //number of memeplexes
                     const int    numbCyclesP,          //number of cycles in the memeplex
                     const int    frogStepsToLocalMaxP, //frog steps to the local maximum
                     const double movConstantP);        //movement step (0.0 .. 1.0)

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coordinatesNumber;   //coordinates number
  private: int    frogsNumber;         //frogs number
  private: int    numbMems;            //number of memeplexes
  private: int    numbCycles;          //number of cycles in the memeplex
  private: int    frogStepsToLocalMax; //frog steps to the local maximum
  private: double movConstant;         //movement step (0.0 .. 1.0)
  private: int    memsFrogs;           //number of frogs in the memplex
  private: int    numbCyclesCNT;       //cycle counter

  private: double vect    [];          //vector
  private: int    indexes [];          //indexes
  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

Um den Algorithmus zu initialisieren, verwenden wir die Initialisierungsmethode Init, die mehrere Parameter hat:

coordinatesNumberP - Anzahl der Koordinaten
populationSizeP - Größe der Bevölkerung
numbMemsP - Anzahl der Memeplexe
numbCyclesP - Anzahl der Zyklen im Memeplex
frogStepsToLocalMaxP - Anzahl der Froschschritte bis zum lokalen Maximum
movConstantP - Bewegungsschritt (von 0,0 bis 1,0)

Zunächst setzt die Methode den Zufallszahlengenerator zurück und setzt den Anfangswert der Variablen fB (-DBL_MAX) und revision (false).
Anschließend erstellt die Methode die Arrays rangeMax, rangeMin, rangeStep, vect, indexes, cB, frogs und mems mit den erforderlichen Dimensionen.
Die Methode initialisiert jeden Frosch im frogs-Array und jeden Frosch in jedem Memeplex im mems-Array mit der Init-Methode unter Angabe der Anzahl der Koordinaten.
Die Methode setzt dann den Anfangswert der fBest-Variablen jedes Memeplexes auf -DBL_MAX und erstellt das cBest-Array für jedes Memeplex mit der erforderlichen Größe.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SFL::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    numbMemsP,            //number of memeplexes
                     const int    numbCyclesP,          //number of cycles in the memeplex
                     const int    frogStepsToLocalMaxP, //frog steps to the local maximum
                     const double movConstantP)         //movement step (0.0 .. 1.0)
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber   = coordinatesNumberP;
  frogsNumber         = populationSizeP;
  numbMems            = numbMemsP;
  numbCycles          = numbCyclesP;
  frogStepsToLocalMax = frogStepsToLocalMaxP;
  movConstant         = movConstantP;
  memsFrogs           = frogsNumber / numbMems;

  numbCyclesCNT       = 0;

  ArrayResize (rangeMax,  coordinatesNumber);
  ArrayResize (rangeMin,  coordinatesNumber);
  ArrayResize (rangeStep, coordinatesNumber);
  ArrayResize (vect,      coordinatesNumber);
  ArrayResize (indexes,   frogsNumber);

  ArrayResize (cB, coordinatesNumber);

  ArrayResize (frogs, frogsNumber);
  for (int i = 0; i < frogsNumber; i++)
  {
    frogs [i].Init (coordinatesNumber);
  }

  ArrayResize (mems, numbMems);
  for (int i = 0; i < numbMems; i++)
  {
    ArrayResize (mems [i].frogs, memsFrogs);
    for (int frgs = 0; frgs < memsFrogs; frgs++)
    {
      mems [i].frogs [frgs].Init (coordinatesNumber);
    }

    mems [i].fBest = -DBL_MAX;
    ArrayResize (mems [i].cBest, coordinatesNumber);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode Moving wurde entwickelt, um Frösche durch den Suchraum zu bewegen. Die Methode ist recht umfangreich, daher werden wir sie in Teilen analysieren.

Zu Beginn des Codes überprüfen wir den Wert der Variable revision. Wenn ‚false‘, wird der folgende Codeblock ausgeführt:

- Wir legen den Anfangswert der Variablen fB fest, der die beste Schätzung der Funktion darstellt. In diesem Fall wird ihm der Wert -DBL_MAX (minus Unendlich) zugewiesen.
- Wir starten den Zyklus, bei dem jeder Frosch initialisiert wird. Für jeden Frosch:
- Starten des Zyklus für jede c-Koordinate.
- Erzeugen eines Zufallswerts für die c-Koordinate mit der Funktion RNDfromCI, die eine Zufallszahl innerhalb eines bestimmten Bereichs liefert.
- c-Koordinatenwert wird mit der Funktion SeInDiSp in den Bereich umgewandelt, mit der wir einen Wert innerhalb eines Bereichs mit einem bestimmten Schritt verschieben können.
- Der f-Funktionswert für den Frosch wird auf -DBL_MAX gesetzt.
- Setzten des Werts des vorherigen fPrev-Funktionswertes für einen Frosch auf -DBL_MAX.
- frogStep ist auf 0 gesetzt.

- Starten des Zyklus für jede c-Koordinate.
- Berechnen von vect[c], das Produkt aus der Differenz zwischen dem maximalen und dem minimalen Wert des Bereichs von movConstant.
- Die Variable revision wird auf „true“ gesetzt, um anzuzeigen, dass die Initialisierung abgeschlossen ist.
- Die Variable numbCyclesCNT wird auf 0 gesetzt.

Dieser Code initialisiert also die Frösche, legt die Anfangswerte der Funktion und anderer Parameter fest und berechnet außerdem den vect[c]-Wert für jede c-Koordinate.

if (!revision)
{
  fB = -DBL_MAX;

  for (int frgs = 0; frgs < frogsNumber; frgs++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      frogs [frgs].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      frogs [frgs].c [c] = SeInDiSp (frogs [frgs].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      frogs [frgs].f        = -DBL_MAX;
      frogs [frgs].fPrev    = -DBL_MAX;
      frogs [frgs].frogStep = 0;
    }
  }

  for (int c = 0; c < coordinatesNumber; c++)
  {
    vect [c] = (rangeMax [c] - rangeMin [c]) * movConstant;
  }

  revision      = true;
  numbCyclesCNT = 0;
}

Wenn das Flag revision ‚true‘ ist, bedeutet dies, dass der Algorithmus in die Phase der Froschbewegung eingetreten ist. Mit den Methodenvariablen haben wir uns bereits vertraut gemacht, sodass wir nicht näher darauf eingehen werden. Dieser Teil des Codes implementiert die Froschsprünge in Übereinstimmung mit dem individuellen Schritt für jeden Frosch. Beim ersten Schritt springt der Frosch in Richtung des lokalen Anführers, der Versuch wird gezählt, wenn sich die Position des Frosches verbessert hat, ansonsten wird der Schrittzähler erhöht. Mit anderen Worten, es wird eine feste Anzahl von Versuchen für den Sprung zum lokalen Führer entsprechend den externen Parametern des Algorithmus zugewiesen.

Beim Anführerfrosch wird ein anderes Bewegungsprinzip angewandt als bei allen anderen im Memeplex. Der Anführer springt einfach in eine zufällige Richtung in einem kleinen Umkreis von seiner Position.

Im Gegensatz zum Anführer springen alle anderen Frösche gemäß der folgenden Gleichung auf den Anführer zu:

coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);

Die Gleichung zeigt, dass die neue Koordinate des Frosches durch die Annäherung an den Anführer um den Abstand zwischen ihnen, normiert auf den euklidischen Abstand für alle Koordinaten, unter Einführung der Zufallskomponente rnd erhalten wird.

else
{
  int cnt = 0;
  double eDistance = 0.0; //euclidean distance
  double coordDiff = 0.0; //the difference in coordinates

  for  (int m = 0; m < numbMems; m++)
  {
    for (int frgs = 0; frgs < memsFrogs; frgs++)
    {
      //2.1 move the frogs towards the best one in the memeplex-----------------
      if (mems [m].frogs [frgs].frogStep < frogStepsToLocalMax)
      {
        if (mems [m].frogs [frgs].fPrev != -DBL_MAX && mems [m].fBest != -DBL_MAX)
        {
          if (mems [m].frogs [frgs].fPrev == mems [m].fBest)
          {
            for (int c = 0; c < coordinatesNumber; c++)
            {
              rnd = RNDfromCI (-1.0, 1.0);
              rnd = rnd < 0.0 ? -rnd * rnd : rnd * rnd;
              coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * 0.2;
              mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
            }
          }
          else
          {
            eDistance = 0.0;
            coordDiff = 0.0;

            //calculate Euclidean distance----------------------------------
            for (int c = 0; c < coordinatesNumber; c++)
            {
              coordDiff  = mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c];
              coordDiff *= coordDiff;
              eDistance += coordDiff;
            }

            eDistance = sqrt (eDistance);

            for (int c = 0; c < coordinatesNumber; c++)
            {
              rnd = RNDfromCI (-1.0, 1.0);
              coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);
              mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
            }
          }
        }
        else
        {
          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);
            rnd = rnd < 0.0 ? -rnd * rnd : rnd * rnd;
            coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c];
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
      }
      else
      {
        //2.2 move towards global if the move is worse than the previous one-----
        if (mems [m].frogs [frgs].frogStep /*==*/ >= frogStepsToLocalMax)
        {
          eDistance = 0.0;
          coordDiff = 0.0;

          //calculate Euclidean distance------------------------------------
          for (int c = 0; c < coordinatesNumber; c++)
          {
            coordDiff  = cB [c] - mems [m].frogs [frgs].cPrev [c];
            coordDiff *= coordDiff;
            eDistance += coordDiff;
          }

          eDistance = sqrt (eDistance);

          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);
            coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((cB [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
        //2.3 move randomly across the field --------------------------------
        else
        {
          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);

            coord    = RNDfromCI (rangeMin [c], rangeMax [c]);
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
      }

      frogs [cnt] = mems [m].frogs [frgs];
      cnt++;
    }
  }


  //--------------------------------------------------------------------------
  numbCyclesCNT++;
}

Die Revisionsmethode ist so konzipiert, dass sie bei jeder Iteration des Algorithmus den globalen Führer bestimmt und lokale Führer ermittelt. Wenn die Anzahl der Zyklen, die für die Bewegung der Frösche innerhalb jedes Memeplexes vorgesehen sind, erschöpft ist, führen wir eine Umverteilung durch - wir ordnen die Frösche den Memeplexen nach dem Zufallsprinzip neu zu und tauschen so Informationen zwischen den Memeplexen aus. Bei dieser Methode werden auch die entsprechenden Sprungschritte berücksichtigt, d. h. die Richtung, in die sich der Frosch bei der nächsten Iteration bewegen wird (in Richtung des lokalen oder globalen Führers oder in eine zufällige Richtung im Suchraum).

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SFL::Revision ()
{
  //4.1 determine the globally best one by population-------------------------------
  for (int i = 0; i < frogsNumber; i++)
  {
    if (frogs [i].f > fB)
    {
      fB = frogs [i].f;
      ArrayCopy (cB, frogs [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  int cnt = 0;

  //if the last loop=========================================================
  if (numbCyclesCNT >= numbCycles)
  {
    //4.2.0 reset the memeplex cycle counter-----------------------------------
    numbCyclesCNT = 0;

    //4.2.1 generate random indices--------------------------------------
    for (int i = 0; i < frogsNumber; i++) indexes [i] = i;

    Shuffle (indexes, frogsNumber);

    //4.2.2 copy to memeplexes accidentally------------------------------------
    for  (int m = 0; m < numbMems; m++)
    {
      mems [m].fBest = -DBL_MAX;

      for (int frgs = 0; frgs < memsFrogs; frgs++)
      {
        mems [m].frogs [frgs] = frogs [indexes [cnt]];
        cnt++;

        //4.2.3 determine the best one in each memeplex---------------------------
        if (mems [m].frogs [frgs].f > mems [m].fBest)
        {
          mems [m].fBest = mems [m].frogs [frgs].f;
          ArrayCopy (mems [m].cBest, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
        }

        //4.2.4 reset frogs' fitness and step------------------------
        mems [m].frogs [frgs].f        = -DBL_MAX;
        mems [m].frogs [frgs].fPrev    = -DBL_MAX;
        mems [m].frogs [frgs].frogStep = 0;
      }
    }
  }
  //if NOT the last cycle======================================================
  else
  {
    for  (int m = 0; m < numbMems; m++)
    {
      for (int frgs = 0; frgs < memsFrogs; frgs++)
      {
        mems [m].frogs [frgs].frogStep++;

        //4.3.1 copy the fitness and coordinates of frogs from the population to the
        //corresponding frog memeplexes
        mems [m].frogs [frgs].f = frogs [cnt].f;
        ArrayCopy (mems [m].frogs [frgs].c, frogs [cnt].c, 0, 0, WHOLE_ARRAY);

        //4.3.2 determine the best one in each memeplex---------------------------
        if (frogs [cnt].f > mems [m].fBest)
        {
          mems [m].fBest = frogs [cnt].f;
          ArrayCopy (mems [m].cBest, frogs [cnt].c, 0, 0, WHOLE_ARRAY);
        }

        //4.3.3 determine the direction of the next jump------------------------
        if (mems [m].frogs [frgs].frogStep <= frogStepsToLocalMax)
        {
          if (mems [m].frogs [frgs].f > mems [m].frogs [frgs].fPrev)
          {
            mems [m].frogs [frgs].fPrev = mems [m].frogs [frgs].f;
            ArrayCopy (mems [m].frogs [frgs].cPrev, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
            mems [m].frogs [frgs].frogStep = 0;
          }
        }
        else
        {
          if (mems [m].frogs [frgs].frogStep >= frogStepsToLocalMax + 1)
          {
            if (mems [m].frogs [frgs].f > mems [m].frogs [frgs].fPrev)
            {
              mems [m].frogs [frgs].fPrev = mems [m].frogs [frgs].f;
              ArrayCopy (mems [m].frogs [frgs].cPrev, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
              mems [m].frogs [frgs].frogStep = 0;
            }
          }
          else
          {
            mems [m].frogs [frgs].f        = -DBL_MAX;
            mems [m].frogs [frgs].fPrev    = -DBL_MAX;
            mems [m].frogs [frgs].frogStep = 0;
          }
        }

        cnt++;
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Im SFL-Optimierungsalgorithmus müssen wir die Frösche zufällig zwischen den Memeplexen mischen. Das Problem der Zufallsmischung ist interessant, weil seine algorithmische Lösung nicht trivial ist, aber Ronald Fisher und Frank Yates haben einen effektiven und schnellen Algorithmus entwickelt. Bisher haben wir ein ähnliches Konzept nicht verwendet, weil es keinen Bedarf dafür gab. Sie ist in der Informatik weit verbreitet, insbesondere in den Bereichen genetische Algorithmen, Kryptographie und Statistik.

Die wichtigsten Vorteile des Fisher-Yates-Algorithmus:
1. Leichte Umsetzung: Der Fisher-Yates-Algorithmus ist in jeder Programmiersprache leicht zu implementieren. Sie erfordert keine komplexen mathematischen Berechnungen oder spezielle Bibliotheken.
2. Effizienz: Der Fisher-Yates-Algorithmus hat einen linearen Zeitaufwand. Mit anderen Worten: Die Ausführungszeit hängt von der Anzahl der Elemente ab, die neu angeordnet werden müssen. Dies macht es sehr effizient für große Datensätze.
3. Zufälligkeit: Der Fisher-Yates-Algorithmus gewährleistet sehr zufällige Permutationen. Dies ist für viele Anwendungen wichtig, z. B. für Zufallstests, Verschlüsselung und Simulationen.
4. Unabhängigkeit bei der Eingabe: Der Fisher-Yates-Algorithmus kann auf jeden Datensatz angewandt werden, ohne dass man dessen Struktur oder Eigenschaften kennen muss. Das macht ihn zu einem vielseitigen Werkzeug für viele Aufgaben.
5. Pseudo-Zufälligkeit: Der Fisher-Yates-Algorithmus erzeugt pseudozufällige Permutationen, die in vielen Anwendungen verwendet werden können, in denen Zufälligkeit (aber nicht unbedingt echte Zufälligkeit) erforderlich ist.

Im Allgemeinen ist der Fisher-Yates-Algorithmus einfach, effizient und vielseitig. Es ist ein nützliches Werkzeug für viele Probleme, die mit Zufälligkeit und Datenpermutationen zu tun haben.

//——————————————————————————————————————————————————————————————————————————————
void Shuffle (int & arr [], int size)
{
  int index, temp;
  for (int i = size - 1; i > 0; i--)
  {
    index = MathRand () % (i + 1);
    temp = arr [i];
    arr [i] = arr [index];
    arr [index] = temp;
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Testergebnisse

Ergebnisse des SFL-Prüfstands:

C_AO_SFL:50;25;15;5;0.7
=============================
5 Rastrigin; Funktion führt 10000 Ergebnis aus: 66.52578871476199
Ergebnis: 0.82429
25 Rastrigin; Funktion führt 10000 Ergebnis aus: 52.38937199890908
Ergebnis: 0.64913
500 Rastrigin; Funktion führt 10000 Ergebnis aus: 44.5591163558836
Ergebnis: 0.55211
=============================
5 Forest; Funktion führt 10000 Ergebnis aus: 0.5762718670482314
Ergebnis: 0.32597
25 Forest; Funktion führt 10000 Ergebnis aus: 0.16329693292687839
Ergebnis: 0.09237
500 Forest; Funktion führt 10000 Ergebnis aus: 0.04968320483668511
Ergebnis: 0.02810
=============================
5 Megacity; Funktion führt 10000 Ergebnis aus: 3.1599999999999997
Ergebnis: 0.26333
25 Megacity; Funktion führt 10000 Ergebnis aus: 1.016
Ergebnis: 0.08467
500 Megacity; Funktion führt 10000 Ergebnis aus: 0.3004
Ergebnis: 0.02503
=============================
Alle Ergebnisse: 2.84501

Bei der Betrachtung der Animation des SFL-Algorithmus ist keine Clusterbildung oder Gruppierung nach einzelnen Memen zu erkennen, obwohl das Gegenteil zu erwarten war. Die Optimierungsagenten (Punkte) sind chaotisch über das Feld verteilt, und es gibt keine Muster in der Bewegung der Partikel. Die geringe Konvergenzqualität des Algorithmus fällt sofort auf und äußert sich im Steckenbleiben in lokalen Extrema, die durch lange glatte Abschnitte auf dem Konvergenzgraphen bestimmt werden können. Mit zunehmender Anzahl der optimierten Parameter nimmt die Schrittweite jedoch ab.

SFL auf die Rastrigin-Testfunktion.

SFL auf die Funktion Forest-Testfunktion.

SFL auf der Megacity-Testfunktion.

Es ist Zeit für Schlussfolgerungen. Aus der Ergebnistabelle geht hervor, dass der SFL-Algorithmus in Bezug auf die Optimierung unterdurchschnittliche Ergebnisse erzielt. Obwohl die SFL bei der glatten Rastrigin-Funktion einige Vorteile aufweist, reicht dies nicht aus, um sie als bevorzugten Algorithmus für glatte Funktionen zu empfehlen. Bei gekrümmten Wald- und Megacity-Funktionen zeigt die SFL im Vergleich zu glatten Funktionen schlechtere Ergebnisse. Dies lässt sich dadurch erklären, dass die springenden Frösche auf den flachen Abschnitten der optimierten Funktion ihre Position nicht verbessern und immer wieder an ihren ursprünglichen Platz zurückkehren, ohne sich im Gelände „verfangen“ zu können.

AO	Beschreibung	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (diskret)			Megacity final	Endergebnis
AO	Beschreibung	10 Parameter (5 F)	50 Parameter (25 F)	1000 Parameter (500 F)	Rastrigin final	10 Parameter (5 F)	50 Parameter (25 F)	1000 Parameter (500 F)	Forest final	10 Parameter (5 F)	50 Parameter (25 F)	1000 Parameter (500 F)	Megacity final	Endergebnis
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	100.000
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
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
IWO	Optimierung mit invasivem Unkraut	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
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
FAm	Feuerfliegen-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
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
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
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
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
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
SFL	shuffled frog-leaping	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
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
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
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
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
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

SFL ist eher ein „Überbau“ für andere Optimierungsalgorithmen, die als Logik für die Bewegung von Agenten in Memeplexen verwendet werden können. SFL wurde ursprünglich als eine Technik zur Verbesserung der Optimierungsqualität bestehender Algorithmen entwickelt. Als eigenständiger Optimierungsalgorithmus zeigt SFL unterdurchschnittliche Ergebnisse im Vergleich zu den zuvor besprochenen Populationsalgorithmen. SFL bietet ein großes Potenzial für Experimente mit der Kombination logischer Schritte in einem Algorithmus, um sowohl die Erkundung als auch die Ausnutzung zu verbessern. SFL ist äußerst flexibel und anpassungsfähig, sodass es sich für den gezielten Einsatz bei bestimmten Optimierungsproblemen eignet.

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).

HistogrammtitlealtHistogrammalt

Abb. 3. Histogramm der Endergebnisse der Testalgorithmen

Vor- und Nachteile des Shuffled-Frog-Leaping-Algorithmus (SFL):

Vorteile:
1. Eine kleine Anzahl von externen Parametern.
2. Die Originalität der Architektur des Algorithmus, die Fähigkeit, andere Optimierungsalgorithmen in Memen zu verwenden.

Nachteile
1. Hohe rechnerische Komplexität.
2. Schlechte Ergebnisse bei glatten und diskreten Funktionen.
3. Hängenbleiben bei Funktionen mit flachen horizontalen „Plätzen“.

Jeder Artikel verfügt über ein Archiv, das aktualisierte aktuelle Versionen der Algorithmuscodes für alle früheren Artikel enthält. Der Artikel basiert auf den gesammelten Erfahrungen des Autors und stellt seine persönliche Meinung dar. Die Schlussfolgerungen und Urteile beruhen auf den Experimenten.

Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/13366

Beigefügte Dateien |

ZIP herunterladen

17_The_world_of_AO_SFL.zip (143.2 KB)

Warnung: Alle Rechte sind von MetaQuotes Ltd. vorbehalten. Kopieren oder Vervielfältigen untersagt.

Andere Artikel von diesem Autor

Zur Diskussion im Händlerforum

Datenwissenschaft und maschinelles Lernen (Teil 17): Geld von Bäumen? Die Kunst und Wissenschaft der Random Forests im Devisenhandel

Entdecken Sie die Geheimnisse der algorithmischen Alchemie, während wir Sie durch die Mischung aus Kunstfertigkeit und Präzision bei der Entschlüsselung von Finanzlandschaften führen. Entdecken Sie, wie Random Forests Daten in Vorhersagefähigkeiten umwandeln und eine einzigartige Perspektive für die Navigation auf dem komplexen Terrain der Aktienmärkte bieten. Begleiten Sie uns auf dieser Reise in das Herz der Finanzmagie, wo wir die Rolle von Random Forests bei der Gestaltung des Marktgeschehens entmystifizieren und die Türen zu lukrativen Gelegenheiten aufschließen

Wie man einen einfachen Multi-Currency Expert Advisor mit MQL5 erstellt (Teil 3): Hinzufügen von Symbolpräfixen und/oder -suffixen und der Handelszeiten

Mehrere Handelskollegen schickten E-Mails oder äußerten sich dazu, wie man diesen Multi-Currency EA bei Brokern mit Symbolnamen mit Präfixen und/oder Suffixen verwenden kann, und auch dazu, wie man Handelszeitzonen oder Handelszeitsitzungen bei diesem Multi-Currency EA implementiert.

Verständnis von Programmierparadigmen (Teil 1): Ein verfahrenstechnischer Ansatz für die Entwicklung eines Price Action Expert Advisors

Lernen Sie die Programmierparadigmen und ihre Anwendung in MQL5-Code kennen. In diesem Artikel werden die Besonderheiten der prozeduralen Programmierung untersucht und anhand eines praktischen Beispiels in die Praxis umgesetzt. Sie lernen, wie Sie einen Price Action Expert Advisor mit dem EMA-Indikator und Kerzen-Kursdaten entwickeln. Außerdem führt der Artikel in das Paradigma der funktionalen Programmierung ein.

Entwicklung eines MQTT-Clients für Metatrader 5: ein TDD-Ansatz — Teil 4

Dieser Artikel ist der vierte Teil einer Serie, die unsere Entwicklungsschritte für einen nativen MQL5-Client für das MQTT-Protokoll beschreibt. In diesem Teil beschreiben wir, was MQTT v5.0 Properties sind, ihre Semantik, wie wir einige von ihnen lesen, und geben ein kurzes Beispiel, wie die Eigenschaften (Properties) zur Erweiterung des Protokolls verwendet werden können.