Algorithmen zur Optimierung mit Populationen: Evolutionsstrategien, (μ,λ)-ES und (μ+λ)-ES

Inhalt

1. Einführung
2. Der Algorithmus
3. Ersetzen einer Testfunktion
4. Testergebnisse
5. Schlussfolgerungen

1. Einführung

Die Algorithmen der Evolutionsstrategien sind Optimierungsmethoden, die auf in der Natur beobachteten Prinzipien beruhen. Sie simulieren die natürliche Selektion, bei der die besten Lösungen überleben und ihre Eigenschaften an die nächste Generation weitergeben. Diese Algorithmen sind bei der Lösung von Optimierungsproblemen weit verbreitet, insbesondere in den Bereichen des maschinellen Lernens und der künstlichen Intelligenz. Sie wurden in den 1960er Jahren von Professor Ingo Rechenberg und seinen Kollegen in Deutschland entwickelt, um Optimierungsprobleme in Industrie und Technik zu lösen.

Der Grundgedanke evolutionärer Strategien besteht darin, eine Population von Lösungen zu erstellen und diese dann mit Hilfe von Mutations- und Selektionsoperatoren zu verbessern, ähnlich denen, die in der natürlichen Evolution verwendet werden. Evolutionsstrategien verwenden reelle Vektoren zur Darstellung von Lösungen. Dies erlaubt uns, den Lösungsraum flexibler und genauer zu beschreiben und nach optimalen Werten zu suchen, im Gegensatz zum klassischen genetischen Algorithmus, der mit binären Zeichenketten arbeitet.

Es gibt verschiedene Varianten von Evolutionsstrategien, die sich in der Art und Weise unterscheiden, wie die Population erzeugt und verarbeitet wird, sowie in den verwendeten Mutations- und Selektionsoperatoren. Einige der gängigsten Optionen sind:

1. (1+1)-ES: Bei dieser Variante wird für jedes Elternteil nur ein Kind erzeugt, und die beste Lösung der beiden wird zum Elternteil für die nächste Generation. Diese einfache und schnelle Methode kann für einige Probleme effizient sein, ist aber weniger effektiv, wenn es um die Optimierung komplexer Probleme geht. Der (1+1)-ES-Algorithmus wurde in den 1960er Jahren entwickelt und ist eine der einfachsten Methoden zur Optimierung durch evolutionäre Strategien. Sie besteht darin, einen Zufallsvektor zu erzeugen, der dann in einen Zufallsschritt umgewandelt wird. Wenn der geänderte Vektor besser ist, ersetzt er den ursprünglichen, andernfalls bleibt der ursprüngliche Vektor unverändert. Dieser Vorgang wird so lange wiederholt, bis das Optimum erreicht ist.

1. (μ,λ)-ES: In diesem Algorithmus wird eine Eltern-Population der Größe μ erstellt, die λ Kinder hervorbringen, und die besten Kinder ersetzen die Eltern. Es kann für verschiedene Optimierungsprobleme effizient sein. Der (μ,λ)-ES-Algorithmus wurde 1965 von Reinhard Speigelmann entwickelt. Nach der Bewertung der Kinder werden nur die besten μ-Lösungen beibehalten und zu Eltern für die nächste Generation, sodass die Eltern in jeder Epoche vollständig durch Kinder ersetzt werden.

1. (μ+λ)-ES: Bei dieser Option werden λ Nachkommen erstellt. Die besten von ihnen sind gemeinsam mit ihren Eltern an der Gestaltung der nächsten Generation beteiligt. Bei dieser Methode konkurrieren Eltern und Kinder miteinander, was ein wichtiger Unterschied zu (μ,λ)-ES ist. Der (μ+λ)-ES-Algorithmus wurde in den 1970er Jahren von Johannes Reichenbacher und Hans-Paul Schwefel entwickelt und ist eine Methode zur Optimierung durch evolutionäre Strategien. Diese Methode ermöglicht eine vollständigere Erkundung des Lösungsraums und kann bei der Lösung komplexer Probleme effizienter sein.

Es gibt noch andere Varianten von Evolutionsstrategien, aber in diesem Artikel werden wir nur (μ,λ)-ES und (μ+λ)-ES betrachten. Die (1+1)-ES-Option ist einfach und eignet sich nicht für die Lösung mehrdimensionaler Probleme. Da es schwierig ist, die Buchstaben des griechischen Alphabets und Sonderzeichen in Dateinamen und Variablennamen im Code zu verwenden, werden wir PO bzw. P_O verwenden, wobei P für Eltern (parents) und O für Nachkommen (offspring) steht.

Evolutionsstrategien in der Informatik ermöglichen es uns, die Evolution und die natürliche Auswahl zu modellieren, um komplexe Optimierungsprobleme zu lösen. Sie nutzen Prinzipien, die der natürlichen Selektion ähneln, um nach optimalen Lösungen im Parameterraum zu suchen.

