Algorithmen zur Optimierung mit Populationen: Mikro-Künstliches Immunsystem (Mikro-AIS)

Inhalt

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

1. Einführung

Das Immunsystem ist ein erstaunlicher Mechanismus, der eine wichtige Rolle beim Schutz unseres Körpers vor äußeren Bedrohungen spielt. Wie ein unsichtbares Schild bekämpft es Bakterien, Viren und Pilze und hält unseren Körper gesund. Aber was wäre, wenn wir diesen leistungsfähigen Mechanismus nutzen könnten, um komplexe Optimierungs- und Lernprobleme zu lösen? Dies ist genau der Ansatz, der in der Optimierungsmethode des Künstlichen Immunsystems (AIS) verwendet wird.

Das Immunsystem des Körpers ist ein komplexes System von Zellen, Geweben und Organen, das den Körper vor Infektionen, Krankheiten und anderen äußeren Einflüssen schützt. Die Wirkung beruht auf der Erkennung und Zerstörung von Fremdstoffen und Mikroorganismen wie Bakterien, Viren, Pilzen usw.

Der AIS-Algorithmus modelliert diese Prozesse unter Verwendung der Konzepte von Antigenen (Inputs), Antikörpern (Lösungen) und Killerzellen (Optimierungsprozesse), um das Problem optimal zu lösen. Antigene sind die Inputs, die optimiert werden müssen. Antikörper sind eine mögliche Lösung für dieses Problem. Killerzellen sind Optimierungsprozesse, die nach den besten Lösungen für ein Optimierungsproblem suchen.

Die Optimierungsmethode Artificial Immune System (AIS) wurde in den 1990er Jahren vorgeschlagen. Frühe Forschungen zu dieser Methode gehen auf die Mitte der 1980er Jahre zurück, mit wichtigen Beiträgen von Farmer, Packard, Perelson (1986) und Bersini und Varela (1990).

Seitdem hat sich die AIS-Methode weiterentwickelt und ist Gegenstand ständiger Forschung in der wissenschaftlichen Gemeinschaft. Viele Variationen und Modifikationen dieser Methode wurden vorgeschlagen, ebenso wie ihre Anwendung auf verschiedene Optimierungs- und Lernprobleme. Das körpereigene Immunsystem spielt auch eine wichtige Rolle beim Schutz vor äußeren Einflüssen wie Infektionen und Tumoren. Es ist in der Lage, Anomalien zu erkennen und aufzuspüren und feindliche Agenten anzugreifen, während es gleichzeitig in der Lage ist, Informationen über sie zu unterscheiden und für eine spätere Verwendung zu speichern.

Micro-AIS (Micro-Immune Algorithm) ist eine Modifikation des Immunsystem-Algorithmus (AIS), der zur Lösung von Optimierungsproblemen entwickelt wurde. Es unterscheidet sich vom konventionellen AIS dadurch, dass es ein einfacheres Modell des Immunsystems und einfachere Informationsverarbeitungsprozesse des Immunsystems verwendet.

Die Grundidee von Micro-AIS ist die Schaffung und Entwicklung einer Population von Erregern, die Immunzellen nachahmen. Die Agenten bewegen sich im Raum der Lösungssuche, ohne miteinander zu interagieren und ohne Informationen über Lösungen auszutauschen. Gleichzeitig können die Agenten lernen und sich an veränderte Aufgabenbedingungen anpassen.

Beim herkömmlichen AIS wird ein komplexes Modell des Immunsystems verwendet, das viele Zelltypen und Moleküle umfasst, z. B. B-Zellen, T-Zellen, Antikörper, Zytokine usw. Micro-AIS verwendet ein einfacheres Modell, das nur Antikörper umfasst. Darüber hinaus verwendet Micro-AIS einfachere immunologische Informationsverarbeitungsprozesse, wie Mutation und Selektion.

Einer der Vorteile von Micro-AIS im Vergleich zu AIS ist seine Einfachheit und leichte Implementierbarkeit. In manchen Fällen kann jedoch ein komplexeres Modell des Immunsystems effektiver sein, um komplexe Probleme zu lösen.

Insgesamt hängt die Entscheidung zwischen Mikro-AIS und herkömmlichem AIS vom jeweiligen Anwendungskontext ab. Wenn das Optimierungsproblem relativ einfach ist und eine schnelle Lösung benötigt wird, dann kann Micro-AIS eine gute Wahl sein. Wenn das Problem komplexer ist und eine genauere Lösung benötigt wird, kann ein herkömmliches AIS die bessere Wahl sein.

