Algorithmen zur Optimierung mit Populationen Optimierung gemäß einer bakteriellen Nahrungssuche (BFO)

Inhalt

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

1. Einführung

Der Algorithmus zur Optimierung gemäß einer bakteriellen Nahrungssuche oder auch dem Bacterial Foraging Optimization (BFO) ist eine faszinierende Optimierungstechnik, mit der sich Näherungslösungen für extrem komplexe oder unmögliche numerische Funktionsmaximierungs-/Minimierungsprobleme finden lassen. Der Algorithmus ist weithin als globaler Optimierungsalgorithmus für verteilte Optimierung und Steuerung anerkannt. BFO ist inspiriert durch das soziale Verhalten bei der Nahrungssuche von Escherichia coli. BFO hat bereits die Aufmerksamkeit von Forschern auf sich gezogen, weil es reale Optimierungsprobleme in verschiedenen Anwendungsbereichen effektiv löst. Die Biologie hinter der Futtersuchstrategie von E. coli wird auf originelle Weise nachgeahmt und als einfacher Optimierungsalgorithmus verwendet.

Bakterien, wie E. coli oder Salmonellen, gehören zu den erfolgreichsten Organismen auf unserem Planeten. Diese wendigen Bakterien haben halbstarre Anhängsel, die so genannten Geißeln, mit denen sie sich in einer Drehbewegung fortbewegen. Wenn sich alle Geißeln gegen den Uhrzeigersinn drehen, entsteht ein Propellereffekt, und das Bakterium bewegt sich in einer mehr oder weniger geradlinigen Richtung. In diesem Fall führt das Bakterium eine Bewegung aus, die als Schwimmen bezeichnet wird. Alle Geißeln drehen sich in dieselbe Richtung.

Die Geißeln helfen dem E. coli-Bakterium beim Taumeln und Schwimmen, den beiden wichtigsten Operationen, die das Bakterium bei der Nahrungssuche ausführt. Wenn sie die Geißeln im Uhrzeigersinn drehen, stößt jede Geißel gegen die Zelle. Wenn sich die Geißeln in verschiedene Richtungen drehen, taumelt das Bakterium. In einer günstigen Umgebung bewegt sich das Bakterium mit weniger Umdrehungen, während es in einer schädlichen Umgebung häufig umhertaumelt, um den Nährstoffgradienten zu finden. Die Bewegung der Geißeln gegen den Uhrzeigersinn hilft den Bakterien, mit sehr hoher Geschwindigkeit zu schwimmen.

In dem oben genannten Algorithmus wird das Verhalten von Bakterien durch einen Mechanismus bestimmt, der als bakterielle Chemotaxis bezeichnet wird und eine motorische Reaktion dieser Mikroorganismen auf einen chemischen Reiz in der Umgebung darstellt. Dieser Mechanismus ermöglicht es dem Bakterium, sich in Richtung der anlockende Stoffe (meist Nahrung) und weg von den abstoßende Stoffe (für das Bakterium potenziell schädliche) zu bewegen. An den Polen des Bakteriums befinden sich Rezeptoren, die Lockstoffe und abstoßende Stoffe erkennen.

Aufgrund der geringen Größe des Bakteriums ist es nicht in der Lage, die unterschiedlichen Konzentrationen von nützlichen und schädlichen Stoffen zwischen den Polen zu erfassen. Die Bakterien bestimmen die Gradienten dieser Stoffe, indem sie die Veränderungen ihrer Konzentrationen während der Bewegung messen. Die Geschwindigkeit dieser Bewegung kann mehrere Dutzend Bakterienlängen pro Sekunde erreichen. Escherichia coli zum Beispiel bewegt sich normalerweise mit einer Geschwindigkeit vom 10-20-fachem seiner Länge pro Sekunde.

Abb. 1. Replikation: Teilung in originales (mit beibehaltenen Bewegungsvektoren) und geklontes (mit veränderten Bewegungsvektoren) Bakterium.
Taumeln - eine Veränderung des Bewegungsvektors der Bakterie

Entspricht die vom Bakterium gewählte Bewegungsrichtung einer Zunahme der Konzentration des Lockstoffs (einer Abnahme der Konzentration des Abstoßungsstoffs), so verlängert sich die Zeit bis zum nächsten Taumel. Aufgrund der geringen Größe des Bakteriums wird seine Bewegung stark von der Brownschen Bewegung beeinflusst. Infolgedessen bewegt sich das Bakterium im Durchschnitt nur in Richtung nützlicher Substanzen und weg von schädlichen Substanzen.

