Fraktal-basierter Algorithmus (FBA)

Inhalt

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

Einführung

Metaheuristische Algorithmen haben sich als leistungsfähige Werkzeuge für die Lösung komplexer Optimierungsprobleme erwiesen, da sie in der Lage sind, akzeptable Lösungen in angemessener Zeit zu finden. In den letzten Jahrzehnten wurden viele metaheuristische Methoden entwickelt, die von verschiedenen natürlichen und sozialen Prozessen inspiriert sind: genetische Algorithmen, Partikelschwarm-Optimierung, differentielle Evolution, Ameisenkolonie-Optimierung und viele andere, die wir bereits in früheren Artikeln behandelt haben.

In diesem Artikel betrachten wir einen neuen metaheuristischen Algorithmus zur Lösung kontinuierlicher Optimierungsprobleme – den Fractal-based Algorithm (FBA) von Marjan Kaedi aus dem Jahr 2017. Dieser Ansatz basiert auf den geometrischen Eigenschaften von Fraktalen und nutzt das Konzept der Selbstähnlichkeit, um den Raum adaptiv zu erkunden. Der Algorithmus basiert auf einer innovativen Heuristik, die das Potenzial verschiedener Suchbereiche auf der Grundlage der Dichte hochwertiger Lösungen in diesen Bereichen bewertet.

Ein zentrales Merkmal des Verfahrens ist die iterative Aufteilung des Suchraums in Unterräume, wobei die vielversprechendsten Zonen identifiziert und anschließend genauer untersucht werden. Während der Ausführung des Algorithmus bilden sich selbstähnliche fraktale Strukturen, die auf die optimale Lösung ausgerichtet sind und ein Gleichgewicht zwischen globaler Erkundung und lokaler Verfeinerung der gefundenen Lösungen gewährleisten. In diesem Artikel werden wir die theoretischen Grundlagen des Algorithmus, die Details seiner Implementierung und die Konfiguration der Schlüsselparameter im Detail untersuchen und die Ergebnisse einer vergleichenden Analyse mit anderen gängigen Optimierungsverfahren für Standard-Testfunktionen vorstellen.

Implementierung des Algorithmus

Stellen Sie sich vor, Sie suchen auf einem riesigen Feld nach einem Schatz. Wie würden Sie vorgehen? Sie hätten wahrscheinlich nicht jeden Zentimeter des Bodens umgegraben, weil das zu viel Zeit gekostet hätte. Genau dieses Problem löst der fraktale Algorithmus (FBA) – er hilft, den „Schatz“ (die optimale Lösung) in einem riesigen Raum von Möglichkeiten zu finden, ohne jeden Punkt zu überprüfen.

Zunächst wird das gesamte Suchgebiet wie ein Schachbrett in gleiche Quadrate unterteilt. Dann verteilen wir „Sucher“ (zufällige Punkte) über das gesamte Feld, um einen ersten Überblick über das Gebiet zu bekommen. Jeder Sucher meldet die Qualität des von ihm gefundenen Gebiets. Der Algorithmus wählt die erfolgreichsten (60 % der besten Punkte) aus und untersucht die Quadrate, in denen sie sich konzentrieren. Diese Quadrate sind als „vielversprechende Zonen“ gekennzeichnet (die obersten 30 % der Quadrate).

Jetzt richten wir unsere Aufmerksamkeit auf vielversprechende Bereiche. Jeder dieser Bereiche ist in kleinere Quadrate unterteilt, wodurch eine fraktale Struktur entsteht. Die meisten neuen Schatzsucher begeben sich in diese vielversprechenden Gebiete, und um zu vermeiden, dass sie Schätze außerhalb ihrer erforschten Zonen verpassen, zwingt der Algorithmus einige Sucher (5 %) dazu, sich ein wenig unberechenbar zu verhalten – sie wandern von ihren Positionen aus in zufällige Richtungen und erkunden unerwartete Orte.

Dieser Prozess wiederholt sich immer wieder. Mit jedem Schritt bestimmt der Algorithmus genauer, wo sich der Schatz befinden könnte, und schickt mehr Sucher dorthin. Nach und nach entsteht eine hierarchische Struktur von Quadraten unterschiedlicher Größe, die an ein Fraktal erinnert – daher der Name des Algorithmus.

Abbildung 1. Visualisierung der Funktionsweise des FBA-Algorithmus

Die Grundidee der FBA, die in der obigen Abbildung dargestellt ist, besteht darin, den Suchraum nach und nach fraktal in immer kleinere Regionen aufzuteilen und die Rechenressourcen auf die vielversprechendsten Regionen zu konzentrieren. So entsteht eine selbstähnliche Struktur, die den Lösungsraum erkundet. Gehen wir nun dazu über, den Pseudocode für den FBA-Algorithmus zu schreiben.

Initialisierung:

• Aufteilung des gesamten Suchraums in gleiche Teilräume
• Erzeugen einer gleichmäßig im Raum verteilten Ausgangspopulation
• Bewertung des Fitnesswerts jedes Punkts

Iteration:

• Identifizierung vielversprechender Punkte: Auswahl der P1%-Punkte mit den besten Fitnesswerten.
• Berechnung der Ränge der Unterräume: Zählen Sie, wie viele vielversprechende Punkte in jeden Unterraum fallen.
• Auswahl der vielversprechenden Unterräume: Auswahl der P2% der Unterräume mit den höchsten vielversprechenden Rängen.
• Unterteilung vielversprechender Teilräume: weitere Unterteilung vielversprechender Gebiete in kleinere Teilräume.
• Erzeugung einer neuen Population: Schaffung neuer Punkte mit höherer Dichte in vielversprechenden Regionen.
• Anwendung der Mutation: Hinzufügen von Gaußschem Rauschen zu P3% der Punkte (Explorationsmechanismus).
• Integration der Populationen: Zusammenführung der aktuellen und der neuen Populationen unter Beibehaltung der besten Punkte.

Kriterium für das Anhalten:

• Fortfahren, bis ein Abbruchkriterium erreicht ist (maximale Anzahl von Iterationen, Fitnessschwelle usw.)
• Rückgabe der besten gefundenen Lösung

Nachdem wir nun das Konzept des Algorithmus verstanden haben, können wir mit dem Schreiben des Codes fortfahren. Die Klasse C_AO_FBA ist eine spezialisierte Implementierung eines auf fraktalen Prinzipien basierenden Optimierungsalgorithmus und wird von der allgemeinen Klasse C_AO abgeleitet.

Die Klasse verfügt über öffentliche Methoden und Parameter, die für die Konfiguration und die wichtigsten Aktionen des Algorithmus verantwortlich sind. Der Konstruktor gibt Anfangsparameter an, wie z. B. die Größe der Population, den prozentualen Anteil der vielversprechenden Punkte und Unterräume, den Anteil der Punkte für Zufallsvariationen und die Anzahl der Intervalle für die Aufteilung jeder Dimension in Intervalle. Die Methode SetParams ermöglicht die Aktualisierung von Parametern in Echtzeit aus externen Quellen. Die Init-Methode und die nachfolgenden Funktionen Moving und Revision steuern die Phasen und Iterationen des Algorithmus.

Die Klasse deklariert auch die interne Struktur S_Subspace, die zur Beschreibung des Suchunterraums verwendet wird. Jeder Unterraum ist durch minimale und maximale Grenzen für jede Dimension, sein Potenzial, die Ebene in der Hierarchie und die Verbindung mit dem übergeordneten Unterraum gekennzeichnet.