2. Der Algorithmus

Micro-AIS verwendet zur Bestimmung der Eignung das Konzept der „Affinität“, das ein Maß für die Ähnlichkeit zwischen einem Antikörper und einem Antigen ist. Die Affinität misst den Grad der Ähnlichkeit zwischen einem Antikörper und einem Antigen. Je höher die Affinität, desto ähnlicher sind sich Antikörper und Antigen. Bei Micro-AIS wird die Affinität genutzt, um die besten Antikörper auszuwählen, die durch Mutation und Kreuzung zur Schaffung neuer Antikörper verwendet werden. Antikörper mit höherer Affinität werden mit größerer Wahrscheinlichkeit für die Entwicklung neuer Antikörper ausgewählt.

Die Affinität kann definiert werden als der Abstand zwischen dem Merkmalsvektor des Objekts und dem Gewichtsvektor des Klassifikators. Je kleiner der Abstand, desto ähnlicher sind sich die Vektoren und desto höher ist die Affinität. Im Allgemeinen kann die Affinität als eine Funktion des Abstands zwischen zwei Gleitkommazahlen definiert werden. Die Abstandsfunktion kann je nach spezifischer Anwendung und Anforderungen des Micro-AIS-Algorithmus ausgewählt werden. Bei Optimierungsproblemen zum Beispiel wird der Abstand in der Regel als euklidischer Abstand, Manhattan-Abstand oder eine andere Art von Abstand definiert.

Experimente mit Micro-AIS haben jedoch gezeigt, dass die Verwendung der Affinität bei dieser Suchstrategie nicht der effizienteste Ansatz ist und dass stattdessen der Wert der Fitnessfunktion direkt verwendet werden kann.

Das ursprüngliche Micro-AIS verwendet eine probabilistische Anwendung von Mutationen auf Gene. Je größer die Fitness ist, desto geringer ist die Wahrscheinlichkeit einer Mutation. Auch dieser Ansatz musste wegen Ineffizienz aufgegeben werden, was leicht zu überprüfen ist - es müssen nur ein paar Zeilen Code hinzugefügt werden.

Micro-AIS-Pseudocode:

1. Erstelle eine Population von Antikörperklonen und verteile diese nach dem Zufallsprinzip über den Suchraum. Antikörper und ihre Klone stellen potenzielle Lösungen für das Optimierungsproblem dar. Klone werden durch zufällige Generierung eines Genotyps erzeugt, der die Parameterwerte des Optimierungsproblems bestimmt.
   
2. Definiere die Fitness, die ein Maß für die Qualität der Lösung ist. Der Fitnesswert kann durch Schätzung der Zielfunktion für jeden Antikörper berechnet werden.
   
3. Erzeuge für jeden Antikörper Klone in einer Menge, die der Regel der abnehmenden Progression entspricht: Der erste Antikörper (in Bezug auf die Fitness) erzeugt mehr Klone als der zweite, der zweite mehr als der dritte usw. Die Anzahl der Klone entspricht also nicht dem Grad der Fitness, sondern einer streng definierten Progressionsregel. Stärker angepasste Antikörper erzeugen mehr Klone als weniger angepasste, immer im gleichen Verhältnis.
   
4. Wende die Mutation auf die Gene der Klone an. Für jeden Klon findet eine Gen-Mutation statt, die es uns ermöglicht, neue Lösungen zu erstellen und den Parameterraum des Optimierungsproblems zu erkunden.
   
5. Bestimme die Fitness der Klone.
   
6. Nach der Mutation und der Fitnessberechnung wird die Klonpopulation der Eltern-Antikörperpopulation hinzugefügt.
   
7. Sortiere die Population (Antikörper + Klone) in absteigender Reihenfolge der Fitness, um anschließend die besten Lösungen für die Schaffung einer neuen Population von Klonen in der nächsten Iteration auszuwählen, wodurch ein Wettbewerb zwischen den Nachkommen der Klone und den Eltern-Antikörpern entsteht.
   
8. Wiederhole den Vorgang ab Schritt 2, bis das Stoppkriterium erfüllt ist. Das Abbruchkriterium kann im Voraus festgelegt werden, z. B. das Erreichen eines bestimmten Fitnesswertes oder das Erreichen der maximalen Anzahl von Iterationen.
   

