Algorithmen zur Optimierung mit Populationen: Stochastische Diffusionssuche (SDS)

Inhalt

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

1. Einführung

Der Algorithmus Stochastic Diffusion Search (Stochastische Diffusionssuche, SDS) wurde 1989 von J. Bishop vorgeschlagen und von Bishop und S. Nasuto aktiv weiterentwickelt. Eine Besonderheit dieses Algorithmus ist seine tiefe mathematische Begründung im Vergleich zu anderen Populationsalgorithmen. SDS wurde ursprünglich für die diskrete Optimierung entwickelt. Im Jahr 2011 wurde seine Modifikation für die globale kontinuierliche Optimierung vorgeschlagen.

Interessante Fakten:

1. Stochastic Diffusion Search (SDS) war die erste Schwarmintelligenz-Metaheuristik, die zur Familie der Schwarmintelligenz und der natürlichen Such- und Optimierungsalgorithmen gehört. Weitere Beispiele für solche Algorithmen sind die Ameisenkolonie-Optimierung, die Partikelschwarm-Optimierung und genetische Algorithmen.

2. Im Gegensatz zur Optimierung von Ameisenkolonien, die auf Stigmergy-Kommunikation basiert, nutzt SDS die direkte Kommunikation zwischen den Agenten, ähnlich dem Tandem-Ruf-Mechanismus, den die Ameisen von Leptothorax acervorum verwenden.

Der SDS-Algorithmus basiert auf der kostengünstigen partiellen Bewertung einer Hypothese (eines Lösungskandidaten für ein Suchproblem) durch Agenten. Die Agenten tauschen dann Informationen über die Hypothesen durch direkte persönliche Kommunikation aus. Durch den Diffusionsmechanismus können hochwertige Lösungen aus Gruppen von Agenten mit der gleichen Hypothese ermittelt werden.

Um die Funktionsweise des SDS-Algorithmus besser zu verstehen, können wir eine einfache Analogie verwenden - das Restaurant-Spiel.

Bei dem Restaurant-Spiel spielen die Teilnehmer die Rolle von Agenten und die Restaurants die Rolle von Hypothesen. Jeder Agent wählt auf der Grundlage seiner Vorlieben und der Informationen, die er von anderen Agenten erhält, ein Restaurant aus, in dem er essen möchte. Die Agenten tauschen dann Informationen über ihre Wahlmöglichkeiten und Präferenzen aus. Als Ergebnis dieses Prozesses bilden sich Cluster von Agenten, die das gleiche Restaurant gewählt haben, und können als potenziell gute Entscheidungen identifiziert werden.

Der SDS-Algorithmus hat mehrere Vorteile. Erstens erlaubt er den Agenten, billige partielle Hypothesenschätzungen vorzunehmen, was die Berechnungskomplexität des Algorithmus verringert. Zweitens nutzt er die direkte persönliche Kommunikation zwischen den Agenten, was eine effiziente Verbreitung von Informationen ermöglicht. Drittens basiert die SDS auf mathematischen Grundlagen, was sie zuverlässiger und berechenbarer macht.

Der SDS-Algorithmus hat jedoch auch seine Grenzen. Erstens kann er nur bei bestimmten Arten von Problemen wirksam sein, bei denen das Konzept einer Hypothese anwendbar ist. Zweitens kann das Problem der vorzeitigen Konvergenz auftreten, bei der sich die Akteure zu schnell auf eine Hypothese einigen, ohne andere Möglichkeiten zu prüfen. Drittens erfordert der Algorithmus eine Abstimmung der Parameter, was ein komplexer und zeitaufwändiger Prozess sein kann. Die Einschränkungen wurden von einigen Autoren geäußert. Prüfen wir, ob sie gerechtfertigt sind.

Insgesamt ist SDS ein interessanter und effizienter Algorithmus zur Lösung von Optimierungsproblemen. Er vereint die Vorteile von Populationsalgorithmen und mathematischer Rationalität, was ihn für Forschung und Anwendung in verschiedenen Bereichen attraktiv macht.

2. Der Algorithmus

Kommen wir nun zu einer genaueren Betrachtung des SDS-Algorithmus.

Stochastic Diffusion Search (SDS) ist ein Populationsalgorithmus, der auf zwei Ideen für Suchstrategien beruht:

1. Teilweise Bewertung von Lösungen.
2. Verbreitung vielversprechender Lösungen in der Population.

Es gibt zwei kanonische Spiele, die in einfachen Worten beschreiben, wie SDS funktioniert.
1. Das Restaurant-Spiel
2. Das Goldgräber-Spiel.

Das Restaurant-Spiel

Eine Gruppe von Delegierten befindet sich auf einer langen Konferenz in einer unbekannten Stadt. Jeden Abend stehen sie vor dem Problem, ein Restaurant für das Abendessen auszuwählen. In der Stadt gibt es eine große Anzahl von Restaurants, die eine Vielzahl von Gerichten anbieten. Ziel der Gruppe ist es, den besten Ort zu finden, an dem jeder Delegierte eine Mahlzeit genießen kann. Eine erschöpfende Suche nach allen möglichen Kombinationen von Restaurants und Gerichten würde jedoch zu viel Zeit in Anspruch nehmen. Um dieses Problem zu lösen, greifen die Delegierten auf die stochastische Diffusionssuche (stochastic diffusion search) zurück.

