Algorithmen zur Optimierung mit Populationen: Der Algorithmus Charged System Search (CSS)

Inhalt

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

1. Einführung

In der Physik hat der Raum, der eine elektrische Ladung umgibt, eine Eigenschaft, die als elektrisches Feld bezeichnet wird. Dieses Feld übt eine Kraft auf andere elektrisch geladene Objekte aus. Das elektrische Feld, das eine Punktladung umgibt, wird durch das Coulombsche Gesetz bestimmt. Coulomb bestätigte, dass die elektrische Kraft zwischen zwei kleinen geladenen Kugeln umgekehrt proportional zum Quadrat des Abstands zwischen den Teilchen entlang der Verbindungslinie und proportional zum Produkt der Ladungen der beiden Teilchen ist. Außerdem kann die Größe des elektrischen Feldes an einem Punkt innerhalb einer geladenen Kugel mit Hilfe des Gaußschen Gesetzes ermittelt werden, das besagt, dass es proportional zum Abstand zwischen den Teilchen ist. Auf der Grundlage dieser Prinzipien definiert CSS eine Reihe von möglichen Lösungen, die als geladene Teilchen bezeichnet werden. Jedes Teilchen wird als geladene Kugel betrachtet (im Gegensatz zum elektromagnetischen Algorithmus - EM, wo das Teilchen ein eindimensionaler Punkt ist) und kann eine elektrische Wirkung auf andere Agenzien (geladene Teilchen) haben.

Andererseits erklärt das zweite Newtonsche Gesetz, dass die Beschleunigung eines Objekts direkt proportional zur Nettokraft ist, die auf dieses Objekt wirkt. Die daraus resultierende elektrische Kraft, die auf das Teilchen wirkt, führt zu dessen Beschleunigung. Nach der Newtonschen Mechanik ist die Position eines Teilchens, das als Punktmasse von infinitesimaler Größe betrachtet wird, zu jedem Zeitpunkt vollständig bekannt, wenn seine Position, Geschwindigkeit und Beschleunigung im Raum zu einem früheren Zeitpunkt bekannt sind. CSS verwendet die Bewegungsgesetze der Newtonschen Mechanik, um die Position von Teilchen zu bestimmen. Die Anwendung dieser Gesetze sollte theoretisch ein ausgewogenes Verhältnis zwischen Erkundung und Nutzung des Algorithmus gewährleisten.

Charged System Search (CSS, Suche geladener Systeme) wurde erstmals von A. Kaveh und S. Talatahari im Jahr 2010 vorgeschlagen.

Die Optimierung ist ein wichtiger und integraler Bestandteil der Lösung von Problemen der mathematischen Modellierung und des maschinellen Lernens. Metaheuristische Algorithmen sind eine effektive und beliebte Klasse von Optimierungsmethoden. Metaheuristiken können als Algorithmus verstanden werden, der stochastisch nach möglichen Lösungen für ein Problem sucht, die nahe am Optimum liegen, bis eine bestimmte Bedingung erfüllt ist oder eine bestimmte Anzahl von Iterationen erreicht ist.

In der wissenschaftlichen Literatur wird davon ausgegangen, dass Metaheuristiken grundlegende heuristische Methoden zu übergeordneten algorithmischen Schemata kombinieren, die eine effizientere Erkundung von Suchräumen und Entscheidungsfindung ermöglichen. Dies erfordert in der Regel weniger Arbeit als die Entwicklung neuer spezialisierter Heuristiken. Die Herausforderung besteht darin, allgemeine metaheuristische Verfahren zur Lösung schwieriger Optimierungsprobleme anzupassen. Darüber hinaus kann eine effektive Implementierung von Metaheuristiken sicherstellen, dass eine Lösung, die dem Optimum nahe kommt, in einer akzeptablen Zeit gefunden wird. Verschiedene Ansätze zum Verständnis von Metaheuristiken ermöglichen es, einige grundlegende Eigenschaften zu formulieren, die sie charakterisieren. In den letzten Jahren hat der Einsatz metaheuristischer Methoden zugenommen, und es wurden Anstrengungen unternommen, um die Leistungsfähigkeit der Algorithmen zu erhöhen und die Optimierungszeit zu verringern.

2. Der Algorithmus