Die Mutation von Genen in Klonen ist die Erzeugung von Zufallszahlen mit einer gleichmäßigen Verteilung gemäß der Gleichung:

X' = X + dist * rnd * k * mutation

wobei:

• X' - neuer Wert des Klon-Gens (Koordinaten)
• X - Wert des Eltern-Antikörper-Gens
• dist - Inkrement zum Elterngen
• rnd - Zufallszahl mit Gleichverteilung im Bereich [-1.0;1.0]
• k - gleichmäßig abnehmendes Verhältnis in Abhängigkeit von der aktuellen Epoche
• mutation - Mutationsverhältnis, tatsächlich - Skalensteigerungsfaktor (externer Parameter)

Das Verhältnis „k“ wird wie folgt berechnet:

k = (epochs - epochsCNT) / epochs

wobei:

• epochs - Grenzwert der Epochen
• epochsCNT - Epochenzähler (Iterationszähler)

Die Inkrementgröße „dist“ ist der Abstand zwischen dem Maximalwert des optimierten Parameters und „X“, wenn „rnd“ größer als 0 ist, und zwischen „X“ und dem Minimalwert des optimierten Parameters, wenn nicht.

Die Mutation ermöglicht es uns also, die Werte der Lösungsparameter zufällig zu ändern, was die Erkundung des Problemraums gewährleistet. Der abnehmende Koeffizient „k“ ermöglicht es, die Wahrscheinlichkeit zu plötzlicher Änderungen der Parameter in späteren Iterationen zu verringern, wodurch die Konvergenz des Algorithmus zur optimalen Lösung verbessert und die gefundenen Koordinaten verfeinert werden.

Schreiben wir eine Struktur, die als Antikörper fungieren soll, S_Agent. Die Struktur enthält nur zwei Felder:

• c: Array von Agentenkoordinaten
• f: Fitness-Index
  

Die Methode Init initialisiert die Felder der Struktur, ändert die Größe des Arrays „c“ und weist dem Feld „f“ den Anfangswert „-DBL_MAX“ zu.

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

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

Wir deklarieren die Klasse C_AO_Micro_AIS des Algorithmus des Mikroimmunsystems, die verschiedene Felder und Methoden definiert.

Felder der Klasse:

• cB: Feld der besten Koordinaten.
• fB: Fitnessindex für die besten Koordinaten.
• a: Array von Agenten des Typs S_Agent.
• rangeMax: Array der maximalen Suchbereichswerte.
• rangeMin: Array der minimalen Suchbereichswerte.
• rangeStep: Array von Suchschritten.

Die Parameter „coords“, „popSize“, „minClonesNumber“, „cloneStep“, „mutation“ und „epochs“ akzeptieren die externen Parameter des Algorithmus.

Methoden der Klasse:

• Init: Initialisierung der Felder der Klasse mit den angegebenen Werten.
• Moving: Verschieben der Agenten.
• Revision: Durchführen einer Revision.

Die Klasse definiert auch die privaten Methoden „SeInDiSp“, „RNDfromCI“ und „Sorting“ für die Normalisierung, die Erzeugung von Zufallszahlen bzw. die Sortierung.

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

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

  public: void Init (const int    coordsP,          //coordinates number
                     const int    popSizeP,         //population size
                     const int    minClonesNumberP, //minimum number of clones
                     const int    cloneStepP,       //clone step
                     const double mutationP,        //mutation
                     const int    epochP);          //total epochs

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

  //----------------------------------------------------------------------------
  private: int    coords;          //coordinates number
  private: int    popSize;         //population size
  private: int    minClonesNumber; //minimum number of clones
  private: int    cloneStep;       //clone step
  private: double mutation;        //mutation
  private: int    epochs;          //total epochs
  private: int    epochsCNT;       //epoch counter
  private: int    parentsNumb;     //number of parents
  private: bool   revision;

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

  private: int     cCnt    [];  //clone counters for each antibody

  private: double SeInDiSp           (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI          (double min, double max);
  private: void   Sorting            (S_Agent &p [], int size);
};
//——————————————————————————————————————————————————————————————————————————————

Um ein Klassenobjekt zu initialisieren, implementieren wir die Methode Init, um die Felder der Klasse mit den angegebenen Werten zu initialisieren.

Zu Beginn der Methode wird der Zufallszahlengenerator mit der Funktion MathSrand initialisiert und sein Zustand mit der Funktion GetMicrosecondCount zurückgesetzt.