Jeder Delegierte agiert als Agent, der eine Vermutung bezüglich der Auswahl des besten Restaurants in der Stadt anstellt. Jeden Abend testen die Delegierten ihre Hypothesen, indem sie Restaurants besuchen und nach dem Zufallsprinzip ein Angebot aus der Speisenauswahl des Restaurants auswählen. Am nächsten Morgen beim Frühstück bittet jeder Delegierte, der mit dem Abendessen am Vorabend unzufrieden war, einen seiner Kollegen, ihm seine Eindrücke vom Abendessen mitzuteilen. Wenn die Eindrücke des Kollegen positiv sind, wählt der Delegierte ebenfalls dieses Restaurant. Andernfalls wählt der Delegierte zufällig einen anderen Ort aus der Liste der verfügbaren Restaurants in dieser Stadt aus.

Dank dieser Strategie bildet sich schnell eine beträchtliche Anzahl von Delegierten, die sich um das beste Restaurant der Stadt versammeln.

Das Spiel hat mehrere interessante Funktionen. In völliger Abwesenheit von externer Kontrolle und Verwaltung kommuniziert eine Gruppe von Delegierten, um ein Problem zu lösen, das allein nicht schnell zu lösen ist. Wenn der Service oder die Speisekarte des aktuellen Restaurants deutlich nachlässt oder das Geschäft geschlossen wird, ziehen die Delegierten effektiv zum nächstbesten Restaurant weiter. Die Hauptanforderung ist die Vergleichbarkeit von Restaurants, Speisekarten und einzelnen Gerichten. Jeder Vermittler entscheidet selbst, ob seine Erfahrungen gut waren.

Die Delegierten verbringen mehrere Abende in einem hochwertigen Restaurant, bevor alle Gerichte in allen Lokalen der Stadt bewertet werden.
Kritiker weisen darauf hin, dass die Delegierten wahrscheinlich unterschiedliche Essensvorlieben haben, sodass ein Delegierter vielleicht ein Restaurant findet, in dem ihm alle Gerichte schmecken, aber der Rest der Gruppe nicht zufrieden ist. Wenn nur einer oder eine kleine Anzahl von Delegierten dauerhaft in einem solchen Restaurant verbleibt, agieren die übrigen wie gewohnt weiter, und am Ende versammelt sich die Mehrheit immer noch im besten Restaurant. Im Extremfall kann es jedoch vorkommen, dass alle Bediensteten allein essen, selbst wenn es ein einziges ausgezeichnetes Restaurant gibt, das die Mehrheit der Delegierten zufrieden stellt. Dieses Restaurant wird nie gefunden werden, da alle Delegierten mit ihrer derzeitigen Auswahl zufrieden sind und nicht nach neuen Lokalen suchen werden.

Unsere Implementierung nimmt kleine Änderungen an der Logik der Suchstrategie vor, dank derer die Delegierten die Suche nach Restaurants auch dann fortsetzen, wenn es keinen Delegierten mit besserer Erfahrung gibt, sodass die Suche nach Restaurants nicht aufhört, im Gegensatz zur kanonischen Version, in der die Tatsache der Änderung der aktuellen Meinung über ein Restaurant gegenüber der vorherigen wichtig ist. Wenn sich die Meinung der Mehrheit der Delegierten nicht zum Besseren wandelt, werden sie weiterhin in das gleiche Restaurant gehen, was bedeutet, dass sie in einem lokalen Extrem stecken bleiben.

Das Goldgräber-Spiel

Eine Gruppe von Freunden, bestehend aus erfahrenen Bergleuten, erfährt von der Möglichkeit, in den Hügeln eines Gebirges Gold zu schürfen. Sie haben jedoch keine Informationen darüber, wo genau sich der reichste Ort befindet. Auf ihren Karten ist das Gebirge in mehrere einzelne Hügel unterteilt, die jeweils eine Reihe von Schichten enthalten, die abgebaut werden müssen. Die Wahrscheinlichkeit, im Laufe der Zeit Gold zu finden, ist proportional zu seinem Reichtum.

Um ihren kollektiven Reichtum zu maximieren, sollten die Bergleute den Hügel mit den reichsten Goldflözen ausfindig machen, damit möglichst viele Bergleute dort schürfen können. Diese Informationen sind jedoch nicht im Voraus verfügbar. Um dieses Problem zu lösen, beschließen die Bergleute, eine einfache stochastische Diffusionssuche durchzuführen.

Der Abbauprozess beginnt damit, dass jedem Bergmann zufällig ein abzubauender Hügel zugewiesen wird (nutzerdefinierte Hügelhypothese). Jeden Tag wählt jeder Bergmann nach dem Zufallsprinzip ein Flöz auf seinem Hügel zum Abbau aus.