Der CSS-Algorithmus arbeitet mit geladenen Teilchen in Form einer Kugel. Die Mindestgröße der Kugel wird durch einen externen Parameter bestimmt (sie ist ein Teil des maximal möglichen euklidischen Abstands entlang aller Koordinaten des Suchraums); wenn sich die Teilchen in einem Abstand nähern, der kleiner ist als der Radius der Kugel, wirken abstoßende Kräfte auf die Teilchen. Gleichzeitig wird die Richtung der Kräfte zwischen den Teilchen auch durch ihre unterschiedlichen Ladungen beeinflusst. Der Algorithmus berücksichtigt die Koordinatenwerte der vorherigen Iteration und simuliert so die Partikelgeschwindigkeit. Die Beschleunigung (eine Komponente der Teilchenbewegung) wird durch die Ladungen und ihren gegenseitigen Abstand beeinflusst.

In Anbetracht der obigen Ausführungen wollen wir die Pseudocode-Schritte des Algorithmus aufschreiben:

1. Initialisiere die Partikel mit einer zufälligen Anfangsposition im Suchraum und setze auch eine zufällige Position im Raum für die vorherige Iteration (wir gehen davon aus, dass es eine vorherige Iteration gab).

2. Berechne den Wert der Fitnessfunktion.

3. Berechne die nächste Position der Teilchen anhand der Gleichungen.

4. Bestimme die besten und schlechtesten Werte der Fitnessfunktion unter allen Partikeln.

5. Wiederhole die Schritte ab Schritt 2, bis die Stoppbedingung erfüllt ist.

Schauen wir uns die Gleichungen zur Berechnung der gegenseitigen Bewegung von Teilchen an. Das Hauptmerkmal eines geladenen Teilchens ist seine Ladung:

q = (φp - φw) / (φb - φw)

wobei:

• q - aktuelle Teilchenladung
• φp - Wert der Partikelfitnessfunktion
• φb - bester Wert der Fitnessfunktion unter allen Partikeln
• φw - schlechtester Wert der Fitnessfunktion unter allen Partikeln

Um den Abstand zwischen den Teilchen zu bestimmen, wird die Gleichung verwendet:

r(i,j) = (|Xi - Xj|) / (|(Xi - Xj) * 0.5 - Xb|)

wobei:

• |..| - Euklidischer Abstand
• r(i,j) - Abstand zwischen den Teilchen i und j
• Xi und Xj - entsprechende Koordinaten der Teilchen i und j
• Xb - entsprechende Koordinate der besten über alle Iterationen gefundenen Position.

Hier hatten die Autoren offenbar die Idee, die Position der Partikel relativ zu den besten globalen Koordinaten zu berücksichtigen. Das mag eine gute Idee gewesen sein, aber meine Experimente ergaben, dass die beste Lösung für diesen Algorithmus darin besteht, nur den Zähler der Gleichung zu berechnen.

Wie beim elektromagnetischen EM-Algorithmus können die Wechselwirkungskräfte entweder anziehend oder abstoßend sein. Bezeichnen wir das Vorzeichen der Richtung der Variablen c. Verwenden Sie den folgenden Bedingungsausdruck, um die Richtung der Kräfte zu berücksichtigen:

c = -1 wenn φi < φj, sonst c = 1

wobei:

• c - Vorzeichen der Richtung der Wechselwirkungskräfte
• φi und φj - Werte der Fitnessfunktionen der Partikel i und j

Das Vorzeichen der Kraftrichtung kann so interpretiert werden, dass ein Partikel mit einem kleineren Wert der Fitnessfunktion abstößt, und ein Partikel mit einem größeren Wert anzieht.

Da wir uns darauf geeinigt haben, dass das Teilchen im Gegensatz zum EM-Algorithmus eine Kugel ist, deren Radius größer als 0 ist (ein externer Parameter des Algorithmus), ist die Kraft auf das Teilchen kollinear zur entsprechenden Koordinate (in unserem Algorithmus ist die Gesamtkraft auf das Teilchen ein Satz von Vektoren) und kann als Gleichung dargestellt werden:

F = qi * Q * c * (Xj - Xi)

wobei:

• F - Aktionskraft, die auf das Teilchen wirkt
• qi - Partikel wird die Aktionskraft berechnet für
• Q - Komponente, die die relative Position der beiden betrachteten Teilchen in Abhängigkeit von der Penetration ihrer Kugeln ineinander berücksichtigt, die Gleichung für Q:

Q = ((qj * r(i,j) * b1) / a^3) + (qj * b2) / r(i,j)^2

wobei:

• qj - Ladung des Teilchens, das die betrachtete Größe beeinflusst
• b1 und b2 zur „Aktivierung/Deaktivierung“ des entsprechenden Ausdrucks. b1 = 0 und b2 = 1 für r >= Partikelradius. Andernfalls ist b1 = 1 und b2 = 0.

Schließlich können wir die neue Koordinate der Partikelbewegung anhand der Gleichung berechnen:

Xn = X + λ1 * U * V + λ2 * U * coordinatesNumber * (F / qi)

wobei:

• Xn - neue Koordinate
• λ1 - Gewichtskoeffizient (externer Parameter) bestimmt den Grad des Einflusses des zweiten Terms - Geschwindigkeit
• λ2 - Gewichtskoeffizient (externer Parameter) bestimmt den Grad des Einflusses des dritten Terms - Beschleunigung
• U - Zufallszahl im Bereich [0;1]
• V - Differenz zwischen der Koordinate bei der aktuellen Iteration und bei der vorherigen Iteration
• coordinatesNumber - Anzahl der Koordinaten. Dieses „Verhältnis“ ist in der ursprünglichen Gleichung nicht enthalten. Ich habe sie eingeführt, da mit zunehmender Dimension des Suchraums das λ2-Verhältnis erhöht werden muss (daher wurde sie eingeführt, um den Effekt des „Einfrierens“ von Teilchen zu vermeiden)

Die relativen Werte von λ1 und λ2 bestimmen das Gleichgewicht zwischen Diversifizierung und Intensivierung der Suche. Durch die Erhöhung der Werte des Parameters λ1 wird der Einfluss der vorherigen Position des Partikels verstärkt, wodurch die Forschungseigenschaften des Algorithmus verbessert werden. Große Werte von λ2 führen zu einem starken Einfluss der Anziehungskräfte und können zu einer vorzeitigen Konvergenz des Algorithmus führen. Im Gegenteil, kleine Werte verlangsamen die Konvergenzrate des Algorithmus und ermöglichen eine breitere Erkundung des Suchbereichs.

Beginnen wir mit der Analyse des CSS-Algorithmus-Codes. Der Suchagent des Algorithmus ist ein Partikel, der bequem durch die Struktur S_Particle dargestellt werden kann.

Die Partikelstruktur umfasst die folgenden Felder:

• -c: Array von Partikelkoordinaten. Dieses Array enthält die aktuellen Koordinaten des Partikels im Raum.
• -cPrev: Array der vorherigen Partikelkoordinaten. Dieses Array enthält die vorherigen Koordinaten des Partikels im Raum.
• -cNew: Array der neuen Partikelkoordinaten. Dieses Array enthält die neuen Partikelkoordinaten, die bei der nächsten Iteration des Algorithmus verwendet werden sollen.
• -q: Teilchenladung. Dieser Wert stellt die dem Teilchen zugewiesene Ladung dar. Die Ladung kann nur positive Werte ungleich 0 annehmen.
• -f: Wert der Partikelfitnessfunktion.

Das Vorhandensein einer Reihe neuer Koordinaten in der Struktur des Teilchens und seiner Ladung ermöglichte es, den Algorithmus aufgrund seiner Eigenschaften zu vereinfachen, obwohl diese Größen in Form von Variablen für die allgemeine Verwendung durch alle Teilchen beibehalten werden konnten (auf den ersten Blick scheint dies logisch). 

//——————————————————————————————————————————————————————————————————————————————
struct S_Particle
{
  double c     [];  //coordinates
  double cPrev [];  //coordinates
  double cNew  [];  //coordinates
  double q;         //particle charge
  double f;         //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Deklarieren wir die Klasse C_AO_CSS, die Folgendes enthält:

Eigenschaften der Klasse:

• - p: Partikelanordnung
• - rangeMax: Array mit maximalen Suchbereichswerten für jede Koordinate
• - rangeMin: Array mit minimalen Suchbereichswerten für jede Koordinate
• - rangeStep: Array mit Suchschrittgrößen für jede Koordinate
• - cB: Array mit den besten gefundenen Koordinaten
• - fB: Wert der Fitnessfunktion für die besten Koordinaten
• - fW: Wert der Fitnessfunktion für die schlechtesten Koordinaten

Methoden der Klasse:

• - Init: initialisiert die Algorithmusparameter (Anzahl der Koordinaten, Anzahl der Partikel, Radiusgröße, Geschwindigkeits- und Beschleunigungsverhältnisse)
• - Bewegen: führt eine Partikelbewegung durch
• - Revision: führt eine Aktualisierung der besten Koordinaten durch

Private Klasseneigenschaften:

• - coordinatesNumber: Anzahl der Koordinaten
• - particlesNumber: Anzahl der Partikel
• - Radius: Größe des Radius
• - speedCo: Geschwindigkeitsverhältnis
• - accelCo: Beschleunigungsverhältnis
• - F: Kraftvektor
• - Revision: Flag, das die Notwendigkeit einer Revision anzeigt

Private Methoden der Klasse:

• - SeInDiSp: Berechnet einen neuen Koordinatenwert in einem bestimmten Bereich mit einem bestimmten Schritt
• - RNDfromCI: erzeugt eine Zufallszahl in einem bestimmten Intervall

//——————————————————————————————————————————————————————————————————————————————
class C_AO_CSS
{
  //----------------------------------------------------------------------------
  public: S_Particle p     []; //particles
  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: double fW;           //FF of the worst coordinates