Die Werte „-DBL_MAX“ und „false“ werden dann den Variablen „fB“ bzw. „revision“ zugewiesen. Wir initialisieren auch die privaten Felder mit den Eingaben der Methode.

Anschließend werden die Werte des Arrays „cCnt“ berechnet, in dem die Anzahl der Klone für jeden Antikörper in einer Schleife gespeichert wird. Wir wenden die Progressionsgleichung an, wobei der erste Term der Progression „a1“, die Differenz der Progression „d“ und die Summe aller Terme der Progression „Sn“ ist. Die Fortschrittswerte werden in dem Array „cCnt“ gespeichert.

Die Methode bestimmt dann den Wert der Variablen „parentsNumb“ als die Größe des Arrays „cCnt“.

Als Nächstes werden die Arraygrößen geändert: „ind“, „val“, „pTemp“, „a“, „parents“, „rangeMax“, „rangeMin“, „rangeStep“ und „cB“. Die Arraygrößen werden entsprechend den Werten „popSize“ und „parentsNumb“ festgelegt.

Als Nächstes werden in der Schleife die Elemente des Arrays „a“ mit der Init-Methode der Klasse S_Agent initialisiert, und die Elemente des Arrays „parents“ werden ebenfalls mit der Init-Methode initialisiert.

Am Ende der Methode werden die Größen der Arrays „rangeMax“, „rangeMin“, „rangeStep“ und „cB“ entsprechend dem Wert „coords“ geändert.

So initialisiert die Init-Methode die Felder der Klasse C_AO_Micro_AIS und berechnet die Fortschrittswerte für das Array „cCnt“.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Micro_AIS::Init (const int    coordsP,          //coordinates number
                           const int    popSizeP,         //population size
                           const int    minClonesNumberP, //minimum number of clones
                           const int    cloneStepP,       //clone step
                           const double mutationP,        //mutation
                           const int    epochP)           //total epochs
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords          = coordsP;
  popSize         = popSizeP;
  minClonesNumber = minClonesNumberP;
  cloneStep       = cloneStepP;
  mutation        = mutationP;
  epochs          = epochP;
  epochsCNT       = 1;

  //----------------------------------------------------------------------------
  int Sn = popSize;         //sum
  int a1 = minClonesNumber; //first member of progression
  int d  = cloneStep;       //progression difference

  int an   = 0;             //n th member of progression,
  int Ssum = 0;

  ArrayResize (cCnt, 1);

  for (int n = 1;; n++)
  {
    an = a1 + (n - 1) * d;
    Ssum = n * (a1 + an) / 2;

    if (Ssum == Sn)
    {
      ArrayResize (cCnt, n);
      cCnt [n - 1] = an;
      break;
    }
    else
    {
      if (Ssum < Sn)
      {
        ArrayResize (cCnt, n);
        cCnt [n - 1] = an;
      }
      else
      {
        if (n == 1)
        {
          ArrayResize (cCnt, n);
          cCnt [n - 1] = Sn;
          break;
        }
        else
        {
          n--;
          an = a1 + (n - 1) * d;
          int diff = Sn - ((n) * (a1 + an) / 2);

          int index = ArraySize (cCnt) - 1;

          while (true)
          {
            if (index < 0) index = ArraySize (cCnt) - 1;

            cCnt [index]++;

            index--;
            diff--;

            if (diff <= 0) break;
          }

          break;
        }
      }
    }
  }
  
  
  parentsNumb   = ArraySize (cCnt);
  ArrayReverse (cCnt, 0, WHOLE_ARRAY);

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

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

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

Mit Hilfe der Klassenmethode Moving implementieren wir die Bewegung von Antikörpern durch den Suchraum.

Zu Beginn der Methode wird der Wert der Variablen „Revision“ überprüft. Ist sie „falsch“, werden die Antikörperklone im Suchraum platziert, indem Koordinaten mit einer Gleichverteilung erzeugt werden.

Nach der Erzeugung von Antikörperklonen in der Population wird die Variable „revision“ auf „true“ gesetzt und die Methode beendet.

Wenn der Wert der Variablen „revision“ nicht „false“ ist, wird der nächste Codeblock ausgeführt.

Es folgt eine verschachtelte „for“-Schleife, die die Anzahl der „parentsNumb“-Elternagenten durchläuft. Innerhalb dieser Schleife geschieht Folgendes:

• Eine verschachtelte „for“-Schleife durchläuft die Anzahl der Klone für einen bestimmten „cCnt[i]“-Elternantikörper.
• Innerhalb dieser Schleife durchläuft eine verschachtelte „for“-Schleife alle „c“-Koordinaten des Agenten.
• Der Wert der Koordinate „a[indx].c[c]“ wird gleich dem Wert der Koordinate „parents[i].c[c]“ gesetzt.

Der folgende Codeblock wird dann ausgeführt:

• Der Wert der Variablen „k“ wird als Differenz zwischen „Epochen“ und „epochsCNT“ geteilt durch „Epochen“ berechnet.
• Die Zufallszahl „rnd“ wird im Bereich von [-1,0;1,0] erzeugt.
• Wenn „rnd“ größer als 0,0 ist, wird der Wert der Variablen „dist“ als Differenz zwischen „rangeMax[c]“ und „a[indx].c[c]“ berechnet. Ansonsten ist „dist“ gleich der Differenz zwischen „a[indx].c[c]“ und „rangeMin[c]“.
• “a[indx].c[c]“ wird unter Verwendung der Gleichung „a[indx].c[c] + dist * rnd * k * mutation“ neu berechnet. Dabei ist „mutation“ die Mutationsrate.
• “a[indx].c[c]“ durchläuft die Funktion SeInDiSp, die es im Bereich von „rangeMin[c]“ bis „rangeMax[c]“ mit dem Schritt von „rangeStep[c]“ normalisiert.

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

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  int    indx = 0;
  double min  =  DBL_MAX;
  double max  = -DBL_MAX;
  double dist = 0.0;
  int    cnt  = 0;
  double rnd  = 0.0;
  
  for (int i = 0; i < parentsNumb; i++)
  {
    for (int cl = 0; cl < cCnt [i]; cl++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [indx].c [c] = parents [i].c [c];
        
        //----------------------------------------------------------------------
        double k = ((double)epochs - (double)epochsCNT) / (double)epochs;
        rnd = RNDfromCI (-1.0, 1.0);

        if (rnd > 0.0) dist = (rangeMax [c] - a [indx].c [c]);
        else           dist = (a [indx].c [c] - rangeMin [c]);

        a [indx].c [c] = a [indx].c [c] + dist * rnd * k * mutation;
        a [indx].c [c] = SeInDiSp  (a [indx].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }

      indx++;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Zum Schluss wollen wir die Methode Revision implementieren. Die Methode führt eine Prüfung des aktuellen Zustands der Agentenpopulation im Micro-AIS-Algorithmus durch.

Der erste Codeblock, der durch einen Kommentar getrennt ist, aktualisiert die beste globale Lösung, indem er die Population der Klone auf ihren Fitnesswert überprüft.

Dann kopieren wir in einer Schleife die Klone in die Population der Elternantigene am Ende des Arrays.

Danach wird die Sortierfunktion mit den Argumenten „parents“ und „parentsNumb + popSize“ aufgerufen. Die Funktion sortiert das Array „parents“ nach Fitnesspunkten in absteigender Reihenfolge.

Am Ende der Methode wird die Variable „epochsCNT“ inkrementiert, die für die Zählung der Epochen des Algorithmus verantwortlich ist.

Bei der Revisionsmethode wird also der aktuelle Zustand der Population der Antikörper (Agenten) überprüft, der Agent mit dem besten Fitness-Indexwert gefunden und die Reihe der Elternagenten aktualisiert.

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

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

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

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

  Sorting (parents, parentsNumb + popSize);
  
  epochsCNT++;
}
//——————————————————————————————————————————————————————————————————————————————

3. Testergebnisse

Ausdruck des Test von Micro-AIS-Algorithmus:

C_AO_Micro_AIS:50:1:2:0.3
=============================
5 Hilly's; Func runs: 10000; result: 0.7954680903046107
25 Hilly's; Func runs: 10000; result: 0.5192246492565626
500 Hilly's; Func runs: 10000; result: 0.30860655744850657
=============================
5 Forest's; Func runs: 10000; result: 0.7295587642801589
25 Forest's; Func runs: 10000; result: 0.36878621216829993
500 Forest's; Func runs: 10000; result: 0.09398090798741626
=============================
5 Megacity's; Func runs: 10000; result: 0.37666666666666665
25 Megacity's; Func runs: 10000; result: 0.15866666666666668
500 Megacity's; Func runs: 10000; result: 0.028016666666666672
=============================
All score: 3.37898 (37.54%)

Ausgehend vom letzten Artikel bin ich zu absoluten Werten der Testergebnisse übergegangen. So ist es jetzt sehr einfach, die Ergebnisse verschiedener Algorithmen in einer Tabelle zu vergleichen und zu navigieren. 37,54 % sind kein herausragendes Ergebnis, aber immerhin ein Platz in der oberen Tabellenhälfte.

Die Visualisierung des Optimierungsprozesses zeigte, dass der Algorithmus hartnäckig nach signifikanten lokalen Extrema sucht, um eine bessere Lösung zu finden. Dies führt zu einer Konzentration von Agenten in verschiedenen Bereichen des Raums. Die Konvergenzkurve zeigte ein ungewöhnliches Verhalten. Typischerweise ist bei den betrachteten Algorithmen ein starker Anstieg der Konvergenz in der ersten Hälfte der Iterationen zu verzeichnen, danach nimmt die Konvergenzrate allmählich ab. Bei diesem Algorithmus ist die Konvergenzkurve jedoch S-förmig. Ein starker Anstieg der Konvergenz ist nur in den ersten 10-20% der Iterationen zu beobachten, dann nimmt die Konvergenzgeschwindigkeit ab, aber näher am Ende der Optimierung ist wieder eine deutliche Beschleunigung der Konvergenz zu beobachten.

Dieses Verhalten des Konvergenzgraphen lässt sich durch die Strategie erklären, den Bereich der Inkremente während der Mutationen nach einem linearen Gesetz zu verkleinern. Die Konvergenz erfolgt jedoch nicht nach einem linearen Gesetz, da der Algorithmus ungleichmäßig Informationen über die Oberfläche der Testfunktion „ansammelt“. Die Verengung des Mutationsbereichs spielt erst gegen Ende der Optimierung eine spürbare Rolle. Die Ersetzung des linearen Gesetzes der Verengung des Bereichs der Mutationen durch andere Varianten nichtlinearer Gesetze führte nicht zu einer Verbesserung der Konvergenz, aber vielleicht gibt es Raum für die konstruktive Phantasie der Forscher bei der Wahl anderer Varianten der Gesetze der Verengung des Bereichs.

Der Konvergenzgraph lässt zu wünschen übrig, aber sein Aussehen lässt hoffen, dass die Suchstrategie noch verbessert werden kann.

  Micro-AIS mit der Testfunktion Hilly

  Micro-AIS mit der Testfunktion Forest

  Micro-AIS mit der Testfunktion Megacity

Der Micro-AIS-Algorithmus nahm seinen rechtmäßigen Platz in der 11. Zeile der Bewertungstabelle ein, noch vor so bekannten und beliebten Algorithmen wie dem Kuckucks-Optimierungsalgorithmus, der künstlichen Bienenkolonie und dem simulierten Annealing. Dies zeigt, wie effizient dieser Algorithmus bei der Lösung komplexer Optimierungsprobleme ist.

Die Farbtabelle zeigt jedoch, dass die Leistung bei Funktionen mit einer großen Anzahl von Variablen abnimmt, was auf die schwache Skalierbarkeit des Algorithmus hinweist. Dies kann darauf zurückzuführen sein, dass Micro-AIS ein einfacheres Modell des Immunsystems und einfachere Immuninformationsverarbeitungsvorgänge verwendet, was seine Fähigkeit, optimale Lösungen in hochdimensionalen Räumen zu finden, einschränken kann.

Dies bedeutet jedoch nicht, dass Micro-AIS nicht zur Lösung von Problemen mit einer großen Anzahl von Variablen verwendet werden kann. Möglicherweise könnte seine Leistung durch eine Modifizierung des Algorithmus oder eine Kombination mit anderen Optimierungsmethoden verbessert werden.

#	AO	Beschreibung	Hilly			Hilly final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result	% von MAX
			10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)