Diese Algorithmen können vor allem bei Problemen nützlich sein, für die es keine offensichtliche analytische Lösung gibt oder bei denen der Suchraum sehr groß ist. Sie können effizient nach optimalen Lösungen suchen, indem sie von der Evolution inspirierte Verfahren wie Kreuzung, Mutation und Selektion einsetzen.

Der Name „Evolutionsstrategien“ kann irreführend sein, da die Forscher denken könnten, es handele sich um eine allgemeine Bezeichnung für eine Klasse von Evolutionsalgorithmen. Dies ist jedoch nicht der Fall. Es handelt sich dabei um eine spezielle Gruppe von Algorithmen, die Ideen der Evolution zur Lösung von Optimierungsproblemen nutzen.

2. Der Algorithmus

(μ,λ)-ES bedeutet, dass bei jeder Iteration des Algorithmus μ Eltern ausgewählt und λ Kinder erzeugt werden. Dann werden die besten μ aus den λ Kindern ausgewählt, die dann die Eltern für die nächste Iteration werden. Bei (μ,λ)-ES ersetzen also neue Nachkommen ihre Eltern vollständig und nehmen an der Entstehung der nächsten Generation teil.

(μ+λ)-ES funktioniert auf ähnliche Weise, aber anstatt die besten Nachkommen aus λ auszuwählen, werden sie mit den Eltern kombiniert, um eine neue Population der Größe μ+λ zu bilden. Aus dieser kombinierten Population werden dann die besten μ Individuen ausgewählt, die in der nächsten Iteration zu Eltern werden. Bei (μ+λ)-ES arbeiten die neuen Nachkommen also mit ihren Eltern zusammen, um die nächste Population zu bilden, und konkurrieren miteinander.

Der Hauptunterschied zwischen (μ,λ)-ES und (μ+λ)-ES besteht darin, wie neue Nachkommen mit den Eltern um einen Platz in der nächsten Population konkurrieren. Bei (μ,λ)-ES konkurrieren neue Kinder mit ihren Eltern um eine begrenzte Anzahl von Plätzen, was zu einer vorzeitigen Konvergenz zu einem lokalen Optimum führen kann. Bei (μ+λ)-ES arbeiten neue Kinder mit ihren Eltern zusammen, was zu einer breiteren Erkundung des Lösungsraums führt.

Beide evolutionären Strategiealgorithmen beruhen auf einer Kombination von genetischen Operatoren: Mutation und Selektion. Bei jeder Iteration des Algorithmus wird ein Individuum aus der aktuellen Population ausgewählt und der Mutationsoperator darauf angewandt. Anschließend wird die Fitness des resultierenden Individuums berechnet und das fitteste in die nächste Population aufgenommen. Zur Erzeugung der Ausgangspopulation wird für jede Komponente des Vektors variabler Parameter ein Intervall festgelegt, und es wird davon ausgegangen, dass die Ausgangswerte der Komponenten in dem festgelegten Intervall gleichmäßig verteilt sind. Der Algorithmus kann verschiedene Abbruchbedingungen verwenden, z. B. das Erreichen einer bestimmten Anzahl von Generationen, eines bestimmten Populationsstatus oder eines bestimmten Konvergenzniveaus. Im Falle des (μ+λ)-Algorithmus werden alle Individuen in die Population aufgenommen, während im Falle des (μ,λ)-Algorithmus nur die Nachkommenschaft berücksichtigt wird. Für den (μ+λ)-Algorithmus wurde die Konvergenz mit hoher Wahrscheinlichkeit nachgewiesen, für den (μ,λ)-Algorithmus bleibt die Frage der Konvergenz jedoch offen.

Ein Vergleich der Algorithmen (μ+λ) und (μ,λ) zeigt, dass der Algorithmus (μ+λ) sparsamer mit hochgradig angepassten Individuen umgeht und sie mit Nachkommen konkurrieren lässt. Dies erhöht die Intensität der Suche, kann aber zu einer vorzeitigen Konvergenz zu einem lokalen Extremum führen. Der Mutationsoperator im kanonischen evolutionären Strategiealgorithmus ist der einzige evolutionäre Operator und verwendet den Gaußschen Mutationsalgorithmus.

Der klassische (μ,λ)-ES-Algorithmus kann durch den folgenden Pseudocode beschrieben werden:

1. Initialisieren der Ausgangspopulation mit zufälligen Individuen.
2. Wiederholen des Vorgangs, bis das Kriterium des Anhaltens erreicht ist:
2.1. Jedes der μ Elternteile erzeugt mit Hilfe des Mutationsoperators λ Nachkommen in der aktuellen Population.
2.2. Auswahl der besten μ-Nachkommen, um die nächste Population zu bilden.
3. Gibt das beste Individuum aus der letzten Population zurück.

