Algorithmen zur Optimierung mit Populationen: Evolution sozialer Gruppen (ESG)

Inhalt

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

1. Einführung

Im Bereich der Optimierung gibt es eine breite Palette von Populationsalgorithmen, die darauf ausgelegt sind, optimale Lösungen für verschiedene Probleme zu finden. Trotz ihrer Bedeutung sind die Algorithmen mit mehreren Populationen und Schwärmen bisher in meinen Artikeln nicht ausreichend behandelt worden. In diesem Zusammenhang halte ich es für notwendig, dieses faszinierende und vielversprechende Thema ausführlicher zu behandeln.

Algorithmen mit mehreren Populationen basieren auf der Idee, mehrere unabhängige Populationen zur Lösung von Optimierungsproblemen zu verwenden. Die Populationen arbeiten logisch parallel und können Informationen über optimale Lösungen austauschen, wodurch es möglich ist, gleichzeitig verschiedene Regionen des Parameterraums zu untersuchen und verschiedene Optima zu finden. Andererseits verwenden Multischwarm-Algorithmen soziale Gruppen (Schwärme) aus vielen interagierenden Partikeln (Mitgliedern), die auch miteinander kooperieren und Informationen austauschen können, um optimale Lösungen zu erzielen.

In diesem Artikel werden wir den ESG-Algorithmus mit mehreren Populationen betrachten, den ich speziell für diesen Artikel entwickelt habe. Wir werden uns mit den Grundprinzipien solcher Algorithmen befassen. Darüber hinaus werden wir die Ergebnisse vergleichender Studien berücksichtigen, die es uns ermöglichen, die Effektivität dieser Algorithmen im Vergleich zu Monopopulations-Optimierungsmethoden zu bewerten.

2. Der Algorithmus

Der Mehrpopulationsalgorithmus kann auf den folgenden Prinzipien in verschiedenen Kombinationen beruhen:

1. Soziale Gruppen. Der Algorithmus arbeitet nicht mit Individuen, sondern mit sozialen Gruppen, die durch Zusammenarbeit und Erfahrungsaustausch verbunden sind. Jede Gruppe hat ihr eigenes Entscheidungszentrum und einen Satz von Partikeln (Mitgliedern) als Optimierungsagenten. Gruppen interagieren, tauschen Erfahrungen aus und nutzen Informationen über die besten Lösungen, um ihre Ergebnisse zu verbessern.

2. Kollektive Bewegung. Die „Partikel“ der sozialen Gruppen interagieren und bewegen sich gemeinsam im Parameterraum. Auf diese Weise können die Gruppen verschiedene Regionen des Parameterraums untersuchen und Informationen über die besten gefundenen Lösungen austauschen.

3. Lokale und globale Erfahrung. Jede soziale Gruppe speichert Informationen über die beste Lösung innerhalb ihrer Gruppe (lokale Erfahrung). Es gibt auch eine beste Gesamtbewertung unter allen Gruppen (globale Erfahrung). Gruppen behalten die besten Lösungen, tauschen Erfahrungen aus und nutzen sie zur Verbesserung der Ergebnisse.

4. Entwicklung und Austausch von Erfahrungen. Der Algorithmus durchläuft Iterationen, während derer soziale Gruppen ihre Erfahrungen aktualisieren und austauschen. Es gibt eine iterative Verbesserung der Lösungen und eine Suche nach dem optimalen Ergebnis.

5. Anpassungsfähigkeit und Vielfalt. Durch Interaktion und Erfahrungsaustausch können sich Gruppen an veränderte Bedingungen anpassen und eine Vielzahl optimaler Lösungen finden. Der Algorithmus hat die Eigenschaft der Anpassungsfähigkeit, die es ihm ermöglicht, effektiv auf sich ändernde Bedingungen und Anforderungen des Optimierungsproblems zu reagieren. Gruppen können sich an neue Bedingungen anpassen, ihre Strategie für die Bewegung durch den Parameterraum ändern und ihre Entscheidungen aufgrund von Erfahrungen aktualisieren. Dadurch kann der Algorithmus effizient nach optimalen Lösungen suchen, insbesondere in Fällen, in denen sich die Problembedingungen im Laufe der Zeit ändern.

Oben haben wir über die Grundprinzipien von Algorithmen mit mehreren Populationen gesprochen. Schauen wir uns nun die Besonderheiten der ESG-Suchstrategie an.

Nehmen wir an, wir haben eine Gesellschaft von „Partikeln“, die wir eine „soziale Gruppe“ nennen. In dieser Gruppe herrscht ein bestimmtes Verhaltensmodell (das „Zentrum“) vor, und die Partikel der Gruppe folgen diesem Modell mit einer gewissen Abweichung, die durch ein bestimmtes Verteilungsgesetz beschrieben werden kann. Die meisten Partikel weichen geringfügig vom Zentrum ab, aber einige weichen stark innerhalb der Einflusszone der Gruppe ab, deren Grenzen durch die Verteilung bestimmt werden. Wenn ein besser angepasstes Verhaltensmuster unter den Partikeln auftaucht, wird es zum neuen Zentrum der Gruppe. Die Gruppe ist also auf der Suche nach dem stabilsten Modell des Partikelverhaltens.

