MetaTrader 5 / Beispiele
English Русский 中文 Español 日本語 Português 한국어 Français Italiano Türkçe
preview
Algorithmen zur Optimierung mit Populationen Firefly-Algorithmus (FA)

Algorithmen zur Optimierung mit Populationen Firefly-Algorithmus (FA)

MetaTrader 5 — Beispiele | 16 Februar 2023, 16:48
190 0
Andrey Dik
Andrey Dik

Inhalt

1. Einführung
2. Beschreibung des Algorithmus
3. Testergebnisse


1. Einführung

Die Natur war schon immer eine Inspiration für viele metaheuristische Algorithmen. Es gelang ihr, ohne Aufforderung Lösungen für Probleme zu finden, die auf individuellen Erfahrungen beruhten. Die natürliche Auslese und das Überleben des Stärkeren waren die Hauptmotivation für die Entwicklung der ersten metaheuristischen Algorithmen. In der Natur kommunizieren die Tiere auf vielfältige Weise miteinander. Glühwürmchen nutzen ihre Fähigkeit zu blinken für die Kommunikation. Es gibt etwa 2000 Arten von Glühwürmchen mit ihren eigenen, speziellen Leuchtmustern. Sie erzeugen in der Regel einen kurzen Blitz mit einem bestimmten Muster. Das Licht und seine Intensität sind das Ergebnis von biochemischen Prozessen, die als Biolumineszenz bezeichnet werden. Es wird angenommen, dass die Hauptfunktion dieser Blitze darin besteht, Paarungsmuster und potenzielle Opfer anzulocken. Einige tropische Glühwürmchen können ihre Lichtblitze synchronisieren und zeigen damit ein Beispiel für biologische Selbstorganisation. Die Intensität des Lichts in Abhängigkeit von der Entfernung von der Quelle folgt dem Gesetz des umgekehrten Quadrats, sodass das flackernde Licht eines Glühwürmchens die Glühwürmchen (Firefly, deut. Feuerkäfer ist eine Unterart der Glühwürmchen) in seiner Umgebung dazu bringt, in Sichtweite des Aufleuchtens zu reagieren.

Es gibt zwei Varianten von Populationsoptimierungsalgorithmen, die durch das Verhalten von Glühwürmchen inspiriert sind: der Firefly-Algorithmus und der Glühwürmchen-Schwarm-Optimierungsalgorithmus (GSO). Der Hauptunterschied zwischen dem Feuerkäfer und den Glühwürmchen besteht darin, dass letztere flügellos sind. In diesem Artikel betrachten wir den ersten Typ des Optimierungsalgorithmus.

2. Beschreibung des Algorithmus

Der Firefly-Algorithmus (F-Algorithmus) wurde von X-Sh vorgeschlagen. Yang an der University of Cambridge (UK) im Jahr 2007 und erregte sofort die Aufmerksamkeit der Optimierungsforscher. Der Firefly-Algorithmus gehört zu einer Familie von Schwarmintelligenz-Algorithmen, die in letzter Zeit beeindruckende Ergebnisse bei der Lösung von Optimierungsproblemen gezeigt haben. Insbesondere der Firefly-Algorithmus wird zur Lösung kontinuierlicher und diskreter Optimierungsprobleme eingesetzt.

Der Firefly-Algorithmus hat drei Regeln, die auf den Flackereigenschaften echter Glühwürmchen basieren. Die Regeln lauten wie folgt:

  1. Alle Glühwürmchen werden sich auf attraktivere und hellere Kollegen zubewegen.
  2. Der Grad der Anziehung eines Glühwürmchens ist proportional zu seiner Helligkeit, die mit zunehmender Entfernung von einem anderen Glühwürmchen abnimmt, da die Luft Licht absorbiert. Daher bewegt sich zwischen zwei flackernden Glühwürmchen das weniger helle auf das hellere zu. Wenn es kein helleres oder attraktiveres Gegenstück gibt, bewegt sich ein Glühwürmchen zufällig.
  3. Die Helligkeit oder Lichtintensität des Glühwürmchens wird durch den Wert der Zielfunktion des Problems bestimmt.


Zu Beginn des Algorithmus werden alle Glühwürmchen nach dem Zufallsprinzip im Suchraum verstreut. Der Algorithmus bestimmt dann in zwei Phasen die optimalen Partitionen:

  1. Änderung der Lichtintensität - die Helligkeit des Glühwürmchens an seiner aktuellen Position spiegelt sich im Wert seiner Fitness wider, die sich in Richtung eines attraktiven Glühwürmchens bewegt.
  2. Das Glühwürmchen verändert seine Position, indem es die Lichtintensität der benachbarten Glühwürmchen beobachtet.


Jetzt können wir die Feinheiten der Firefly-Optimierung im Detail erforschen. Das Wesen des Algorithmus ist in Abbildung 1 deutlich dargestellt.

Fas

Abb. 1. Fireflies im Suchraum. Die Sichtbarkeit nimmt mit zunehmender Entfernung ab