Der betrachtete Mechanismus der bakteriellen Bewegung ist nicht der einzige. Einige Bakterien haben nur eine Geißel. Die Varianten der Bewegung des Bakteriums bieten in diesem Fall verschiedene Arten der Rotation und des Anhaltens. Wenn sich das Bakterium jedoch in die richtige Richtung bewegt, nimmt die Dauer dieser Bewegung in jedem Fall zu. Im Allgemeinen kann die bakterielle Chemotaxis (Empfindlichkeit gegenüber dem chemischen Umfeld), als eine komplexe Kombination aus Schwimmen und Taumeln definiert werden, die es den Bakterien ermöglicht, sich an Orten mit hoher Nährstoffkonzentration aufzuhalten und unannehmbare Konzentrationen von Schadstoffen zu vermeiden.

Im Kontext eines Suchmaschinen-Optimierungsproblems kann die bakterielle Chemotaxis auch als ein Mechanismus zur Optimierung der Nutzung bekannter Nahrungsressourcen durch ein Bakterium und zur Suche nach neuen, potenziell wertvolleren Gebieten interpretiert werden Eine Population von Bakterien in ausreichender Menge kann komplexe räumlich-zeitliche Strukturen bilden - der Effekt der Strukturbildung in bakteriellen Populationen. Dieser Effekt kann sowohl durch Chemotaxis als auch durch viele andere Gründe verursacht werden.

Bei einigen Bakterien wird die Bildung solcher Strukturen durch die regulatorischen Eigenschaften ihrer Stoffwechselprodukte erklärt. Ein ähnlicher Effekt ist durch die Phänomene der Magnetotaxis (Empfindlichkeit gegenüber einem Magnetfeld), der Biokonvektion, der negativen Geotaxis (bevorzugte Bewegung von Mikroorganismen gegen die Schwerkraft) und andere Phänomene möglich. In der Regel legen Bakterien in einer freundlichen Umgebung eine größere Strecke zurück. Wenn sie genug Nahrung bekommen, wachsen sie in die Länge und brechen bei der richtigen Temperatur in der Mitte und verwandeln sich in eine exakte Kopie ihrer selbst.

Dieses Phänomen inspirierte Passino dazu, das Reproduktionsereignis in das BFO aufzunehmen. Durch plötzliche Veränderungen in der Umwelt oder einen Angriff kann der chemotaktische Prozess gestört werden und die Bakteriengruppe kann sich an einen anderen Ort bewegen. Dies stellt ein Eliminierungs- und Ausbreitungsereignis in einer realen Bakterienpopulation dar, wenn alle Bakterien in der Region sterben oder eine Gruppe von Bakterien sich in einen neuen Teil der Umgebung ausbreitet. Darüber hinaus sind die betrachteten Verfahren der Chemotaxis und der Reproduktion im Allgemeinen unzureichend, um das globale Maximum der multiextremalen Zielfunktion zu finden, da diese Verfahren es den Bakterien nicht erlauben, die von ihnen gefundenen lokalen Maxima dieser Funktion zu verlassen. Mit dem Eliminierungs- und Dispersionsverfahren soll dieses Manko beseitigt werden. Nach dem Prinzip der natürlichen Auslese (survival of the fittest) werden Bakterien mit schlechter Fitness vernichtet und Bakterien mit höherer Fitness vermehren sich.

2. Beschreibung des Algorithmus

Die kanonische Version von BFO umfasst die folgenden Hauptschritte:

1. Initialisieren wir eine Bakterienkolonie.
2. Chemotaxis.
3. Schwärmen.
4. Reproduktion.
5. Liquidation und Entfernung.

      
1. Initialisierung der Parameter.
Bakterien können in einigen halbfesten Nährstoffen komplexe, stabile räumlich-zeitliche Muster bilden, und sie können in einer Umgebung überleben, wenn sie anfangs gemeinsam im Zentrum stehen. Außerdem geben sie unter bestimmten Bedingungen interzelluläre Locksignale ab, sodass sie sich zusammenschließen und sich gegenseitig schützen.
2. Chemotaxis.
Die Merkmale der Bewegung von Bakterien auf der Suche nach Nahrung können auf zwei Arten bestimmt werden, nämlich durch gemeinsames Schwimmen und Taumeln, was als Chemotaxis bezeichnet wird. Man sagt, dass ein Bakterium „schwimmt“, wenn es sich in die richtige Richtung bewegt, und „taumelt“, wenn es sich in die Richtung der Umweltverschlechterung bewegt.