1	(P+O)ES	(P+O) Entwicklungsstrategien	0.99934	0.91895	0.56297	2.48127	1.00000	0.93522	0.39179	2.32701	0.83167	0.64433	0.21155	1.68755	6.496	72.18
2	SDSm	stochastische Diffusionssuche M	0.93066	0.85445	0.39476	2.17988	0.99983	0.89244	0.19619	2.08846	0.72333	0.61100	0.10670	1.44103	5.709	63.44
3	SIA	Simuliertes isotropes Abkühlen	0.95784	0.84264	0.41465	2.21513	0.98239	0.79586	0.20507	1.98332	0.68667	0.49300	0.09053	1.27020	5.469	60.76
4	DE	differentielle Evolution	0.95044	0.61674	0.30308	1.87026	0.95317	0.78896	0.16652	1.90865	0.78667	0.36033	0.02953	1.17653	4.955	55.06
5	HS	Harmoniesuche	0.86509	0.68782	0.32527	1.87818	0.99999	0.68002	0.09590	1.77592	0.62000	0.42267	0.05458	1.09725	4.751	52.79
6	SSG	Setzen, Säen und Wachsen	0.77839	0.64925	0.39543	1.82308	0.85973	0.62467	0.17429	1.65869	0.64667	0.44133	0.10598	1.19398	4.676	51.95
7	(PO)ES	(PO) Entwicklungsstrategien	0.79025	0.62647	0.42935	1.84606	0.87616	0.60943	0.19591	1.68151	0.59000	0.37933	0.11322	1.08255	4.610	51.22
8	ACOm	Ameisen-Kolonie-Optimierung M	0.88190	0.66127	0.30377	1.84693	0.85873	0.58680	0.15051	1.59604	0.59667	0.37333	0.02472	0.99472	4.438	49.31
9	MEC	Evolutionäre Berechnung des Geistes	0.69533	0.53376	0.32661	1.55569	0.72464	0.33036	0.07198	1.12698	0.52500	0.22000	0.04198	0.78698	3.470	38.55
10	IWO	Optimierung mit invasiven Unkräutern	0.72679	0.52256	0.33123	1.58058	0.70756	0.33955	0.07484	1.12196	0.42333	0.23067	0.04617	0.70017	3.403	37.81
11	Micro-AIS	Künstliches Mikro-Immunsystem	0.79547	0.51922	0.30861	1.62330	0.72956	0.36879	0.09398	1.19233	0.37667	0.15867	0.02802	0.56335	3.379	37.54
12	COAm	Kuckuck-Optimierungsalgorithmus M	0.75820	0.48652	0.31369	1.55841	0.74054	0.28051	0.05599	1.07704	0.50500	0.17467	0.03380	0.71347	3.349	37.21
13	SDOm	Optimierung der Spiraldynamik M	0.74601	0.44623	0.29687	1.48912	0.70204	0.34678	0.10944	1.15826	0.42833	0.16767	0.03663	0.63263	3.280	36.44
14	NMm	Nelder-Mead-Verfahren M	0.73807	0.50598	0.31342	1.55747	0.63674	0.28302	0.08221	1.00197	0.44667	0.18667	0.04028	0.67362	3.233	35.92
15	FAm	Firefly-Algorithmus M	0.58634	0.47228	0.32276	1.38138	0.68467	0.37439	0.10908	1.16814	0.28667	0.16467	0.04722	0.49855	3.048	33.87
16	GSA	Algorithmus für die Schwerkraftsuche	0.64757	0.49197	0.30062	1.44016	0.53962	0.36353	0.09945	1.00260	0.32667	0.12200	0.01917	0.46783	2.911	32.34
17	ABC	Künstliches Bienenvolk (Artificial Bee Colony, ABC)	0.63377	0.42402	0.30892	1.36671	0.55103	0.21874	0.05623	0.82600	0.34000	0.14200	0.03102	0.51302	2.706	30.06
18	BFO	Optimierung der bakteriellen Futtersuche	0.54626	0.43533	0.31907	1.30066	0.41626	0.23156	0.06266	0.71048	0.35500	0.15233	0.03627	0.54360	2.555	28.39
19	BA	Fledermaus-Algorithmus	0.59761	0.45911	0.35242	1.40915	0.40321	0.19313	0.07175	0.66810	0.21000	0.10100	0.03517	0.34617	2.423	26.93
20	SA	simuliertes Abkühlen	0.55787	0.42177	0.31549	1.29513	0.34998	0.15259	0.05023	0.55280	0.31167	0.10033	0.02883	0.44083	2.289	25.43
21	IWDm	intelligente Wassertropfen M	0.54501	0.37897	0.30124	1.22522	0.46104	0.14704	0.04369	0.65177	0.25833	0.09700	0.02308	0.37842	2.255	25.06
22	PSO	Partikelschwarmoptimierung	0.59726	0.36923	0.29928	1.26577	0.37237	0.16324	0.07010	0.60572	0.25667	0.08000	0.02157	0.35823	2.230	24.77
23	MA	Affen-Algorithmus	0.59107	0.42681	0.31816	1.33604	0.31138	0.14069	0.06612	0.51819	0.22833	0.08567	0.02790	0.34190	2.196	24.40
24	SFL	schlurfender Froschsprung	0.53925	0.35816	0.29809	1.19551	0.37141	0.11427	0.04051	0.52618	0.27167	0.08667	0.02402	0.38235	2.104	23.38
25	FSS	Fischschulsuche	0.55669	0.39992	0.31172	1.26833	0.31009	0.11889	0.04569	0.47467	0.21167	0.07633	0.02488	0.31288	2.056	22.84
26	RND	zufällig	0.52033	0.36068	0.30133	1.18234	0.31335	0.11787	0.04354	0.47476	0.25333	0.07933	0.02382	0.35648	2.014	22.37
27	GWO	Grauer-Wolf-Optimierung	0.59169	0.36561	0.29595	1.25326	0.24499	0.09047	0.03612	0.37158	0.27667	0.08567	0.02170	0.38403	2.009	22.32
28	CSS	Suche geladener Systeme	0.44252	0.35454	0.35201	1.14907	0.24140	0.11345	0.06814	0.42299	0.18333	0.06300	0.02322	0.26955	1.842	20.46
29	EM	elektromagnetismusähnlicher Algorithmus	0.46250	0.34594	0.32285	1.13129	0.21245	0.09783	0.10057	0.41085	0.15667	0.06033	0.02712	0.24412	1.786	19.85

