Algorithmen zur Optimierung mit Populationen Fish School Search (FSS)

Inhalt

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

1. Einführung

Ein Fischschwarm ist die allgemeine Bezeichnung für eine Ansammlung von Fischen, die sich an einem bestimmten Ort versammelt haben. Fischschwarm können strukturiert oder unstrukturiert sein. Bei einem unstrukturierten Ansammlung könnte es sich um eine Gruppe verschiedener Arten und Größen handeln, die sich zufällig in der Nähe einer lokalen Ressource wie Nahrung oder Nistplätze versammelt hat.

Wenn der Schwarm darüber hinaus in interaktiver, sozialer Weise zusammenkommt, kann man von einem Schwarmverhalten sprechen. Die meisten von ihnen befinden sich in der gleichen Phase ihres Lebenszyklus, stehen in aktivem Kontakt zueinander und können jederzeit biologisch aktive und organisierte Aktivitäten entfalten, die für die Mitglieder der Gruppe nützlich sind.
Im Gegensatz zur individuellen Lebensweise ist die gesellige Lebensweise ein Kompromiss zwischen den Vorteilen des Gruppenlebens in Bezug auf den besseren Schutz vor Raubtieren und dem verstärkten Wettbewerb bei der Nahrungsbeschaffung.

In der Natur bilden Fische Schwärme auf verschiedene Weise. In der Regel bevorzugen sie größere Schwärme, die nur aus Individuen ihrer eigenen Art bestehen. Jedes Mitglied des Schwarms, das durch sein Äußeres auffällt oder sich in irgendeiner Weise von der Masse abhebt, wird zu einem bevorzugten Ziel für Raubtiere. Diese Tatsache erklärt, warum Fische Schwärme gleicher Individuen bevorzugen. Auf diese Weise wird eine Homogenität der gesamten Schule erreicht.

Ein Schwarm ist recht starr organisiert, wenn die Fische synchron mit derselben Geschwindigkeit und in dieselbe Richtung schwimmen. Das liegt daran, dass sich die Fische derselben Art, desselben Alters und derselben Größe in einem bestimmten Abstand voneinander bewegen. Fischschwärme sind in der Lage, komplexe Manöver durchzuführen, als ob sie eine Gruppenintelligenz und einen gemeinsamen Verstand hätten.
Die Feinheiten der Schulbildung sind noch lange nicht vollständig erforscht, insbesondere die Aspekte der Bewegung und der Ernährung.

Viele Hypothesen wurden aufgestellt, um das gesellige Verhalten zu erklären, darunter die bessere Orientierung, die Synchronisierung der Jagd, die Verwirrung der Raubtiere und das geringere Risiko, gefangen zu werden. Fischschwärme scheinen Informationen auszutauschen, um das Verhalten der anderen aus nächster Nähe zu kontrollieren. Das Fressverhalten eines Fisches löst bei anderen schnell eine aktive Nahrungssuche aus. Fischschwärme schwimmen in schlanken Phalanxen, die oft schnell auf- und absteigen und sich um die eigene Achse drehen, während sie die Form des Schwarmes verändern, um Zusammenstöße zu vermeiden. Solche Manöver erfordern ein sehr schnelles Reaktionssystem. Eine schwimmende Lebensweise setzt voraus, dass die Fische über Sinnessysteme verfügen, die sofort auf kleine Veränderungen ihrer Position im Verhältnis zu ihren Nachbarn reagieren können.

Um ein vollständigeres Bild zu erhalten, wird eine mathematische Modellierung dieses Verhaltens vorgenommen. Die gängigsten mathematischen Modelle gehen davon aus, dass die einzelnen Tiere in einer Schule drei Grundregeln befolgen:

1. Sich in dieselbe Richtung wie der Nachbar bewegen
2. In der Nähe Ihrer Nachbarn bleiben
3. Kollisionen mit benachbarten Individuen zu vermeiden

Die Frage, wie Schwarmfische die Richtung wählen, in die sie schwimmen, ist nach wie vor ungelöst. Auch wenn alle Mitglieder eines Schwarmes gleichermaßen über die Verfügbarkeit von Nahrung informiert sind, gibt es doch einige Anführer in der Gruppe, die mutiger sind als ihre anderen Verwandten. Dieses Schulungsverhalten hat viele Forscher dazu veranlasst, nicht nur ein mathematisches Modell, sondern auch ein algorithmisches Modell für die Lösung verschiedener Optimierungsprobleme zu entwickeln.

2. Beschreibung des Algorithmus