Es kann mehrere solcher Gruppen geben, und sie sind unabhängig, sodass man von einem Mehrpopulationsalgorithmus sprechen kann, der das Verhalten einzelner Mitglieder in sozialen Gruppen auf einer niedrigen Ebene und das allgemeine Verhalten von Gruppen auf einer hohen Ebene simuliert.

Angesichts dieses Konzepts sind Situationen möglich, in denen einige einzelne Gruppen oder sogar alle Gruppen gleichzeitig in ihrer Entwicklung stehen bleiben und in lokalen Extremen stecken bleiben. Um dies zu vermeiden, führen wir das Konzept der „Erweiterung des Einflussbereichs einer sozialen Gruppe“ ein. Wenn bei jeder Iteration kein Fortschritt erzielt wird, werden die Gruppengrenzen erweitert, sodass neue Suchbereiche eröffnet werden und die Gruppenpopulation diversifiziert wird. Findet die Gruppe eine Lösung, die besser ist als die vorherige, wird der Radius der Gruppengrenze wieder auf den vorgegebenen Mindestwert reduziert. Dies hilft dem Algorithmus, nicht in lokalen Fallen stecken zu bleiben, und verbessert gegebenenfalls die Erkundung neuer Gebiete. Die Vergrößerung des Radius trägt auch zur Vielfalt der sozialen Gruppen bei. Verschiedene Gruppen werden unterschiedliche Regionen des Parameterraums untersuchen.

Dieses Konzept eines Mehrpopulationsalgorithmus für die Evolution sozialer Gruppen ist vielversprechend. Doch nicht alles ist so einfach, wie es auf den ersten Blick scheinen mag. Die derzeitige Position des Zentrums der Gruppe kann sich in einer ungünstigen Lage auf den entsprechenden Koordinaten befinden, und selbst eine Ausweitung des Einflussbereichs ist möglicherweise nicht wirksam. In solchen Fällen kann man von einer „diagonalen Ausdehnung“ sprechen (wie beim ACO-Algorithmus, bei dem die Ameisen nur entlang ihrer Pfade laufen, ohne seitlich abzuweichen), während in Wirklichkeit eine „senkrechte Ausdehnung“ erforderlich ist, oder es ist auch das genaue Gegenteil möglich.

Um das oben genannte Problem zu überwinden, muss sichergestellt werden, dass erfolgreiche Erfahrungen zwischen den Gruppen weitergegeben werden. Zu diesem Zweck kann es einigen Partikeln gestattet werden, Ideen aus den Zentren „fremder“ Gruppen zu übernehmen. So wird das zentrale Verhaltensmuster einzelne Partikel anderer Gruppen beeinflussen. Übrigens können und werden die Auswirkungen nicht unbedingt positiv sein. Das Verhaltensmodell für soziale Gruppen ist in Abbildung 1 schematisch dargestellt.

Abbildung 1. Algorithmus-Methode. Getrennte Gruppen, Erweiterung bei mangelndem Fortschritt, Verengung bei Verbesserung der Lösung,

Ausleihen der „besten Ideen“ (Koordinaten) aus benachbarten „Bt“ (best of team) Gruppen durch „p0“ Partikel (Partikel am bedingten 0. Gruppenindex)

Der Pseudocode des ESG-Algorithmus kann wie folgt dargestellt werden:

1. Platziere die Zentren der Gruppen nach dem Zufallsprinzip im Suchraum.
2. Platziere die Partikel der Gruppen um die entsprechenden Zentren mit einer bestimmten Verteilung*.
3. Berechne die Fitnesswerte der Partikel.
4. Aktualisiere die globale Lösung.
5. Aktualisiere die Mitte jeder Gruppe.
6. Erweiter die Grenzen der Gruppen, wenn sich die Position des Zentrums nicht verbessert, und verkleine sie, wenn es uns gelungen ist, die Position zu verbessern.
7. Platziere die Partikel der Gruppen um die entsprechenden Zentren mit einer vorgegebenen Verteilung.
8. Füge Informationen aus den Zentren von „Alien-Gruppen“ zu einem Partikel jeder Gruppe hinzu (das Partikel erhält einen Satz von Koordinaten aus zufällig ausgewählten Alien-Gruppen).
9. Berechne die Fitnesswerte der Partikel.
   
10. Wiederhole den Vorgang ab Schritt 4 bis das Stoppkriterium erfüllt ist.

* - In ESG habe ich das Potenzgesetz für die Verteilung der Gruppenpartikel relativ zum Zentrum verwendet. Es können jedoch auch andere Verteilungsgesetze verwendet werden, einschließlich ihrer Kombinationen für einzelne Teile der Strategielogik. Das Thema ist offen für Experimente.

Kommen wir nun zur Überprüfung des Codes. Um eine soziale Gruppe zu beschreiben, schreiben wir die Struktur S_Group, die mehrere Mitgliedsvariablen enthält:

• “cB“ - Array von Werten zur Speicherung der „Mittelpunktskoordinaten“.
• “fB“ - zentrale Fitnessfunktion, initialisiert durch „-DBL_MAX“.
• “sSize“ - Größe der Gruppe.
• “sRadius“ - Radius der Gruppe.
  

Die Init-Methode in der Struktur nimmt zwei Argumente entgegen: „coords“ - die Anzahl der Koordinaten und „groupSize“ - die Größe der Gruppe.

//——————————————————————————————————————————————————————————————————————————————
struct S_Group
{
  void Init (int coords, int groupSize)
  {
    ArrayResize (cB, coords);
    fB          = -DBL_MAX;
    sSize       = groupSize;
  }

  double cB [];
  double fB;
  int    sSize;
  double sRadius;
};
//——————————————————————————————————————————————————————————————————————————————

Eine einfache Struktur, die den Suchagenten beschreibt, ist für die Logik des ESG-Algorithmus geeignet. Ich habe mich dafür entschieden, die Struktur der Agentenpartikel nicht in die Gruppenbeschreibungsfelder aufzunehmen. Jede Gruppe wird Zugang zu ihren Partikeln als Teil der allgemeinen Population haben, wodurch der übliche Zugang zu Agenten von außerhalb des Algorithmus beibehalten und gleichzeitig das unnötige Kopieren von Gruppenpartikeln in Agenten vermieden werden kann.

Die Definition der S_Agent-Struktur enthält zwei Variablen:

• „c“ - Array von Koordinatenwerten des Agenten.
• „f“ - Fitnesswert des Agenten, initialisiert durch „-DBL_MAX“.
  

Die Init-Methode nimmt das Argument „coords“, um die Größe des Arrays „c“ zu ändern.

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (const int coords)
  {
    ArrayResize (c, coords);
    f = -DBL_MAX;
  }

  double c []; //coordinates
  double f;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Definieren der Klasse C_AO_ESG, die mehrere Felder und Methoden enthält:

1. Öffentliche Felder:

• „cB“ - Array von Werten für die besten Koordinaten der globalen Lösung.
• „fB“ - Fitnesswert der besten Koordinaten.
• „a“ - Array von Objekten des Typs S_Agent, die Agenten darstellen.
• „rangeMax“ - Array der maximalen Suchbereichswerte.
• „rangeMin“ - Array der minimalen Suchbereichswerte.
•  „rangeStep“ - Array von Werten für Suchschritte.

2. Methoden:

• „Init“ - Funktion zur Initialisierung der Variablen der Klassenmitglieder. Akzeptiert Argumente: Anzahl der Koordinaten, Bevölkerungsgröße, Anzahl der Gruppen, anfänglicher Gruppenradius, Gruppenexpansionsfaktor und Grad der Verteilung.
  
• „Moving“ - die Methode ist für das Verschieben von Bearbeitern zuständig.
• „Revision“ - die Methode ist für die Revision von Bearbeitern zuständig.
• „SeInDiSp“ - Methode zur Berechnung von Werten in einem Bereich mit einem bestimmten Schritt.
• „RNDfromCI“ - Methode zur Erzeugung von Zufallszahlen in einem bestimmten Intervall.
• „Skalieren“ - Methode zur Skalierung von Werten von einem Bereich in einen anderen.
• „PowerDistribution“ - Methode zur Erzeugung von Werten gemäß einer Leistungsverteilung.

3. Private Felder:

• „coords“ - Anzahl der Koordinaten.
• „popSize“ - Größe der Bevölkerung.
• „gr“ - Array von Objekten des Typs S_Group, die Gruppen darstellen.
• „groups“ - Anzahl der Gruppen.
• „groupRadius“ - Radius der Gruppe.
• „expansionRatio“ - Ausdehnungsverhältnis.
• „power“ - Wert der Verteilung nach dem Potenzgesetz.
•  „revision“ - Flag, das die Notwendigkeit einer Revision anzeigt.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ESG
{
  //----------------------------------------------------------------------------
  public: double  cB [];       //best coordinates
  public: double  fB;          //FF of the best coordinates
  public: S_Agent a  [];       //agents

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search

  public: void Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    groupsP,              //number of groups
                     const double groupRadiusP,         //group radius
                     const double expansionRatioP,      //expansion ratio
                     const double powerP);              //power

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

  //----------------------------------------------------------------------------
  private: int     coords;
  private: int     popSize;          //population size
  private: S_Group gr [];            //group

  private: int    groups;            //number of groups
  private: double groupRadius;       //group radius
  private: double expansionRatio;    //expansion ratio
  private: double power;             //power

  private: bool   revision;

  private: double SeInDiSp          (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI         (double min, double max);
  private: double Scale             (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
  private: double PowerDistribution (const double In, const double outMin, const double outMax, const double power);
};
//——————————————————————————————————————————————————————————————————————————————

Die Init-Methode der Klasse dient der Initialisierung von Klassenvariablen auf der Grundlage der übergebenen Parameter. Neben der primären Initialisierung von Variablen und der Festlegung der Größen von Arrays berechnet die Methode die Anzahl der Partikel in jeder Gruppe, wenn die Anzahl der Gruppen nicht ein Vielfaches der Populationsgröße ist.

Die Größe des Arrays „partInSwarms“ wird auf „groups“ geändert, wobei „groups“ die Anzahl der Gruppen angibt. Die Variable „particles“ wird dann auf das Ergebnis der Division von „popSize“ durch „groups“ gesetzt, wobei „popSize“ die Populationsgröße ist. Die Werte des Arrays „partInSwarms“ werden mit dem Wert „particles“, d. h. der Menge ohne Rest, gefüllt. Die Anzahl der verlorenen Mitglieder wird dann berechnet, indem das Produkt aus „particles“ und „groups“ von „popSize“ abgezogen wird. Wenn es verlorene Mitglieder gibt („lost > 0“), werden sie gleichmäßig auf die Gruppen in der „while“-Schleife verteilt.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ESG::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    groupsP,              //number of groups
                     const double groupRadiusP,         //group radius
                     const double expansionRatioP,      //expansion ratio
                     const double powerP)
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords         = coordinatesNumberP;
  popSize        = populationSizeP;
  groups         = groupsP;
  groupRadius    = groupRadiusP;
  expansionRatio = expansionRatioP;
  power          = powerP;

  //----------------------------------------------------------------------------
  int partInSwarms [];
  ArrayResize (partInSwarms, groups);

  int particles = popSize / groups;
  ArrayInitialize (partInSwarms, particles);

  int lost = popSize - particles * groups;

  if (lost > 0)
  {
    int pos = 0;

    while (true)
    {
      partInSwarms [pos]++;
      lost--;
      pos++;
      if (pos >= groups) pos = 0;
      if (lost == 0) break;
    }
  }

  //----------------------------------------------------------------------------
  ArrayResize (rangeMax,  coords);
  ArrayResize (rangeMin,  coords);
  ArrayResize (rangeStep, coords);
  ArrayResize (cB,        coords);

  ArrayResize (gr,        groups);
  for (int s = 0; s < groups; s++) gr [s].Init (coords, partInSwarms [s]);

  ArrayResize (a, popSize);
  for (int i = 0; i < popSize; i++) a [i].Init (coords);
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode „Moving“ wird verwendet, um zu Beginn der Optimierung Gruppenzentren und Individuen zu erzeugen. Die Methode geht folgendermaßen vor:

• Generierung von Zentren für jede „s“-Gruppe in der äußeren „for“-Schleife. Zu diesem Zweck erzeugt eine verschachtelte „for“-Schleife für jede „c“-Koordinate einen Zufallswert in einem bestimmten Bereich. Der „Koordinaten“-Wert wird dann in den gewünschten Bereich umgewandelt und in dem Array „gr[s].cB[c]“ gespeichert.

• Erzeugung von Individuen für jede Gruppe „s“ und jedes Individuum „p“ in der äußeren „for“-Schleife. Der Wert von „radius“ wird auf der Grundlage der angegebenen Parameter und des aktuellen Zustands der Gruppe in den verschachtelten „for“-Schleifen berechnet. Die „Min“- und „Max“-Werte werden dann durch Anpassung des „Radius“ relativ zu den Bereichsgrenzen berechnet. Mit der Funktion „PowerDistribution“ wird dann ein zufälliger „Koordinaten“-Wert innerhalb des angegebenen Bereichs erzeugt. Der sich daraus ergebende „Koordinaten“-Wert wird umgewandelt und in der Matrix „a[cnt].c[c]“ gespeichert.