Der herkömmliche (μ+λ)-ES-Algorithmus kann durch den folgenden Pseudocode beschrieben werden:

1. Initialisieren der Ausgangspopulation mit zufälligen Individuen.
2. Wiederholen des Vorgangs, bis das Kriterium des Anhaltens erreicht ist:
2.1. Jedes der μ Elternteile erzeugt mit Hilfe des Mutationsoperators λ Nachkommen in der aktuellen Population.
2.2. Kombinieren von Eltern und Nachkommen, um eine kombinierte Population der Größe μ+λ zu erhalten.
2.3. Auswahl der besten μ Individuen aus der kombinierten Population, um die nächste Population zu bilden.
3. Gibt das beste Individuum aus der letzten Population zurück.

Wir haben uns die klassischen Versionen der beiden wichtigsten Algorithmen für „evolutionäre Strategien“ angesehen. In beiden Fällen erzeugen die Eltern λ-Nachkommen, die nur ihre genetische Information nutzen. Dies führt zu einer sternförmigen Verzweigung, bei der sich jeder Nachkomme unabhängig von den anderen entwickelt. Es findet auch kein Informationsaustausch zwischen den Eltern statt, was die Möglichkeit einer Kombination ihrer genetischen Eigenschaften ausschließt. Kombinatorische Qualitäten sind daher völlig abwesend.

Die Testergebnisse haben gezeigt, dass diese beiden ES-Optionen eine geringe Effizienz aufweisen. Ich habe versucht, sie durch Rekombination zu erhöhen.

Durch Rekombination kann genetisches Material von verschiedenen Individuen kombiniert werden, um neue Kombinationen zu schaffen, die möglicherweise bessere Eigenschaften oder Merkmale aufweisen. Dieser Prozess fördert die Vielfalt in der Bevölkerung.

Rekombination (oder Kreuzung) ist der Prozess der Kombination des genetischen Materials der Eltern, um einen Nachkommen zu erzeugen. Dieser Prozess simuliert die natürliche Kreuzung in der biologischen Evolution. Bei der Rekombination verbinden sich die Gene der Eltern, um neues genetisches Material für die Nachkommen zu schaffen. Die Rekombination erfolgt in der Regel auf der Ebene von Genen oder genetischen Merkmalen. Gene sind Informationseinheiten im Genom, die für bestimmte Eigenschaften oder Merkmale eines Organismus kodieren.

Nach der Rekombination werden die Gene des Nachkommens mit Hilfe des Mutationsoperators verändert, der zufällige Änderungen an den Genen vornimmt. Dies trägt dazu bei, neue Forschungsvarianten in die Population einzuführen und die Vielfalt des genetischen Materials zu fördern.

Daher werden wir für jedes Nachkommen-Gen die Gene zufällig ausgewählter Eltern verwenden, wobei Gen die entsprechende Koordinate des Elternteils ist. Somit erben die Nachkommen die Merkmale aller Eltern in der Population.

(μ,λ)-ES-Algorithmus.

Gehen wir nun zur Überprüfung des Codes über und beginnen wir mit einem einfacheren Algorithmus (μ,λ)-ES, der durch Hinzufügen von Rekombination (Vererbung von Genen von mehreren Elternteilen) modifiziert wurde.

Für einen Elternteil und ein Kind, die als Agenten agieren, ist eine gute Struktur S_Agent, die ein Feld von Koordinaten „c“ und eine Variable „f“ - den Fitnesswert - enthält. Die Init-Funktion initialisiert den Agenten, indem sie die Größe des Arrays „c“ ändert und den Wert von „f“ auf „-DBL_MAX“ (den schlechtest möglichen Fitnesswert) setzt.

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

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

Wir deklarieren die Klasse C_AO_POES, um den (μ,λ)-ES-Algorithmus zu beschreiben.

Die Klasse enthält die folgenden Elemente:

• Die öffentlichen Variablen „cB“, „fB“, „a“, „rangeMax“, „rangeMin“, „rangeStep“: Diese Variablen werden verwendet, um die beste Koordinate, den entsprechenden Wert der Fitnessfunktion, die Agenten, den maximalen und minimalen Suchwert bzw. den Suchschritt zu speichern.
• Public Init(): Diese Funktion initialisiert den Optimierungsalgorithmus. Sie benötigt mehrere Argumente wie die Anzahl der Koordinaten, die Populationsgröße, die Anzahl der Elternagenten, die Mutationsstärke und den Sigma-Wert. Innerhalb der Funktion werden die im Algorithmus verwendeten Variablen und Arrays initialisiert.
• Die öffentlichen Funktionen „Moving()“ und „Revision()“: Diese Funktionen werden zur Durchführung von Agentenbewegungen bzw. zur Überprüfung der Population verwendet.
• Die privaten Variablen „coords“, „popSize“, „parentsNumb“, „mutationPower“, „sigmaM“ und „revision“: Diese Variablen werden verwendet, um die Anzahl der Koordinaten, die Populationsgröße, die Anzahl der Elternagenten, die Mutationsstärke, den Sigma-Wert bzw. das Revisions-Flag zu speichern.
• Die privaten Arrays „parents“, „ind“, „val“ und „pTemp“: Diese Arrays werden verwendet, um Informationen über übergeordnete Agenten, Indizes, Werte und temporäre Variablen zu speichern.
• Die privaten Funktionen GaussDistribution(), SeInDiSp(), RNDfromCI(), Scale(), Sorting(): Diese Funktionen werden zur Erzeugung von Zufallszahlen, zur Skalierung von Werten und zur Sortierung von Arrays verwendet.

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

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

  public: void Init (const int    coordsP,          //coordinates number
                     const int    popSizeP,         //population size
                     const int    parentsP,         //number of parents, < Population size
                     const double mutationPowerP,   //mutation power
                     const double sigmaP);          //sigma

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

  //----------------------------------------------------------------------------
  private: int    coords;        //coordinates number
  private: int    popSize;       //population size
  private: int    parentsNumb;   //number of parents
  private: double mutationPower; //mutation power
  private: double sigmaM;
  private: bool   revision;

  private: S_Agent parents [];  //parents
  private: int     ind     [];
  private: double  val     [];
  private: S_Agent pTemp   [];

  private: double GaussDistribution   (const double In, const double outMin, const double outMax, const double sigma);
  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: void   Sorting   (S_Agent &p [], int size);
};
//——————————————————————————————————————————————————————————————————————————————

Um den Optimierungsalgorithmus zu initialisieren, verwenden wir die Funktion Init der Klasse C_AO_POES. Die Funktion benötigt mehrere Argumente: Anzahl der Koordinaten, Populationsgröße, Anzahl der Elternagenten, Mutationsstärke und Sigma-Wert.

Innerhalb der Funktion werden die im Algorithmus verwendeten Variablen und Arrays initialisiert. Die Funktion bewirkt Folgendes:

• Sie setzt den Zufallszahlengenerator zurück und die Variable „fB“ auf „-DBL_MAX“. 
• Sie setzt die Variablenwerte „coords“, „popSize“, „parentsNumb“, „mutationPower“ und „sigmaM“. 
• Sie ändert die Arraygrößen „ind“, „val“, „pTemp“, „a“, „parents“, „rangeMax“, „rangeMin“, „rangeStep“ und „cB“ mit der Funktion ArrayResize. 
• Sie initialisiert die Arrays „a“ und „parents“ mit der Funktion Init der Klasse „S_Agent“, die die Koordinaten des Agenten initialisiert und den Wert der Variablen „f“ auf „-DBL_MAX“ setzt.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Init (const int    coordsP,          //coordinates number
                      const int    popSizeP,         //population size
                      const int    parentsP,         //number of parents, < Population size
                      const double mutationPowerP,   //mutation power
                      const double sigmaP)           //sigma
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords        = coordsP;
  popSize       = popSizeP;
  parentsNumb   = parentsP;
  mutationPower = mutationPowerP;
  sigmaM        = sigmaP;

  ArrayResize (ind,   popSize);
  ArrayResize (val,   popSize);
  ArrayResize (pTemp, popSize);
  ArrayResize (a,     popSize);
  for (int i = 0; i < popSize; i++) a [i].Init (coords);

  ArrayResize (parents, parentsNumb);
  for (int i = 0; i < parentsNumb; i++) parents [i].Init (coords);

  ArrayResize (rangeMax,  coords);
  ArrayResize (rangeMin,  coords);
  ArrayResize (rangeStep, coords);
  ArrayResize (cB,        coords);
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode Moving verschiebt Agenten im Suchraum.

Die Funktion enthält zwei Codeblöcke, die durch die Bedingung „if (!revision)“ getrennt sind.