  public: void Init (const int    coordinatesNumberP, //coordinates number
                     const int    particlesNumberP,   //particles number
                     const double radiusSizeP,        //radius size
                     const double speedCoP,           //speed coefficient
                     const double accelCoP);          //acceleration coefficient

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

  //----------------------------------------------------------------------------
  private: int    coordinatesNumber; //coordinates number
  private: int    particlesNumber;   //particles number
  private: double radius;            //radius size
  private: double speedCo;           //speed coefficient
  private: double accelCo;           //acceleration coefficient
  private: double F       [];        //force vector
  private: bool   revision;

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

Die Methode C_AO_CSS initialisiert die Parameter des Klassenobjekts. Als Argumente werden die Anzahl der Koordinaten, die Anzahl der Teilchen, die Größe des Radius, die Geschwindigkeit und die Beschleunigungsverhältnisse angegeben.

Innerhalb der Methode wird der Zufallszahlengenerator zurückgesetzt und die Anfangswerte für die Variablen fB und revision werden festgelegt. Die Argumentwerte werden dann den entsprechenden Objektvariablen zugewiesen.
Anschließend ändern sich die Größen der Felder rangeMax, rangeMin, rangeStep, F, p und cB entsprechend der Anzahl der Koordinaten und Partikel.
Dann werden die Arrays für jedes Teilchen in einer Schleife in der Größe verändert und der Anfangswert der Variablen f für jedes Teilchen festgelegt.
Am Ende der Methode ändert sich die Größe des cB-Arrays entsprechend der Anzahl der Koordinaten.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_CSS::Init (const int    coordinatesNumberP, //coordinates number
                     const int    particlesNumberP,   //particles number
                     const double radiusSizeP,        //radius size
                     const double speedCoP,           //speed coefficient
                     const double accelCoP)           //acceleration coefficient
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber = coordinatesNumberP;
  particlesNumber   = particlesNumberP;
  radius            = radiusSizeP;
  speedCo           = speedCoP;
  accelCo           = accelCoP;

  ArrayResize (rangeMax,  coordinatesNumber);
  ArrayResize (rangeMin,  coordinatesNumber);
  ArrayResize (rangeStep, coordinatesNumber);
  ArrayResize (F,         coordinatesNumber);

  ArrayResize (p,  particlesNumber);

  for (int i = 0; i < particlesNumber; i++)
  {
    ArrayResize (p [i].c,     coordinatesNumber);
    ArrayResize (p [i].cPrev, coordinatesNumber);
    ArrayResize (p [i].cNew,  coordinatesNumber);
    p [i].f  = -DBL_MAX;
  }

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

Die Hauptlogik für die Bewegung von Partikeln (Suchagenten) ist in der Methode Moving() implementiert.

Bei der allerersten Iteration werden die Anfangswerte der Partikelkoordinaten mit einer Zufallszahl im Bereich von rangeMin bis rangeMax initialisiert und der Fitnesswert der Partikel mit dem Wert „-DBL_MAX“ gleichgesetzt.

Der externe Parameter des RadiusSize_P-Algorithmus bestimmt die Partikelgröße in Teilen des maximal möglichen euklidischen Abstands für alle Koordinaten, der die Wurzel aus der Summe der quadrierten Differenzen zwischen den maximal und minimal zulässigen Werten für jede Koordinate ist.
Am Ende des Codes wird die Variable „revision“ auf „true“ gesetzt.

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