• Setzen des Flags „Revision“ auf „true“, um anzuzeigen, dass die Erstellung von Zentren und Einzelpersonen im Gange ist.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ESG::Moving ()
{
  if (!revision)
  {
    int    cnt        = 0;
    double coordinate = 0.0;
    double radius     = 0.0;
    double min        = 0.0;
    double max        = 0.0;

    //generate centers----------------------------------------------------------
    for (int s = 0; s < groups; s++)
    {
      gr [s].sRadius = groupRadius;

      for (int c = 0; c < coords; c++)
      {
        coordinate    = RNDfromCI (rangeMin [c], rangeMax [c]);
        gr [s].cB [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    //generate individuals of groups--------------------------------------------
    for (int s = 0; s < groups; s++)
    {
      for (int p = 0; p < gr [s].sSize; p++)
      {
        for (int c = 0; c < coords; c++)
        {
          radius = (rangeMax [c] - rangeMin [c]) * gr [s].sRadius;
          min    = gr [s].cB [c] - radius;
          max    = gr [s].cB [c] + radius;

          if (min < rangeMin [c]) min = rangeMin [c];
          if (max > rangeMax [c]) max = rangeMax [c];

          coordinate    = PowerDistribution (gr [s].cB [c], min, max, power);
          a [cnt].c [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
        }

        cnt++;
      }
    }

    revision = true;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die wichtigsten Aktionen zur Erzeugung neuer Partikel finden in der „Revisions“-Methode statt, die die beste globale Lösung aktualisiert, neue Individuen von Gruppen erzeugt und Erfahrungen zwischen Gruppen austauscht, indem Informationen aus den Zentren „fremder“ Gruppen auf ein Partikel übertragen werden. So darf nur ein Partikel einer Gruppe Erfahrungen von anderen Gruppen ausleihen. Die Methode geht folgendermaßen vor:

• Aktualisierung der globalen Lösung. In der „for“-Schleife gehen wir durch alle Individuen und prüfen, ob der Wert der Fitnessfunktion des aktuellen Individuums den aktuell besten Wert der Fitnessfunktion übersteigt. Dann wird der beste Wert aktualisiert und das Koordinatenfeld des aktuellen Individuums wird in das Koordinatenfeld der besten Lösung kopiert.

• Generierung neuer Gruppenindividuen. In der „for“-Schleife gehen wir alle Gruppen und deren Einzelpersonen durch. Der Radius sowie die minimalen und maximalen Koordinatenwerte für jede Gruppe werden in verschachtelten Schleifen berechnet. Anschließend werden mit der Funktion „PowerDistribution“ zufällige Koordinatenwerte erzeugt und das Ergebnis in einem Array mit den Koordinaten der Individuen gespeichert.

• Erfahrungsaustausch zwischen den Gruppen. In der „for“-Schleife gehen wir alle Gruppen durch. In der verschachtelten „for“-Schleife wird ein Zufallswert generiert, der bestimmt, mit welcher Gruppe das Erlebnis ausgetauscht wird. Die Koordinatenwerte der Personen in der aktuellen Gruppe werden dann mit den Koordinatenwerten der ausgewählten Gruppe aktualisiert.

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

  //----------------------------------------------------------------------------
  int cnt = 0;
  bool impr = false;

  for (int s = 0; s < groups; s++)
  {
    impr = false;

    for (int p = 0; p < gr [s].sSize; p++)
    {
      if (a [cnt].f > gr [s].fB)
      {
        gr [s].fB = a [cnt].f;
        ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY);
        impr = true;
      }

      cnt++;
    }

    if (!impr) gr [s].sRadius *= expansionRatio;
    else       gr [s].sRadius  = groupRadius;

    if (gr [s].sRadius > 0.5) gr [s].sRadius = 0.5;
  }

  //generate individuals of groups----------------------------------------------
  double coordinate = 0.0;
  double radius     = 0.0;
  double min        = 0.0;
  double max        = 0.0;
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < gr [s].sSize; p++)
    {
      for (int c = 0; c < coords; c++)
      {
        if (RNDfromCI (0.0, 1.0) < 1.0)
        {
        radius = (rangeMax [c] - rangeMin [c]) * gr [s].sRadius;
        min    = gr [s].cB [c] - radius;
        max    = gr [s].cB [c] + radius;

        if (min < rangeMin [c]) min = rangeMin [c];
        if (max > rangeMax [c]) max = rangeMax [c];

        coordinate    = PowerDistribution (gr [s].cB [c], min, max, power);
        a [cnt].c [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
        }
      }

      cnt++;
    }
  }

  //exchange of experience----------------------------------------------------------------
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int c = 0; c < coords; c++)
    {
      int posSw = (int)RNDfromCI (0, groups);
      if (posSw >= groups) posSw = groups - 1;

      //if (sw [posSw].fB > sw [s].fB)
      {
        a [cnt].c [c] = gr [posSw].cB [c];
      }
    }

    cnt += gr [s].sSize;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Nachdem ich den oben vorgestellten ESG-Algorithmus geschrieben hatte, beschloss ich, Änderungen vorzunehmen und den Partikeln verschiedener Gruppen den Austausch von Informationen zu ermöglichen, um die kombinatorischen Eigenschaften des Algorithmus zu verbessern. Zu diesem Zweck müssen wir Änderungen an der Agentenstruktur vornehmen. Wir benötigen zusätzliche Felder: „cMain“ - Hauptkoordinaten und „fMain“ - Haupterfahrung.

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (const int coords)
  {
    ArrayResize (c,     coords);
    ArrayResize (cMain, coords);
    f     = -DBL_MAX;
    fMain = -DBL_MAX;
  }

  double c     []; //coordinates
  double cMain []; //coordinates
  double f;        //fitness
  double fMain;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Der Unterschied zwischen den beiden Optionen liegt in den Änderungen, die an der Methode „Revision“ vorgenommen wurden:

1. In der Hauptversion findet der Erfahrungsaustausch zwischen den Agenten auf Gruppenebene statt. In der inneren „for“-Schleife wird eine zufällige Gruppe ausgewählt, und der Koordinatenwert des aktuellen Agenten wird durch den mittleren Koordinatenwert der ausgewählten Gruppe ersetzt. Gruppen tauschen also Erfahrungen aus, indem sie diese auf nur ein Partikel der entsprechenden Gruppe übertragen.

2. Bei der zweiten Option erfolgt der Erfahrungsaustausch zwischen Agenten auf der Ebene der gesamten Population, d. h. zwischen Partikeln von Gruppen, wenn das für den Austausch ausgewählte Partikel eine höhere Fitness aufweist. Daher können nur die besten Partikel Erfahrungen an die schlechtesten Teilchen zwischen den Gruppen weitergeben. In der inneren „for“-Schleife wird ein zufälliger Agent ausgewählt, und mit einer bestimmten Wahrscheinlichkeit (bestimmt durch den Wert „copyProb“) wird der Koordinatenwert des aktuellen Agenten durch den Koordinatenwert des ausgewählten Agenten in der Population ersetzt.

Außerdem enthält die zweite Option einen zusätzlichen Codeblock, der die Agenten aktualisiert. Wenn der Wert der Fitnessfunktion des aktuellen Agenten größer ist als sein vorheriger bester Wert (f > fMain), dann werden die Koordinatenwerte des aktuellen Agenten mit den Werten seiner aktuell besten Lösung (cMain) aktualisiert. So können die Agenten ihre besten Entscheidungen speichern und später nutzen.

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

  //----------------------------------------------------------------------------
  //update agents
  for (int p = 0; p < popSize; p++)
  {
    if (a [p].f > a [p].fMain)
    {
      a [p].fMain = a [p].f;
      ArrayCopy (a [p].cMain, a [p].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  int cnt = 0;
  bool impr = false;

  for (int s = 0; s < groups; s++)
  {
    impr = false;

    for (int p = 0; p < gr [s].sSize; p++)
    {
      if (a [cnt].f > gr [s].fB)
      {
        gr [s].fB = a [cnt].f;
        ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY);
        impr = true;
      }

      cnt++;
    }

    if (!impr) gr [s].sRadius *= expansionRatio;
    else       gr [s].sRadius  = groupRadius;

    if (gr [s].sRadius > 0.5) gr [s].sRadius = 0.5;
  }

  //generate individuals of groups----------------------------------------------
  double coordinate = 0.0;
  double radius     = 0.0;
  double min        = 0.0;
  double max        = 0.0;
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < gr [s].sSize; p++)
    {
      for (int c = 0; c < coords; c++)
      {
        if (RNDfromCI (0.0, 1.0) < 0.6)
        {
        radius        = (rangeMax [c] - rangeMin [c]) * gr [s].sRadius;
        min           = gr [s].cB [c] - radius;
        max           = gr [s].cB [c] + radius;

        if (min < rangeMin [c]) min = rangeMin [c];
        if (max > rangeMax [c]) max = rangeMax [c];

        coordinate    = PowerDistribution (gr [s].cB [c], min, max, power);
        a [cnt].c [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
        }
      }

      cnt++;
    }
  }

  //exchange of experience----------------------------------------------------------------
  cnt = 0;

  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      int pos = (int)RNDfromCI (0, popSize);
      if (pos >= popSize) pos = popSize - 1;

      if (RNDfromCI(0.0, 1.0) < copyProb)
      {
        if (a [pos].fMain > a [p].fMain)
        {
          a [p].c [c] = a [pos].cMain [c];
        }
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Versuche und Tests der zweiten Version des Algorithmus ergaben, dass das Gesamtergebnis nicht den erwarteten Fortschritt brachte und sich leicht verschlechterte. Dies lässt sich dadurch erklären, dass es wichtig ist, die Erfahrungen der Partikel innerhalb der Grenzen ihrer eigenen Gruppe zu halten und keine vollständige Vermischung der Ideen zwischen den Gruppen zuzulassen. Die einzigartigen Erfahrungen jeder einzelnen Gruppe sollten bewahrt und nur ein teilweiser Austausch von Erfahrungen gewährleistet werden.

Das Scheitern des Experiments ist nicht endgültig und bedeutet nicht, dass eine Verbesserung des Algorithmus unmöglich ist. Dies ist nur ein Versuch, der es uns ermöglicht zu verstehen, welche Aspekte es wert sind, beachtet zu werden und welche Strategien am besten anzuwenden sind. Durch weitere Forschung und Entwicklung können die gewonnenen Erkenntnisse genutzt werden, um neue Varianten des Algorithmus zu entwickeln, die zu erheblichen Verbesserungen der Suchfunktionen führen können. Es ist wichtig, optimistisch und beharrlich zu bleiben, um die gesetzten Ziele zu erreichen. Die Testergebnisse werden im Folgenden vorgestellt.

3. Testergebnisse

Testergebnisse der ESG-Hauptversion:

C_AO_ESG|200|100|0.1|2.0|10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9990564816911227
25 Hilly's; Func runs: 10000; result: 0.7965424362150277
500 Hilly's; Func runs: 10000; result: 0.35055904999599663
=============================
5 Forest's; Func runs: 10000; result: 1.0
25 Forest's; Func runs: 10000; result: 0.8286255415345216
500 Forest's; Func runs: 10000; result: 0.13102081222227177
=============================
5 Megacity's; Func runs: 10000; result: 0.8233333333333333
25 Megacity's; Func runs: 10000; result: 0.5529999999999999
500 Megacity's; Func runs: 10000; result: 0.04724999999999998
=============================
All score: 5.52939 (61.44%)

Leicht veränderte Testergebnisse der ESG-Version:

C_AO_MPSO|200|100|0.1|1.1|10.0|1.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9986983861349696
25 Hilly's; Func runs: 10000; result: 0.7971379560351051
500 Hilly's; Func runs: 10000; result: 0.3351159723676586
=============================
5 Forest's; Func runs: 10000; result: 1.0
25 Forest's; Func runs: 10000; result: 0.8288612676775615
500 Forest's; Func runs: 10000; result: 0.11374411604788078
=============================
5 Megacity's; Func runs: 10000; result: 0.8333333333333333
25 Megacity's; Func runs: 10000; result: 0.5116666666666667
500 Megacity's; Func runs: 10000; result: 0.049316666666666654
=============================
All score: 5.46787 (60.75%)

Wir können eine gute Konvergenz der Hauptversion des Algorithmus feststellen. Bei den Testfunktionen „Hilly“ und „Forest“ ist im Konvergenzdiagramm eine leichte Streuung der Trajektorien zu erkennen. Bei der Megacity-Funktion ist diese Streuung jedoch recht groß, obwohl die meisten Algorithmen bei dieser Testfunktion ebenfalls eine große Streuung der Konvergenz aufweisen. Im Gegensatz zu den meisten früher vorgestellten Algorithmen „bevorzugt“ der Algorithmus eine viel größere Populationsgröße - 200 (normalerweise werden 50 verwendet), obwohl die Anzahl der Epochen proportional reduziert wird. Die ESG funktioniert gut bei lokalen Extremen. Diese Eigenschaft wird durch die „Natur“ des Algorithmus mit mehreren Populationen beeinflusst.

  ESG mit der Testfunktion Hilly

  ESG mit der Testfunktion Forest

  ESG mit der Testfunktion Megacity

Der ESG-Algorithmus zeigte ordentliche Ergebnisse und lag in der Bewertungstabelle an der Spitze. Man kann eine 100%ige Konvergenz bei der Forrest-Funktion mit 10 Parametern und eine fast vollständige, 99,9%ige Konvergenz bei der Hilly-Funktion mit 10 Parametern feststellen. Die Tabelle enthält die Ergebnisse der Hauptversion des Algorithmus, während sich die experimentelle Version im Ordner „variant2“ befindet.

#	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	BGA	binärer genetischer Algorithmus	0.99992	0.99484	0.50483	2.49959	1.00000	0.99975	0.32054	2.32029	0.90667	0.96400	0.23035	2.10102	6.921	76.90
2	(P+O)ES	(P+O) Entwicklungsstrategien	0.99934	0.91895	0.56297	2.48127	1.00000	0.93522	0.39179	2.32701	0.83167	0.64433	0.21155	1.68755	6.496	72.18
3	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
4	ESG	Entwicklung der sozialen Gruppen	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
5	SIA	Simuliertes isotropes Abkühlen	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
6	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
7	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
8	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
9	(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
10	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
11	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
12	MEC	Evolutionäre Berechnung des Geistes	0.69533	0.53376	0.32661	1.55569	0.72464	0.33036	0.07198	1.12698	0.52500	0.22000	0.04198	0.78698	3.470	38.55
13	IWO	Optimierung mit invasiven Unkräutern	0.72679	0.52256	0.33123	1.58058	0.70756	0.33955	0.07484	1.12196	0.42333	0.23067	0.04617	0.70017	3.403	37.81
14	Micro-AIS	Künstliches Mikro-Immunsystem	0.79547	0.51922	0.30861	1.62330	0.72956	0.36879	0.09398	1.19233	0.37667	0.15867	0.02802	0.56335	3.379	37.54
15	COAm	Kuckuck-Optimierungsalgorithmus M	0.75820	0.48652	0.31369	1.55841	0.74054	0.28051	0.05599	1.07704	0.50500	0.17467	0.03380	0.71347	3.349	37.21
16	SDOm	Optimierung der Spiraldynamik M	0.74601	0.44623	0.29687	1.48912	0.70204	0.34678	0.10944	1.15826	0.42833	0.16767	0.03663	0.63263	3.280	36.44
17	NMm	Nelder-Mead-Verfahren M	0.73807	0.50598	0.31342	1.55747	0.63674	0.28302	0.08221	1.00197	0.44667	0.18667	0.04028	0.67362	3.233	35.92
18	FAm	Firefly-Algorithmus M	0.58634	0.47228	0.32276	1.38138	0.68467	0.37439	0.10908	1.16814	0.28667	0.16467	0.04722	0.49855	3.048	33.87
19	GSA	Algorithmus für die Schwerkraftsuche	0.64757	0.49197	0.30062	1.44016	0.53962	0.36353	0.09945	1.00260	0.32667	0.12200	0.01917	0.46783	2.911	32.34
20	BFO	Optimierung der bakteriellen Futtersuche	0.61171	0.43270	0.31318	1.35759	0.54410	0.21511	0.05676	0.81597	0.42167	0.13800	0.03195	0.59162	2.765	30.72
21	ABC	Künstliches Bienenvolk (Artificial Bee Colony, ABC)	0.63377	0.42402	0.30892	1.36671	0.55103	0.21874	0.05623	0.82600	0.34000	0.14200	0.03102	0.51302	2.706	30.06
22	BA	Fledermaus-Algorithmus	0.59761	0.45911	0.35242	1.40915	0.40321	0.19313	0.07175	0.66810	0.21000	0.10100	0.03517	0.34617	2.423	26.93
23	SA	simuliertes Abkühlen	0.55787	0.42177	0.31549	1.29513	0.34998	0.15259	0.05023	0.55280	0.31167	0.10033	0.02883	0.44083	2.289	25.43
24	IWDm	intelligente Wassertropfen M	0.54501	0.37897	0.30124	1.22522	0.46104	0.14704	0.04369	0.65177	0.25833	0.09700	0.02308	0.37842	2.255	25.06
25	PSO	Partikelschwarmoptimierung	0.59726	0.36923	0.29928	1.26577	0.37237	0.16324	0.07010	0.60572	0.25667	0.08000	0.02157	0.35823	2.230	24.77
26	MA	Affen-Algorithmus	0.59107	0.42681	0.31816	1.33604	0.31138	0.14069	0.06612	0.51819	0.22833	0.08567	0.02790	0.34190	2.196	24.40
27	SFL	schlurfender Froschsprung	0.53925	0.35816	0.29809	1.19551	0.37141	0.11427	0.04051	0.52618	0.27167	0.08667	0.02402	0.38235	2.104	23.38
28	FSS	Fischschulsuche	0.55669	0.39992	0.31172	1.26833	0.31009	0.11889	0.04569	0.47467	0.21167	0.07633	0.02488	0.31288	2.056	22.84
29	RND	zufällig	0.52033	0.36068	0.30133	1.18234	0.31335	0.11787	0.04354	0.47476	0.25333	0.07933	0.02382	0.35648	2.014	22.37
30	GWO	Grauer-Wolf-Optimierung	0.59169	0.36561	0.29595	1.25326	0.24499	0.09047	0.03612	0.37158	0.27667	0.08567	0.02170	0.38403	2.009	22.32
31	CSS	Suche geladener Systeme	0.44252	0.35454	0.35201	1.14907	0.24140	0.11345	0.06814	0.42299	0.18333	0.06300	0.02322	0.26955	1.842	20.46
32	EM	elektromagnetismusähnlicher Algorithmus	0.46250	0.34594	0.32285	1.13129	0.21245	0.09783	0.10057	0.41085	0.15667	0.06033	0.02712	0.24412	1.786	19.85

Zusammenfassung

Zusammenfassend lässt sich sagen, dass der Algorithmus der sozialen Gruppenevolution eine wirksame Optimierungsmethode darstellt, die auf der Zusammenarbeit und dem Erfahrungsaustausch zwischen Gruppen beruht. Es hat die Eigenschaften der Anpassungsfähigkeit, der Vielfalt und ist in der Lage, optimale Lösungen in verschiedenen Optimierungsproblemen zu finden.

Ich kann den ESG-Algorithmus für den Einsatz in verschiedenen Bereichen empfehlen, in denen eine Optimierung der Parameter erforderlich ist. Sie kann zum Beispiel zur Abstimmung von Hyperparametern beim maschinellen Lernen, zur Optimierung von Funktionen bei optimalen Steuerungsproblemen, zur Lösung kombinatorischer Optimierungsprobleme und anderer Probleme, bei denen optimale Parameterwerte gefunden werden müssen, eingesetzt werden.

Der vorgestellte Algorithmus kann als eine Art Schablone betrachtet werden, die durch verschiedene individuelle Techniken und Suchstrategien ergänzt werden kann, die in früheren Artikeln beschrieben wurden. Darüber hinaus kann jede Gruppe eigene Optimierungsalgorithmen wie PSO, ABC, ACO usw. verwenden. Die Architektur des ESG-Algorithmus macht es daher einfach, solche Optimierungsmethoden zu implementieren und sie gemeinsam zu nutzen, indem die Vorteile jedes einzelnen Algorithmus kombiniert werden.

Es ist wichtig zu betonen, dass die ESG eine eigenständige Lösung mit guten Ergebnissen ist und einen äußerst flexiblen Ansatz zur Lösung komplexer Probleme darstellt. Sein volles Potenzial kann durch Experimentieren und Weiterentwicklung der Kernidee erschlossen werden, und die Möglichkeiten für solche Experimente stehen jedem offen.

Bild 2. Farbliche Abstufung der Algorithmen nach relevanten Tests Ergebnisse größer oder gleich 0,99 sind weiß hervorgehoben

Abb. 3. Das Histogramm der Algorithmus-Testergebnisse (auf einer Skala von 0 bis 100, größer ist besser,

wobei 100 das maximal mögliche theoretische Ergebnis ist; das Archiv enthält ein Skript zur Berechnung der Bewertungstabelle)

ESG-Vor- und Nachteile:

Vorteile:

1. Einfache Architektur.
   
2. Hohe Konvergenz.
3. Keine hohen Anforderungen an die Computerressourcen.

Nachteile

1. Schlechte Ergebnisse bei Funktionen mit einer großen Anzahl von Parametern.
   

Dem Artikel ist ein Archiv mit aktualisierten Versionen der in früheren Artikeln beschriebenen 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.