Die Fish School Search (FSS) ist eine Unterfamilie der Schwarmintelligenz-Algorithmen, die zur Klasse der metaheuristischen Algorithmen gehören. Es wurde 2008 von Bastos Filho und Lima Neto vorgeschlagen und 2009 erstmals veröffentlicht. In FSS werden einfache Agenten als Fische bezeichnet, und jeder Fisch hat ein Gewicht, das den während der Suche erzielten „Erfolg“ darstellt. Die Werte und Schwankungen der Gewichte wirken sich auf individuelle und kollektive Bewegungen aus. Eingebaute Fütterungs- und koordinierte Aktionsmechanismen zwingen die Schule, sich in Richtung eines positiven Gradienten zu bewegen, um an Gewicht zu gewinnen und die besten Plätze lokal und global zu finden. FSS wurde für kontinuierliche Optimierungsprobleme in multimodalen Suchräumen entwickelt. Dies veranlasste auch andere Forscher, Optionen für die Lösung anderer Probleme vorzuschlagen, wie z. B. die Optimierung bei binären Problemen und die Mehrzieloptimierung.

Beim FSS-Algorithmus kann man sich vereinfacht vorstellen, dass Fische in einem ‚bedingten‘ Aquarium schwimmen, dessen Wände die Grenzen des Bereichs der untersuchten Funktionsdefinition sind. Das Fischgewicht ist ein Maß für den Erfolg bei der Suche nach Nahrung (Lösungen). Außerdem spielt es die Rolle des Gedächtnisses der Fische. Die Existenz der Gewichte ist die Hauptidee des Algorithmus und der Unterschied zu einem Schwarm von Partikeln. Durch diese Eigenschaft des FSS-Algorithmus entfällt die Notwendigkeit, global beste Lösungen zu finden und festzulegen, wie es bei einem Partikelschwarm der Fall ist.

Die Operatoren des FSS-Algorithmus werden in zwei Gruppen unterteilt:
- Der fütternde Operator formalisiert den Erfolg der Gebietserkundung.
- Der schwimmende Operator implementieren Migrationsalgorithmen für einzelne Fische und den Schwarm als Ganzes.

Der fütternde Operator berechnet das Gewicht des Fisches. Die Grundidee besteht darin, die Fische dazu zu bringen, in Richtung eines positiven Gefälles zu „schwimmen“, um zu „fressen“ und „an Gewicht zuzulegen“. Insgesamt haben schwerere Fische einen größeren Einfluss auf den gesamten Suchprozess, was dazu führt, dass sich das Zentrum des Fischschwarms im Laufe der Iterationen in Richtung besserer Positionen im Suchraum bewegt. Der Gewichtszuwachs bei einer bestimmten Iteration ist proportional zur normierten Differenz der Werte der Fitnessfunktion:

fishes [f].weight = fishes [f].weight + (fishes [f].delta_fitness / max_delta_fitness);

wobei:

• weight - Fischgewicht
• delta_fitness - Differenz zwischen den Werten der Fitnessfunktion
  
• max_delta_fitness - Höchstwert der Differenz der Fitnessfunktionen aller Fische

Je nach Art der Bewegung werden die schwimmenden Händler in drei Typen unterteilt:

- individuell;

- instinktiv-kollektiv;

- kollektiv-volitional;

Individuelles Schwimmen kann als eine lokale Suche in der Nähe der aktuellen Position des Fisches interpretiert werden. Der Bewegungsvektor jedes Individuums ist zufällig ausgerichtet und hat einen anderen Wert.

fishes [f].new_position [d] = fishes [f].current_position [d] + step_ind [d] * r;

wobei:

• new_position - neue Position an der entsprechenden Koordinate
• current_position - aktuelle Position auf der entsprechenden Koordinate
• step_ind - individueller Bewegungsschritt, berechnet als

initial_step_ind * (rangeMax [d] - rangeMin [d]);

wobei:

• initial_step_ind - Algorithmusparameter für individuelle Bewegung
• rangeMax und rangeMin - optimierte Wertebereiche für Argumente
  
• r - Zufallszahl [-1.0;1.0]

Das individuelle Schwimmen ist in Abbildung 1 schematisch dargestellt.

Abb. 1. Individuelles Schwimmen. Der Bewegungsvektor eines jeden Fisches hat eine zufällige Richtung und jeweils andere Skalarwerte

Nach dem individuellen Schwimmen wird die Fitnessfunktion gemessen. Wenn sich die Position des Fisches nicht verbessert hat, gehen wir davon aus, dass dieser Fisch sich nicht bewegt hat und an seinem Platz bleibt. Nur die Fische, die ihre Fitnessfunktionen verbessert haben, werden in eine neue Position gebracht.

Nach Beendigung des Einzelschwimmens wird der instinktiv-kollektive Bewegungsoperator ausgeführt. Schauen wir uns zunächst Abbildung 2 an.