3. Schwärmen.
Damit die Bakterien an den nahrungsreichsten Ort gelangen, ist es wünschenswert, dass das optimale Bakterium bis zu einem bestimmten Zeitpunkt in der Suchperiode versucht, andere Bakterien anzulocken, damit sie sich schneller am gewünschten Ort versammeln. Zu diesem Zweck wird der ursprünglichen Kostenfunktion eine Straffunktion hinzugefügt, die auf dem relativen Abstand jeder Bakterie von der fittesten Bakterie zu dieser Suchdauer basiert. Schließlich, wenn alle Bakterien zum Entscheidungspunkt verschmelzen, wird diese Straffunktion Null. Der Effekt des Schwärmens besteht darin, dass sich die Bakterien in Gruppen zusammenfinden und sich in konzentrischen Mustern mit hoher Bakteriendichte bewegen.

4. Reproduktion.
Die erste Gruppe von Bakterien erreicht nach mehreren chemotaktischen Stadien das Stadium der Vermehrung. Hier wird die beste Gruppe von Bakterien in zwei Gruppen aufgeteilt. Die gesündere Hälfte wird durch die andere Hälfte der Bakterien ersetzt, die aufgrund ihrer geringeren Fähigkeit, Nahrung zu finden, liquidiert werden. Dadurch bleibt die Population der Bakterien im Laufe der Evolution konstant.

5. Beseitigung und Ausbreitung.
Im Laufe der Evolution kann ein plötzliches, unvorhergesehenes Ereignis eintreten, das den reibungslosen Ablauf der Evolution drastisch verändern und die Eliminierung vieler Bakterien und/oder ihre Ausbreitung in eine neue Umgebung verursachen kann. Ironischerweise kann dieses unbekannte Ereignis, anstatt das normale chemotaktische Wachstum einer Gruppe von Bakterien zu stören, eine neuere Gruppe von Bakterien näher an den Ort der Nahrung bringen. Im Großen und Ganzen gehören Liquidation und Ausbreitung zum Verhalten einer Population über große Entfernungen. Bei der Optimierung hilft dies, die Stagnation zu verringern, die bei solchen parallelen Suchalgorithmen häufig auftritt.

Meine Implementierung von BFO unterscheidet sich leicht von der anerkannten Version. Bei der Betrachtung einzelner Abschnitte des Kodex werde ich auf die Unterschiede eingehen und die Gründe für die Notwendigkeit dieser Änderungen erläutern. Im Allgemeinen können Änderungen an der Implementierung nicht als signifikant angesehen werden, sodass ich den Namen des Algorithmus nicht mit einem „m“ (modified version) kennzeichne. Ich möchte nur anmerken, dass die durchgeführten Änderungen die Ergebnisse verbessert haben.

Betrachten wir nun den Algorithmus und den Code, den ich implementiert habe.

Schritte des Algorithmus:

1. Initialisierung von Bakterienkolonien.
2. Messung der Bakteriengesundheit (Fitness).
3. Replikation?
3.1. Ja: Replikation durchführen.
3.2. Nein: S. 4.
4. Alt (Lebensdauergrenze erreicht)?
4.1. Ja: Taumeln (Ändern des Bewegungsvektors).
4.2. Nein: S. 5.
5. Bewegung in die richtige Richtung?
5.1. Ja: Weiter mit demselben Vektor bewegen.
5.2. Nein: Taumeln (Ändern des Bewegungsvektors).
6. Messen der Gesundheit (Fitness) der Bakterien.
7. Weiter ab S. 3 bis das Stoppkriterium erfüllt ist.

Das logische Schema des Algorithmus ist in Abb. 1 dargestellt.

Abb. 2. Logisches Blockdiagramm des BFO-Algorithmus

Werfen wir einen Blick auf den Code.

Ein Bakterium lässt sich am besten durch eine Struktur beschreiben, die Anordnungen von Koordinaten und Bewegungsvektoren enthält. Aktuelle und frühere Gesundheitswerte und Alterszähler (life counter) der Bakterien. Der Alterszähler ist im Wesentlichen notwendig, um die Anzahl der sequentiellen Bewegungen in eine Richtung zu begrenzen, im Gegensatz zur ursprünglichen Version, in der bei Erreichen der Altersgrenze das Bakterium zerstört und ein neues an einem zufälligen Ort im Suchraum erzeugt wird. Da wir dieses Thema jedoch bereits in früheren Artikeln behandelt haben, hat das Anlegen eines neuen Agenten an einem zufälligen Ort keine praktische Bedeutung und verschlechtert nur die Suchmöglichkeiten. In diesem Fall ist es besser, entweder einen neuen Agenten am Ort der besten Lösung zu erstellen oder sich vom aktuellen Ort aus weiter zu bewegen, aber den Richtungsvektor zu ändern. Die zweite Option zeigte bessere Ergebnisse.