Der Grundgedanke des Suchprinzips ist eine nichtlineare Abnahme der Sichtbarkeit mit zunehmendem Abstand zwischen den Glühwürmchen. Ohne diese nichtlineare Beziehung würde sich jedes Glühwürmchen deterministisch auf eine hellere Lichtquelle zubewegen. Wie in Abbildung 1 zu sehen ist, wählt das Glühwürmchen jedoch nicht seinen hellsten Verwandten, da sein Licht aufgrund der Absorption des Lichts durch die Umgebung weniger auffällt. Stattdessen wählt er ein weniger helles Gegenstück (wenn auch das hellste in seiner Umgebung). Diese Eigenschaft erklärt die gute Fähigkeit des Algorithmus, sich in kleinere Schwärme aufzuteilen. Dies geschieht natürlich nur aufgrund der nicht-linearen Funktion der Lichtabsorption aus der Entfernung. In Abbildung 2 sehen Sie die Funktion der Sichtbarkeit in Abhängigkeit von der Entfernung für den Algorithmus mit verschiedenen Werten des Absorptionskoeffizienten des Gammamediums, der einer der Parameter des Algorithmus ist.


Sichtbarkeit

Abb. 2. Die Funktion der Transparenz des Mediums aus der Entfernung f(x), wobei der gamma-Transparenzkoeffizient gleich 1,0, 0,2, 0,05 bzw. 0,01 ist.

Wenn gamma gegen unendlich geht, wird die Umgebung undurchsichtig, und wenn gamma gleich Null ist, ist die Umgebung völlig transparent, und jedes Glühwürmchen sieht die anderen in jeder Entfernung im Suchraum. Was passiert, wenn gamma = 0,0 ist? Alle Glühwürmchen fliegen zu dem hellsten, relativ zu einem nicht optimalen Punkt konvergierenden Punkt. Der Algorithmus wird also nicht konvergieren und in einem der lokalen Extrema stecken bleiben. Was passiert, wenn die Umgebung völlig undurchsichtig ist? Die Glühwürmchen werden niemanden sehen, der attraktiver ist als sie selbst. Nach dem vom Autor des Algorithmus vorgeschlagenen Konzept führt die Tatsache, dass man niemanden sieht, der besser ist als man selbst, dazu, dass sich ein Glühwürmchen nach dem Zufallsprinzip bewegt. Der Algorithmus wird zu einer Zufallssuche degenerieren. In unserer Bewertungstabelle zur Klassifizierung der Algorithmen nimmt der Zufallssuchalgorithmus den letzten Platz ein.  

Betrachten wir nun die weitere Analyse des Algorithmus und die Gleichungen, die die Bewegungen der Glühwürmchen beschreiben. Die Funktion der Sichtbarkeit gegenüber der Entfernung liegt der Berechnung des so genannten Attraktivitätsindex zugrunde:

attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

wobei:
attractiveness - Attraktivität, selbsterklärend
gamma - Trübungskoeffizient der Umgebung
distance - Euklidischer Abstand zwischen Glühwürmchen
fireflies [k].f - Lichtintensität des k-ten Glühwürmchens

Die Gleichung verdeutlicht, dass die Attraktivitätsfunktion direkt von der Dimension des Problems und den Grenzen des Abstandswertes abhängt, sodass der Autor des Algorithmus empfiehlt, den Transparenzkoeffizienten für ein bestimmtes Optimierungsproblem auszuwählen. Ich denke, dass es unpraktisch und zeitaufwändig ist, dies zu tun, ohne im Voraus zu wissen, wie sich der Algorithmus verhalten wird. Daher denke ich, dass es notwendig ist, die Abstandswerte im Bereich von 0 bis 20 zu normalisieren. Wir benutzen dazu die Funktion Scale() (skalieren) an, die wir bereits in anderen Algorithmen verwendet haben. Die Umrechnung der „Entfernung“ vor der Attraktivitätsberechnung sieht folgendermaßen aus:

distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);

wobei:

maxDist - maximaler euklidischer Abstand zwischen einem Glühwürmchenpaar und allen anderen

In diesem Fall hängt die Attraktivität der Glühwürmchen nicht von der Dimension des Problems ab, und es besteht keine Notwendigkeit, den Koeffizienten gamma für ein bestimmtes Optimierungsproblem zu wählen. Die Attraktivitätsfunktion bestimmt, welche Art von Partnerwahl jedes Glühwürmchen treffen wird. Diese Wahl ist streng festgelegt. Der Einfluss der gegenseitigen Anziehungskraft der Glühwürmchen bestimmt den Koeffizienten beta (den zweiten Parameter des Algorithmus). Wie wird die Suchfähigkeit des Algorithmus gewährleistet, wenn die Auswahl der Glühwürmchen bei jeder entsprechenden Iteration bereits im Voraus festgelegt wird? Um dies zu erreichen, werden eine Zufallsvektorkomponente und der dritte Algorithmusparameter (alpha) eingeführt. Die komplexen Verhaltensbeziehungen von Glühwürmchen würden folgendermaßen aussehen:

fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];

wobei:
fireflies [i].c [c] - die c-te Koordinate der i-ten Firefly
beta - Einflusskoeffizient der Anziehungskraft von Glühwürmchen
alpha - Koeffizient, der die Zufallskomponente beim Bewegen von Glühwürmchen beeinflusst und Abweichungen vom Bewegungsziel angibt
r - Zufallszahl im Bereich [-1.0;1.0]
v[c] - Vektorkomponente, die den Abstand zwischen den Extrempunkten des Suchbereichs durch die c-te Koordinate charakterisiert
Хj - entsprechende Koordinate des Glühwürmchens in dem Paar, zu dem eine Bewegung stattfinden wird
Xi - entsprechende Koordinate des Glühwürmchens, für das die Bewegung berechnet wird

Nun ist es an der Zeit, den Code des Algorithmus zu beschreiben. Es ist relativ einfach. Betrachten wir ihn genauer.

Ein Glühwürmchen wird mit einer einfachen Struktur S_Firefly beschrieben, die aus zwei Komponenten besteht, nämlich [] - Koordinaten, f - die Leuchtkraft des Glühwürmchens (Fitnessfunktion). Da es für jedes Glühwürmchen nur ein einziges Individuum in der entsprechenden Iteration gibt, zu dem es sich bewegt und ein Paar bildet, riskieren wir nicht, die Koordinaten zu überschreiben, wenn wir die nächste Bewegung berechnen. Zu diesem Zweck werde ich eine spezielle Struktur einführen, die im Folgenden betrachtet wird.
//——————————————————————————————————————————————————————————————————————————————
struct S_Firefly
{
  double c  []; //coordinates
  double f;     //the value of the fitness function
};
//——————————————————————————————————————————————————————————————————————————————

Die Struktur S_Attractiveness dient dazu, den Attraktivitätswert und die Nummer des entsprechenden Glühwürmchens als Paar zu speichern. Jedes Glühwürmchen bewegt sich nicht zu den Koordinaten des attraktivsten Glühwürmchens, sondern zu den Koordinaten, zu denen sich sein Partner bereits bewegt hat. Hier gibt es einige Abweichungen von der vom Autor beschriebenen Version des Algorithmus, aber so funktioniert es besser.

//——————————————————————————————————————————————————————————————————————————————
struct S_Attractiveness
{
  double a; //attractiveness
  int    i; //index of the most attractive firefly
};
//——————————————————————————————————————————————————————————————————————————————