Abb. 2. Instinktiv-kollektives Schwimmen Die Bewegung ist für alle Fische durch Vektoren derselben Richtung und Länge relativ zum Massenschwerpunkt G gekennzeichnet.

Die instinktive-kollektive Bewegung dient dazu, die allgemeine Position des Fischschwarms zu korrigieren, wobei die Veränderung der Fitnessfunktion jedes Fisches in der vorherigen Iteration berücksichtigt wird. Die neuen Koordinaten werden wie folgt berechnet:

fishes [f].new_position [d] = fishes [f].current_position [d] + collective_instinct [d];

wobei:

• new_position - neue Position des Fisches an der entsprechenden Koordinate
• current_position - aktuelle Position auf der entsprechenden Koordinate
• collective_instinct - Betrag der Bewegung entlang der entsprechenden Koordinate, berechnet als:

collective_instinct [d] = fishes [f].delta_position [d] * fishes [f].delta_fitness;

wobei:

• delta_position - Differenz zwischen den Koordinaten der aktuellen und der vorherigen Position, die in der Phase des individuellen Schwimmens ermittelt wurde
• delta_fitness - Veränderung der Fitnessfunktionen der aktuellen Position und der vorherigen Position beim individuellen Schwimmen

Instinktiv-kollektives Schwimmen formalisiert die gruppensynchrone Bewegung eines Fischschwarms zu einem neuen Ort und ermöglicht die Suche nach neuen Futterplätzen, während die individuelle Bewegung eine Verbesserung der lokalen Situation ermöglicht.

Betrachten wir nun das kollektiv-volitionelle Schwimmen. Es wird in zwei Arten unterteilt:

- Vom Zentrum der Masse weg - wenn sich die Position des Schwarmes als Ganzes im Vergleich zur vorherigen Position nicht verbessert hat, während die Fische sich seitlich ausbreiten, was eine weitere Nahrungssuche symbolisiert (Abbildung 3).

- Zum Zentrum der Masse hin - wenn eine Verbesserung eingetreten ist. Dann bewegen sich die Fische zum Zentrum der Masse, wobei sie den Ring zusammendrücken und den Angriff auf die Beute symbolisieren. Algorithmisch gesehen bedeutet dies eine Verfeinerung der Lösung des Optimierungsproblems (Abbildung 4).

Abb. 3. Kollektiv-volitionelles Schwimmen. Die Richtungsvektoren zeigen vom Zentrum G der Masse weg

Abb. 4. Kollektiv-volitionelles Schwimmen. Die Richtungsvektoren zeige zum Zentrum G der Masse

Für die Berechnung des kollektiven Schwimmens wird das Konzept des Massenzentrums eingeführt. Von hier aus sieht die Gleichung für das kollektive Schwimmen wie folgt aus:

fishes [f].new_position [d] = pos + (((pos - barycenter [d]) * step_vol [d] * r) * search_operator);

wobei:

• pos ist die gleiche Position wie current_position
• search_operator - 1, wenn der vorherige Zug zu einer Positionsverbesserung führte, und -1, wenn nicht
  
• 
  
• step_vol [d] - kollektiver Bewegungsschritt, berechnet als:

step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]);

wobei:

• initial_step_vol - Algorithmusparameter für die kollektive Bewegung
• 
  
• barycenter [d] - Massenzentrum, berechnet aus der Summe der Fischgewichte multipliziert mit der Koordinate:

barycenter [d] += fishes [f].weight * fishes [f].current_position [d];

und dividiert durch das Gesamtgewicht des Fischschwarms:

barycenter [d] /= current_total_weight;

Der Pseudocode des Algorithmus sieht wie folgt aus:

1) Initialisierung der Fischpositionen mit Zufallszahlen

2) Einzelbewegungen

3) Berechnung der Fitnessfunktion

4) Neudefinition der Gewichte für jeden Fisch

5) Instinktiv-kollektive Bewegung

6) Kollektiv-volitionelle Bewegung

7) Neuberechnung das Gesamtgewicht

8) Berechnung der Fitnessfunktion

9) Wiederholung ab Schritt 2) bis das Stoppkriterium erfüllt ist.

Abbildung 5. Blockschaltbild des Algorithmus

Beginnen wir mit der Beschreibung des Codes.

Wie man sich vorstellen kann, ist die einfachste logische Einheit des Algorithmus die Struktur, die den Fisch beschreibt. Da wir den Fisch mehrmals initialisieren müssen, ist es ratsam, diese Struktur aufgrund ihrer relativ großen Größe in der speziellen Methode Init() „auf Null“ zu setzen, wodurch wir den Code leicht optimieren können. Die Struktur enthält die Koordinatenfelder für die aktuelle Position, die neue Position und die Differenz der Koordinaten seit der letzten Bewegung. Das Standardgewicht von 1000 Standardeinheiten kann einen beliebigen Wert haben. Ein Fisch wird auch durch den Wert der aktuellen Fitnessfunktion, der vorherigen und der Differenz zwischen ihnen charakterisiert. In der Methode Init() wird die Fitnessfunktion mit dem kleinstmöglichen 'double'-Wert initialisiert. Der Fitnessunterschied ist also gleich Null, da sich der Fisch noch nicht bewegt hat.