Die kanonische Version verwendet einen konstanten Bewegungsvektor. Bei einer großen Anzahl von Lebewesen würde dies dazu führen, dass sich die Bakterien entlang einer geraden Linie im Suchraum bewegen. Würde diese Linie kein Extremum durchqueren, würde sich dieser Prozess der geradlinigen Bewegung unendlich fortsetzen, aber hier spielt der Zähler die Rolle eines erzwungenen Taumels, der es dem Bakterium ermöglicht, eine geradlinige Bewegung während seines gesamten Lebens zu vermeiden. Bei Funktionen mit Bereichen, die keinen Gradienten aufweisen, wird sie schließlich doch zu einem Ort führen, an dem sie beginnen kann, ihre Fitness zu verbessern.

//——————————————————————————————————————————————————————————————————————————————
struct S_Bacteria
{
  double c  [];   //coordinates
  double v  [];   //vector
  double f;       //current health
  double fLast;   //previous health
  double lifeCNT; //life counter
};
//——————————————————————————————————————————————————————————————————————————————

Wir deklarieren die BFO-Algorithmusklasse als C_AO_BFO. Die Klasse enthält die Deklaration der Bakterienkolonie, die Grenzen des Suchraums, den Wert der besten Lösung und das Koordinatenfeld der besten Lösung. Außerdem geben wir konstante Werte für die Algorithmusparameter an.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BFO
{
  //----------------------------------------------------------------------------
  public: S_Bacteria b     []; //bacteria
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates

  public: void Init (const int    paramsP,         //number of opt. parameters
                     const int    populationSizeP, //population size
                     const double lambdaP,         //lambda
                     const double reproductionP,   //probability of reproduction
                     const int    lifeCounterP);   //life counter

  public: void Swimming   ();
  public: void Evaluation ();

  //----------------------------------------------------------------------------
  private: double NewVector (int paramInd);
  private: S_Bacteria bT []; //bacteria
  private: double v      [];
  private: int    ind    [];
  private: double val    [];
  private: int    populationSize; //population size
  private: int    parameters;     //number of optimized parameters
  private: double lambda;         //lambda
  private: double reproduction;   //probability of reproduction
  private: int    lifeCounter;    //life counter
  private: bool   evaluation;

  private: void   Sorting ();
  private: double SeInDiSp             (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI            (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

Die öffentliche Methode Init() dient dazu, konstante Variablen zu initialisieren, Array-Größen zu verteilen und Flags und den Wert der besten Lösung zurückzusetzen.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO::Init (const int    paramsP,         //number of opt. parameters
                     const int    populationSizeP, //population size
                     const double lambdaP,         //lambda
                     const double reproductionP,   //probability of reproduction
                     const int    lifeCounterP)    //life counter
{
  fB = -DBL_MAX;
  evaluation = false;

  parameters      = paramsP;
  populationSize  = populationSizeP;
  lambda          = lambdaP;
  reproduction    = reproductionP;
  lifeCounter     = lifeCounterP;

  ArrayResize (rangeMax,  parameters);
  ArrayResize (rangeMin,  parameters);
  ArrayResize (rangeStep, parameters);
  ArrayResize (v,         parameters);

  ArrayResize (ind,       populationSize);
  ArrayResize (val,       populationSize);

  ArrayResize (b,  populationSize);
  ArrayResize (bT, populationSize);

  for (int i = 0; i < populationSize; i++)
  {
    ArrayResize (b [i].c,  parameters);
    ArrayResize (b [i].v,  parameters);
    b [i].f  = -DBL_MAX;
    b [i].fLast = -DBL_MAX;

    ArrayResize (bT [i].c,  parameters);
    ArrayResize (bT [i].v,  parameters);
  }

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

Die erste öffentliche Methode, die bei jeder Iteration aufgerufen werden muss - Swimming() oder Bakterienschwimmen - enthält die gesamte Hauptlogik des Algorithmus.

void C_AO_BFO::Swimming ()
{}

Schauen wir uns die Methode im Detail an. Bei der ersten Iteration, wenn das Auswerteflag auf „false“ gesetzt ist, streuen wir die Bakterien zufällig mit einer Gleichverteilung über den gesamten Suchraum. In diesem Stadium sind der aktuelle Gesundheitszustand (Fitness) und der vorherige unbekannt. Weisen wir den DBL_MAX-Wert den entsprechenden Variablen zu. Wir überprüfen die zufällig erhaltenen Koordinaten auf Überschreitung der Grenzen und führen den Schritt der Änderung der optimierten Parameter durch. Bei dieser Iteration muss für jedes Bakterium ein individueller Bewegungsvektor mit Hilfe der privaten Methode NewVector() festgelegt werden (ich werde sie weiter unten besprechen). Alle Bakterien schwimmen gleichmäßig vorwärts und in einer geraden Linie mit demselben individuellen Vektor, bis die Bedingungen für seine Veränderung erfüllt sind.

//----------------------------------------------------------------------------
if (!evaluation)
{
  fB = -DBL_MAX;

  for (int s = 0; s < populationSize; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);

      v [k] = rangeMax [k] - rangeMin [k];

      b [s].v [k] = NewVector (k);

      b [s].f  = -DBL_MAX;
      b [s].fLast = -DBL_MAX;

      b [s].lifeCNT = 0;
    }
  }

  evaluation = true;
}

Bei der zweiten und den folgenden Iterationen werden die Operationen Schwimmen, Taumeln, Replikation und Zerstörung der Bakterien durchgeführt, wenn die Grenze der Lebenszeit erreicht ist. Die erste in der Logik ist der Vorgang der Reproduktion (mit der in den Parametern angegebenen Wahrscheinlichkeit). Das bedeutet, dass die Bakterienkolonie in der vorherigen Iteration in absteigender Reihenfolge des Gesundheitswertes sortiert wird.

Die Fortpflanzung im Algorithmus erfüllt eine wichtige Funktion: Sie beschleunigt die Konvergenz des Algorithmus, indem sie den „Genpool“ der Bakterienkolonie verbessert. Der Vorgang ist eine imaginäre Teilung der Bakterien in zwei Teile, wobei nur die erste, bessere Hälfte der Kolonie sich teilen darf. Die erste Hälfte der Kolonie wird halbiert, die ursprüngliche Elternversion wird in die zweite Hälfte der Kolonie gesetzt. Das Elternbakterium wird sich im Gegensatz zu seinem Klon weiterhin mit demselben Vektor bewegen. Der Klon bleibt an seinem Platz in der Kolonie und ihm wird ein neuer Bewegungsvektor zugewiesen. Das Elternteil und sein Klon bewegen sich von dem Punkt im Raum weiter, an dem die Teilung stattgefunden hat.

r = RNDfromCI (0.0, 1.0);

//==========================================================================
if (r < reproduction)
{
  int st = populationSize / 2;
  for (int s = 0; s < st; s++)
  {
    //bacterium original--------------------------------------------------
    for (int k = 0; k < parameters; k++)
    {
      b [st + s].v [k] = b [s].v [k];
      b [st + s].c [k] = b [s].c [k] + b [s].v [k];
      b [st + s].c [k] = SeInDiSp (b [st + s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [st + s].fLast = b [s].f;
      b [st + s].lifeCNT++;
    }

    //bacterium clone-------------------------------------------------------
    for (int k = 0; k < parameters; k++)
    {
      b [s].v [k] = NewVector (k);
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT = 0;
    }
  }
}

Wenn die Replikationswahrscheinlichkeit nicht erfüllt ist, wird geprüft, ob die Lebensdauer der Bakterien erreicht ist. In der kanonischen Version des Algorithmus sollte das „alte“ Bakterium zerstört und stattdessen ein neues an einer zufälligen Stelle im Suchraum innerhalb der Liste der Bakterien erzeugt werden. Im allgemeinen Fall reichen die Operationen der Reproduktion und der Chemotaxis nicht aus, um das globale Maximum der multiextremen Fitnessfunktion zu finden, da
Diese Verfahren erlauben es den Bakterien nicht, die von ihnen gefundenen lokalen Minima zu verlassen. Das Liquidationsverfahren soll dieses Manko beseitigen. Wie die Praxis der Experimente mit diesem und anderen Algorithmen jedoch gezeigt hat, ist es in diesem Fall effizienter, einfach den Bewegungsvektor zu ändern. Der Alterszähler wird zurückgesetzt. Der Zähler ist ein Auslöser für die Änderung der Bewegungsrichtung nach einer bestimmten Anzahl von Schritten (Lebensalter). Die Gesamtzahl der Bakterien bleibt aufgrund von Replikation und Eliminierung konstant.

if (b [s].lifeCNT >= lifeCounter)
{
  for (int k = 0; k < parameters; k++)
  {
    b [s].v [k] = NewVector (k);
    b [s].c [k] = b [s].c [k] + b [s].v [k];
    b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    b [s].fLast = b [s].f;
    b [s].lifeCNT = 0;
  }
}

Wenn das Lebenslimit noch nicht ausgeschöpft ist, wird geprüft, ob sich das Bakterium in Richtung einer Verbesserung des Gradienten der Fitnessfunktion bewegt. Mit anderen Worten, wir überprüfen zwei Gesundheitswerte - bei der aktuellen Iteration und bei der vorherigen. Wenn sich der Gesundheitszustand verbessert hat, wird der Bewegungsvektor beibehalten, andernfalls sollte das Bakterium taumeln (den Bewegungsvektor ändern).

In der kanonischen Version wird eine strenge „größer als“-Prüfung des aktuellen und des vorherigen Gesundheitszustands durchgeführt, während in meiner Version „größer oder gleich“ angewendet wird, was es dem Bakterium ermöglicht, sich auch auf einem völlig „horizontalen“ Abschnitt der untersuchten Oberfläche fortzubewegen, wo es keinen Gradienten der Fitnessfunktion gibt, da das Bakterium sonst endlos an einer Stelle taumeln würde (es gibt keine Veränderung des Gesundheitszustands, was bedeutet, dass es keine Schwimmrichtung gibt). In diesem Stadium muss auch geprüft werden, ob die empfangenen neuen Koordinaten über die Grenzen des Suchraums hinausgehen.

else
{
  if (b [s].f >= b [s].fLast)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT++;
    }
  }
  else
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].v [k] = NewVector (k);
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT++;
    }
  }
}