  for (int obj = 0; obj < particlesNumber; obj++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      p [obj].c     [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      p [obj].cPrev [c] = RNDfromCI (rangeMin [c], rangeMax [c]);

      p [obj].c     [c] = SeInDiSp (p [obj].c     [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      p [obj].cPrev [c] = SeInDiSp (p [obj].cPrev [c], rangeMin [c], rangeMax [c], rangeStep [c]);

      p [obj].f         = -DBL_MAX;
    }
  }

  double r = 0.0;
  double t = 0.0;

  for (int c = 0; c < coordinatesNumber; c++)
  {
    t = rangeMax [c] - rangeMin [c];
    r += t * t;
  }

  radius *= sqrt (r);
  revision = true;
}

Der verbleibende Teil des Codes der Methode Moving() wird in der zweiten und den folgenden Iterationen ausgeführt und ist für die Bewegung der Partikel im Suchraum verantwortlich.

Die Differenz zwischen den fB- und fW-Werten der Fitnessfunktion wird zuerst berechnet (für die besten Koordinaten, die über alle Iterationen gefunden wurden, und die schlechtesten Koordinaten unter den Partikeln in der aktuellen Iteration) und in der Variablen „Differenz“ gespeichert. Ist die „Differenz“ 0,0, so wird ihr der Wert 1,0 zugewiesen.

Es folgt die Schleife, in der für jedes Teilchen ein neuer Wert berechnet wird. Für jedes Teilchen i wird ein neuer Wert der Ladung q berechnet.

Als Nächstes werden die Variablen summ1, summ2, q, e, c, b1, b2, X, Q, U, V, t1 und t2 deklariert und für die Verwendung in den oben beschriebenen Gleichungen initialisiert.

In der Schleife berechnen wir für jedes Teilchen die Gesamtkraft F, die auf alle anderen Teilchen der Population wirkt. Für jedes i-Partikel wird eine Schleife durchlaufen, in der die Summe von summ1 und summ2 berechnet wird. Dann wird der Abstand r zwischen den Partikeln i und j berechnet. Ist r gleich 0,0, so wird ihm der Wert 0,01 zugewiesen, um eine Division durch 0 zu vermeiden. Die Werte von b1 und b2 werden dann in Abhängigkeit vom Wert von r und „Radius“ berechnet. Der Wert der Richtung der Kraft c wird dann in Abhängigkeit von den Fitnesswerten der beiden betreffenden Partikel berechnet. Als Nächstes berechnen wir den Q-Wert. Dann wird der Kraftwert F[k] für jede k-Koordinate berechnet.

Mit den Werten des Vektors der auf das Teilchen wirkenden Kräfte können wir die Werte der neuen Koordinaten für seine Bewegung berechnen. Dann erfolgt ein Zyklus, in dem die Werte der vorherigen Koordinaten und die aktuellen Koordinaten des Partikels i aktualisiert werden.

Im Code bleiben Teile der ursprünglichen Gleichungen als auskommentierte Elemente erhalten, um zu zeigen, wie die CSS-Autoren vorgegangen sind.

double difference = fB - fW;
if (difference == 0.0) difference = 1.0;

for (int i = 0; i < particlesNumber; i++)
{
  p [i].q = ((p [i].f - fW) / difference) + 0.1;
}

double summ1 = 0.0;
double summ2 = 0.0;
double q     = 0.1;
double e     = 0.001;
double c     = 0.0;
double b1    = 0.0;
double b2    = 0.0;
double X     = 0.0;
double Q     = 0.0;
double U     = 0.0;
double V     = 0.0;
double t1    = 0.0;
double t2    = 0.0;

for (int i = 0; i < particlesNumber && !IsStopped (); i++)
{
  ArrayInitialize (F, 0.0);

for (int j = 0; j < particlesNumber && !IsStopped (); j++)
{
  if (i == j) continue;

  summ1 = 0.0;
  summ2 = 0.0;

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    t1 = p [i].c [k] - p [j].c [k];
    summ1 += t1 * t1;

    //t2 = t1 * 0.5 - cB [k];
    //summ2 += t2 * t2;
  }

  //r = sqrt (summ1) / (sqrt (summ2) + e);
  r = sqrt (summ1);
        
  if (r == 0.0) r = 0.01;

  if (r >= radius)
  {
    b1 = 0.0;
    b2 = 1.0;
  }
  else
  {
    b1 = 1.0;
    b2 = 0.0;
  }

  c = p [i].f < p [j].f ? -1.0 : 1.0;

  q = p [j].q;

  Q = ((q * r * b1 / (radius * radius * radius)) + (q * b2 / (r * r))) * c;

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    F [k] += /*p [i].q */ Q * (p [j].c [k] - p [i].c [k]);
  }
}

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    V = p [i].c [k] - p [i].cPrev [k];
    U = RNDfromCI (0.0, 1.0);

    X = p [i].c [k] + speedCo * U * V + accelCo * U * coordinatesNumber * (F [k] / p [i].q);
        
    p [i].cNew [k] = SeInDiSp (X, rangeMin [k], rangeMax [k], rangeStep [k]);
  }
}