Der Firefly-Algorithmus wird durch die Klasse C_AO_FA beschrieben. Es gibt hier drei öffentliche Methoden, eine davon ist Init() für die Initialisierung und zwei öffentliche Methoden, die bei jeder Iteration aufgerufen werden müssen - Flight() und Luminosity(), private Hilfsmethoden und Mitglieder zum Speichern von Parameterkonstanten.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_FA
{
  //----------------------------------------------------------------------------
  public: S_Firefly fireflies []; //fireflies
  public: double    rangeMax  []; //maximum search range
  public: double    rangeMin  []; //minimum search range
  public: double    rangeStep []; //step search
  public: double    cB        []; //best coordinates
  public: double    fB;           //FF of the best coordinates

  public: void Init (const int    paramsP,  //number of opt. parameters
                     const int    sizeP,    //swarm size
                     const double alphaP,   //alpha, randomness in motion
                     const double betaP,    //beta, effect of attractiveness
                     const double gammaP);  //gamma, transparency of the environment

  public: void Flight ();
  public: void Luminosity ();

  //----------------------------------------------------------------------------
  private: S_Attractiveness att [];
  private: int    swarmSize;
  private: int    params;
  private: double maxDist;
  private: double v [];

  private: double alpha;      //randomness in motion
  private: double beta;       //effect of attractiveness
  private: double gamma;      //transparency of the environment
  private: bool   luminosity;

  private: double SeInDiSp  (double In, double inMin, double inMax, double step);
  private: double RNDfromCI (double min, double max);
  protected: double Scale   (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

Die offene Methode Init() dient der Initialisierung und sollte vor Beginn jeder Optimierung aufgerufen werden. Seine Parameter sind Überbauparameter für den Algorithmus. Die Methode weist Speicher für Arrays zu und setzt den Helligkeitswert des globalen und jedes einzelnen Glühwürmchens zurück. 

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Init (const int    paramsP, //number of opt. parameters
                    const int    sizeP,   //swarm size
                    const double alphaP,  //alpha, randomness in motion
                    const double betaP,   //beta, effect of attractiveness
                    const double gammaP)  //gamma, transparency of the environment
{
  fB = -DBL_MAX;

  params    = paramsP;
  swarmSize = sizeP;
  alpha     = alphaP;
  beta      = betaP;
  gamma     = gammaP;

  ArrayResize (rangeMax,  params);
  ArrayResize (rangeMin,  params);
  ArrayResize (rangeStep, params);
  ArrayResize (v,         params);
  ArrayResize (att,       swarmSize);

  luminosity = false;

  ArrayResize (fireflies, swarmSize);

  for (int i = 0; i < swarmSize; i++)
  {
    ArrayResize (fireflies [i].c,  params);
    fireflies [i].f = -DBL_MAX;
  }

  ArrayResize (cB, params);
}
//——————————————————————————————————————————————————————————————————————————————

Betrachten Sie die erste öffentliche Methode, die bei jeder Iteration aufgerufen wird - Flight(). Die Hauptlogik des Algorithmus ist in dieser Methode konzentriert, sodass es notwendig ist, sie ausführlicher zu betrachten. Die Variable „luminosity“ (Leuchtstärke) dient als Flag, mit der wir feststellen können, ob der Algorithmus bei der ersten Iteration oder bei nachfolgenden Iterationen ausgeführt wird. Ist das Flag nicht gesetzt, müssen die Glühwürmchen nach dem Zufallsprinzip gemäß der Gleichverteilung im Koordinatenraum verteilt werden. Bei dieser Aktion wird der Verschiebungsvektor für jede Koordinate festgelegt und sofort der maximal mögliche euklidische Abstand zwischen den Fireflies berechnet (wie bereits erwähnt, ist dies notwendig, um die Abstände zwischen den Glühwürmchen zu normalisieren, um die Abhängigkeit des Transparenzkoeffizienten der Umgebung von der Dimension des Problems zu vermeiden). Nach diesen Vorgängen wird das Flag „luminosity“ aktiviert.

if (!luminosity)
{
  fB = -DBL_MAX;

  //--------------------------------------------------------------------------
  double summCoordinates = 0.0;
  for (int c = 0; c < params; c++)
  {
    v [c] = rangeMax [c] - rangeMin [c];
    summCoordinates += pow (v [c], 2.0);
  }
  maxDist = pow (summCoordinates, 0.5);

  //--------------------------------------------------------------------------
  for (int s = 0; s < swarmSize; s++)
  {
    for (int k = 0; k < params; k++)
    {
      fireflies [s].c  [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      fireflies [s].c  [k] = SeInDiSp (fireflies [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
  }

  luminosity = true;
}

Ab der zweiten und weiteren Iterationen, nachdem die Glühwürmchen bei der ersten Iteration zufällig verteilt wurden und zu leuchten begannen (für sie wurde die Fitnessfunktion berechnet), kann der Grad der Attraktivität für jedes Glühwürmchen berechnet werden. Dazu müssen wir den euklidischen Abstand zwischen allen möglichen Paaren von Fireflies berechnen. Dazu addiert man einfach die Quadrate der Koordinatendifferenzen und ermittelt aus deren Summe die Wurzel. Der berechnete Abstand wird in die Gleichung zur Berechnung der Attraktivität eingesetzt. Auf diese Weise erhalten wir für jedes Glühwürmchen das einzig mögliche Paar. Bestimmen wir die maximale Leuchtkraft aller Fireflies. Dies ist erforderlich, um das hellste Glühwürmchen zu bestimmen, für das sich kein Paar finden lässt und das allein im Raum umherwandert. Nun, vielleicht wird sie bei der nächsten Iteration mehr Glück haben.

//measure the distance between all------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  att [i].a = -DBL_MAX;

  for (int k = 0; k < swarmSize; k++)
  {
    if (i == k) continue;

    summCoordinates = 0.0;
    for (int c = 0; c < params; c++) summCoordinates += pow (fireflies [i].c [c] - fireflies [k].c [c], 2.0);

    distance = pow (summCoordinates, 0.5);
    distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);
    attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

    if (attractiveness > att [i].a)
    {
      att [i].a = attractiveness;
      att [i].i = k;
    }

    if (fireflies [i].f > maxF) maxF = fireflies [i].f;
  }
}

Dieser Teil des Codes der Methode Flight() ist für den Flug des Glühwürmchens verantwortlich. Für das glücklose Glühwürmchen, deren Leuchtkraft größer ist als die aller anderen, wird die Berechnung etwas anders durchgeführt. Zu seiner aktuellen Position addieren wir den Verschiebungsvektor über alpha multipliziert mit der Zufallszahl [-1.0;1.0]. Theoretisch wirkt dies im Algorithmus wie eine zusätzliche Untersuchung der besten Lösung, in der Erwartung, dass sie noch besser wird, aber wie wir später sehen werden, wird sich diese Technik als nutzlos erweisen. In diesem Stadium betrachten wir die klassische Version des Algorithmus.

Für alle anderen Glühwürmchen, für die bereits ein Paar gefunden wurde, besteht die Berechnung der Bewegung darin, sich auf das entsprechende Paar zuzubewegen, wobei eine Zufallskomponente hinzugefügt wird (ich habe sie bereits erwähnt).

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      fireflies [i].c [c] = fireflies [i].c [c] + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); 
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];
      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Eine einfache offene Methode, die bei jeder Iteration aufgerufen wird. Hier werden wir die beste Lösung aktualisieren. 

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Luminosity ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    if (fireflies [i].f > fB)
    {
      fB = fireflies [i].f;
      ArrayCopy (cB, fireflies [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Kommen wir nun zu den Tests. Schauen wir uns die Ergebnisse des Algorithmus für die Testfunktionen an:

2022.12.16 13:39:00.102    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:39:05.930    Test_AO_FA (EURUSD,M1)    1 Skin; Funktionsdurchläufe 10000 Ergebnis: 4.901742065217812
2022.12.16 13:39:05.930    Test_AO_FA (EURUSD,M1)    Score: 0.99603
2022.12.16 13:39:13.579    Test_AO_FA (EURUSD,M1)    20 Skins; Funktionsdurchläufe 10000 Ergebnis: 3.2208359936020665
2022.12.16 13:39:13.579    Test_AO_FA (EURUSD,M1)    Score: 0.59468
2022.12.16 13:39:53.607    Test_AO_FA (EURUSD,M1)    500 Skins; Funktionsdurchläufe 10000 Ergebnis: 0.98491319842575
2022.12.16 13:39:53.607    Test_AO_FA (EURUSD,M1)    Score: 0.06082
2022.12.16 13:39:53.607    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:39:59.313    Test_AO_FA (EURUSD,M1)    1 Forest; Funktionsdurchläufe 10000 Ergebnis: 1.578196881663454
2022.12.16 13:39:59.313    Test_AO_FA (EURUSD,M1)    Score: 0.89271
2022.12.16 13:40:07.274    Test_AO_FA (EURUSD,M1)    20 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.3101994341994826
2022.12.16 13:40:07.274    Test_AO_FA (EURUSD,M1)    Score: 0.17546
2022.12.16 13:40:49.159    Test_AO_FA (EURUSD,M1)    500 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.06829102669136165
2022.12.16 13:40:49.159    Test_AO_FA (EURUSD,M1)    Score: 0.03863
2022.12.16 13:40:49.159    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:40:54.895    Test_AO_FA (EURUSD,M1)    1 Megacity; Funktionsdurchläufe 10000 Ergebnis: 8.2
2022.12.16 13:40:54.895    Test_AO_FA (EURUSD,M1)    Score: 0.68333
2022.12.16 13:41:02.777    Test_AO_FA (EURUSD,M1)    20 Megacities; Funktionsdurchläufe 10000 Ergebnis: 1.5900000000000003
2022.12.16 13:41:02.777    Test_AO_FA (EURUSD,M1)    Score: 0.13250
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    500 Megacities; Funktionsdurchläufe 10000 Ergebnis: 0.2892
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    Score: 0.02410
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    All score for C_AO_FA: 0.39980648892951776

Die Ergebnisse sind, gelinde gesagt, wenig beeindruckend. Der Algorithmus ist nur geringfügig besser als PSO, FSS, GWO in einzelnen Tests. Im Gesamtbewertungsindikator liegt er jedoch an zweiter Stelle von unten und lässt nur den Algorithmus der Zufallssuche hinter sich. In Anbetracht all dessen kam die Idee auf, die Berechnung der geschätzten Indikatoren in den Tests zu überarbeiten. In den folgenden Artikeln werde ich zu einem bequemeren Berechnungsschema für die Bewertung übergehen, während ich im aktuellen Artikel das Histogramm der Endergebnisse hinzufügen werde. Es wird das Leistungsverhältnis zwischen den einzelnen Algorithmen deutlich machen.

Der klassische Firefly-Algorithmus ist einfach zu implementieren. Studien zeigen jedoch, dass er nur langsam konvergiert und bei multimodalen Problemen leicht in die Falle der lokalen Extremitäten gerät. Darüber hinaus fehlen Koeffizienten, die parametrisch von der aktuellen Iteration abhängig sind. Eines der Ziele der Studie war es daher, den Standard-Firefly-Algorithmus zu modifizieren, um seine Leistung zu verbessern.

Die Idee des Algorithmus selbst ist recht originell, und es wäre schade, alles so zu belassen, wie es ist, und nicht zu versuchen, seine Eigenschaften zu verbessern. Deshalb habe ich versucht, den Algorithmus zu ändern, indem ich die Zufallskomponente durch einen Levy-Flug ersetzt habe. Levys Flug kann nicht bei jedem Algorithmus die Suchfähigkeit verbessern. Nach der Prüfung des Kuckuckssuchalgorithmus habe ich versucht, andere Algorithmen mit dieser Methode zu verbessern, was jedoch nicht die erwarteten Ergebnisse brachte. Offensichtlich sollte dies in gewisser Weise mit der internen Suchstrategie innerhalb des Algorithmus übereinstimmen und diesen ergänzen. In diesem speziellen Fall führte die Anwendung von Levys Flight zu einem bemerkenswerten Effekt - die Fähigkeiten des Algorithmus stiegen dramatisch an. Darüber werden wir in dem Teil des Artikels sprechen, der sich mit den Testergebnissen befasst.

Hier ist der Teil des Codes, an dem die Änderung vorgenommen wurde. In der klassischen Version bewegt sich zunächst das Glühwürmchen mit der besten Leuchtkraft in eine zufällige Richtung von seiner aktuellen Position aus. Dann bewegt sich unser bestes Glühwürmchen von der besten globalen Position aus und versucht, nicht seine aktuelle Position, sondern die Lösung als Ganzes zu verbessern. Fügen wir den Koordinaten der besten Lösung eine Zufallszahl aus der Levy-Flugverteilung (Verteilung mit starkem Schweif) mit demselben Alphakoeffizienten hinzu, wobei der Bewegungsvektor berücksichtigt wird. Dadurch war es möglich, die Koordinaten der globalen Lösung durch die Verfeinerung des benachbarten Gebiets zu verbessern.

Wie Sie sehen, gehorcht das Verhalten der übrigen Glühwürmchen nun denselben klassischen Regeln, wenn auch angepasst an die Zufallskomponente von Levys Flug. Das ist die gesamte Änderung des Algorithmus. 

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      fireflies [i].c [c] = cB [c] + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];

      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Levys Funktion flight, Diagramm in Abb. 3. Wie kann der Exponent in der Funktionsgleichung das Verhalten des Algorithmus beeinflussen? Meinen Forschungen zufolge nimmt mit steigendem Grad die Zahl der langen (schweren) Sprünge im Verhältnis zu den kurzen ab, während sich die Fähigkeit des Algorithmus verbessert, Koordinaten in der Nähe der besten Lösung zu verfeinern. Da es nur wenige weite Sprünge gibt, steigt die Wahrscheinlichkeit, in lokalen Extrema stecken zu bleiben. Dieser Effekt ist bei der Untersuchung von diskreten Funktionen stärker ausgeprägt, während er bei glatten Funktionen nicht so ausgeprägt ist. Im Gegenteil, mit einer Verringerung des Exponenten steigt die Anzahl der langen Sprünge, die Suchfähigkeiten des Algorithmus verbessern sich, aber die Konvergenzgenauigkeit verschlechtert sich, sodass wir einen Mittelweg zwischen Genauigkeit und Suche brauchen. Außerdem kann sie je nach Optimierungsproblem unterschiedlich ausfallen.


Levy

Abb. 3. Levys Funktion flight, Grade 0.5...3.0 


Kommen wir nun zu den Testergebnissen der modifizierten Version des Algorithmus. Unten können Sie sehen, wie sehr sich die Leistung der Originalversion im Vergleich zur klassischen Version verbessert hat.

2022.12.16 13:07:15.925    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:07:21.544    Test_AO_FAm (EURUSD,M1)    1 Skin; Funktionsdurchläufe 10000 Ergebnis: 4.854437214435259
2022.12.16 13:07:21.544    Test_AO_FAm (EURUSD,M1)    Score: 0.98473
2022.12.16 13:07:29.518    Test_AO_FAm (EURUSD,M1)    20 Skins; Funktionsdurchläufe 10000 Ergebnis: 4.588539001298423
2022.12.16 13:07:29.518    Test_AO_FAm (EURUSD,M1)    Score: 0.92124
2022.12.16 13:08:12.587    Test_AO_FAm (EURUSD,M1)    500 Skins; Funktionsdurchläufe 10000 Ergebnis: 1.981278990090829
2022.12.16 13:08:12.587    Test_AO_FAm (EURUSD,M1)    Score: 0.29872
2022.12.16 13:08:12.587    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:08:18.336    Test_AO_FAm (EURUSD,M1)    1 Forest; Funktionsdurchläufe 10000 Ergebnis: 1.7665409595127233
2022.12.16 13:08:18.336    Test_AO_FAm (EURUSD,M1)    Score: 0.99924
2022.12.16 13:08:26.432    Test_AO_FAm (EURUSD,M1)    20 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.6261364994589462
2022.12.16 13:08:26.432    Test_AO_FAm (EURUSD,M1)    Score: 0.35417
2022.12.16 13:09:10.587    Test_AO_FAm (EURUSD,M1)    500 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.14269062630878
2022.12.16 13:09:10.587    Test_AO_FAm (EURUSD,M1)    Score: 0.08071
2022.12.16 13:09:10.587    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:09:16.393    Test_AO_FAm (EURUSD,M1)    1 Megacity; Funktionsdurchläufe 10000 Ergebnis: 10.0
2022.12.16 13:09:16.393    Test_AO_FAm (EURUSD,M1)    Score: 0.83333
2022.12.16 13:09:24.373    Test_AO_FAm (EURUSD,M1)    20 Megacities; Funktionsdurchläufe 10000 Ergebnis: 1.7899999999999998
2022.12.16 13:09:24.373    Test_AO_FAm (EURUSD,M1)    Score: 0.14917
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    500 Megacities; Funktionsdurchläufe 10000 Ergebnis: 0.5076
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    Score: 0.04230
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    All score for C_AO_FAm: 0.5181804234713119

Wie Sie sehen können, zeigt der modifizierte Algorithmus nicht nur bessere Ergebnisse, sondern nimmt auch eine führende Position in der Bewertungstabelle ein. Sehen wir uns die Ergebnisse im nächsten Abschnitt genauer an. Nachfolgend sehen Sie eine Animation der modifizierten Version des Algorithmus im Test.

Skin

  FAm über die Testfunktion Skin.

Forest

  FAm über die Testfunktion Forest.

Megacity

  FAm über die Testfunktion Megacity.


3. Testergebnisse

Der modifizierte Firefly-Algorithmus (FAm) schnitt in allen Tests hervorragend ab. Im Allgemeinen hängen die Ergebnisse von den Einstellungen des Algorithmus ab. Bei einigen Einstellungen wurde bei allen drei Funktionen mit zwei Variablen eine 100%ige Konvergenz erreicht. Die hohe Skalierbarkeit des Algorithmus sorgt für die Führung bei Tests mit 40 und 1000 Parametern. Die Parameter beta und gamma haben einen starken Einfluss, sodass sowohl eine hohe Konvergenz als auch eine hohe Resistenz gegen das Verharren in lokalen Extrema erreicht werden kann. Die Ergebnisse sind sehr unterschiedlich, was im Allgemeinen auf die Nachteile des Algorithmus zurückzuführen ist. Bei sonst gleichen Voraussetzungen ist der Algorithmus der stärkste unter den zuvor betrachteten. Es kann für eine Vielzahl von Aufgaben empfohlen werden, einschließlich des maschinellen Lernens und der künstlichen Intelligenz, insbesondere beim Training neuronaler Netze.

Nachstehend finden Sie die endgültige Bewertungstabelle, in der der modifizierte Firefly-Algorithmus die Nase vorn hat. Leider konnte der klassische Algorithmus, trotz seiner Originalität, keine guten Ergebnisse erzielen. Auch die Auswahl der Tuning-Parameter brachte keinen Erfolg.

AO

Beschreibung

Skin

Skin final

Forest

Forest final

Megacity (diskret)

Megacity final

Endergebnis

2 Parameter (1 F)

40 Parameter (20 F)

1000 Parameter (500 F)

2 Parameter (1 F)

40 Parameter (20 F)

1000 Parameter (500 F)

2 Parameter (1 F)

40 Parameter (20 F)

1000 Parameter (500 F)

FAm

Firefly-Algorithmus M

0.98473

0.92124

0.29872

0.73490

0.99924

0.35417

0.08071

0.47804

0.83333

0.14917

0.04230

0.34160

0.51817889

COAm

Kuckuck-Optimierungsalgorithmus M

1.00000

0.85911

0.14316

0.66742

0.99283

0.28787

0.04551

0.44207

1.00000

0.24917

0.03537

0.42818

0.51255778

ACOm

Ameisen-Kolonie-Optimierung M

0.98229

0.79108

0.12602

0.63313

1.00000

0.62077

0.11521

0.57866

0.38333

0.44000

0.02377

0.28237

0.49805222

ABCm

Künstliches Bienenvolk M (Artificial Bee Colony, ABC)

1.00000

0.63922

0.08076

0.57333

0.99908

0.20112

0.03785

0.41268

1.00000

0.16333

0.02823

0.39719

0.46106556

ABC

Künstliches Bienenvolk (Artificial Bee Colony, ABC)

0.99339

0.73381

0.11118

0.61279

0.99934

0.21437

0.04215

0.41862

0.85000

0.16833

0.03130

0.34988

0.46043000

GWO

Grauer-Wolf-Optimierung

0.99900

0.48033

0.18924

0.55619

0.83844

0.08755

0.02555

0.31718

1.00000

0.10000

0.02187

0.37396

0.41577556

FSS

Fischschulsuche

0.99391

0.5692

0.11341

0.55884

0.85172

0.12143

0.03223

0.33513

0.91667

0.08583

0.02583

0.34278

0.41224778

PSO

Partikelschwarmoptimierung

0.99627

0.38080

0.05089

0.47599

0.93772

0.14540

0.04856

0.37723

1.00000

0.09333

0.02233

0.37189

0.40836667

FA

Firefly-Algorithmus

0.99603

0.59468

0.06082

0.55051

0.89271

0.17546

0.03863

0.36893

0.68333

0.13250

0.02410

0.27998

0.39980649

RND

zufällig

0.99932

0.44276

0.06827

0.50345

0.83126

0.11524

0.03048

0.32566

0.83333

0.09000

0.02403

0.31579

0.38163222


Ab diesem Artikel werde ich ein Histogramm veröffentlichen, in dem der beste Algorithmus zum Zeitpunkt des Tests 100 bedingte Punkte hat, während der schlechteste Algorithmus 1 Punkt hat. Ich denke, dies ist die bequemste Darstellungsmethode in Bezug auf die visuelle Wahrnehmung, da wir die Skala der Endergebnisse der Bewertungstabellen-Algorithmen deutlich sehen können. Jetzt können wir sehen, wie sehr der Zufallsalgorithmus hinter dem führenden Algorithmus zurückbleibt.

Bewertung

Abb. 4. Histogramm der Endergebnisse der Testalgorithmen


Wie Sie sich vielleicht erinnern, sind metaheuristische Algorithmen Näherungsmethoden zur Lösung von Optimierungsproblemen, die die Eigenschaft der Zufälligkeit mit einer vernünftigen Annahme in ihrer Suchmaschine nutzen und versuchen, die Qualität der verfügbaren Lösungen durch Iterationen aus einer zufällig generierten Menge gültiger Lösungen zu verbessern, indem sie den Lösungsraum untersuchen und nutzen. Diese Algorithmen sind zwar nicht garantiert optimal, aber sie sind so getestet, dass sie eine vernünftige und akzeptable Lösung ergeben. Darüber hinaus haben sie den Vorteil, dass das Verhalten des Problems sie nicht stark beeinflusst, was sie für viele Aufgaben nützlich macht. Das Vorhandensein vieler verfügbarer Algorithmen macht es möglich, den geeigneten Algorithmus für die Lösung eines Problems zu wählen, je nach dessen Verhalten.

Seit dem Aufkommen der evolutionären Algorithmen wurde viel an heuristischen Algorithmen geforscht. Die Implementierung neuer Algorithmen ist einer der führenden Forschungsbereiche. Derzeit gibt es mehr als 40 metaheuristische Algorithmen. Die meisten von ihnen werden durch Simulation von Szenarien aus der Natur erstellt.

Die Vor- und Nachteile beziehen sich auf eine modifizierte Version des Firefly-Algorithmus (FAm).

Vorteile:
  • Einfache Umsetzung. Leicht zu ändern.
  • Hohe Skalierbarkeit.
  • Hohe Konvergenz (kann je nach Algorithmuseinstellungen variieren).
  • Die Fähigkeit, die Region des Suchraums in separate Gruppen um lokale Extrema herum zu gruppieren.

Nachteile
  • Starker Einfluss der Einstellungen auf die Optimierungsergebnisse.
  • Bei einigen Einstellungen neigt der Algorithmus dazu, in lokalen Extrema stecken zu bleiben.

Jeder Artikel verfügt über ein Archiv, das aktualisierte aktuelle Versionen der Algorithmuscodes für alle früheren Artikel enthält. Jeder neue Artikel ist die gesammelte persönliche Erfahrung des Autors, und die Schlussfolgerungen und Beurteilungen beruhen auf den Experimenten, die auf einem speziell für diesen Zweck entwickelten Prüfstand durchgeführt wurden.



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

Beigefügte Dateien |
ZIP herunterladen
8_The_world_of_AO_vFA2.zip (77.04 KB)
Warnung: Alle Rechte sind von MetaQuotes Ltd. vorbehalten. Kopieren oder Vervielfältigen untersagt.

Andere Artikel von diesem Autor

Zur Diskussion im Händlerforum
Lernen Sie, wie man ein Handelssystem mit Gator Oscillator entwickelt Lernen Sie, wie man ein Handelssystem mit Gator Oscillator entwickelt
Ein neuer Artikel in unserer Serie über die Entwicklung eines Handelssystems auf der Grundlage beliebter technischer Indikatoren wird sich mit dem technischen Indikator Gator Oscillator und der Erstellung eines Handelssystems durch einfache Strategien befassen.
Matrix Utils, Erweiterung der Funktionalität der Standardbibliothek für Matrizen und Vektoren Matrix Utils, Erweiterung der Funktionalität der Standardbibliothek für Matrizen und Vektoren
Matrizen dienen als Grundlage für Algorithmen des maschinellen Lernens und für Computer im Allgemeinen, da sie große mathematische Operationen effektiv verarbeiten können. Die Standardbibliothek bietet alles, was man braucht, aber wir wollen sehen, wie wir sie erweitern können, indem wir in der Datei utils mehrere Funktionen einführen, die in der Bibliothek noch nicht vorhanden sind
Erstellen eines Ticker-Panels: Basisversion Erstellen eines Ticker-Panels: Basisversion
Hier zeige ich Ihnen, wie Sie Bildschirme mit Preistickern erstellen, die normalerweise zur Anzeige von Börsenkursen verwendet werden. Ich werde es nur mit MQL5 machen, ohne eine komplexe externe Programmierung zu verwenden.
Algorithmen zur Optimierung mit Populationen Fish School Search (FSS) Algorithmen zur Optimierung mit Populationen Fish School Search (FSS)
Fish School Search (FSS, Suche mittels Fischschulen) ist ein neuer Optimierungsalgorithmus, der durch das Verhalten von Fischen in einem Schwarm inspiriert wurde, von denen die meisten (bis zu 80 %) in einer organisierten Gemeinschaft von Verwandten schwimmen. Es ist erwiesen, dass Fischansammlungen eine wichtige Rolle für die Effizienz der Nahrungssuche und den Schutz vor Räubern spielen.