Zusammenfassung

Die Optimierungsmethode des künstlichen Mikro-Immunsystems (Micro-AIS) ist ein interessanter und vielversprechender Ansatz zur Lösung von Optimierungsproblemen, der auf den Prinzipien der Funktionsweise des Immunsystems basiert. Es ermöglicht die Nutzung der leistungsfähigen Mechanismen des Immunsystems zur Lösung komplexer Optimierungs- und Lernprobleme.

Zu den Vorteilen von Micro-AIS gehören eine geringe Anzahl externer Parameter und eine einfache Implementierung des Algorithmus. Das macht es für den Einsatz in der Praxis sehr attraktiv.

Der Micro-AIS-Algorithmus hat jedoch auch Nachteile. Es neigt dazu, an lokalen Extremen hängen zu bleiben und hat eine geringe Konvergenz. Außerdem nimmt die Leistung des Algorithmus bei Funktionen mit einer großen Anzahl von Variablen ab, was auf seine schwache Skalierbarkeit hinweist.

Micro-AIS ist jedoch eine vielversprechende Optimierungsmethode, die durch Modifizierung des Algorithmus oder Kombination mit anderen Optimierungsmethoden verbessert werden kann. Insgesamt ist die Optimierungsmethode unter Verwendung eines künstlichen Mikroimmunsystems ein wichtiger Beitrag zum Bereich der Optimierung und kann ein nützliches Instrument für die Lösung komplexer Probleme in verschiedenen Bereichen wie maschinelles Lernen, künstliche Intelligenz, Bioinformatik usw. sein.