NewVecror() - ist eine private Methode zur Änderung des Bewegungsvektors (taumeln). Die Methode wird für jede Koordinate angewendet. Die Idee dahinter ist einfach: Die Differenz zwischen den Suchgrenzen für die entsprechende Koordinate v wird mit einer Zufallszahl r aus dem Bereich [-1,0;1,0] multipliziert und mit dem Lambda-Skalierungsfaktor (einem der Algorithmusparameter) multipliziert. Das Bakterium verwendet den Bewegungsvektor unverändert, bis das Limit an Leben erschöpft ist (ein neues Bakterium wird an der gleichen Stelle, aber mit einem neuen Bewegungsvektor geschaffen), während der Replikation (der Klon hat einen neuen Vektor) und während der Verschlechterung des Gesundheitszustands (ein Versuch, eine neue, günstigere Umgebung zu finden).  

//——————————————————————————————————————————————————————————————————————————————
double C_AO_BFO::NewVector (int paramInd)
{
  double r = RNDfromCI (-1.0, 1.0);
  return lambda * v [paramInd] * r;
}
//——————————————————————————————————————————————————————————————————————————————

Die zweite öffentliche Methode Evaluation(), die bei jeder Iteration ausgeführt werden sollte, ruft die Sortiermethode auf, prüft auf Aktualisierungen der globalen Lösung und vergleicht den Gesundheitszustand des besten Bakteriums in der sortierten Kolonie mit der besten gefundenen Lösung.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO::Evaluation ()
{
  Sorting ();

  if (b [0].f > fB)
  {
    fB = b [0].f;
    ArrayCopy (cB, b [0].c, 0, 0, WHOLE_ARRAY);
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Testergebnisse

Ergebnisse des BFO-Prüfstands:

2023.01.21 12:52:46.501    Test_AO_BFO (.US500Cash,M1)    C_AO_BFO:50;0.01;0.8;100
2023.01.21 12:52:46.501    Test_AO_BFO (.US500Cash,M1)    =============================
2023.01.21 12:52:48.451    Test_AO_BFO (.US500Cash,M1)    5 Rastrigins; Funktionsdurchläufe 10000 Ergebnis: 72.94540549092933
2023.01.21 12:52:48.451    Test_AO_BFO (.US500Cash,M1)    Score: 0.90383
2023.01.21 12:52:51.778    Test_AO_BFO (.US500Cash,M1)    25 Rastrigins; Funktionsdurchläufe 10000 Ergebnis: 54.75744312933767
2023.01.21 12:52:51.778    Test_AO_BFO (.US500Cash,M1)    Score: 0.67848
2023.01.21 12:53:21.197    Test_AO_BFO (.US500Cash,M1)    500 Rastrigins; Funktionsdurchläufe 10000 Ergebnis: 40.668487609790404
2023.01.21 12:53:21.197    Test_AO_BFO (.US500Cash,M1)    Score: 0.50391
2023.01.21 12:53:21.197    Test_AO_BFO (.US500Cash,M1)    =============================
2023.01.21 12:53:23.211    Test_AO_BFO (.US500Cash,M1)    5 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.8569098398505888
2023.01.21 12:53:23.211    Test_AO_BFO (.US500Cash,M1)    Score: 0.48471
2023.01.21 12:53:26.878    Test_AO_BFO (.US500Cash,M1)    25 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.37618151461180294
2023.01.21 12:53:26.878    Test_AO_BFO (.US500Cash,M1)    Score: 0.21279
2023.01.21 12:54:22.339    Test_AO_BFO (.US500Cash,M1)    500 Forests; Funktionsdurchläufe 10000 Ergebnis: 0.08748190028975696
2023.01.21 12:54:22.339    Test_AO_BFO (.US500Cash,M1)    Score: 0.04948
2023.01.21 12:54:22.339    Test_AO_BFO (.US500Cash,M1)    =============================
2023.01.21 12:54:28.849    Test_AO_BFO (.US500Cash,M1)    5 Megacities; Funktionsdurchläufe 10000 Ergebnis: 4.8
2023.01.21 12:54:28.849    Test_AO_BFO (.US500Cash,M1)    Score: 0.40000
2023.01.21 12:54:40.089    Test_AO_BFO (.US500Cash,M1)    25 Megacities; Funktionsdurchläufe 10000 Ergebnis: 2.216
2023.01.21 12:54:40.089    Test_AO_BFO (.US500Cash,M1)    Score: 0.18467
2023.01.21 12:55:24.640    Test_AO_BFO (.US500Cash,M1)    500 Megacities; Funktionsdurchläufe 10000 Ergebnis: 0.4232
2023.01.21 12:55:24.640    Test_AO_BFO (.US500Cash,M1)    Score: 0.03527

Es ist aber noch zu früh, um eindeutige Schlussfolgerungen zu ziehen. Es ist notwendig, die Ergebnisse zunächst im Verhältnis zu den anderen Testteilnehmern zu analysieren.

  BFO mit die Rastrigin-Testfunktion.

BFO über den Forest-Testfunktion.

BFO über die Megacity-Testfunktion.

Schauen wir uns die Testvisualisierung an. Die Animation bestätigte die Richtigkeit der Entscheidung, das „größer als“-Zeichen in unserem Algorithmus durch „größer oder gleich“ zu ersetzen. Dadurch konnten sich die Bakterien in den horizontalen Abschnitten der Testfunktionen weiter bewegen. Besonders auffällig ist dies bei den Funktionen Forest und Megacity. Die Bakterien versuchen, sich auch dort fortzubewegen, wo es überhaupt keine Funktionsgradienten gibt. Zu beachten ist auch die Fähigkeit einer Bakterienkolonie, sich in mehrere separate Kolonien aufzuteilen, die visuell in verschiedene lokale Extreme unterteilt sind, was eindeutig als positives Merkmal gewertet werden kann, obwohl der Algorithmus keine logischen Methoden für die Bildung von Unterkolonien enthält. Im Allgemeinen ist eine gleichmäßige Bewegung der Bakterien im Suchraum festzustellen, ohne dass versucht wird, einen scharfen Sprung in eine der Richtungen zu machen, was durch eine gleichmäßige inkrementelle Bewegung - Chemotaxis - erklärt wird.

AO	Beschreibung	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (diskret)			Megacity final	Endergebnis
		10 Parameter (5 F)	50 Parameter (25 F)	1000 Parameter (500 F)		10 Parameter (5 F)	50 Parameter (25 F)	1000 Parameter (500 F)		10 Parameter (5 F)	50 Parameter (25 F)	1000 Parameter (500 F)
IWO	Optimierung mit invasiven Unkräutern	1.00000	1.00000	0.33519	2.33519	0.79937	0.46349	0.41071	1.67357	0.75912	0.44903	0.94088	2.14903	100.000
ACOm	Ameisen-Kolonie-Optimierung M	0.36118	0.26810	0.17991	0.80919	1.00000	1.00000	1.00000	3.00000	1.00000	1.00000	0.10959	2.10959	95.996
COAm	Kuckuck-Optimierungsalgorithmus M	0.96423	0.69756	0.28892	1.95071	0.64504	0.34034	0.21362	1.19900	0.67153	0.34273	0.45422	1.46848	74.204
FAm	Firefly-Algorithmus M	0.62430	0.50653	0.18102	1.31185	0.55408	0.42299	0.64360	1.62067	0.21167	0.28416	1.00000	1.49583	71.024
BA	Fledermaus-Algorithmus	0.42290	0.95047	1.00000	2.37337	0.17768	0.17477	0.33595	0.68840	0.15329	0.07158	0.46287	0.68774	59.650
ABC	Künstliches Bienenvolk (Artificial Bee Colony, ABC)	0.81573	0.48767	0.22588	1.52928	0.58850	0.21455	0.17249	0.97554	0.47444	0.26681	0.35941	1.10066	57.237
BFO	Optimierung der bakteriellen Futtersuche	0.70129	0.46155	0.11627	1.27911	0.41251	0.26623	0.26695	0.94569	0.42336	0.34491	0.50973	1.27800	55.516
FSS	Fischschulsuche	0.48850	0.37769	0.11006	0.97625	0.07806	0.05013	0.08423	0.21242	0.00000	0.01084	0.18998	0.20082	20.109
PSO	Partikelschwarmoptimierung	0.21339	0.12224	0.05966	0.39529	0.15345	0.10486	0.28099	0.53930	0.08028	0.02385	0.00000	0.10413	14.232
RND	zufällig	0.17559	0.14524	0.07011	0.39094	0.08623	0.04810	0.06094	0.19527	0.00000	0.00000	0.08904	0.08904	8.142
GWO	Grauer-Wolf-Optimierung	0.00000	0.00000	0.00000	0.00000	0.00000	0.00000	0.00000	0.00000	0.18977	0.04119	0.01802	0.24898	1.000

Nun ist es an der Zeit, die Testergebnisse zu analysieren. In der aktuellen Liste der teilnehmenden Algorithmen befindet sich BFO mit einer Gesamtpunktzahl von knapp über 55 im Mittelfeld der Bewertungstabelle. Die Ergebnisse sind nicht beeindruckend, aber auch nicht schlecht. Gute Ergebnisse wurden insbesondere bei der Rastrigin-Funktion mit 10 Variablen erzielt. Im Falle von 50 und 1000 Variablen sind die Ergebnisse deutlich schlechter. Außerdem schnitt der Algorithmus bei der Forest-Funktion nicht gut ab. Das relativ gute Verhalten bei der diskreten Megacity-Funktion ist überraschend, da es im Algorithmus keine Mechanismen für die Bearbeitung solcher Funktionen gibt. Außerdem ist eine gute Skalierbarkeit im Vergleich zu anderen Algorithmen gegeben (Test mit 1000 Megacity-Parametern).

BFO ist ein wissenschaftliches Gebiet mit einer Vielzahl von Möglichkeiten. Es gibt eine Reihe von Aspekten der bakteriellen Nahrungssuche und der tierischen Nahrungssuche im Allgemeinen, die modelliert werden können, um die Optimierungsleistung zu verbessern. Für den BFO-Algorithmus kann die automatische Anpassung der Kontrollparameter von besonderer Bedeutung sein, da es viele Parameter gibt, und sie kann zu einer besseren Leistung führen, was ein Grund für zusätzliche Versuche ist.

BFO hat eine Reihe von Vorteilen, darunter eine geringe Empfindlichkeit gegenüber den Anfangswerten der Koordinaten bei der Initialisierung und der Wahl der Parameter, eine hohe Zuverlässigkeit, eine einfache Logik, eine leichte Implementierung, die Möglichkeit der Parallelisierung und der globalen Suche. Der BFO-Algorithmus wird daher zur Lösung einer Vielzahl von Optimierungsproblemen eingesetzt. BFO hat jedoch auch eine Reihe von Nachteilen, darunter langsame Konvergenz, die Unfähigkeit, in einigen Fällen über lokale Optima hinauszugehen, und eine feste Schrittlänge. BFO ist eine Metaheuristik, d. h. es handelt sich lediglich um einen konzeptionellen Rahmen, der für die Entwicklung von Algorithmusänderungen verwendet werden kann. Die hier vorgestellte Version des BFO ist nur eine von vielen Möglichkeiten und sollte als Ausgangspunkt für Experimente und nicht als letztes Wort zu diesem Thema betrachtet werden.

Das Histogramm der Algorithmus-Testergebnisse ist unten dargestellt.

Abb. 3. Histogramm der Endergebnisse der Testalgorithmen

Schlussfolgerungen zu den Eigenschaften des Bacterial Foraging Optimization (BFO)-Algorithmus:

Vorteile:
1. Hohe Geschwindigkeit.
2. Einfache Logik.
3. Konvergenz in allen Iterationen, wenn auch langsam.

Nachteile
1. Langsame Konvergenz.
2. Keine Methoden zum Verlassen lokaler Extrema.