1. Im ersten Block werden für jeden Agenten zufällige Koordinaten erzeugt, wenn das Flag „Revision“ auf „false“ steht. Für jede Koordinate wird eine Zufallszahl mit einer gleichmäßigen Verteilung zwischen „rangeMin“ und „rangeMax“ generiert, dann wird diese Zahl mit der Funktion SeInDiSp normalisiert, die den Koordinatenwert auf das nächste Vielfache von „rangeStep“ setzt.
2. Im zweiten Block erfolgt die Bewegung der Agenten, wenn das Flag „Revision“ gleich „true“ ist. Für jeden Agenten wird ein zufälliger Eltern-Agent aus dem Feld „Eltern“ ausgewählt. Dann wird der Mutationswert „dist“ für jede Agentenkoordinate berechnet. Der Wert hängt von der Mutationsstärke „mutationPower“ und dem Suchbereich „rangeMin“ und „rangeMax“ ab. Der Koordinatenwert des Agenten wird mit der Funktion GaussDistribution geändert, die eine normalverteilte Zufallszahl um den übergeordneten Koordinatenwert mit dem Sigma-Wert „sigmaM“ erzeugt. Der Koordinatenwert wird dann mit der Funktion SeInDiSp normalisiert.
   

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Moving ()
{
  //----------------------------------------------------------------------------
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  int    indx = 0;
  double min  = 0.0;
  double max  = 0.0;
  double dist = 0.0;

  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      indx = (int)RNDfromCI (0, parentsNumb);
      if (indx >= parentsNumb) indx = parentsNumb - 1;

      a [i].c [c] = parents [indx].c [c];

      dist = (rangeMax [c] - rangeMin [c]) * mutationPower;

      min = a [i].c [c] - dist; if (min < rangeMin [c]) min = rangeMin [c];
      max = a [i].c [c] + dist; if (max > rangeMax [c]) max = rangeMax [c];

      a [i].c [c] = GaussDistribution (a [i].c [c], min, max, sigmaM);
      a [i].c [c] = SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Überarbeitung der Population erfolgt durch die Methode „Revision“, die dazu dient, den aktuellen Zustand der Agenten im Optimierungsalgorithmus zu überarbeiten.

Die Funktion enthält zwei Codeblöcke.

1. Im ersten Block wird mit Hilfe der „for“-Schleife der beste Agent im Array „a“ gesucht. Wird ein Agent mit einem höheren Fitnesswert als der derzeit beste Agent „fB“ gefunden, so wird der Index dieses Agenten in der Variablen „indx“ gespeichert. Der „fB“-Wert und die „cB“-Koordinaten des derzeit besten Agenten werden dann entsprechend dem neuen besten Agenten aktualisiert.
2. Im zweiten Block wird das Array „a“ mit Hilfe der Sortierfunktion in absteigender Reihenfolge der Fitness sortiert, und dann wird die „parentsNumb“ der besten Agenten aus dem Array „a“ in das Array „parents“ kopiert.

Die Funktion „Revision“ ermöglicht es also, den aktuellen Zustand der Agenten zu aktualisieren und die besten Agenten im Feld „Eltern“ zu speichern, wobei die besten Kinder alle Eltern vollständig ersetzen.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Revision ()
{
  //----------------------------------------------------------------------------
  int indx = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB) indx = i;
  }

  if (indx != -1)
  {
    fB = a [indx].f;
    ArrayCopy (cB, a [indx].c, 0, 0, WHOLE_ARRAY);
  }

  //----------------------------------------------------------------------------
  Sorting (a, popSize);
  for (int i = 0; i < parentsNumb; i++)
  {
    parents [i] = a [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

(μ+λ)-ES-Algorithmus.

Die Änderungen beginnen mit dem Hinzufügen der Lebenserwartung einer Person in Form des Parameters „yearsNumber“. Auf diese Weise kann das Höchstalter der Bevölkerung kontrolliert und eine „Überfüllung“ mit sehr alten Menschen vermieden werden, was die Erkundung neuer Horizonte des unendlichen Lebensraums und neue Entdeckungen verhindern kann. Ich hoffe, dass dies bei diesem Algorithmus nützlich sein wird.

Warum ist dieser Zähler nicht im „(μ,λ)-ES“-Algorithmus enthalten? Denn so war es ja auch gedacht. Die Eltern werden vollständig durch Nachkommenschaft ersetzt. Es macht auch Sinn, wie im Fall der Semelogisten im Tierreich, wo sich einige Arten nur einmal im Leben fortpflanzen. Beispiele für solche Arten sind Salmoniden, Agaven, Bambus, Kokosnusskrabben und Cycadeen. In unserem Algorithmus geben wir den Individuen jedoch die Möglichkeit, sich mehrmals zu vermehren, unbegrenzt zu leben oder wie ein stolzer Bambus zu sterben. Die Lebenserwartung kann ein einstellbarer externer Parameter sein, und im Rahmen unserer Tests wurde die optimale Dauer von 10 Jahren experimentell ermittelt.

Darüber hinaus kann ein Lebenszähler dazu beitragen, eine „Überanpassung“ des Modells zu vermeiden, wenn die Population beginnt, sich an bestimmte Lösungen zu „erinnern“ und diese zu akkumulieren, anstatt an anderer Stelle im Suchraum neue erfolgreiche Lösungen zu finden. Die Begrenzung der Lebensdauer von Individuen ermöglicht es uns, die Vielfalt der Population zu erhalten und weiterhin nach optimalen Lösungen zu suchen.

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

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

Bei der Methode „Init“ wird die Größe der Elternpopulation um die Anzahl der Kinder erhöht. Dadurch können Eltern und Kinder gemeinsam sortiert werden, obwohl, wie beim (μ,λ)-ES-Algorithmus, in Zukunft nur der μ-Teil der gemeinsamen Population zur Erzeugung neuer Kinder verwendet wird. Während im vorherigen Algorithmus die Anzahl der Eltern kleiner oder gleich der Population der Nachkommen sein musste, spielt dies in diesem Algorithmus keine Rolle, und die Population der Eltern kann auf eine beliebige Größe gesetzt werden, sogar sehr groß. Dies hat keinen Einfluss auf die Anzahl der Epochen. Es wurde experimentell festgestellt, dass eine Elternpopulation von 150 der optimale Wert für 100 Nachkommen ist (ein größerer Wert ist nicht möglich, wenn die Anzahl der Epochen abnimmt). Eine weitere Vergrößerung der Elternpopulation führt zu einer zu großen Vielfalt im Genpool und der Algorithmus beginnt schlechter zu konvergieren (das ist an sich schon interessant).

ArrayResize (ind,   popSize + parentsNumb);
ArrayResize (val,   popSize + parentsNumb);
ArrayResize (pTemp, popSize + parentsNumb);
ArrayResize (a,     popSize);
for (int i = 0; i < popSize; i++) a [i].Init (coords);

ArrayResize (parents, popSize + parentsNumb);
for (int i = 0; i < popSize + parentsNumb; i++) parents [i].Init (coords);

Wir setzen in der Methode „Moving“ den Jahreszähler der Person auf 1, wenn wir neue Nachkommen anlegen.

a [i].yearsNumber = 1;

Die Änderungen betrafen auch die Revisionsmethode, bei der der Code unter Berücksichtigung der Änderungen Folgendes durchführt:

• Erhöhen des Werts von „yearsNumber“ eines jeden Elternteils um 1.
• Überschreitet der Wert von „yearsNumber“ den angegebenen Grenzwert (Lebensspanne), wird der Fitnesswert „f“ für den entsprechenden Elternteil auf „-DBL_MAX“ gesetzt, was bedeutet, dass das Individuum aus der Population entfernt wird.
  
• Kopieren der neuen Kinder aus dem Array „a“ in das Array „parents“.
• Sortieren des Arrays „parents“ nach dem Fitnesswert „f“.

//----------------------------------------------------------------------------
for (int i = 0; i < parentsNumb; i++)
{
  parents [i].yearsNumber++;

  if (parents [i].yearsNumber > lifespan)
  {
    parents [i].f = - DBL_MAX;
  }
}

for (int i = parentsNumb; i < parentsNumb + popSize; i++)
{
  parents [i] = a [i - parentsNumb];
}

Sorting (parents, parentsNumb + popSize);

3. Ersetzen einer Testfunktion

Zuvor haben wir die Rastrigin-Funktion als Testfunktion zur Bewertung von Optimierungsalgorithmen verwendet. Die Rastrigin-Funktion ist für solche Zwecke jedoch nicht die perfekte Wahl. Sie weist eine strenge Periodizität und ausgeglichene Minima und Maxima auf, die von einigen Algorithmen relativ leicht erkannt werden können. Die Rastrigin-Funktion weist also Muster auf, die die Fähigkeit des Algorithmus beeinträchtigen können, die Extrema der Funktion zu bestimmen.

Um Optimierungsalgorithmen zuverlässiger und objektiver zu testen, empfiehlt es sich, Funktionen mit unterschiedlichen und unvorhersehbaren Eigenschaften zu verwenden. Solche Funktionen haben in der Regel keine offensichtlichen Muster oder ein Gleichgewicht zwischen Minimal- und Maximalwerten. Beispiele für solche Funktionen sind Rauschfunktionen, Funktionen mit nichtlinearen Abhängigkeiten oder Funktionen mit einer großen Anzahl von lokalen Extrema. Diese Auswahl an Funktionen ermöglicht es uns, die Fähigkeit der Algorithmen, globale Optima unter verschiedenen Bedingungen zu erkennen und zu ihnen zu konvergieren, genauer zu bewerten.

Herkömmlicherweise können alle Funktionen in „einfach“ und „komplex“ unterteilt werden. Einfache Funktionen sind solche, deren größte Fläche oberhalb der Mittellinie zwischen „max“ und „min“ liegt, und je mehr Fläche näher an „max“ liegt, desto einfacher ist sie für Optimierungsalgorithmen. Wenn wir also einfach zufällig Punkte über die gesamte Fläche im Bereich der Funktion setzen, erhalten wir einen falschen Eindruck von „hohen“ Optimierungsergebnissen, da die Ergebnisse in der Nähe des absoluten globalen Maximums liegen werden. Ein Beispiel für eine solche einfache Funktion ist die schematische Zeichnung der hypothetischen Funktion in Abb. 1.

Abbildung 1. Ein Beispiel für eine „einfache“ Funktion für Optimierungsalgorithmen

In Anbetracht der obigen Ausführungen kann die Rastrigin-Funktion als eine einfache Funktion eingestuft werden, die bei einigen Optimierungsalgorithmen zu überhöhten Ergebnissen führen kann. Dies ist auf die Besonderheiten der Suchstrategie dieser Algorithmen zurückzuführen, die ihre Agenten über die gesamte Funktionsfläche verstreut platzieren können.

Die Auswirkungen sind besonders bei Rastrigin-Funktionen mit einer großen Anzahl von Variablen, z. B. 1000, spürbar. Während einige Algorithmen „ehrlich“ versuchen, das globale Extremum zu finden, können andere einfach Agenten gleichmäßig über die gesamte Oberfläche der Funktion verteilen. Dieser Ansatz sagt nichts über die Fähigkeit des Optimierungsalgorithmus aus, eine genaue Suche durchzuführen, sondern erweckt nur den Anschein, dies zu können.

Die Rastrigin-Funktion wurde erheblich verändert, um ein komplexeres und anspruchsvolleres Umfeld für Optimierungsalgorithmen zu schaffen. In der neuen Version der Funktion wurden mehrere „Hügel“ (hills) und „Täler“ hinzugefügt, wobei die Periodizität in dem Teil der Oberfläche beibehalten wurde, der bei der Suche nach dem globalen Extremwert nicht hilfreich ist. Diese Veränderungen schaffen zusätzliche Hindernisse, die die Agenten ablenken und als Fallen wirken.

Jetzt kann man nicht mehr einfach periodisch auf- und abwärts springen, um das globale Extremum zu erreichen, wie es bei der klassischen Version von Rastrigin der Fall war. Außerdem wurde das globale Optimum vom Rand weg verschoben, sodass es im Falle von Artefakten in den Algorithmen, die sich oft auf die Grenzen der Funktionsdefinition konzentrieren, schwer zu finden ist.

Die neue Funktion wird „Hilly“ genannt (Abb. 2). Wie „Forest“ und „Megacity“ bezieht er sich auf komplexe Testfunktionen. Bei diesen drei Funktionen ist die Fläche, die über 50 % der maximalen Höhe liegt, ungefähr gleich groß und macht etwa 20 % der Gesamtfläche der Funktion aus.

Die Funktionen „Hilly“, „Forest“ und „Megacity“ bieten komplexe und realistische Optimierungsszenarien, mit deren Hilfe die Leistung von Algorithmen unter komplexen und unterschiedlichen Bedingungen bewertet werden kann. Indem wir diese Funktionen als umfassenden Test von Optimierungsalgorithmen verwenden, können wir mehr Einblick in ihre Fähigkeit gewinnen, globale Optima zu finden und lokale Fallstricke zu überwinden.

Darüber hinaus wurden Änderungen an der Prüfmethodik vorgenommen. Anstelle der 5-fachen (Anzahl der wiederholten Durchläufe des Optimierungsprozesses) wird nun eine 10-fache Prüfung durchgeführt, um zufällige „Spitzen“ in den Ergebnissen zu reduzieren.

Abbildung 2. Die Testfunktion Hilly

4. Testergebnisse

(μ,λ)-ES-Algorithmus Testergebnisse:

C_AO_(PO)ES:100:10:0.025:8.0
=============================
5 Hilly's; Func runs: 10000; result: 0.7902459324049909
25 Hilly's; Func runs: 10000; result: 0.6264667539839893
500 Hilly's; Func runs: 10000; result: 0.42934981087827656
=============================
5 Forest's; Func runs: 10000; result: 0.8761631782479373
25 Forest's; Func runs: 10000; result: 0.6094343681829253
500 Forest's; Func runs: 10000; result: 0.19591138782930953
=============================
5 Megacity's; Func runs: 10000; result: 0.5900000000000001
25 Megacity's; Func runs: 10000; result: 0.37933333333333336
500 Megacity's; Func runs: 10000; result: 0.11321666666666666
=============================
All score: 4.61012

(μ+λ)-ES-Algorithmus Testergebnisse:

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
5 Hilly's; Func runs: 10000; result: 0.9993447297882565
25 Hilly's; Func runs: 10000; result: 0.9189524317647721
500 Hilly's; Func runs: 10000; result: 0.562968579605404
=============================
5 Forest's; Func runs: 10000; result: 1.0
25 Forest's; Func runs: 10000; result: 0.9352215748931851
500 Forest's; Func runs: 10000; result: 0.3917923122543615
=============================
5 Megacity's; Func runs: 10000; result: 0.8316666666666664
25 Megacity's; Func runs: 10000; result: 0.6443333333333332
500 Megacity's; Func runs: 10000; result: 0.21155000000000007
=============================
All score: 6.49583

Die nachstehende Visualisierung gilt für den (μ+λ)-ES-Algorithmus, der eine hervorragende Erkundung des Suchraums zeigt, ohne potenziell vielversprechende Bereiche auszulassen.

(μ+λ)-ES mit der Testfunktion Hilly

  (μ+λ)-ES mit der Testfunktion Forest

  (μ+λ)-ES mit der Testfunktion Megacity

Es wurde auch beschlossen, zu absoluten Werten der Testergebnisse zurückzukehren und die relativen Werte aufzugeben. Um dies zu erreichen, wurden die Testfunktionen so geändert, dass sie Werte im Bereich von 0,0 bis 1,0 liefern. Wenn das Ergebnis nun 1,0 ist, bedeutet dies 100 % Konvergenz, während 0,32527 32,5 % des globalen Maximums der Testfunktion bedeutet. Da also die Gesamtzahl der Tests 9 beträgt, können die Algorithmen theoretisch das maximal mögliche Gesamtergebnis für alle Tests von höchstens 9,0 im Falle einer 100%igen Konvergenz des Algorithmus bei jedem Test in der Spalte „Endergebnis“ der Tabelle anzeigen. Zusätzlich wurde die Spalte „% von MAX“ hinzugefügt, die den Prozentsatz des maximal möglichen Ergebnisses anzeigt.

Jetzt ändern sich die Ergebniszahlen nicht mehr, wenn neue Algorithmen in die Tabelle aufgenommen werden, da sie in absoluten Werten angegeben werden.

Kommen wir nun zu den Ergebnissen der betrachteten Algorithmen, vor allem zu (μ+λ)-ES. Dieser Algorithmus hat mich mit seinen phänomenalen Ergebnissen wirklich verblüfft: Er erzielte insgesamt 72,18 % des theoretisch möglichen Ergebnisses. Um sich dieser beeindruckenden Ergebnisse zu vergewissern, wurde speziell für diesen Algorithmus ein Test mit 20 Durchläufen durchgeführt. Jeder der 20 Durchläufe zeigte 100% Konvergenz bei der komplexen Forest-Funktion - das ist einfach großartig! Darüber hinaus waren die Ergebnisse bei anderen Funktionen ebenfalls bemerkenswert.

Nun einige gute Worte über (μ,λ)-ES. Dieser Algorithmus zeigte stabile und gute Ergebnisse. In der Farbgrafik ist sie gleichmäßig „grün“, ohne plötzliche Farbänderungen.

#	AO	Beschreibung	Hilly			Hilly final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result	% von 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	(P+O)ES	(P+O) evolution strategies	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
2	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
3	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
4	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
5	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
6	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
7	(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
8	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
9	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
10	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
11	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
12	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
13	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
14	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
15	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
16	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
17	BFO	Optimierung der bakteriellen Futtersuche	0.54626	0.43533	0.31907	1.30066	0.41626	0.23156	0.06266	0.71048	0.35500	0.15233	0.03627	0.54360	2.555	28.39
18	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
19	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
20	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
21	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
22	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
23	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
24	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
25	RND	random	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
26	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
27	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
28	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

Abb. 3. Farbabstufung der Algorithmen gemäß den einschlägigen Tests

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

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

5. Zusammenfassung

Der Einsatz evolutionärer Strategien eröffnet neue Möglichkeiten in verschiedenen Bereichen, darunter die Parameteroptimierung beim maschinellen Lernen, die Konstruktion von Robotern und die Steuerung komplexer Systeme. Sie ermöglichen es uns, bessere Lösungen auf der Grundlage der biologischen Prinzipien der Evolution zu finden.

Wir haben derzeit einen neuen unangefochtenen Tabellenführer, der seinen nächsten Konkurrenten SDSm um fast 10 % übertrifft.

(μ,λ)-ES-Algorithmus - Vor- und Nachteile:

Vorteile:

1. Geringe Anzahl von externen Parametern.
2. Hohe Effizienz bei der Lösung einer Vielzahl von Problemen.
3. Leichte Umsetzung.
4. Widerstandsfähigkeit gegen das Hängenbleiben.
5. Vielversprechende Ergebnisse sowohl für glatte als auch für komplexe diskrete Funktionen.
6. Hohe Konvergenz.

Nachteile

1. Große Streuung der Ergebnisse bei diskreten Funktionen.
   

(μ+λ)-ES-Algorithmus - Vor- und Nachteile:

Vorteile:

1. Geringe Anzahl von externen Parametern.
2. Hohe Effizienz bei der Lösung einer Vielzahl von Problemen.
3. Leichte Umsetzung.
4. Widerstandsfähigkeit gegen das Hängenbleiben.
5. Vielversprechende Ergebnisse sowohl für glatte als auch für komplexe diskrete Funktionen.
6. Hohe Konvergenz.

Nachteile

1. Große Streuung der Ergebnisse bei diskreten Funktionen (obwohl dies derzeit die besten Ergebnisse sind).

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.