Am Ende eines jeden Tages ist die Wahrscheinlichkeit, dass der Bergmann glücklich ist, proportional zu der Menge an Gold, die er gefunden hat (der Wert der Fitnessfunktion).
Abends, nach getaner Arbeit, treffen sich die Bergleute. Ein unzufriedener Bergmann wählt zufällig einen anderen Bergmann aus, mit dem er sprechen möchte. Wenn der ausgewählte Bergmann zufrieden ist, sagt er seinem Kollegen gerne den Namen des Hügels, den er abbaut. Beide Bergleute unterstützen also die Hügel-Hypothese. Wenn der gewählte Bergmann unzufrieden ist, sagt er nichts, und der ursprüngliche Bergmann ist erneut gezwungen, eine neue Hypothese zu wählen - und den Hügel, den er am nächsten Tag abbauen wird, zufällig zu bestimmen.

Im Rahmen von SDS (selbstorganisierende dynamische Systeme) fungieren Agenten als Bergmänner. Aktive Agenten sind „glückliche Bergleute“ und inaktive Agenten sind „unglückliche Bergleute“. Die Hypothese eines jeden Agenten stellt die „Hügelhypothese“ des Bergmanns dar. Dieser Prozess ist isomorph zu SDS und ermöglicht es den Bergleuten, sich auf natürliche Weise selbst zu organisieren und schnell auf die Hügel eines Bergrückens mit einer hohen Goldkonzentration zu stoßen.

Die Zufriedenheit der Bergleute kann probabilistisch gemessen oder als absoluter boolescher Wert dargestellt werden, da jeder Bergmann am Ende eines jeden Tages entweder glücklich oder unglücklich ist. Wenn Gold als eine begrenzte Ressource modelliert wird, die mit der Zeit abnimmt, dann wird die Suche recht anpassungsfähig, und die Bergleute ziehen an Orte mit dem meisten Gold.

Obwohl der Begriff „glücklich“ subjektiv ist, wie die Essgewohnheiten, wird er in diesem Fall in einem objektiven Sinne verwendet. Alle Bergleute arbeiten nach demselben Verfahren: Die Menge an Gold, die sie an einem Tag finden, bestimmt die Wahrscheinlichkeit, dass sie sich am Ende des Tages als „glücklich“ bezeichnen, wenn sie zusammenkommen, um möglicherweise Informationen über die Hügel, die sie abbauen, auszutauschen.

Die Einteilung der Bergleute in „glückliche“ und „unglückliche“ Bergleute wird nicht verwendet. Wie im Fall des Konzeptes des Restaurant-Spiels ermöglicht dies eine Steigerung der Aktivität der Agenten bei der Suche nach neuen unerforschten Orten.

Um den Algorithmus zu formalisieren, verwenden wir den Begriff „Kandidat“ für die Delegierte im Restaurant-Spiel und die Bergmänner im Goldgräber-Spiel. Der Kandidat ist ein Suchagent. Zum einfacheren Verständnis des Wesens eines Restaurants oder eines Hügels können wir uns einen Raum mit zwei Koordinaten vorstellen, obwohl in Wirklichkeit eine unbegrenzte Anzahl von Koordinaten verwendet werden kann, um mehrdimensionale Probleme zu lösen. In Abbildung 1 bezeichnen die Bezeichnungen C1, C2, C3 Kandidaten, die die Restaurantnummern speichern (die entsprechenden Leerzeichen im Suchfeld). Im Prozess des diffusen Austauschs von Informationen über Restaurants leihen sich die Kandidaten Restaurantnummern von zufällig ausgewählten Konferenzteilnehmern, wenn der Wert der Fitnessfunktion des Gesprächspartners höher ist. Der Bereich jedes Optimierungsparameters (Suchraumkoordinaten) wird durch die Anzahl der in den externen Parametern des Algorithmus angegebenen Restaurants geteilt. Wenn beispielsweise die Anzahl von 100 Restaurants in den Algorithmusparametern angegeben ist, bedeutet dies, dass der Bereich jeder Koordinate in 100 Teile unterteilt wird.

Jedes Restaurant bietet eine Liste der Gerichte auf der Speisekarte. Jedes Menügericht ist eine spezifische Koordinate des Suchraums innerhalb eines Restaurants. Der Algorithmus setzt ein Schema um, bei dem der Kandidat nur ein zufällig ausgewähltes Restaurantgericht probiert.

Bild 1. Eine visuelle Darstellung des Diffusionsprinzips für den Informationsaustausch in Restaurants

Schauen wir uns die Schritte des SDS-Algorithmus in Form eines Pseudocodes an.

1. Initialisierung der Kandidaten (Zuweisung zufälliger Restaurants und Gerichte).

2.0. Prüfung von Hypothesen und Austausch von Informationen zwischen den Kandidaten.

2.1. Vergleiche die aktuelle Erfahrung des Kandidaten mit seiner früheren Erfahrung.