Die wichtigsten Methoden innerhalb der Klasse umfassen Funktionen für:

• Prüfung, ob ein Punkt innerhalb eines bestimmten Unterraums liegt.
• Erstellung der anfänglichen Raumaufteilung und seiner weiteren Aufteilung.
• Identifizierung vielversprechender Punkte, Berechnung ihrer Rangfolge und Auswahl der besten Unterräume für die weitere Aufteilung.
• Generierung einer neuen Population durch Kombination, Mutation und Sortierung nach Effizienz- oder Fitnesskriterien.

So implementiert die Klasse C_AO_FBA einen adaptiven, hierarchischen, fraktal-basierten Algorithmus für die Suche nach optimalen Lösungen in komplexen mehrdimensionalen Problemen, der eine dynamische Raumaufteilung, die Bewertung vielversprechender Bereiche und heuristische Operatoren zur Verbesserung der Sucheffizienz verwendet.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_FBA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_FBA () { }
  C_AO_FBA ()
  {
    ao_name = "FBA";
    ao_desc = "Fractal-Based Algorithm";
    ao_link = "https://www.mql5.com/en/articles/17458";

    popSize = 50;  // population size
    P1      = 60;  // percentage of promising points
    P2      = 30;  // percentage of promising subspaces
    P3      = 0.8; // percentage of points for random modification
    m_value = 10;  // number of intervals to split each dimension into

    ArrayResize (params, 5);

    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "P1";      params [1].val = P1;
    params [2].name = "P2";      params [2].val = P2;
    params [3].name = "P3";      params [3].val = P3;
    params [4].name = "m_value"; params [4].val = m_value;
  }

  void SetParams ()
  {
    popSize = (int)params [0].val;
    P1      = (int)params [1].val;
    P2      = (int)params [2].val;
    P3      =      params [3].val;
    m_value = (int)params [4].val;
  }

  bool Init (const double &rangeMinP  [],  // minimum values
             const double &rangeMaxP  [],  // maximum values
             const double &rangeStepP [],  // step change
             const int     epochsP = 0);   // number of epochs

  void Moving   ();
  void Revision ();

  //----------------------------------------------------------------------------
  int    P1;           // percentage of promising points
  int    P2;           // percentage of promising subspaces
  double P3;           // share of points for random modification
  int    m_value;      // number of intervals to split each dimension into

  private: //-------------------------------------------------------------------

  // Structure for representing a subspace
  struct S_Subspace
  {
      double min [];        // minimal boundaries of the subspace
      double max [];        // maximum boundaries of the subspace
      double promisingRank; // potential rank (normalized value)
      bool   isPromising;   // flag of potential
      int    parentIndex;   // index of the parent subspace (-1 for root ones) 
      int    level;         // level in hierarchy (0 for original space)

      void Init (int coords)
      {
        ArrayResize (min, coords);
        ArrayResize (max, coords);
        promisingRank = 0.0;
        isPromising   = false;
        parentIndex   = -1;
        level         = 0;
      }
  };

  S_Subspace subspaces     []; // array of subspaces

  // Auxiliary methods
  bool   IsPointInSubspace              (const double &point [], const S_Subspace &subspace);
  void   CreateInitialSpacePartitioning ();
  void   DivideSubspace                 (int subspaceIndex);
  void   IdentifyPromisingPoints        (int &promisingIndices []);
  void   CalculateSubspaceRanks         (const int &promisingIndices []);
  void   SelectPromisingSubspaces       ();
  void   DividePromisingSubspaces       ();
  void   GenerateNewPopulation          ();
  void   MutatePoints                   ();
  void   SortByFitness                  (double &values [], int &indices [], int size, bool ascending = false);
  void   QuickSort                      (double &values [], int &indices [], int low, int high, bool ascending);
  int    Partition                      (double &values [], int &indices [], int low, int high, bool ascending);
};
//——————————————————————————————————————————————————————————————————————————————

Die Initialisierungsmethode Init dient dazu, die Anfangsbedingungen für den Betrieb des Algorithmus festzulegen. Sie akzeptiert Arrays mit den minimalen und maximalen Variablengrenzen und Schrittgrößen für jeden Parameter sowie die Anzahl der Epochen. Innerhalb der Methode wird zunächst die Basisinitialisierung aufgerufen, nach der die anfängliche Aufteilung des Suchraums erstellt wird, d. h. die anfängliche Struktur der Unterräume wird auf der Grundlage der angegebenen Bereiche und Schritte gebildet. Wenn alle Operationen erfolgreich waren, gibt die Methode „true“ zurück, andernfalls „false“.

Bei der zentralen Methode Moving wird eine Lösungssuchschleife mit aufeinanderfolgenden Iterationen durchgeführt. Die erste Iteration ist die Initialisierung der Ausgangspopulation von Punkten, die gleichmäßig über den gesamten Suchraum verteilt sind: Jeder Wert der Variablen wird zufällig innerhalb des Bereichs ausgewählt und an einen bestimmten Schritt angepasst.

Im weiteren Verlauf des Algorithmus werden mehrere Schritte durchgeführt. Zunächst werden die vielversprechendsten Punkte ermittelt – ein kleiner Teil der besten Punkte entsprechend dem Wert der Fitnessfunktion. Dann werden die Ränge dieser Punkte in Bezug auf ihr Potenzial für jeden Unterraum berechnet. Auf der Grundlage dieser Ränge werden die vielversprechendsten Teilräume für eine weitere Unterteilung in kleinere Bereiche ausgewählt. Diese vielversprechenden Bereiche werden dann geteilt, wodurch genauere Suchregionen entstehen. Dann wird eine neue Population von Punkten unter Berücksichtigung ihrer potenziellen Ränge gebildet, was es uns ermöglicht, unsere Bemühungen auf die vielversprechendsten Bereiche zu konzentrieren. Am Ende werden die Punkte nach dem Zufallsprinzip verändert (Mutation), um die Vielfalt zu erhöhen und ein Steckenbleiben zu vermeiden.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_FBA::Init (const double &rangeMinP  [],  // minimum values
                     const double &rangeMaxP  [],  // maximum values
                     const double &rangeStepP [],  // step change
                     const int     epochsP = 0)    // number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  // Create an initial partition of the search space
  CreateInitialSpacePartitioning ();

  return true;
}
//——————————————————————————————————————————————————————————————————————————————