for (int i = 0; i < particlesNumber && !IsStopped (); i++)
{
  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    p [i].cPrev [k] = p [i].c [k];
    p [i].c [k] = p [i].cNew [k];
  }
}

Schließlich kommt die Methode Revision().
Zu Beginn der Methode wird der Variablen fW der Maximalwert vom Typ double (DBL_MAX) zugewiesen, sodass wir anschließend das schlechteste Partikel mit dem minimalen Wert der Fitnessfunktion bestimmen können.
Dann findet ein Zyklus durch alle Systemteilchen statt. Die folgenden Aktionen werden für jedes Partikel durchgeführt:
- Wenn der f-Wert des aktuellen Partikels größer ist als fB (die beste Fitnessfunktion aller Partikel), dann wird der fB-Wert mit dem f-Wert des aktuellen Partikels aktualisiert, und das cB-Array (beste Position) wird von der Position des aktuellen Partikels kopiert.
- Wenn der f-Wert des aktuellen Partikels kleiner ist als der fW-Wert (die kleinste Fitnessfunktion aller Partikel), dann wird der fW-Wert mit dem f-Wert des aktuellen Partikels aktualisiert.

Dieser Code findet also die beste und die schlechteste Fitnessfunktion unter allen Partikeln und aktualisiert die entsprechenden Werte.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_CSS::Revision ()
{
  fW  = DBL_MAX;

  for (int i = 0; i < particlesNumber; i++)
  {
    if (p [i].f > fB)
    {
      fB = p [i].f;
      ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY);
    }

    if (p [i].f < fW)
    {
      fW = p [i].f;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Testergebnisse

Ausdruck des Algorithmus für die Suche nach dem geladenen System auf dem Prüfstand:

C_AO_CSS:50;0.1;0.7;0.01
=============================
5 Rastrigin's; Func runs 10000 result: 70.43726076935499
Score: 0.87276
25 Rastrigin's; Func runs 10000 result: 68.88569793414477
Score: 0.85353
500 Rastrigin's; Func runs 10000 result: 66.01225385184436
Score: 0.81793
=============================
5 Forest's; Func runs 10000 result: 0.4891262437640296
Score: 0.27667
25 Forest's; Func runs 10000 result: 0.1494549763925046
Score: 0.08454
500 Forest's; Func runs 10000 result: 0.07829232143185726
Score: 0.04429
=============================
5 Megacity's; Func runs 10000 result: 2.04
Score: 0.17000
25 Megacity's; Func runs 10000 result: 0.744
Score: 0.06200
500 Megacity's; Func runs 10000 result: 0.26880000000000004
Score: 0.02240
=============================
All score: 3.20412

Der Ausdruck der Ergebnisse der Algorithmusoperationen zeigt ein niedriges Gesamtergebnis. Es wird darauf hingewiesen, dass die Ergebnisse der Fitnessfunktionen für die Rastrigin-Funktionen für 10, 50 und 1000 Variablen nicht sehr unterschiedlich sind. Im Folgenden werden wir versuchen herauszufinden, was das bedeutet.

Die Visualisierung der Rastrigin-Testfunktion zeigt eine deutlich sichtbare Aufteilung der Partikelpopulation entlang signifikanter lokaler Extrema, was eine gute Untersuchung lokaler Gebiete bedeutet, aber ein ähnliches Verhalten wird bei den Funktionen Forest und Megacity nicht beobachtet, wo sich die Population wie eine formlose Wolke verhält. Lange horizontale Abschnitte des Konvergenzgraphen deuten darauf hin, dass der Algorithmus dazu neigt, in lokalen Extrema stecken zu bleiben, obwohl dieser beträchtliche Nachteil durch seine ausgezeichnete Skalierbarkeit auf der glatten Rastrigin-Funktion einigermaßen kompensiert wird.

  CSS der Rastrigin-Testfunktion.

  CSS der Forest-Testfunktion.

  CSS der Megacity-Testfunktion.

Beim Testen des CSS-Algorithmus wurde ein neuer Spitzenreiter für die Optimierung glatter Funktionen ermittelt. Der bisherige Anführer der Rastrigin-Funktion war ebenfalls ein Algorithmus, der von der unbelebten Natur inspiriert war - die elektromagnetische Suche (EM). Dieses Mal übertrifft der neue Rekord den vorherigen um fast 10 %. Leider zeigt der Algorithmus einige der schlechtesten Ergebnisse bei der Forest-Funktion mit einem scharfen globalen Extremum und bei der diskreten Megacity-Funktion. Dank der beeindruckenden Ergebnisse auf Rastrigin mit 1000 Variablen konnte der Algorithmus auf der Grundlage der Gesamtparameter den 13. von 20 Plätzen erreichen. Bei den 10.000 Durchläufen des CSS-Algorithmus, die in den Testvorschriften vorgesehen sind, gelang es CSS nicht, näher als 90 % an das globale Extremum heranzukommen (siehe Ausdrucke des oben abgebildeten Prüfstands).   

#	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.58904	2.58641	0.96893	1.00000	0.95092	2.91985	1.00000	1.00000	0.72149	2.72149	100000
2	SSG	Setzen, Säen und Wachsen	1.00000	0.95313	0.51630	2.46944	0.72740	0.69680	1.00000	2.42421	0.69612	0.65918	1.00000	2.35531	87.506
3	HS	Harmoniesuche	0.99676	0.90817	0.44686	2.35179	1.00000	0.72930	0.44806	2.17736	0.91159	0.76578	0.41537	2.09274	79.501
4	ACOm	Ameisen-Kolonie-Optimierung M	0.34611	0.17142	0.15808	0.67562	0.86888	0.73719	0.77362	2.37968	0.91159	0.68163	0.05606	1.64929	55.026
5	IWO	Optimierung mit invasiven Unkräutern	0.95828	0.63939	0.27647	1.87415	0.70773	0.34168	0.31773	1.36714	0.72927	0.32539	0.33289	1.38756	54.060
6	MEC	Evolutionäre Berechnung des Geistes	0.99270	0.48648	0.21148	1.69066	0.60762	0.29973	0.25459	1.16194	0.85083	0.31978	0.26170	1.43231	49.669
7	COAm	Kuckuck-Optimierungsalgorithmus M	0.92400	0.44601	0.24120	1.61121	0.58378	0.25090	0.16526	0.99994	0.66298	0.25666	0.17083	1.09047	42.223
8	FAm	Firefly-Algorithmus M	0.59825	0.32387	0.15893	1.08106	0.51073	0.31182	0.49790	1.32045	0.31491	0.21880	0.35258	0.88629	36.941
9	ABC	Künstliches Bienenvolk (Artificial Bee Colony, ABC)	0.78170	0.31182	0.19313	1.28664	0.53837	0.15816	0.13344	0.82998	0.51381	0.20758	0.13926	0.86064	32.977
10	BA	Fledermaus-Algorithmus	0.40526	0.60773	0.78330	1.79629	0.20841	0.12884	0.25989	0.59714	0.27073	0.08135	0.17371	0.52579	32.236
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.27208	0.00000	0.81352	31.522
12	BFO	Optimierung der bakteriellen Futtersuche	0.67203	0.29511	0.10957	1.07671	0.39702	0.19626	0.20652	0.79980	0.47514	0.25807	0.18932	0.92253	30.702
13	CSS	Suche geladener Systeme	0.56605	0.70573	1.00000	2.27178	0.14081	0.01980	0.16282	0.32343	0.09393	0.00000	0.03481	0.12874	29.743
14	EM	elektromagnetismusähnlicher Algorithmus	0.12235	0.44109	0.92752	1.49096	0.00000	0.02578	0.34880	0.37458	0.00000	0.00562	0.10924	0.11486	20.252
15	SFL	schlurfender Froschsprung	0.40072	0.22627	0.24624	0.87323	0.20153	0.03057	0.02652	0.25862	0.24862	0.04769	0.06639	0.36270	14.050
16	MA	Affen-Algorithmus	0.33192	0.31883	0.13582	0.78658	0.10012	0.05817	0.08932	0.24762	0.19889	0.03787	0.10720	0.34396	12.564
17	FSS	Fischschulsuche	0.46812	0.24149	0.10483	0.81445	0.12840	0.03696	0.06516	0.23052	0.15471	0.04208	0.08283	0.27961	11.880
18	PSO	Partikelschwarmoptimierung	0.20449	0.07816	0.06641	0.34906	0.18895	0.07730	0.21738	0.48363	0.21547	0.05049	0.01957	0.28553	9.246
19	RND	zufällig	0.16826	0.09287	0.07438	0.33551	0.13496	0.03546	0.04715	0.21757	0.15471	0.03507	0.04922	0.23900	5.083
20	GWO	Grauer-Wolf-Optimierung	0.00000	0.00000	0.02093	0.02093	0.06570	0.00000	0.00000	0.06570	0.29834	0.06170	0.02557	0.38561	1.000

Zusammenfassung

Ich musste eine Menge Experimente durchführen und den Code ändern, um die Partikel dazu zu bringen, sich über das Feld zu bewegen, ohne dass sie „zusammenkleben“ und „einfrieren“. Die Autoren des Algorithmus berücksichtigten nicht den Einfluss der Anzahl der optimierten Parameter auf die Qualität der Optimierung (mit zunehmender Dimension des Problems verschlechterte sich die Konvergenz überproportional schnell). Durch die Einbeziehung weiterer Koordinaten in die Gleichung konnte die Wirkung der Beschleunigung verstärkt und die Leistung von CSS verbessert werden (ohne diese Änderungen zeigte der Algorithmus sehr schlechte Ergebnisse). Die inhärenten Gesetze der Partikelbewegung sind zu kapriziös, um sie zu Forschungszwecken zu verändern, und erschweren daher Versuche, die Leistung dieses interessanten Optimierungsalgorithmus zu verbessern.

Der Algorithmus ist eine effektive Methode zur Optimierung glatter Funktionen. Es handelt sich um eine Wolke aus geladenen Teilchen, die durch Coulomb-Kräfte miteinander verbunden sind. Bei der Anwendung dieses interessanten Algorithmus sollte man seine geringe Eignung für Probleme mit einem diskreten Suchraumfeld berücksichtigen. Dies ist jedoch der beste Optimierungsalgorithmus für glatte Funktionen mit mehreren Variablen unter den bisher betrachteten Algorithmen. CSS kann in allen Bereichen der Optimierung mit einer großen Anzahl von Variablen eingesetzt werden. Es benötigt weder Gradienteninformationen noch die Kontinuität des Suchraums.

Zur besseren Veranschaulichung der Vor- und Nachteile der einzelnen Algorithmen kann die obige Tabelle anhand der Farbskala in Abbildung 1 dargestellt werden. Die farbliche Abstufung der Tabelle ermöglicht eine deutlichere Darstellung der Einsatzmöglichkeiten der einzelnen Algorithmen in Abhängigkeit von dem jeweiligen Optimierungsproblem. Bisher konnte ich noch keinen vollkommen universellen Algorithmus für die beste Lösung eines Problems finden (vielleicht gelingt es mir ja, bei späteren Forschungen einen solchen zu finden).

Wenn wir zum Beispiel den allerersten Algorithmus in der Bewertung (SDS) betrachten, dann ist er nicht der beste bei einzelnen Testproblemen (glatte Funktionen mit mehreren Variablen sind in der Tabelle als Durchschnitt angegeben). Was den ACOm-Algorithmus betrifft, so liegen seine Einzelergebnisse weit unter dem Durchschnitt der Tabelle (er löst glatte Funktionen überraschend schlecht), aber er kommt sehr gut mit Forest und diskreter Megacity zurecht (er wurde ursprünglich entwickelt, um diskrete Probleme zu lösen - wie das Traveling-Salesman-Problem), obwohl die Skalierbarkeit sehr zu wünschen übrig lässt.

Der zuletzt vorgestellte Algorithmus (CSS) funktioniert gut bei der Rastrigin-Funktion mit 1000 Variablen (er könnte eine gute Wahl für das Training neuronaler Netze mit vielen Parametern sein) und zeigt das beste Ergebnis unter allen zuvor betrachteten Optimierungsalgorithmen, obwohl er auf der Grundlage der Gesamtergebnisse nicht als der beste in der Tabelle erscheint. Daher ist die richtige Wahl des Algorithmus in Abhängigkeit von den Besonderheiten des Problems sehr wichtig.

Groß angelegte Tests von Optimierungsalgorithmen mit einer Vielzahl von Suchstrategien ergaben eine unerwartete Tatsache - die Strategie kann sich als noch schlechter erweisen als bei einer einfachen Zufallssuche mit der Auswahl des besten Ergebnisses - RND nimmt den zweiten Platz von unten ein, anstatt den letzten erwarteten, GWO erwies sich als schlechter als die Zufallssuche mit Ausnahme der diskreten Megacity mit 10 Parametern.

Bild 1. Farbabstufung der Algorithmen gemäß den einschlägigen Tests

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

Bild 2. Histogramm der Endergebnisse der Testalgorithmen

Vor- und Nachteile des CSS-Algorithmus (Charge System Search):

Vorteile:
1. Hohe Skalierbarkeit bei glatten Funktionen.
2. Eine kleine Anzahl von externen Parametern.

Nachteile
1. Niedrige Ergebnisse bei diskreten Funktionen.
2. Geringe Konvergenz.
3. Tendenz, in lokalen Extremen stecken zu bleiben.

Zu jedem Artikel gibt es ein Archiv mit aktualisierten Versionen der in früheren Artikeln beschriebenen Algorithmencodes. 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.