2.1.1. Wenn die Erfahrung besser ist, weise die Restaurantadressen als Hypothese für die nächste Iteration zu.

2.1.2. Wenn die Erfahrung schlechter ist, frag einen zufällig ausgewählten Kandidaten nach seiner Meinung.

2.1.2.1. Wenn die Erfahrung des Gesprächspartners (des Kandidaten) besser ist, dann nimm die Adressen der (für den aktuellen Kandidaten) vielversprechenden Restaurants.

2.1.2.2. Wenn die Erfahrung des Gesprächspartners - des Kandidaten - schlechter ist, dann wähle mit einer gewissen Wahrscheinlichkeit entweder die Adresse eines zufällig ausgewählten Restaurants oder behalten das aktuelle.

3.0. Wähle die Gerichte aus der generierten Liste von Restaurants als Hypothese für die nächste Iteration aus.

Das logische Schema der Hypothesenprüfung ist in Abbildung 2 dargestellt. Der größte Teil der logischen Schleife beschäftigt sich mit der Aufgabe, erst ein Restaurant und, nachdem die Auswahl des Restaurants abgeschlossen ist, ein Gericht nach dem Zufallsprinzip auszuwählen. Die Wahl eines Restaurants ist die Hauptaufgabe des Algorithmus, aber die Wahl eines Gerichts ist völlig zufällig und unabhängig von früheren Iterationen.

Bild 2. Logisches Schema zur Prüfung von Hypothesen

Es ist an der Zeit, sich den SDS-Code (Stochastic Diffusion Search) anzusehen und mit dem Herzstück des Algorithmus zu beginnen - dem Agenten, auch Kandidat genannt, der durch die Struktur S_Candidate beschrieben werden kann. Er verfügt über folgende Felder:

1. raddr: Array mit Restaurantadressen. Jedes Array-Element steht für die Adresse eines Restaurants.
2. raddrPrev: Array mit früheren Restaurantadressen. Jedes Array-Element steht für die Adresse eines Restaurants.
3. c: Array mit den Koordinaten (Gerichte). Jedes Element des Arrays stellt die Koordinate eines Gerichts dar.
4. cPrev: Array mit den vorherigen Koordinaten (Gerichte). Jedes Element des Arrays stellt die Koordinate eines Gerichts dar.
5. f: Wert der Fitnessfunktion für den aktuellen Zustand des Agenten.
6. fPrev: Wert der Fitnessfunktion für den vorherigen Zustand des Agenten.

Die Struktur S_Candidate verfügt über die Methode Init, die alle Arrays der Größe „coords“ (die Anzahl der Koordinaten - zu optimierende Parameter) initialisiert und die Anfangswerte von f und fPrev auf -DBL_MAX setzt, da es bei der ersten Iteration nichts und niemanden gibt, mit dem man die Erfahrungen des Kandidaten vergleichen kann.

//——————————————————————————————————————————————————————————————————————————————
struct S_Candidate
{
  void Init (int coords)
  {
    ArrayResize (c,         coords);
    ArrayResize (cPrev,     coords);
    ArrayResize (raddr,     coords);
    ArrayResize (raddrPrev, coords);
    f        = -DBL_MAX;
    fPrev    = -DBL_MAX;
  }
  int    raddr     []; //restaurant address
  int    raddrPrev []; //previous restaurant address
  double c         []; //coordinates (dishes)
  double cPrev     []; //previous coordinates (dishes)
  double f;            //fitness
  double fPrev;        //previous fitness
};
//——————————————————————————————————————————————————————————————————————————————

Deklarieren wir eine SDS-Algorithmusklasse, die Folgendes enthält:

Felder der Klasse:
- cB: Array mit den besten Koordinaten
- fB: Wert der Fitnessfunktion für die besten Koordinaten
- cands: Feld von Kandidaten für die Suche nach optimalen Koordinaten
- rangeMax: Array mit den Höchstwerten für jede Koordinate
- rangeMin: Array mit den Mindestwerten für jede Koordinate
- rangeStep: Array mit Suchschritten für jede Koordinate

Methoden der Klasse:
- Init: Initialisierung der Algorithmusparameter wie Anzahl der Koordinaten, Größe der Population, Anzahl der Restaurants und Wahrscheinlichkeit der Auswahl eines Restaurants
- Moving: Durchführen eines Algorithmusschrittes, Verschieben der Kandidaten zu neuen Koordinaten
- Revision: Durchführung des Revisionsschritts, Aktualisierung der besten Koordinaten und Fitnessfunktionen
- SeInDiSp: Methode zur Berechnung einer neuen Koordinate in einem bestimmten Bereich mit einem bestimmten Schritt
- RNDfromCI: Methode zur Erzeugung einer Zufallszahl in einem bestimmten Intervall