//+----------------------------------------------------------------------------+
//| Basic optimization method                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::Moving ()
{
  // First iteration - initialization of the initial population
  if (!revision)
  {
    // Initialize the initial population uniformly throughout the space
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  // Main optimization

  // 1. Identifying promising points (P1% of points with the best function values)
  int promisingIndices [];
  IdentifyPromisingPoints (promisingIndices);

  // 2. Calculation of potential ranks for each subspace
  CalculateSubspaceRanks (promisingIndices);

  // 3. Selecting the P2% most promising subspaces
  SelectPromisingSubspaces ();

  // 4. Dividing promising subspaces into smaller ones
  DividePromisingSubspaces ();

  // 5. Generating new points taking into account potential ranks
  GenerateNewPopulation ();

  // 6. Random modification (mutation)
  MutatePoints ();
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode Revision ist für die Aktualisierung der aktuell besten Lösung zuständig, die während der Ausführung des Algorithmus gefunden wurde. Sie durchläuft alle Elemente der aktuellen Population und vergleicht den Zielfunktionswert eines jeden Elements mit dem aktuell besten Wert. Wenn ein Element ein besseres Ergebnis liefert, wird die Variable, die das beste Ergebnis speichert, aktualisiert, und das dazugehörige Array der Variablen (Koordinaten) wird kopiert, um diese optimale Lösung zu speichern. Dadurch gewährleistet die Methode eine kontinuierliche Verfolgung und Speicherung des besten Ergebnisses, das zu einem bestimmten Zeitpunkt gefunden wurde.

//+----------------------------------------------------------------------------+
//| Update the best solution                                                   |
//+----------------------------------------------------------------------------+
void C_AO_FBA::Revision ()
{
  // Search for the best solution
  for (int i = 0; i < popSize; i++)
  {
    // Update the best solution
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Mit dieser Methode wird die anfängliche Unterraumstruktur geschaffen, die zur Lokalisierung der Suche nach optimalen Lösungen verwendet wird. Sie bestimmt die Gesamtzahl der Unterräume auf der Grundlage eines bestimmten Teilungsgrades und einer bestimmten Dimension. Bei einer sehr hohen Dimensionalität wird sie auf ein vorgegebenes Maximum begrenzt, um einen übermäßigen Ressourcenverbrauch zu vermeiden.

Anschließend wird ein Array der Unterräumen initialisiert, denen jeweils Anfangsparameter für die Ebene und die Grenzen der einzelnen Koordinaten zugewiesen werden. Je nach den Abmessungen des Raums wird eine geeignete Aufteilungsmethode gewählt:

• Bei einem eindimensionalen Raum wird dieser in gleichmäßige Intervalle unterteilt, wobei jeder erzeugte Unterraum einen bestimmten Abschnitt des Bereichs einnimmt.
• Im zweidimensionalen Raum wird er entlang zweier Achsen unterteilt und bildet ein Gitter aus rechteckigen Flächen.
• Bei höheren Dimensionen wird ein iterativer Ansatz verwendet, bei dem in Analogie zum Zählersystem für jede Koordinate Kombinationen von Indizes erzeugt werden und für jede erzeugte Region Grenzen auf der Grundlage der entsprechenden Intervalle festgelegt werden.

Die Berechnung der Grenzen erfolgt durch Aufteilung der Bereiche für jede Dimension in gleiche Teile, und für jeden Unterraum werden Mindest- und Höchstgrenzen in Übereinstimmung mit den aktuellen Indizes festgelegt. Die Iteration wird so lange fortgesetzt, bis alle erforderlichen Unterräume erstellt wurden oder bis der Grenzwert für ihre Anzahl erreicht ist. Als Ergebnis entsteht eine Struktur, die die anfängliche Partitionierung des Suchraums darstellt und für die weitere Verfeinerung und die Suche nach Lösungen bereit ist.

//+----------------------------------------------------------------------------+
//| Create the initial partition of the search space                           |
//+----------------------------------------------------------------------------+
void C_AO_FBA::CreateInitialSpacePartitioning ()
{
  // Create an initial partition of space
  int totalSubspaces = (int)MathPow (m_value, coords);

  // For very large dimensions, limit the number of subspaces
  if (totalSubspaces > 10000) totalSubspaces = 10000;

  ArrayResize (subspaces, totalSubspaces);

  // Initialize all subspaces
  for (int i = 0; i < totalSubspaces; i++)
  {
    subspaces [i].Init (coords);
    subspaces [i].level = 0; // Initial level
  }

  // Divide the initial space into equal subspaces
  int index = 0;

  // Select the division method depending on the dimensionality of the space
  if (coords == 1)
  {
    // One-dimensional case
    double intervalSize = (rangeMax [0] - rangeMin [0]) / m_value;

    for (int i = 0; i < m_value && index < totalSubspaces; i++)
    {
      subspaces [index].min [0] = rangeMin [0] + i * intervalSize;
      subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize;
      index++;
    }
  }
  else
    if (coords == 2)
    {
      // Two-dimensional case
      double intervalSize0 = (rangeMax [0] - rangeMin [0]) / m_value;
      double intervalSize1 = (rangeMax [1] - rangeMin [1]) / m_value;

      for (int i = 0; i < m_value && index < totalSubspaces; i++)
      {
        for (int j = 0; j < m_value && index < totalSubspaces; j++)
        {
          subspaces [index].min [0] = rangeMin [0] + i * intervalSize0;
          subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize0;
          subspaces [index].min [1] = rangeMin [1] + j * intervalSize1;
          subspaces [index].max [1] = rangeMin [1] + (j + 1) * intervalSize1;
          index++;
        }
      }
    }
    else
    {
      // Multidimensional case - use an iterative approach
      int indices [];
      ArrayResize (indices, coords);
      for (int i = 0; i < coords; i++) indices [i] = 0;

      while (index < totalSubspaces)
      {
        // Calculate the boundaries of the current subspace
        for (int c = 0; c < coords; c++)
        {
          double intervalSize = (rangeMax [c] - rangeMin [c]) / m_value;
          subspaces [index].min [c] = rangeMin [c] + indices [c] * intervalSize;
          subspaces [index].max [c] = rangeMin [c] + (indices [c] + 1) * intervalSize;
        }

        // Move on to the next subspace
        int c = coords - 1;
        while (c >= 0)
        {
          indices [c]++;
          if (indices [c] < m_value) break;
          indices [c] = 0;
          c--;
        }

        // If the full loop completed, exit
        if (c < 0) break;

        index++;
      }
    }
}
//——————————————————————————————————————————————————————————————————————————————

Die folgende Methode dient dazu, festzustellen, ob ein bestimmter Punkt zu einem bestimmten Unterraum gehört. Sie prüft nacheinander jede Koordinate des Punktes und vergleicht ihren Wert mit den Grenzen des entsprechenden Unterraums. Liegt bei mindestens einer Koordinate ein Punkt außerhalb der zulässigen Grenzen (kleiner als das Minimum oder größer als oder gleich dem Maximum), gibt die Methode „false“ zurück, was bedeutet, dass der Punkt nicht im angegebenen Unterraum enthalten ist. Wenn alle Koordinaten die Bedingungen erfüllen, bestätigt die Methode, dass der Punkt zu dem angegebenen Unterraum gehört, und gibt „true“ zurück.

//+----------------------------------------------------------------------------+
//| Determine whether a point belongs to a subspace                            |
//+----------------------------------------------------------------------------+
bool C_AO_FBA::IsPointInSubspace (const double &point [], const S_Subspace &subspace)
{
  // Check if the point is in the specified subspace
  for (int c = 0; c < coords; c++)
  {
    if (point [c] < subspace.min [c] || point [c] >= subspace.max [c])
    {
      return false;
    }
  }

  return true;
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode zur Identifizierung vielversprechender Punkte ist so konzipiert, dass die „vielversprechendsten“ Lösungen aus der aktuellen Population ausgewählt werden. Zunächst werden temporäre Arrays erstellt, um die Fitnessfunktionswerte der einzelnen Elemente und ihre Indizes zu speichern. Anschließend werden diese Arrays mit den Werten und Indizes der entsprechenden Elemente aus der Population gefüllt.

Anschließend werden die Elemente nach dem Wert der Fitnessfunktion in absteigender Reihenfolge sortiert. Nach der Sortierung wird ein bestimmter Prozentsatz der besten Lösungen (P1%) ausgewählt, und aus diesen wird eine Liste von Indizes gebildet, die vielversprechende Punkte darstellen. Die Anzahl der ausgewählten Punkte ist garantiert mindestens eins und übersteigt nicht die Gesamtpopulationsgröße. Als Ergebnis gibt die Funktion ein Array von Indizes vielversprechender Lösungen zurück.

//+----------------------------------------------------------------------------+
//| Identify promising points                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::IdentifyPromisingPoints (int &promisingIndices [])
{
  // Select P1% points with the best function values

  // Create arrays for sorting
  double values  [];
  int    indices [];

  ArrayResize (values,  popSize);
  ArrayResize (indices, popSize);

  // Fill in the arrays
  for (int i = 0; i < popSize; i++)
  {
    values  [i] = a [i].f;
    indices [i] = i;
  }

  // Sort in descending order (for the maximization problem)
  SortByFitness (values, indices, popSize);

  // Select P1% best points
  int numPromisingPoints = (int)MathRound (popSize * P1 / 100.0);
  numPromisingPoints = MathMax (1, MathMin (numPromisingPoints, popSize));

  ArrayResize (promisingIndices, numPromisingPoints);

  for (int i = 0; i < numPromisingPoints; i++)
  {
    promisingIndices [i] = indices [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

Außerdem ist die Methode so konzipiert, dass sie Unterräume nach ihrem Potenzial bewertet und einstuft. Zunächst werden die aktuellen Bewertungswerte für alle Unterräume zurückgesetzt. Anschließend wird gezählt, wie viele vielversprechende Punkte in jeden Unterraum fallen, indem die Koordinaten jedes vielversprechenden Punktes mit den Grenzen jedes Unterraums verglichen und der entsprechende Zähler bei einer Übereinstimmung erhöht wird.

Es ist wichtig, dass ein Punkt nur in einem Unterraum betrachtet wird. Nach der Berechnung der quantitativen Indikatoren werden die Ränge der einzelnen Unterräume normalisiert, indem sie durch die Gesamtzahl der Punkte mit hohem Potenzial geteilt werden, was eine relative Punktzahl für das Potenzial jedes Unterraums ergibt, wobei der Wert zwischen 0 und 1 variiert und dem Anteil der Punkte mit hohem Potenzial innerhalb jedes Unterraums im Verhältnis zur Gesamtpopulation der Punkte mit hohem Potenzial entspricht. Das Ergebnis ist eine Bewertung.

//+----------------------------------------------------------------------------+
//| Calculate potential ranks of subspaces                                     |
//+----------------------------------------------------------------------------+
void C_AO_FBA::CalculateSubspaceRanks (const int &promisingIndices [])
{
  // Reset the ranks of subspaces
  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    subspaces [i].promisingRank = 0.0;
  }

  // Calculate promising points in each subspace
  for (int i = 0; i < ArraySize (promisingIndices); i++)
  {
    int pointIndex = promisingIndices [i];

    for (int j = 0; j < ArraySize (subspaces); j++)
    {
      if (IsPointInSubspace (a [pointIndex].c, subspaces [j]))
      {
        subspaces [j].promisingRank++;
        break; // A point can only be in one subspace
      }
    }
  }

  // Normalize the potential ranks according to the article
  // PromisingRank = Number of promising points in s / Total promising points
  int totalPromisingPoints = ArraySize (promisingIndices);
  if (totalPromisingPoints > 0)
  {
    for (int i = 0; i < ArraySize (subspaces); i++)
    {
      subspaces [i].promisingRank = subspaces [i].promisingRank / totalPromisingPoints;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode SelectPromisingSubspaces bestimmt, welche Unterräume auf der Grundlage ihres Ranges als vielversprechend angesehen werden sollten. Es werden temporäre Arrays „ranks“ und „indices“ erstellt, um die Rangfolge der Unterräume und ihre entsprechenden Indizes zu speichern. Bewertungswerte und Unterraumindizes werden in temporäre Arrays kopiert. Für jeden Unterraum wird das isPromising-Flag auf „false“ gesetzt. Dies ist notwendig, um ohne Berücksichtigung früherer Iterationen neu zu beginnen. Das Array „ranks“ wird in absteigender Reihenfolge sortiert, und gleichzeitig wird das Array „indices“ neu geordnet, um die Entsprechung zwischen Indizes und Bewertungen zu erhalten.

In den „indices“ sind also nach der Sortierung die Indizes der Unterräume in absteigender Reihenfolge ihrer Bewertungen sortiert. Die Anzahl der Unterräume, die als vielversprechend angesehen werden, wird auf der Grundlage des Parameters P2 (Prozentsatz der besten Unterräume) berechnet. Der resultierende Wert ist auf einen Bereich von 1 bis zur Gesamtzahl der Unterräume begrenzt. Wir durchlaufen die ersten numPromisingSubspaces-Elemente des Arrays „indices“. Für jeden Index in diesem Array wird das Flag isPromising für den entsprechenden Unterraum auf „true“ gesetzt. Dies bedeutet, dass dieser Unterraum als vielversprechend gilt.

Es wird auch geprüft, ob der Index innerhalb des zulässigen Bereichs liegt, um Fehler beim Zugriff auf das Array „subspaces“ zu vermeiden. Als Ergebnis der Ausführung der Methode wird das isPromising-Flag für P2%-Unterräume mit den höchsten Rängen auf „true“ gesetzt.

//+----------------------------------------------------------------------------+
//| Select promising subspaces                                                 |
//+----------------------------------------------------------------------------+
void C_AO_FBA::SelectPromisingSubspaces ()
{
  // Select P2% subspaces with the highest ranks as promising ones

  // Create arrays for sorting
  double ranks [];
  int indices [];

  int numSubspaces = ArraySize (subspaces);
  ArrayResize (ranks, numSubspaces);
  ArrayResize (indices, numSubspaces);

  // Fill in the arrays
  for (int i = 0; i < numSubspaces; i++)
  {
    ranks [i] = subspaces [i].promisingRank;
    indices [i] = i;
    // Reset the potential flag
    subspaces [i].isPromising = false;
  }

  // Sort by descending ranks
  SortByFitness (ranks, indices, numSubspaces);

  // Select P2% most promising subspaces
  int numPromisingSubspaces = (int)MathRound (numSubspaces * P2 / 100.0);
  numPromisingSubspaces = MathMax (1, MathMin (numPromisingSubspaces, numSubspaces));

  // Mark promising subspaces
  for (int i = 0; i < numPromisingSubspaces && i < ArraySize (indices); i++)
  {
    // Protection against exceeding the array size
    if (indices [i] >= 0 && indices [i] < ArraySize (subspaces))
    {
      subspaces [indices [i]].isPromising = true;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode DividePromisingSubspaces dient dazu, vielversprechende Teilräume in kleinere Teile zu unterteilen. Zunächst werden alle als vielversprechend gekennzeichneten Unterräume identifiziert, indem das Flag isPromising überprüft wird. Die Indizes dieser Unterräume werden in dem temporären Array „promisingIndices“ gesammelt. Dann wird für jeden Unterraum, dessen Index im Array „promisingIndices“ steht, die Funktion DivideSubspace aufgerufen, um den Index dieses Unterraums zu übergeben.

Die Methode iteriert also durch alle gefundenen vielversprechenden Unterräume und wendet nacheinander auf jeden von ihnen mit der Funktion DivideSubspace eine Division an.

//+----------------------------------------------------------------------------+
//| Separate promising subspaces                                               |
//+----------------------------------------------------------------------------+
void C_AO_FBA::DividePromisingSubspaces ()
{
  // Collect indices of promising subspaces
  int promisingIndices [];
  int numPromising = 0;

  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    if (subspaces [i].isPromising)
    {
      numPromising++;
      ArrayResize (promisingIndices, numPromising);
      promisingIndices [numPromising - 1] = i;
    }
  }

  // Divide each promising subspace
  for (int i = 0; i < numPromising; i++)
  {
    DivideSubspace (promisingIndices [i]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode DivideSubspace dient dazu, einen bestimmten Unterraum in kleinere Teile zu unterteilen. Zunächst wird der übergeordnete Unterraum auf der Grundlage des übergebenen Index ausgewählt. Wir achten darauf, dass die Gesamtzahl der Unterräume die festgelegte Grenze (10.000) nicht überschreitet. Die Gesamtzahl der neuen Unterräume, die sich aus der Aufteilung jeder Dimension in „m_value“-Teile ergibt, wird bestimmt – dies ist die Erhöhung von m_value auf eine Potenz gleich der Anzahl der Dimensionen.

Das Array, in dem alle Unterräume gespeichert sind, wird um die Anzahl der neu erstellten Unterräume erweitert. Für jeden neuen Unterraum werden Anfangsparameter festgelegt, z. B. die Ebene, der Index des übergeordneten Unterraums und die Grenzen für jede Koordinate, die auf der Grundlage der Grenzen des übergeordneten Unterraums und der Aufteilung in gleiche Teile berechnet werden.

Für jede Dimension wird eine Intervallgröße bestimmt, und die Grenzen des aktuellen Unterraums werden entsprechend auf der Grundlage der aktuellen Indizes festgelegt. Nach der Erstellung jedes neuen Unterraums werden die Indizes in den Dimensionen inkrementiert, um zur nächsten Partitionierung gemäß dem Multi-Index-System zu gelangen. Wenn der Index in einer Dimension m_value erreicht, wird er auf Null zurückgesetzt, und der Index der nächsten Dimension wird erhöht, und alle Kombinationen werden ausprobiert.

Der Prozess wird so lange fortgesetzt, bis alle neuen Unterräume erstellt sind oder bis das Limit erreicht ist. Sobald alle Indexkombinationen durchlaufen wurden, endet der Vorgang. Bei dieser Methode wird der übergeordnete Unterraum in viele kleinere Unterräume aufgeteilt, die jeweils einen entsprechenden Teil des ursprünglichen Bereichs in allen Dimensionen abdecken.

//+----------------------------------------------------------------------------+
//| Partition a specific subspace                                              |
//+----------------------------------------------------------------------------+
void C_AO_FBA::DivideSubspace (int subspaceIndex)
{
  // Divide the specified subspace into m_value^coords subspaces

  S_Subspace parent = subspaces [subspaceIndex];

  // Limit the maximum number of subspaces
  if (ArraySize (subspaces) > 10000) return;

  // For each dimension, divide by m_value parts
  int totalNewSubspaces = (int)MathPow (m_value, coords);
  int currentSize = ArraySize (subspaces);
  ArrayResize (subspaces, currentSize + totalNewSubspaces);

  // Create new subspaces
  int newIndex = currentSize;
  int indices [];
  ArrayResize (indices, coords);
  for (int i = 0; i < coords; i++) indices [i] = 0;

  for (int idx = 0; idx < totalNewSubspaces && newIndex < ArraySize (subspaces); idx++)
  {
    subspaces [newIndex].Init (coords);
    subspaces [newIndex].level = parent.level + 1;
    subspaces [newIndex].parentIndex = subspaceIndex;

    // Calculate the boundaries of the current subspace
    for (int c = 0; c < coords; c++)
    {
      double intervalSize = (parent.max [c] - parent.min [c]) / m_value;
      subspaces [newIndex].min [c] = parent.min [c] + indices [c] * intervalSize;
      subspaces [newIndex].max [c] = parent.min [c] + (indices [c] + 1) * intervalSize;
    }

    // Move on to the next subspace
    int c = coords - 1;
    while (c >= 0)
    {
      indices [c]++;
      if (indices [c] < m_value) break;
      indices [c] = 0;
      c--;
    }

    // If the full loop completed, exit
    if (c < 0) break;

    newIndex++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode GenerateNewPopulation erstellt eine neue Population von Punkten, die entsprechend ihrem Wert promisingRank auf die Teilräume verteilt werden.

Zunächst wird die gesamte Summe promisingRank für alle Unterräume berechnet. Dieser Wert wird verwendet, um die proportionale Anzahl von Punkten zu bestimmen, die in jedem Unterraum erzeugt werden sollen. Ist die Summe der Ränge nahe Null (weniger als 0,0001), was der Fall sein kann, wenn alle Unterräume den Rang Null haben, dann wird allen Unterräumen der minimale positive Rang (1,0) zugewiesen, um eine gleichmäßige Verteilung der Punkte zu gewährleisten. Dann wird für jeden Unterraum die Anzahl der darin zu erzeugenden Punkte berechnet, die proportional zu seinem promisingRank im Verhältnis zur Gesamtsumme der Ränge ist.

Wir verwenden die Gleichung (subspaces[i].promisingRank / totalRank) * popSize, wobei popSize eine erforderliche Populationsgröße ist. Das Ergebnis wird auf die nächste ganzzahlige Zahl gerundet. Die Anzahl der Punkte wird von oben her begrenzt, um popSize nicht zu überschreiten. Innerhalb jedes Unterraums wird eine berechnete Anzahl von Punkten erzeugt, und für jeden Punkt werden Koordinaten unter Verwendung einer gleichmäßigen Verteilung innerhalb der Grenzen des Unterraums erzeugt. Für jede Dimension wird der Koordinatenwert durch die angegebenen Minimal- und Maximalwerte eingeschränkt und als Gitter mit dem Schritt rangeStep[c] gebildet.

Wenn nach der Verteilung der Punkte auf die Unterräume die Gesamtzahl der erzeugten Punkte kleiner als popSize ist, werden die verbleibenden Punkte gleichmäßig über den gesamten Suchraum unter Verwendung der Grenzen des gesamten rangeMin[c]- und rangeMax[c]-Raums sowie als Begrenzungen erzeugt und als Gitter mit dem Schritt von rangeStep[c] gebildet. Dadurch wird sichergestellt, dass die Population immer die Größe popSize hat.

//+----------------------------------------------------------------------------+
//| Generate a new population                                                  |
//+----------------------------------------------------------------------------+
void C_AO_FBA::GenerateNewPopulation ()
{
  // Calculate the sum of the ranks of all subspaces
  double totalRank = 0.0;
  for (int i = 0; i < ArraySize (subspaces); i++)
  {
    totalRank += subspaces [i].promisingRank;
  }

  // If all ranks are 0, set the uniform distribution
  if (totalRank <= 0.0001) // Check for approximate equality to zero
  {
    for (int i = 0; i < ArraySize (subspaces); i++)
    {
      subspaces [i].promisingRank = 1.0;
    }
    totalRank = ArraySize (subspaces);
  }

  int points = 0;

  for (int i = 0; i < ArraySize (subspaces) && points < popSize; i++)
  {
    // Calculate the number of points for this subspace according to the equation
    int pointsToGenerate = (int)MathRound ((subspaces [i].promisingRank / totalRank) * popSize);

    // Limitation against exceeding the limits 
    pointsToGenerate = MathMin (pointsToGenerate, popSize - points);

    // Generate points in this subspace
    for (int j = 0; j < pointsToGenerate; j++)
    {
      // Create a new point uniformly within the subspace
      for (int c = 0; c < coords; c++)
      {
        a [points].c [c] = u.RNDfromCI (subspaces [i].min [c], subspaces [i].max [c]);
        a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }

      points++;
      if (points >= popSize) break;
    }
  }

  // If not all points were generated, fill the remaining ones uniformly throughout the space
  while (points < popSize)
  {
    for (int c = 0; c < coords; c++)
    {
      a [points].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
    points++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode MutatePoints der Klasse C_AO_FBA dient der Mutation von Punkten in einer Population und ist Teil des Algorithmusverfahrens zur Erhöhung der Variabilität von Lösungen und zur Vermeidung des Hängenbleibens in lokalen Fallen.

Der ursprüngliche Teil der Methode beruht auf der Idee, den Koordinaten zufällig ausgewählter Punkte Gaußsches Rauschen hinzuzufügen, was nach dem ursprünglichen FBA-Algorithmus erfolgt. Mit einer solchen Mutation ist der Algorithmus jedoch schlecht und unterscheidet sich praktisch nicht von den Ergebnissen eines Zufallsalgorithmus, sodass dieser Block auskommentiert wurde, da ich eine bessere Implementierung gefunden habe.

Der wichtigste Teil der Methode besteht darin, die gesamte Population zu untersuchen. Für jeden Agenten (oder Punkt) und jede Koordinate wird eine Wahrscheinlichkeitsbedingung geprüft. Ist sie erfüllt (auf der Grundlage einer vorgegebenen Mutationswahrscheinlichkeit), wird der Koordinatenwert durch eine Funktion auf der Grundlage einer Potenzgesetzverteilung mit einer Potenz geändert, die eine Kontrolle über den Grad der Variation ermöglicht. Anschließend wird der Wert mit einer Funktion verfeinert und begrenzt, die sicherstellt, dass er innerhalb der angegebenen Bereiche bleibt und die Stichprobenschritte berücksichtigt.

Infolgedessen bietet die Methode zufällige Mutationen der einzelnen Punkte der Population, was die Vielfalt der Lösungen fördert und die Fähigkeit verbessert, ein globales Optimum zu finden.

//+----------------------------------------------------------------------------+
//| Mutation of points in the population                                       |
//+----------------------------------------------------------------------------+
void C_AO_FBA::MutatePoints ()
{
  // Add Gaussian noise to P3% of randomly selected points from the new population
  /*
  int numToMutate = (int)MathRound (popSize * P3 / 100.0);
  numToMutate = MathMax (1, MathMin (numToMutate, popSize));

  for (int i = 0; i < numToMutate; i++)
  {
    int index = u.RNDminusOne (popSize);

    // Add noise to each coordinate
    for (int c = 0; c < coords; c++)
    {
      // Standard deviation of 10% of the range
      //double stdDev = (rangeMax [c] - rangeMin [c]) * 0.1;

      // Gaussian noise using the Box-Muller method
      //double noise = NormalRandom (0.0, stdDev);

      // Add noise and limit the value
      a [index].c [c] += noise;
      a [index].c [c] = u.SeInDiSp (a [index].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  */

  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      if (u.RNDprobab () < P3)
      {
        a [p].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20);
        a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode SortByFitness wurde entwickelt, um zwei Arrays zu sortieren – eines mit den Fitnessfunktionswerten und das andere mit den entsprechenden Elementindizes. Es benötigt Parameter: ein Array mit Werten, ein Array mit Indizes, die Größe der Arrays und ein optionales Flag, das die Sortierreihenfolge angibt.

Wenn die Array-Größe größer als eins ist, ruft die Methode die interne QuickSort-Funktion auf, die eine schnelle Sortierung der Elemente durchführt. In diesem Fall werden beide Arrays gleichzeitig sortiert, sodass die Entsprechung zwischen Werten und Indizes erhalten bleibt. Als Ergebnis werden die Elemente nach Ausführung der Methode nach dem Wert der Fitnessfunktion entsprechend der gewählten Reihenfolge geordnet.

//+----------------------------------------------------------------------------+
//| Sort by fitness function value                                             |
//+----------------------------------------------------------------------------+
void C_AO_FBA::SortByFitness (double &values [], int &indices [], int size, bool ascending = false)
{
  if (size > 1) QuickSort (values, indices, 0, size - 1, ascending);
}
//——————————————————————————————————————————————————————————————————————————————

Die QuickSort-Methode implementiert einen schnellen Sortieralgorithmus für zwei verwandte Arrays: „values“ und „indices“. Es unterteilt und sortiert Arrays rekursiv so, dass die Übereinstimmung zwischen einem Wert und seinem ursprünglichen Index erhalten bleibt. Parameter: zu sortierende Arrays, Grenzen des sortierten Bereichs (niedrig und hoch) und das Flag „aufsteigend“, das die Sortierreihenfolge bestimmt.

//+----------------------------------------------------------------------------+
//| Quick sort algorithm                                                       |
//+----------------------------------------------------------------------------+
void C_AO_FBA::QuickSort (double &values [], int &indices [], int low, int high, bool ascending)
{
  if (low < high)
  {
    int pi = Partition (values, indices, low, high, ascending);

    QuickSort (values, indices, low, pi - 1, ascending);
    QuickSort (values, indices, pi + 1, high, ascending);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Partitionierungsmethode ist ein wichtiger Bestandteil des Quick-Sort-Algorithmus. Seine Aufgabe ist es, ein Pivot-Element auszuwählen und die Elemente des Arrays „indices“ so umzuverteilen, dass alle Elemente, die „kleiner“ als der Pivot sind (oder „größer“, je nach Sortierreihenfolge), links davon liegen, und „größere“ („kleinere“) rechts davon liegen. „Kleiner“ und „größer“ sind relativ zu den Werten im Array „Werte“ definiert, auf die die Indizes in „Indizes“ verweisen.

//+----------------------------------------------------------------------------+
//| Partition function for QuickSort                                           |
//+----------------------------------------------------------------------------+
int C_AO_FBA::Partition (double &values [], int &indices [], int low, int high, bool ascending)
{
  double pivot = values [indices [high]];
  int i = low - 1;

  for (int j = low; j < high; j++)
  {
    bool condition = ascending ? (values [indices [j]] < pivot) : (values [indices [j]] > pivot);
    if (condition)
    {
      i++;
      // Exchange values
      int temp = indices [i];
      indices [i] = indices [j];
      indices [j] = temp;
    }
  }

  // Exchange values
  int temp = indices [i + 1];
  indices [i + 1] = indices [high];
  indices [high] = temp;

  return i + 1;
}
//——————————————————————————————————————————————————————————————————————————————

Testergebnisse

Der Algorithmus schneidet insgesamt gut ab.

FBA|Fractal-Based Algorithm|50.0|60.0|30.0|0.8|10.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7900044352090774
25 Hilly's; Func runs: 10000; result: 0.6513385092404853
500 Hilly's; Func runs: 10000; result: 0.2896548031738138
=============================
5 Forest's; Func runs: 10000; result: 0.8715768614282637
25 Forest's; Func runs: 10000; result: 0.5682316842631675
500 Forest's; Func runs: 10000; result: 0.18876552479611478
=============================
5 Megacity's; Func runs: 10000; result: 0.6107692307692306
25 Megacity's; Func runs: 10000; result: 0.46061538461538465
500 Megacity's; Func runs: 10000; result: 0.12398461538461655
=============================
All score: 4.55494 (50.61%)

Die Visualisierung zeigt, wie der Algorithmus den Suchraum in kleinere Unterräume aufteilt. Die Ergebnisse zeigen auch eine hohe Variabilität bei niedrigdimensionalen Funktionen.

FBA mit der Testfunktion Hilly

FBA mit der Testfunktion Forest

FBA mit der Testfunktion Megacity

Auf der Grundlage der Testergebnisse belegt der FBA-Algorithmus Platz 29 in unserer Rangliste.

#	AO	Beschreibung	Hilly			Hilly Final	Forest			Forest Final	Megacity (discrete)			Megacity Final	Final Result	% of MAX
			10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)
1	ANS	Suche über die gesamte Nachbarschaft	0.94948	0.84776	0.43857	2.23581	1.00000	0.92334	0.39988	2.32323	0.70923	0.63477	0.23091	1.57491	6.134	68.15
2	CLA	Code-Sperr-Algorithmus (joo)	0.95345	0.87107	0.37590	2.20042	0.98942	0.91709	0.31642	2.22294	0.79692	0.69385	0.19303	1.68380	6.107	67.86
3	AMOm	Optimierung der Tiermigration M	0.90358	0.84317	0.46284	2.20959	0.99001	0.92436	0.46598	2.38034	0.56769	0.59132	0.23773	1.39675	5.987	66.52
4	(P+O)ES	(P+O) Entwicklungsstrategien	0.92256	0.88101	0.40021	2.20379	0.97750	0.87490	0.31945	2.17185	0.67385	0.62985	0.18634	1.49003	5.866	65.17
5	CTA	Kometenschweif-Algorithmus (joo)	0.95346	0.86319	0.27770	2.09435	0.99794	0.85740	0.33949	2.19484	0.88769	0.56431	0.10512	1.55712	5.846	64.96
6	TETA	Zeit-Evolutions-Reise-Algorithmus (Joo)	0.91362	0.82349	0.31990	2.05701	0.97096	0.89532	0.29324	2.15952	0.73462	0.68569	0.16021	1.58052	5.797	64.41
7	SDSm	stochastische Diffusionssuche M	0.93066	0.85445	0.39476	2.17988	0.99983	0.89244	0.19619	2.08846	0.72333	0.61100	0.10670	1.44103	5.709	63.44
8	BOAm	Billard-Optimierungsalgorithmus M	0.95757	0.82599	0.25235	2.03590	1.00000	0.90036	0.30502	2.20538	0.73538	0.52523	0.09563	1.35625	5.598	62.19
9	AAm	Algorithmus für das Bogenschießen M	0.91744	0.70876	0.42160	2.04780	0.92527	0.75802	0.35328	2.03657	0.67385	0.55200	0.23738	1.46323	5.548	61.64
10	ESG	Entwicklung sozialer Gruppen (joo)	0.99906	0.79654	0.35056	2.14616	1.00000	0.82863	0.13102	1.95965	0.82333	0.55300	0.04725	1.42358	5.529	61.44
11	SIA	Simuliertes isotropes Glühen (Joo)	0.95784	0.84264	0.41465	2.21513	0.98239	0.79586	0.20507	1.98332	0.68667	0.49300	0.09053	1.27020	5.469	60.76
12	ACS	künstliche, kooperative Suche	0.75547	0.74744	0.30407	1.80698	1.00000	0.88861	0.22413	2.11274	0.69077	0.48185	0.13322	1.30583	5.226	58.06
13	DA	dialektischer Algorithmus	0.86183	0.70033	0.33724	1.89940	0.98163	0.72772	0.28718	1.99653	0.70308	0.45292	0.16367	1.31967	5.216	57.95
14	BHAm	Algorithmus für schwarze Löcher M	0.75236	0.76675	0.34583	1.86493	0.93593	0.80152	0.27177	2.00923	0.65077	0.51646	0.15472	1.32195	5.196	57.73
15	ASO	Anarchische Gesellschaftsoptimierung	0.84872	0.74646	0.31465	1.90983	0.96148	0.79150	0.23803	1.99101	0.57077	0.54062	0.16614	1.27752	5.178	57.54
16	RFO	Optimierung des Royal Flush (joo)	0.83361	0.73742	0.34629	1.91733	0.89424	0.73824	0.24098	1.87346	0.63154	0.50292	0.16421	1.29867	5.089	56.55
17	AOSm	Suche nach atomaren Orbitalen M	0.80232	0.70449	0.31021	1.81702	0.85660	0.69451	0.21996	1.77107	0.74615	0.52862	0.14358	1.41835	5.006	55.63
18	TSEA	Schildkrötenpanzer-Evolutionsalgorithmus (joo)	0.96798	0.64480	0.29672	1.90949	0.99449	0.61981	0.22708	1.84139	0.69077	0.42646	0.13598	1.25322	5.004	55.60
19	DE	differentielle Evolution	0.95044	0.61674	0.30308	1.87026	0.95317	0.78896	0.16652	1.90865	0.78667	0.36033	0.02953	1.17653	4.955	55.06
20	SRA	Algorithmus für erfolgreiche Gastronomen (joo)	0.96883	0.63455	0.29217	1.89555	0.94637	0.55506	0.19124	1.69267	0.74923	0.44031	0.12526	1.31480	4.903	54.48
21	CRO	Optimierung chemischer Reaktionen	0.94629	0.66112	0.29853	1.90593	0.87906	0.58422	0.21146	1.67473	0.75846	0.42646	0.12686	1.31178	4.892	54.36
22	BIO	Optimierung der Blutvererbung (joo)	0.81568	0.65336	0.30877	1.77781	0.89937	0.65319	0.21760	1.77016	0.67846	0.47631	0.13902	1.29378	4.842	53.80
23	BSA	Vogelschwarm-Algorithmus	0.89306	0.64900	0.26250	1.80455	0.92420	0.71121	0.24939	1.88479	0.69385	0.32615	0.10012	1.12012	4.809	53.44
24	HS	Harmoniesuche	0.86509	0.68782	0.32527	1.87818	0.99999	0.68002	0.09590	1.77592	0.62000	0.42267	0.05458	1.09725	4.751	52.79
25	SSG	Setzen, Säen und Wachsen	0.77839	0.64925	0.39543	1.82308	0.85973	0.62467	0.17429	1.65869	0.64667	0.44133	0.10598	1.19398	4.676	51.95
26	BCOm	Optimierung mit der bakteriellen Chemotaxis M	0.75953	0.62268	0.31483	1.69704	0.89378	0.61339	0.22542	1.73259	0.65385	0.42092	0.14435	1.21912	4.649	51.65
27	ABO	Optimierung des afrikanischen Büffels	0.83337	0.62247	0.29964	1.75548	0.92170	0.58618	0.19723	1.70511	0.61000	0.43154	0.13225	1.17378	4.634	51.49
28	(PO)ES	(PO) Entwicklungsstrategien	0.79025	0.62647	0.42935	1.84606	0.87616	0.60943	0.19591	1.68151	0.59000	0.37933	0.11322	1.08255	4.610	51.22
29	FBA	Fraktal-basierter Algorithmus	0.79000	0.65134	0.28965	1.73099	0.87158	0.56823	0.18877	1.62858	0.61077	0.46062	0.12398	1.19537	4.555	50.61
30	TSm	Tabu-Suche M	0.87795	0.61431	0.29104	1.78330	0.92885	0.51844	0.19054	1.63783	0.61077	0.38215	0.12157	1.11449	4.536	50.40
31	BSO	Brainstorming-Optimierung	0.93736	0.57616	0.29688	1.81041	0.93131	0.55866	0.23537	1.72534	0.55231	0.29077	0.11914	0.96222	4.498	49.98
32	WOAm	Wal-Optimierungsalgorithmus M	0.84521	0.56298	0.26263	1.67081	0.93100	0.52278	0.16365	1.61743	0.66308	0.41138	0.11357	1.18803	4.476	49.74
33	AEFA	Algorithmus für künstliche elektrische Felder	0.87700	0.61753	0.25235	1.74688	0.92729	0.72698	0.18064	1.83490	0.66615	0.11631	0.09508	0.87754	4.459	49.55
34	AEO	Algorithmus zur Optimierung auf der Grundlage künstlicher Ökosysteme	0.91380	0.46713	0.26470	1.64563	0.90223	0.43705	0.21400	1.55327	0.66154	0.30800	0.28563	1.25517	4.454	49.49
35	ACOm	Ameisen-Kolonie-Optimierung M	0.88190	0.66127	0.30377	1.84693	0.85873	0.58680	0.15051	1.59604	0.59667	0.37333	0.02472	0.99472	4.438	49.31
36	BFO-GA	Optimierung der bakteriellen Futtersuche — ga	0.89150	0.55111	0.31529	1.75790	0.96982	0.39612	0.06305	1.42899	0.72667	0.27500	0.03525	1.03692	4.224	46.93
37	SOA	einfacher Optimierungsalgorithmus	0.91520	0.46976	0.27089	1.65585	0.89675	0.37401	0.16984	1.44060	0.69538	0.28031	0.10852	1.08422	4.181	46.45
38	ABHA	Algorithmus für künstliche Bienenstöcke	0.84131	0.54227	0.26304	1.64663	0.87858	0.47779	0.17181	1.52818	0.50923	0.33877	0.10397	0.95197	4.127	45.85
39	ACMO	Optimierung atmosphärischer Wolkenmodelle	0.90321	0.48546	0.30403	1.69270	0.80268	0.37857	0.19178	1.37303	0.62308	0.24400	0.10795	0.97503	4.041	44.90
40	ADAMm	adaptive Momentabschätzung M	0.88635	0.44766	0.26613	1.60014	0.84497	0.38493	0.16889	1.39880	0.66154	0.27046	0.10594	1.03794	4.037	44.85
41	CGO	Chaos Game Optimization	0.57256	0.37158	0.32018	1.26432	0.61176	0.61931	0.62161	1.85267	0.37538	0.21923	0.19028	0.78490	3.902	43.35
42	ATAm	Algorithmus für künstliche Stämme M	0.71771	0.55304	0.25235	1.52310	0.82491	0.55904	0.20473	1.58867	0.44000	0.18615	0.09411	0.72026	3.832	42.58
43	CROm	Korallenriff-Optimierung M	0.78512	0.46032	0.25958	1.50502	0.86688	0.35297	0.16267	1.38252	0.63231	0.26738	0.10734	1.00703	3.895	43.27
44	CFO	Schwerkraftoptimierung	0.60961	0.54958	0.27831	1.43750	0.63418	0.46833	0.22541	1.32792	0.57231	0.23477	0.09586	0.90294	3.668	40.76
45	ASHA	Algorithmus für künstliches Duschen	0.89686	0.40433	0.25617	1.55737	0.80360	0.35526	0.19160	1.35046	0.47692	0.18123	0.09774	0.75589	3.664	40.71
	RW	Neuroboids Optimierungsalgorithmus 2(joo)	0.48754	0.32159	0.25781	1.06694	0.37554	0.21944	0.15877	0.75375	0.27969	0.14917	0.09847	0.52734	2.348	26.09

Zusammenfassung

Die durch Mutation veränderte Version des FBA-Algorithmus zeigt mit Ergebnissen von 50,61 % eine zweifache Verbesserung der Effizienz im Vergleich zu den Ergebnissen der ursprünglichen Version.

FBA|Fraktal-basierter Algorithmus|50.0|60.0|30.0|5.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.4780639253626462
25 Hilly's; Func runs: 10000; result: 0.3222029113692554
500 Hilly's; Func runs: 10000; result: 0.25720991988937014
=============================
5 Forest's; Func runs: 10000; result: 0.36567166223346415
25 Forest's; Func runs: 10000; result: 0.22043205527307377
500 Forest's; Func runs: 10000; result: 0.15869146061036057
=============================
5 Megacity's; Func runs: 10000; result: 0.2861538461538461
25 Megacity's; Func runs: 10000; result: 0.15015384615384622
500 Megacity's; Func runs: 10000; result: 0.09838461538461622
=============================
All score: 2.33696 (25.97%)

Aufgrund grundlegender Änderungen im Mutationsmechanismus bietet der neue Ansatz ein vernünftigeres Gleichgewicht zwischen der globalen Erkundung des Suchraums und der lokalen Nutzung der entdeckten vielversprechenden Lösungen.

Die wichtigste Errungenschaft ist, dass der Algorithmus nun das gesammelte Wissen über die Suchlandschaft nutzt, um die Mutation zu steuern, anstatt völlig zufällige Änderungen vorzunehmen. Dies entspricht eher den natürlichen Optimierungsprozessen, bei denen Zufälligkeit und Determinismus in einem ausgewogenen Verhältnis zueinander stehen. Dieser Ansatz ermöglicht es dem Algorithmus, schneller zum globalen Optimum zu konvergieren, insbesondere in komplexen mehrdimensionalen Räumen mit zahlreichen lokalen Extrema, was die deutliche Leistungssteigerung erklärt.

Abbildung 2. Farbskala der Algorithmen nach den entsprechenden Tests

Abbildung 3. Histogramm der Algorithmus-Testergebnisse (Skala von 0 bis 100, je höher, desto besser, wobei 100 das maximal mögliche theoretische Ergebnis ist; im Archiv befindet sich ein Skript zur Berechnung der Bewertungstabelle)

Vor- und Nachteile von FBA:

Vorteile:

1. Stabile Ergebnisse für Funktionen mittlerer und hoher Dimension.

Nachteile:

1. Große Streuung der Ergebnisse bei niedrigdimensionalen Funktionen.
2. Eine interessante, aber eher „schwache“ Grundidee des Algorithmus.

Dem Artikel ist ein Archiv mit den aktuellen Versionen des Algorithmuscodes beigefügt. Der Autor des Artikels übernimmt keine Verantwortung für die absolute Richtigkeit der Beschreibung der kanonischen Algorithmen. An vielen von ihnen wurden Änderungen vorgenommen, um die Suchmöglichkeiten zu verbessern. Die in den Artikeln dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Versuche.

• github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

Programme, die in diesem Artikel verwendet werden

#	Name	Typ	Beschreibung
1	#C_AO.mqh	Include	Übergeordnete Klasse von Populationsoptimierungsalgorithmen
2	#C_AO_enum.mqh	Include	Enumeration der Populationsoptimierungsalgorithmen
3	TestFunctions.mqh	Include	Bibliothek mit Testfunktionen
4	TestStandFunctions.mqh	Include	Bibliothek mit Funktionen für die Testumgebung
5	Utilities.mqh	Include	Bibliothek mit Hilfsfunktionen
6	CalculationTestResults.mqh	Include	Skript zur Berechnung der Ergebnisse in der Vergleichstabelle
7	Testing AOs.mq5	Skript	Die einheitliche Testumgebung für alle Algorithmen zur Populationsoptimierung
8	Simple use of population optimization algorithms.mq5	Skript	Ein einfaches Beispiel für die Verwendung von Algorithmen zur Populationsoptimierung ohne Visualisierung
9	Test_FBA.mq5	Skript	FBA-Testumgebung