//——————————————————————————————————————————————————————————————————————————————
struct S_Fish
{
  void Init (int dimensions)
  {
    ArrayResize (current_position, dimensions);
    ArrayResize (new_position,     dimensions);
    ArrayResize (delta_position,   dimensions);
    weight        = 1000.0;
    fitness       = -DBL_MAX;
    delta_fitness = 0.0;
  }

  double current_position [];
  double new_position     [];
  double delta_position   [];
  double weight;
  double fitness;
  double new_fitness;
  double delta_fitness;
};
//——————————————————————————————————————————————————————————————————————————————

Erklären wir die Klasse C_AO_FSS - ein Fischschwarm, der das natürliche Gemeinschaftsmodell mathematisch darstellt. Das ist nichts Ungewöhnliches. Es gibt auch zwei öffentliche Methoden, die für die Interaktion mit dem Nutzerprogramm erforderlich sind - die Wertebereiche der optimierten Funktion, die notwendig sind, um die Koordinaten der Fische und die Interaktion in einer Schule zu berücksichtigen, sowie die Arrays.

In der öffentlichen Methode der Initialisierungsklasse Init() müssen die Variablen auf ihre ursprünglichen Werte zurückgesetzt und Speicher für Arrays zugewiesen werden. Achten wir besonders auf die Variablen init und swimmingRegime. Gemäß dem Pseudocode, den wir gesehen haben, wird die Berechnung der Fitnessfunktion zweimal durchgeführt: das erste Mal - nach einer individuellen Bewegung, das zweite Mal - nach zwei Arten von kollektiven Bewegungen. Dies widerspricht dem von uns angenommenen Schema der Algorithmus-Anwendungs-Verknüpfung, das besagt, dass jede Iteration eine Abfolge aufweist: erste_Methode -> calculation_fitness_functions -> zweite_Methode. Diese beiden Variablen werden verwendet, um dies zu beheben und die Reihenfolge der Aktionen im kanonischen Algorithmus zu ändern. Die init-Variable sollte zu Beginn des Algorithmus „false“ sein. Dies ist ein Flag, das die Notwendigkeit anzeigt, den Fisch zu initialisieren, die Fitnessfunktion zu berechnen und die Bewegung erneut durchzuführen, da die gesamte Logik des Algorithmus die Differenz zwischen dem aktuellen und dem vorherigen Wert der Koordinaten und der Fitnessfunktion verwendet. Ohne sie hätten wir die Wertdifferenz nicht ermitteln können. Das zweite wichtige Flag ist swimmingRegime. Es erlaubt uns, die Reihenfolge des Aufrufs von Methoden, die die Bewegung von Fischen beschreiben, neu festzulegen, sodass sie unserer Struktur entspricht. Der Wert 1 entspricht dem Aufruf zum „individuellen“ Schwimmen, andernfalls verwenden wir die Abfolge der Gruppenbewegungen, die wir oben betrachtet haben.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Init (const int    dimensionsP,
                     const int    fishSchSizeP,
                     const double initial_step_indP,
                     const double initial_step_volP)
{
  MathSrand (GetTickCount ());
  init = false;
  swimmingRegime = 1;

  dimensions     = dimensionsP;

  ArrayResize (rangeMax,  dimensions);
  ArrayResize (rangeMin,  dimensions);
  ArrayResize (rangeStep, dimensions);

  num_of_individuos = fishSchSizeP;

  ArrayResize (fishes, num_of_individuos);

  for (int i = 0; i < num_of_individuos; i++)
  {
    fishes [i].Init (dimensions);
  }

  global_best = -DBL_MAX;
  ArrayResize (global_best_position, dimensions);

  total_weight     = num_of_individuos;

  initial_step_ind = initial_step_indP;
  ArrayResize (step_ind, dimensions);

  initial_step_vol = initial_step_volP;
  ArrayResize (step_vol, dimensions);

  ArrayResize (collective_instinct, dimensions);
  ArrayResize (barycenter, dimensions);
}
//——————————————————————————————————————————————————————————————————————————————