Andere Klassenfelder:
- coords: Anzahl der Koordinaten
- populationSize: Größe der Population
- restNumb: Anzahl der Restaurants
- probabRest: Wahrscheinlichkeit, ein Restaurant zu wählen
- restSpace: Restaurantfläche
- revision: Flag, das die Notwendigkeit einer Revision anzeigt

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SDS
{
  //----------------------------------------------------------------------------
  public: double cB   [];       //best coordinates
  public: double fB;            //FF of the best coordinates
  public: S_Candidate cands []; //candidates

  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    restaurantsNumberP,   //restaurants number
                     const double probabRestP);         //probability restaurant choosing

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

  //----------------------------------------------------------------------------
  private: int    coords;            //coordinates number
  private: int    populationSize;    //population size

  private: int    restNumb;          //restaurants number
  private: double probabRest;        //probability restaurant choosing
  private: double restSpace [];      //restaurants space

  private: bool   revision;

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

Die Initialisierungsmethode des SDS-Algorithmus beginnt mit der Festlegung von Anfangswerten für einige Variablen und Arrays.

Die Eingabeparameter der Methode sind:
- coordinatesNumberP: Anzahl der Koordinaten (Dimension des Suchraums)
- populationSizeP: Größe der Population (Anzahl der Kandidaten)
- restaurantsNumberP: Anzahl der Restaurants
- probabRestP: Wahrscheinlichkeit der Wahl eines Restaurants

Zunächst wird der Zufallszahlengenerator mit der Funktion MathSrand zurückgesetzt, wobei ihm der aktuelle Wert der Mikrosekunden übergeben wird. Die Variablen fB und revision werden dann mit den Anfangswerten -DBL_MAX bzw. „false“ initialisiert.
Anschließend werden die Werte der Eingaben coordinatesNumberP und populationSizeP den Variablen coords und populationSize zugewiesen.
Die Variablen restNumb und probabRest werden mit den Werten restaurantsNumberP und probabRestP initialisiert.
Das restSpace-Array der Größe „coords“ wird mit der Funktion ArrayResize erstellt.
Das Array „cands“ der Größe populationSize wird dann mit der Funktion ArrayResize erstellt. In der Schleife wird jedes Element des Arrays „cands“ durch Aufruf der Methode Init mit dem Parameter „coords“ initialisiert.
Die Arrays rangeMax, rangeMin, rangeStep und cB der Größe „coords“ werden ebenfalls mit der Funktion ArrayResize erstellt.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    restaurantsNumberP,   //restaurants number
                     const double probabRestP)          //probability restaurant choosing
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords         = coordinatesNumberP;
  populationSize = populationSizeP;

  restNumb   = restaurantsNumberP;
  probabRest = probabRestP;
  ArrayResize (restSpace, coords);

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

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

Obwohl die Methode Moving() bei jeder Iteration aufgerufen wird, wird die Hauptlogik der Methode nur einmal ausgeführt, gesteuert durch das Revisionsflag.

Zu Beginn der Funktion wird die Variable „Revision“ überprüft. Wenn sie „false“ ist, werden die Variablen und Arrays initialisiert.
Dann entsteht eine Schleife entlang der Koordinaten von Punkten im Raum.

Innerhalb dieser Schleife wird restSpace[i] berechnet, d. h. die Länge des Intervalls für jede Koordinate, definiert als die Differenz zwischen dem maximalen und dem minimalen Wert des Bereichs geteilt durch restNumb.

Als Nächstes werden die Variablen min und max deklariert, die dazu dienen, den Wertebereich für den Raum eines bestimmten Restaurants zu bestimmen.

Die Variablen n und dish werden dann so initialisiert, dass sie zur Ermittlung von Zufallswerten innerhalb des Bereichs des ausgewählten Restaurants verwendet werden.

Dann wird eine Schleife durch die Population der Größe populationSize ausgeführt, innerhalb derer eine Schleife über die Koordinaten der Raumpunkte ausgeführt wird. Innerhalb dieser Schleife wird mit der Funktion RNDfromCI() eine Zufallszahl n erzeugt, die zur Bestimmung des Index im Array restSpace verwendet wird. Ist der resultierende Wert n größer oder gleich restNumb, so wird ihm restNumb - 1 zugewiesen, um eine gleichmäßige Verteilung der Zufallsvariablen zu gewährleisten. Die Mindest- und Höchstwerte werden dann mit rangeMin, restSpace und n berechnet.

Mit der Funktion RNDfromCI() wird eine Zufallszahl „dish“ erzeugt, die im Bereich von „min“ bis „max“ liegt (Restaurantbereich).

Der Wert von „dish“ wird dann verwendet, um den Wert von c[i] mit Hilfe der Funktion SeInDiSp() zu berechnen, die rangeMin, rangeMax und rangeStep verwendet, um den richtigen Schritt der optimierten Parameter zu gewährleisten.

Durch diesen Algorithmus erhält jeder Punkt im Raum zufällige Werte für jede Koordinate, die dem Raum des Restaurants entsprechen und eine zufällige Auswahl des Gerichts simulieren.