Der Algorithmus hinterlässt den Eindruck einer Art „Schablone“, auf die mit verschiedenen Methoden aufgebaut werden kann, um die Suchmöglichkeiten zu erweitern. Erleichtert wird dies durch die einfache Architektur, die wirklich viel Spielraum für Experimente mit diesem sehr interessanten Algorithmus lässt.

Bild 1. Farbabstufung der Algorithmen gemäß den entsprechenden Tests

Bild 2. Das Histogramm der Algorithmus-Testergebnisse (auf einer Skala von 0 bis 100, je mehr, desto besser,

wobei 100 das höchstmögliche theoretische Ergebnis ist, das Archiv enthält ein Skript zur Berechnung der Bewertungstabelle)

Vor- und Nachteile des Micro-AIS-Algorithmus:

Vorteile:

1. Geringe Anzahl von externen Parametern.
2. Einfache Implementierung des Algorithmus.

Nachteile

1. Tendenz zum Steckenbleiben.
   
2. Geringe Konvergenz.
   

Dem Artikel ist ein Archiv mit aktualisierten Versionen der in früheren Artikeln beschriebenen Algorithmuscodes beigefügt. Der Autor des Artikels übernimmt keine Verantwortung für die absolute Richtigkeit der Beschreibung der kanonischen Algorithmen. An vielen von ihnen wurden Änderungen vorgenommen, um die Suchmöglichkeiten zu verbessern. Die in den Artikeln dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Versuche.