Die erste öffentliche Methode, die bei jeder Iteration aufgerufen wird, nämlich Swimming(), bestimmt die Reihenfolge der Aufrufe von Einzel- und Gruppenfischbewegungen. Wird die Methode zum ersten Mal aufgerufen, so werden die Einzel- und Gruppenbewegungsschritte mit Hilfe der beiden Algorithmusparameter initial_step_ind und initial_step_vol als Teil des möglichen Bereichs entlang der entsprechenden Koordinate initialisiert. Einige Autoren empfehlen, die Werte auf 0,01 bzw. 0,001 zu setzen. Allerdings habe ich mit diesen Werten keine guten Ergebnisse erzielt. Ich verwende also 0,1 und 0,8. Außerdem wird beim ersten Durchlauf des Algorithmus der aktuelle Wert der Fischpositionskoordinaten mit Zufallszahlen innerhalb des Bereichs der optimierten Parameter initialisiert. Bei nachfolgenden Methodenaufrufen werden die entsprechenden Bewegungsarten entsprechend dem Flag swimmingRegime aufgerufen.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Swimming (int i)
{
  //----------------------------------------------------------------------------
  if (!init)
  {
    global_best    = -DBL_MAX;
    swimmingRegime = 1;

    for (int d = 0; d < dimensions; d++)
    {
      step_ind [d] = initial_step_ind * (rangeMax [d] - rangeMin [d]);
      step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]);
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      fishes [f].Init (dimensions);

      for (int d = 0; d < dimensions; d++)
      {
        fishes [f].new_position [d] = RNDfromCI (rangeMin [d], rangeMax [d]);
        fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
      }
    }
  }
  //----------------------------------------------------------------------------
  else
  {
    switch (swimmingRegime)
    {
    case 1:
      apply_individual_movement ();            //individual movement
      break;
    default:
      apply_instintive_collective_movement (); //instinctively-collective movement
      apply_collective_volitive_movement ();   //collective-volitional movement
      update_total_weight ();                  //recalculate the total weight
      break;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die zweite öffentliche Methode, die bei jeder Iteration aufgerufen wird, Regrouping(), dient in erster Linie dazu, die Reihenfolge der Aufrufe der Schwimmmethoden festzulegen - individuell, kollektiv-instinktiv, kollektiv-volitional. Zusätzliche Funktionalität der Methode zur Sicherstellung der Reihenfolge der Aufrufe wird durch das Flag swimmingRegime bereitgestellt, das die Werte 1 und 2 annimmt. Dies ist notwendig, um die Reihenfolge des Aufrufs von Fischbewegungsmethoden in der klassischen Version für die von mir angenommene Struktur neu zu definieren: first_open_method -> _fitness_function_calculation -> second_open_method. Wenn sich der Algorithmus in der ersten Iteration befindet, wird abhängig vom Init-Flag die aktuelle Position der Koordinaten und der Wert der Fitnessfunktion für die weitere Berechnung ihrer Unterschiede gespeichert, da angenommen wird, dass die Methode nach der Berechnung der Fitnessfunktion aufgerufen wird. Wenn das Init-Flag anzeigt, dass sich der Algorithmus in der zweiten und den folgenden Iterationen befindet, muss nach einer einzelnen Bewegung die Differenz zwischen dem aktuellen und dem vorherigen Wert der Fitnessfunktion sowie die Differenz zwischen den Koordinaten der aktuellen und der vorherigen Position ermittelt werden. Die Differenzen werden unter der Voraussetzung berechnet, dass sich die Lage verbessert hat, andernfalls gehen wir davon aus, dass keine Bewegung stattgefunden hat. Wir setzen also die Werte des Fischgewichts auf den Ausgangszustand zurück, und die Unterschiede in den Bewegungen und den Fitnessfunktionen werden mit Null gleichgesetzt. Wir aktualisieren die beste Lösung sofort, wenn sie erreicht ist, indem wir die Methode updates_optimal_solution() aufrufen, und wir wenden die Fischfütterung mit der Methode apply_feeding() an. Wenn das Flag swimmingRegime ungleich 1 ist, dann wurden kollektiv-instinktive und kollektiv-volitionale Bewegungen angewendet. Nach ihrer Ausführung setzen wir swimmingRegime auf 1. Als Nächstes wird eine individuelle Bewegung folgen.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Regrouping ()
{
  //----------------------------------------------------------------------------
  if (swimmingRegime == 1
  {
    if (!init)
    {
      for (int f = 0; f < num_of_individuos; f++)
      {
        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
        ArrayInitialize (fishes [f].delta_position, 0.0);

        fishes [f].fitness = fishes [f].new_fitness;
        fishes [f].delta_fitness = 0.0;
      }

      init = true;
      return;
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      //remember the best position for the fish
      if (fishes [f].new_fitness > fishes [f].fitness)
      {
        fishes [f].delta_fitness = fishes [f].new_fitness - fishes [f].fitness; //fabs
        fishes [f].fitness = fishes [f].new_fitness;

        for (int d = 0; d < dimensions; d++)
        {
          fishes [f].delta_position [d] = fishes [f].new_position [d] - fishes [f].current_position [d];
        }

        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
      }
      else
      {
        ArrayInitialize (fishes [f].delta_position, 0.0);
        fishes [f].delta_fitness = 0.0;
      }
    }

    swimmingRegime = 2;
    updates_optimal_solution ();
    apply_feeding ();
    return;
  }

  //----------------------------------------------------------------------------
  swimmingRegime = 1;
  updates_optimal_solution ();
}
//——————————————————————————————————————————————————————————————————————————————

Die folgende einfache private Methode wird verwendet, um die besten Ergebnisse des Algorithmus zu aktualisieren, wenn sie erreicht werden. Dazu vergleichen wir einfach die Werte der Fitnessfunktionen der einzelnen Fische mit den globalen Werten. Wenn sie besser sind, sollte man sie sichern.

//——————————————————————————————————————————————————————————————————————————————
// update the best overall solution
void C_AO_FSS::updates_optimal_solution ()
{
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].fitness > global_best)
    {
      global_best = fishes [f].fitness;
      ArrayCopy (global_best_position, fishes [f].current_position, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Wir haben die Gleichung der privaten Methode, die das individuelle Schwimmen ermöglicht, bereits oben betrachtet. Hier ist also alles ganz einfach: Wir addieren zu den aktuellen Koordinaten jedes Fisches einen individuellen Schritt, multipliziert mit einer Zufallszahl im Bereich von -1,0 bis 1,0, was eine Steigerung sowohl in positiver als auch in negativer Richtung ergibt. Wenn die optimierten Parameterwerte über den Bereich hinausgehen, wird der Grenzwert für die Koordinate festgelegt.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_individual_movement ()
{
  // move the fish to new places-----------------------------------------------
  double r = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (-1.0, 1.0);

      fishes [f].new_position [d] = fishes [f].current_position [d] + step_ind [d] * r;
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Art der Fütterung sollte keine Verständnisschwierigkeiten verursachen. Das Gewicht des Fisches wird nämlich als Quotient aus der Differenz in der Fitnessfunktion des Fisches selbst und dem Maximalwert der Differenz im gesamten Fischschwarm bestimmt. Es kann jedoch vorkommen, dass die maximale Differenz zwischen allen Fischen gleich Null ist. Die Beschreibung der klassischen Version des Algorithmus besagt, dass das Gewicht der Fische immer positiv sein muss. Im Allgemeinen werden nur Fälle berücksichtigt, in denen die Fitnessfunktion positive Werte annimmt, aber ich fand diese Anforderung in der Praxis nicht sinnvoll. Ich gebe zu, dass das Gewicht der Fische negative Werte annehmen kann. Wenn also die maximale Differenz der Fitnessfunktion (das ist der Wert, auf den wir das Gewicht jedes Fisches normieren müssen) unter allen Fischen Null ist, dann wird das Gewicht des Fisches mit 1 gleichgesetzt.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_feeding ()
{
  double max_delta_fitness = -DBL_MAX;

  //find the maximum weight among fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].delta_fitness > max_delta_fitness) max_delta_fitness = fishes [f].delta_fitness;
  }

  //feed the fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (max_delta_fitness != 0.0)
    {
      fishes [f].weight = fishes [f].weight + (fishes [f].delta_fitness / max_delta_fitness);
    }
    else fishes [f].weight = 1;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die private Methode der instinktiven-kollektiven Bewegung besteht darin, die Koordinaten jedes Fisches zu ändern, indem der Wert des kollektiven Instinkts erhöht wird, der wiederum nichts anderes ist als das Produkt aus der Differenz der Positionen in der aktuellen und der vorherigen Iteration und der Differenz der Fitnessfunktion, die bei den vorherigen Bewegungen erreicht wurde. Hier weisen wir die Werte der Grenzen zu, wenn wir die Grenzen der optimierten Parameter überschreiten.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_instintive_collective_movement ()
{
  double sum_delta_fitness = 0.0;
  for (int f = 0; f < num_of_individuos; f++)
  {
    sum_delta_fitness += fishes [f].delta_fitness;
  }

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      collective_instinct [d] = fishes [f].delta_position [d] * fishes [f].delta_fitness;

      if (sum_delta_fitness != 0.0)
      {
        collective_instinct [d] /= sum_delta_fitness;
      }

      fishes [f].new_position [d] = fishes [f].current_position [d] + collective_instinct [d];
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die private Methode des kollektiven Schwimmens, bei der der Massenschwerpunkt eines Fischschwarms sowie das aktuelle Gesamtgewicht berechnet werden. Wenn das Gesamtgewicht des Schwarmes zugenommen hat, bewegen sich die Fische in Richtung des Massenzentrums, andernfalls - weg vom Zentrum. Die Gleichung wurde bereits eingehend erörtert. Das Gesamtgewicht eines Fischschwarms wird mit einer speziellen, weiter unten beschriebenen Methode aktualisiert.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_collective_volitive_movement ()
{
  //----------------------------------------------------------------------------
  double current_total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    current_total_weight += fishes [f].weight;
  }

  ArrayInitialize (barycenter, 0.0);

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      barycenter [d] += fishes [f].weight * fishes [f].current_position [d];
    }
  }

  for (int d = 0; d < dimensions; d++)
  {
    barycenter [d] /= current_total_weight;
  }

  //----------------------------------------------------------------------------
  double search_operator = current_total_weight > total_weight ? 1.0 : -1.0;
  double r   = 0.0;
  double pos = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (0.0, 1.0);
      pos = fishes [f].current_position [d];

      fishes [f].new_position [d] = pos + (((pos - barycenter [d]) * step_vol [d] * r) * search_operator);
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Dies ist die eigentliche Methode zur Aktualisierung des Gesamtgewichts der Fische. Alles ist einfach hier. Wir nehmen das Gewicht jedes Fisches und addieren es.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::update_total_weight ()
{
  total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    total_weight += fishes [f].weight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Testergebnisse

Kommen wir nun zum letzten und interessantesten Teil - den Ergebnissen. Der Algorithmus enthält interessante Tricks, wie das Fehlen der Notwendigkeit, das globale Optimum zu berücksichtigen, die Einführung des Konzepts des Massenschwerpunkts und der instinktiv-volitionellen Bewegung, was eine Konvergenz oder Streuung vom Zentrum der Schule aus bedeutet, je nachdem, ob die Position als Ganzes verbessert wurde. All dies ließ auf das ursprüngliche Verhalten des Algorithmus bei den untersuchten Funktionen hoffen.

Im Allgemeinen ist das Verhalten im Suchbereich des Raums originell, d. h. es gibt eine Aufteilung der Fische in verschiedene Teile des Raums, ähnlich wie beim Bienenalgorithmus, obwohl eine detaillierte Betrachtung der Gleichungen und des Funktionsprinzips des FSS nicht die Aufteilung des Schwarmes in einzelne Gruppen impliziert. Im Allgemeinen schnitt der Algorithmus schlecht ab und übertraf den PSO-Algorithmus in Bezug auf das Gesamtergebnis nur leicht.

Betrachtet man die einzelnen Tests, so konnte der FSS in einigen von ihnen dennoch glänzen. Insbesondere bei der glatten Skin-Funktion erwies sich der FSS-Algorithmus als besser als der Wolf-Algorithmus und zeigte gute (aber nicht die besten) Ergebnisse, was leicht zu erklären ist. Der Algorithmus verwendet die Steigung der Oberfläche der zu untersuchenden Funktion, die in Inkrementen für jede der Koordinaten betrachtet wird, und die Veränderung der Fitnessfunktion bei jeder Iteration. Da die Skin-Funktion glatt ist, passt sich der Algorithmus gut an Oberflächenänderungen an.

Was die Forest-Funktion betrifft, so lag der Algorithmus unter dem Durchschnitt. Sanfte Änderungen der Testfunktion halfen dem Algorithmus in gewissem Maße, sich im Raum zurechtzufinden, aber er konnte das globale Maximum nicht finden. Bei der Betrachtung von Megacity werden die Unzulänglichkeiten des FSS noch deutlicher. Der Algorithmus „mag“ es nicht, wenn sich die zu untersuchende Funktion in der Nähe der aktuellen Position der einzelnen Agenten nicht ändert, und der Algorithmus ist nicht in der Lage, weite Sprünge zu machen, um neue, potenziell bessere Orte zu ermitteln. Daher bleibt er in allen lokalen Extrema stecken, die kein Inkrement in der Nähe aufweisen.

Obwohl der Megacity-Test für jeden Optimierungsalgorithmus sehr schwierig ist und die anderen Teilnehmer in der Vergleichstabelle dem FSS im Allgemeinen nicht viel voraus sind, ist es dennoch notwendig, die schwachen Fähigkeiten des Algorithmus bei diskreten Problemen zu erkennen. In einigen Tests zeigte die Zufallssuche das beste Ergebnis. Wie in der Animation zu sehen ist, lässt sich bei der Anwendung des Algorithmus keine „Clusterbildung“ feststellen. Vielleicht erinnern Sie sich an den Optimierungsalgorithmus „Kristallisierung“, der im vorherigen Artikel beschrieben wurde.

Ergebnisse des FSS-Algorithmus:

2022.12.08 13:14:06.033    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:14:08.388    Test_AO_FSS (EURUSD,M1)    1 Skin; Funktionsdurchläufe 10000 Ergebnis: 4.892861444841324
2022.12.08 13:14:08.388    Test_AO_FSS (EURUSD,M1)    Score: 0.99391
2022.12.08 13:14:12.557    Test_AO_FSS (EURUSD,M1)    20 Skins; Funktionsdurchläufe 10000 Ergebnis: 3.11410005347766
2022.12.08 13:14:12.557    Test_AO_FSS (EURUSD,M1)    Score: 0.56920
2022.12.08 13:14:47.176    Test_AO_FSS (EURUSD,M1)    500 Skins; Funktionsdurchläufe 10000 Ergebnis: 1.20519552002827
2022.12.08 13:14:47.176    Test_AO_FSS (EURUSD,M1)    Score: 0.11341
2022.12.08 13:14:47.176    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:14:49.498    Test_AO_FSS (EURUSD,M1)    1 Forest; Funktionsdurchläufe 10000 Ergebnis: 1.5057381856551146
2022.12.08 13:14:49.498    Test_AO_FSS (EURUSD,M1)    Score: 0.85172
2022.12.08 13:14:53.825    Test_AO_FSS (EURUSD,M1)    20 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.21468156279781656
2022.12.08 13:14:53.825    Test_AO_FSS (EURUSD,M1)    Score: 0.12143
2022.12.08 13:15:31.235    Test_AO_FSS (EURUSD,M1)    500 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.056970068652984526
2022.12.08 13:15:31.235    Test_AO_FSS (EURUSD,M1)    Score: 0.03223
2022.12.08 13:15:31.235    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:15:34.066    Test_AO_FSS (EURUSD,M1)    1 Megacity; Funktionsdurchläufe 10000 Ergebnis: 11.0
2022.12.08 13:15:34.066    Test_AO_FSS (EURUSD,M1)    Score: 0.91667
2022.12.08 13:15:38.467    Test_AO_FSS (EURUSD,M1)    20 Megacitys; Funktionsdurchläufe 10000 Ergebnis: 1.03
2022.12.08 13:15:38.467    Test_AO_FSS (EURUSD,M1)    Score: 0.08583
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    500 Megacitys; Funktionsdurchläufe 10000 Ergebnis: 0.31
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    Score: 0.02583
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    All score for C_AO_FSS: 0.4122477188979048

  FSS mit der Testfunktion Skin.

Forestalt

  ACO mit der Testfunktion Forest.

  ACO mit der Testfunktion Megacity.

Hier ist die finale Tabelle. Sie enthält zusätzliche Spalten, um die Bewertung der Algorithmen für jede Testfunktion separat zu erleichtern, was es uns ermöglicht, die Anwendbarkeit der einzelnen Algorithmen für bestimmte Aufgaben fairer zu diskutieren.

AO	Beschreibung	Skin			Skin final	Forest			Forest final	Megacity (diskrete)			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)
COAm	Kuckuck-Optimierungsalgorithmus	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	Ameisenkolonie-Optimierung (ACO)	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	fish school search	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
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

Stochastische (randomisierte) heuristische Methoden garantieren keine exakte Lösung, aber sie ermöglichen es in der Regel, in akzeptabler Zeit Lösungen zu finden, die für den praktischen Einsatz ausreichen. Die Praxis zeigt jedoch, dass einige Algorithmen hervorragende Konvergenzfähigkeiten aufweisen, was bei FSS jedoch nicht der Fall ist. Im Allgemeinen ist der Suchalgorithmus für einen Fischschwarm ein Spezialfall von Algorithmen, die auf einem Schwarm von Partikeln basieren. Daher hat es sowohl Vorteile als auch Nachteile. Zu den einzigartigen Merkmalen des Algorithmus gehört die Aufteilung eines Fischschwarms in einzelne Gruppen, die bei einem Partikelschwarm nicht beobachtet wird. Der Algorithmus kommt mit glatten Funktionen relativ gut zurecht, obwohl nicht sicher ist, ob FSS auch mit Funktionen mit mehreren Variablen zurechtkommt.

Vorteile:
1. Der Algorithmus verarbeitet glatte Funktionen recht gut.
2. Die Fähigkeit eines Fischschwarms, sich in einzelne Gruppen aufzuteilen, was es dem Algorithmus ermöglicht, weitere potenziell gute lokale Extremwerte zu untersuchen.

Nachteile
1. Eine große Streuung der Ergebnisse in einzelnen Tests deutet auf die Instabilität des Algorithmus hin.
2. Sehr schwache Konvergenz bei diskreten Funktionen und bei Funktionen mit Brüchen. Dies ist bei diskreten Funktionen fast nicht möglich.
3. Schwache Skalierbarkeit.