Die Variable „revision“ wird auf „true“ gesetzt, damit beim nächsten Aufruf der Funktion Moving() die Variablen und Arrays nicht initialisiert werden.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Moving ()
{
  if (!revision)
  {
    for (int i = 0; i < coords; i++)
    {
      restSpace [i] = (rangeMax [i] - rangeMin [i]) / restNumb;
    }

    double min = 0.0;
    double max = 0.0;

    int    n   = 0;
    double dish = 0.0;

    for (int i = 0; i < populationSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        n = (int)(RNDfromCI (0, restNumb));
        if (n >= restNumb) n = restNumb - 1;

        cands [i].raddr     [c] = n;
        cands [i].raddrPrev [c] = n;
        min = rangeMin [c] + restSpace [c] * n;
        max = min + restSpace [c];

        dish = RNDfromCI (min, max);

        cands [i].c [c] =  SeInDiSp (dish, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

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

Die Revisionsmethode des SDS-Algorithmus führt die grundlegende Logik für die Auswahl von Restaurants und Restaurantgerichten aus. Dies ist nicht typisch für die zuvor besprochenen Algorithmen, bei denen die Hauptlogik für das Bewegen von Agenten in der Methode Bewegen angesiedelt war, obwohl die Reihenfolge des Aufrufs der Algorithmusmethoden dieselbe bleibt und dem im ersten Artikel der Serie gewählten Konzept entspricht. Der Algorithmus besteht aus den folgenden Schritten:

1. Aktualisierung des besten gefundenen Werts der Fitnessfunktion fB und des entsprechenden Koordinatensatzes cB. Für jeden Kandidaten i in der Grundgesamtheit wird ein Vergleich durchgeführt. Ist der Wert von f (die Funktionsschätzung) größer als der aktuelle globale Wert von fB, wird fB aktualisiert und von i Kandidat in den besten globalen Koordinatensatz cB kopiert.

2. Aktualisierung früherer Bewertungen und Restaurant-Sets für jeden Kandidaten. Für jeden i-Kandidaten in der Grundgesamtheit wird, wenn der Wert von f größer ist als der vorherige Wert von fPrev, fPrev aktualisiert, und die Sätze der Restaurants c und raddr von i-Kandidaten werden auf die entsprechenden vorherigen Werte von cPrev und raddrPrev kopiert.

3. Auswahl einer neuen Reihe von Restaurants für jeden Kandidaten. Für jeden i-Kandidaten in der Grundgesamtheit und jede c-Koordinate wird eine Zufallszahl n im Bereich von 0 bis populationSize gewählt. Wenn der Wert von fPrev für Kandidat n größer ist als der Wert von fPrev für Kandidat i, dann wird die Menge der Restaurants raddr für Kandidat i mit dem Wert von raddrPrev für Kandidat n aktualisiert. Andernfalls wird eine Zufallszahl rnd im Bereich von 0,0 bis 1,0 erzeugt. Wenn rnd kleiner als die Wahrscheinlichkeit probabRest ist, wird die Zufallszahl n im Bereich von 0 bis restNumb ausgewählt und die Menge der Restaurants raddr für i Kandidaten mit dem Wert von n aktualisiert. Andernfalls bleibt die raddr-Gruppe der Restaurants für den Kandidaten i unverändert.

4. Generierung eines neuen Koordinatensatzes für jeden Kandidaten. Die Minimal- und Maximalwerte „min“ und „max“ werden für jeden i-Kandidaten in der Grundgesamtheit und jede c-Koordinate auf der Grundlage der Werte „rangeMin“ und „restSpace“ für die entsprechende Koordinate bestimmt. Anschließend wird mit der Funktion SeInDiSp eine Zufallszahl im Bereich von „min“ bis „max“ generiert, und der sich daraus ergebende Wert wird der entsprechenden c-Koordinate in der c-Menge des i-Kandidaten zugewiesen.

Die Revisionsmethode des SDS-Algorithmus iteriert also durch die Kandidatenpopulation, aktualisiert den gefundenen besten Wert und die Menge der Restaurants, wählt neue Mengen von Restaurants aus und erzeugt neue Koordinatensätze für jeden Kandidaten:

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Revision ()
{
  //----------------------------------------------------------------------------
  for (int i = 0; i < populationSize; i++)
  {
    if (cands [i].f > fB)
    {
      fB = cands [i].f;
      ArrayCopy (cB, cands [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  double min = 0.0;
  double max = 0.0;
  double rnd = 0.0;
  int    n   = 0;

  for (int i = 0; i < populationSize; i++)
  {
    if (cands [i].f > cands [i].fPrev)
    {
      cands [i].fPrev = cands [i].f;
      ArrayCopy (cands [i].cPrev, cands [i].c, 0, 0, WHOLE_ARRAY);
      ArrayCopy (cands [i].raddrPrev, cands [i].raddr, 0, 0, WHOLE_ARRAY);
    }
  }

  for (int i = 0; i < populationSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      n = (int)(RNDfromCI (0, populationSize));
      if (n >= populationSize) n = populationSize - 1;

      if (cands [n].fPrev > cands [i].fPrev)
      {
        cands [i].raddr [c] = cands [n].raddrPrev [c];
      }
      else
      {
        rnd = RNDfromCI (0.0, 1.0);

        if (rnd < probabRest)
        {
          n = (int)(RNDfromCI (0, restNumb));
          if (n >= restNumb) n = restNumb - 1;
          cands [i].raddr [c] = n;
        }
        else
        {
          cands [i].raddr [c] = cands [i].raddrPrev [c];
        }
      }

      min = rangeMin [c] + restSpace [c] * cands [i].raddr [c];
      max = min + restSpace [c];

      cands [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Testergebnisse

Ausdruck der Funktionsweise des stochastischen Diffusionssuchalgorithmus auf dem Prüfstand:

C_AO_SDS:100;1000;0.1
=============================
5 Rastrigin's; Func runs 10000 result: 80.64253803557851
Score: 0.99921
25 Rastrigin's; Func runs 10000 result: 79.00996143538204
Score: 0.97898
500 Rastrigin's; Func runs 10000 result: 54.31544686388126
Score: 0.67300
=============================
5 Forest's; Func runs 10000 result: 1.677891584229713
Score: 0.94910
25 Forest's; Func runs 10000 result: 1.4089003503272384
Score: 0.79694
500 Forest's; Func runs 10000 result: 0.2437939668372883
Score: 0.13790
=============================
5 Megacity's; Func runs 10000 result: 8.6
Score: 0.71667
25 Megacity's; Func runs 10000 result: 6.448
Score: 0.53733
500 Megacity's; Func runs 10000 result: 0.9551999999999999
Score: 0.07960
=============================
All score: 5.86873

Wenn man sich den Ausdruck der Ergebnisse des Algorithmus ansieht, fällt einem sofort auf, dass die Ergebnisse im Vergleich zu anderen Algorithmen unglaublich hoch sind. Ein detaillierter Vergleich ist in der nachstehenden Tabelle aufgeführt.

Beachten Sie das atypische Verhalten des Algorithmus bei der Visualisierung der Bewegung von Agenten. Die Anzahl der Agenten ist gleichmäßig und proportional zur Höhe des Fitnessfunktionshügels verteilt, was eine hohe Qualität der Clusterbildung an den lokalen Extrema zeigt. Es scheint, dass der Algorithmus keinen einzigen Hügel übersehen wird. Wir können auch sehen, dass die Konvergenz des Algorithmus bei jeder Iteration fast stufenlos zunimmt, was auf eine geringe Tendenz hinweist, in lokalen Extrema hängen zu bleiben. Selbst bei der komplexesten Waldfunktion mit einem scharfen globalen Extremum ist keine schrittweise Konvergenz zu beobachten.

  SDS zur Rastrigin-Testfunktion

  SDB über die Funktion Forest-Test

  SDS über die Megacity-Testfunktion

Ich hatte nicht erwartet, dass ein so einfacher Algorithmus, der auf einem reinen Random Walk basiert, erstaunliche Ergebnisse liefern würde. Der SDS übertraf alle zuvor betrachteten Algorithmen erheblich (um fast 13 %) und zeigte in vielen Tests die besten Ergebnisse (4 erste Plätze von 9 möglichen). Die einzige Disziplin ist die multivariable Rastrigin-Funktion, bei der der Spitzenreiter (der EM-Algorithmus) alle anderen weit hinter sich gelassen hat.

Selbst bei der extrem komplexen diskreten Funktion Megacity schneidet der SDS-Algorithmus hervorragend ab, ohne irgendwo stecken zu bleiben. Der einzige Algorithmus, der SDS in Tests mit 1000 Variablen auf Forest und Megacity schlägt, ist der Algorithmus Growing Trees (SSG). 

#	AO	Beschreibung	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (diskret)			Megacity final	Final result
			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	SDS	stochastische Diffusionssuche	0.99737	1.00000	0.63507	2.63244	0.96893	1.00000	0.95092	2.91985	1.00000	1.00000	0.72149	2.72149	100.000
2	SSG	Setzen, Säen und Wachsen	1.00000	0.95313	0.55665	2.50978	0.72740	0.69680	1.00000	2.42421	0.69612	0.65726	1.00000	2.35338	87.489
3	HS	Harmoniesuche	0.99676	0.90817	0.48178	2.38670	1.00000	0.72930	0.44806	2.17736	0.91159	0.76446	0.41537	2.09142	79.474
4	ACOm	Ameisen-Kolonie-Optimierung M	0.34611	0.17142	0.17044	0.68797	0.86888	0.73719	0.77362	2.37968	0.91159	0.67983	0.05606	1.64749	54.863
5	IWO	Optimierung mit invasiven Unkräutern	0.95828	0.63939	0.29807	1.89575	0.70773	0.34168	0.31773	1.36714	0.72927	0.32158	0.33289	1.38375	53.994
6	MEC	mind evolutionary computation	0.99270	0.48648	0.22800	1.70718	0.60762	0.29973	0.25459	1.16194	0.85083	0.31594	0.26170	1.42847	49.567
7	COAm	Kuckuck-Optimierungsalgorithmus M	0.92400	0.44601	0.26004	1.63006	0.58378	0.25090	0.16526	0.99994	0.66298	0.25246	0.17083	1.08627	42.193
8	FAm	Firefly-Algorithmus M	0.59825	0.32387	0.17135	1.09348	0.51073	0.31182	0.49790	1.32045	0.31491	0.21438	0.35258	0.88188	36.860
9	ABC	Künstliches Bienenvolk (Artificial Bee Colony, ABC)	0.78170	0.31182	0.20822	1.30174	0.53837	0.15816	0.13344	0.82998	0.51381	0.20311	0.13926	0.85617	32.954
10	BA	Fledermaus-Algorithmus	0.40526	0.60773	0.84451	1.85750	0.20841	0.12884	0.25989	0.59714	0.27073	0.07616	0.17371	0.52060	32.794
11	GSA	Algorithmus für die Schwerkraftsuche	0.70167	0.43098	0.00000	1.13265	0.31660	0.26845	0.33204	0.91710	0.54144	0.26797	0.00000	0.80941	31.322
12	BFO	Optimierung der bakteriellen Futtersuche	0.67203	0.29511	0.11813	1.08528	0.39702	0.19626	0.20652	0.79980	0.47514	0.25388	0.18932	0.91834	30.615
13	EM	elektromagnetismusähnlicher Algorithmus	0.12235	0.44109	1.00000	1.56344	0.00000	0.02578	0.34880	0.37458	0.00000	0.00000	0.10924	0.10924	21.024
14	SFL	schlurfender Froschsprung	0.40072	0.22627	0.26548	0.89247	0.20153	0.03057	0.02652	0.25862	0.24862	0.04231	0.06639	0.35732	14.189
15	MA	Affen-Algorithmus	0.33192	0.31883	0.14644	0.79719	0.10012	0.05817	0.08932	0.24762	0.19889	0.03243	0.10720	0.33853	12.603
16	FSS	Fischschulsuche	0.46812	0.24149	0.11302	0.82264	0.12840	0.03696	0.06516	0.23052	0.15471	0.03666	0.08283	0.27420	11.893
17	PSO	Partikelschwarmoptimierung	0.20449	0.07816	0.07160	0.35425	0.18895	0.07730	0.21738	0.48363	0.21547	0.04513	0.01957	0.28016	9.238
18	RND	zufällig	0.16826	0.09287	0.08019	0.34132	0.13496	0.03546	0.04715	0.21757	0.15471	0.02962	0.04922	0.23354	5.108
19	GWO	Grauer-Wolf-Optimierung	0.00000	0.00000	0.02256	0.02256	0.06570	0.00000	0.00000	0.06570	0.29834	0.05640	0.02557	0.38031	1.000

Zusammenfassung

Der stochastische Suchalgorithmus (SDS) ist eine effiziente Optimierungsmethode, die Zufallsstichproben verwendet, um das globale Optimum einer gegebenen Funktion zu finden.
In dem Artikel wurden die Grundprinzipien der Funktionsweise des SDS-Algorithmus vorgestellt. Es basiert auf der Idee der zufälligen Auswahl von Punkten in einem partitionierten Suchraum. Die Testergebnisse zeigten, dass SDS in der Lage ist, globale Optima in komplexen Funktionen mit einer großen Anzahl lokaler Extrema zu finden, was eine ausgezeichnete Konvergenz zeigt. Einer der Vorteile des SDS-Algorithmus ist seine Einfachheit und leichte Implementierbarkeit. Es ist nicht sehr rechenintensiv und kann auf verschiedene Arten von Optimierungsproblemen angewendet werden.

Zur besseren Veranschaulichung der Vor- und Nachteile der einzelnen Algorithmen kann die obige Tabelle anhand der Farbskala in Abbildung 3 dargestellt werden.

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

Das Histogramm der Algorithmus-Testergebnisse finden Sie unten (auf einer Skala von 0 bis 100, je mehr, desto besser, im Archiv finden Sie ein Skript zur Berechnung der Bewertungstabelle nach der in diesem Artikel beschriebenen Methode):

Abb. 4. Histogramm der Endergebnisse der Testalgorithmen

Vor- und Nachteile des Stochastic Diffusion Search (SDS)-Algorithmus:

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

Nachteile
1. Keine gefunden.

Jeder Artikel verfügt über ein Archiv, das aktualisierte und aktuelle Versionen der Algorithmuscodes für alle früheren Artikel enthält. Es sei jedoch darauf hingewiesen, dass ich nicht für die absolute Genauigkeit bei der Beschreibung der kanonischen Algorithmen verantwortlich bin. Ich füge oft meine eigenen Ideen und Verbesserungen hinzu, die auf meinen Erfahrungen und persönlichen Meinungen beruhen. Die in den Artikeln dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Versuche.