Algorithmen zur Optimierung mit Populationen Ameisenkolonie-Optimierung (ACO)

Das große Geheimnis eines jeden Verhaltens ist das soziale Verhalten...

F. Bartlett

Inhalt

1. Einführung
2. Grundsätze des Algorithmus
3. Geänderte Version
4. Testergebnisse

1. Einführung

Der belgische Forscher Marco Dorigo hat ein mathematisches Modell entwickelt, das den Prozess der kollektiven Intelligenz in einem Ameisenvolk wissenschaftlich beschreibt. Er veröffentlichte es 1992 in seiner Dissertation und implementierte es als Algorithmus.

Die Ameisenkolonie-Optimierung (ACO) ist eine populationsbasierte, stochastische Suchmethode zur Lösung eines breiten Spektrums kombinatorischer Optimierungsprobleme. ACO basiert auf dem Konzept der Stigmergie. 1959 erfand Pierre-Paul Grasset die Theorie der Stigmergy, um das Nestbauverhalten von Termiten zu erklären. Stigmergy besteht aus zwei griechischen Wörtern: stigma - Zeichen und ergon - Handlung.

Die kanonische Definition ist eine indirekte Art der Interaktion zwischen Mitgliedern einer Population, die sich durch die Interaktion mit der Umwelt zeitlich verlängert. Mit anderen Worten: Einer der Agenten hinterlässt eine Spur oder verändert auf irgendeine Weise den Ort, sodass ein anderer Agent Informationen erhält, wenn er sein Gebiet betritt. Im Falle der Ameisen ist die Stigmergie ein Pheromon. Ein Beispiel für Stigmergy ist die Kommunikation von Ameisen bei der Nahrungssuche: Ameisen kommunizieren indirekt miteinander, indem sie Pheromonspuren auf dem Boden hinterlassen und so die Entscheidungsprozesse anderer Ameisen beeinflussen. Aus dieser einfachen Form der Kommunikation zwischen einzelnen Ameisen ergeben sich das komplexe Verhalten und die Fähigkeiten der Kolonie als Ganzes.

Ameisen sind soziale Insekten, sie leben in Kolonien. Das Verhalten der Ameisen wird durch die Suche nach Nahrung gesteuert. Auf der Suche streifen sie durch ihre Kolonien. Auf der Suche nach Nahrung hüpft die Ameise immer wieder von einem Ort zum anderen, wobei sie eine organische Verbindung, ein so genanntes Pheromon, auf dem Boden absetzt. So kommunizieren die Ameisen untereinander über Pheromonspuren.

Wenn eine Ameise Nahrung findet, nimmt sie so viel mit, wie sie tragen kann. Auf dem Rückweg gibt er je nach Menge und Qualität der Nahrung Pheromone ab. Infolgedessen können andere Ameisen diesem Weg folgen. Je höher der Pheromonspiegel, desto höher ist die Wahrscheinlichkeit, dass dieser Weg gewählt wird, und je mehr Ameisen einen bestimmten Weg passieren, desto mehr Pheromon wird auf dieser Strecke zurückgelassen.

Sehen wir uns das folgende Beispiel an. Angenommen, es gibt zwei Möglichkeiten, Nahrung von der Kolonie zu bekommen. Erstens gibt es keine Pheromone auf dem Boden. Die Wahrscheinlichkeit, diese beiden Wege zu wählen, ist also gleich groß (50 %). Nehmen wir an, dass zwei Ameisen zwei verschiedene Wege zum Futter wählen. Die Entfernungen zwischen diesen beiden Wegen sind unterschiedlich. Die Ameise, die den kürzeren Weg nimmt, erreicht das Futter vor der anderen. Wenn er das Futter findet, nimmt er etwas davon und kehrt zur Kolonie zurück. Auf dem Rückweg setzt er ein Pheromon auf dem Boden ab. Die Ameise, die einen kürzeren Weg nimmt, erreicht die Kolonie früher.

Wenn die dritte Ameise auf Nahrungssuche gehen will, nimmt sie einen Weg, der je nach Pheromonkonzentration auf dem Boden eine kürzere Strecke aufweist. Da der kürzere Weg mehr Pheromone enthält als der längere, wird die dritte Ameise dem Weg folgen, der mehr Pheromone enthält. Als die Ameise, die dem längeren Weg folgte, zur Kolonie zurückkehrte, hatten bereits mehr Ameisen den Weg mit den höheren Pheromonkonzentrationen passiert. Wenn dann eine andere Ameise versucht, von der Kolonie aus zu ihrem Ziel (Nahrung) zu gelangen, wird sie feststellen, dass jeder Weg den gleichen Pheromonwert hat. Es wird also zufällig einer von ihnen ausgewählt. Wenn man diesen Vorgang immer wieder wiederholt, wird nach einer Weile der kürzere Weg mehr Pheromone als die anderen erhalten und die Wahrscheinlichkeit, dass die Ameisen diesen Weg nehmen, wird höher sein.

Der ACO-Algorithmus ist eine Art Schwarmintelligenz-Algorithmus. Durch die Modellierung des Futtersuchprozesses einer Ameisenkolonie wird der kürzeste Weg in verschiedenen Umgebungen mithilfe des internen Datenübertragungsmechanismus der Ameisenkolonie ermittelt. Je höher die Konzentration des Pheromons auf dem Weg ist, desto größer ist die Wahrscheinlichkeit, dass die Ameise diesen Weg wählt. Gleichzeitig nimmt die Konzentration des Pheromons mit der Zeit ab. Aufgrund des Verhaltens der Ameisenkolonie lernen und optimieren die Ameisen daher ständig durch einen Rückkopplungsmechanismus, um den kürzesten Weg zur Futtersuche zu finden. Der ACO-Algorithmus ist in der Bahnplanung weit verbreitet.

2. Grundsätze des Algorithmus

Bei ACO sucht eine Gruppe von Software-Agenten, künstliche Ameisen genannt, nach guten Lösungen für ein bestimmtes Optimierungsproblem. Zur Anwendung von ACO wird das Optimierungsproblem in das Problem umgewandelt, den besten Pfad in einem gewichteten Graphen zu finden. Künstliche Ameisen (im Folgenden als Ameisen bezeichnet) bauen schrittweise Lösungen auf, die sich entlang des Graphen bewegen. Der Prozess der Konstruktion einer Lösung ist stochastisch und hängt vom Pheromonmodell ab - einer Reihe von Parametern, die mit Graphenkomponenten (Knoten oder Kanten) verbunden sind und deren Werte von den Ameisen während der Ausführung geändert werden.

Betrachten wir den Algorithmus für das Travelling-Salesman-Problem. Wir haben eine Reihe von Orten (Städten) und Entfernungen zwischen ihnen. Das Problem besteht darin, einen geschlossenen Weg von minimaler Länge zu finden, der jede Stadt nur einmal besucht. Ein Graph, der durch die Zuordnung einer Menge von Städten zu einer Menge von Graphscheiteln definiert ist, wird als Konstruktionsgraph bezeichnet. Da es möglich ist, von jeder beliebigen Stadt in jede andere Stadt zu ziehen, ist der Konstruktionsgraph vollständig zusammenhängend, und die Anzahl der Eckpunkte ist gleich der Anzahl der Städte. Wir setzen die Kantenlängen zwischen den Eckpunkten proportional zu den Entfernungen zwischen den Städten, die durch diese Eckpunkte repräsentiert werden, und ordnen den Graphkanten Pheromonwerte und heuristische Werte zu. Die Pheromonwerte ändern sich zur Laufzeit und repräsentieren die kumulative Erfahrung des Ameisenvolkes, während die heuristischen Werte problemabhängig sind.

Ameisen konstruieren Lösungen auf folgende Weise. Jede Ameise startet von einer zufällig ausgewählten Stadt (Knoten des Konstruktionsgraphen). Dann bewegt sie sich bei jedem Konstruktionsschritt entlang der Kanten des Graphen. Jede Ameise speichert ihren Weg und wählt in den folgenden Schritten die Kanten aus, die nicht zu den bereits besuchten Knotenpunkten führen. Die Ameise hat eine Lösung gefunden, sobald sie alle Knotenpunkte des Graphen besucht hat. Bei jedem Konstruktionsschritt wählt die Ameise aus den Kanten, die zu noch nicht besuchten Knotenpunkten führen, eine Kante aus, der sie folgt. Die probabilistische Regel basiert auf Pheromonwerten und heuristischen Informationen: Je höher der Pheromonwert und der heuristische Wert einer Kante ist, desto höher ist die Wahrscheinlichkeit, dass die Ameise diese Kante wählt. Wenn alle Ameisen ihre Reise beendet haben, werden die Pheromone an den Rändern aktualisiert. Jeder der Pheromonwerte wird zunächst um einen bestimmten Prozentsatz reduziert. Dieser Vorgang wird so lange wiederholt, bis das Abbruchkriterium erfüllt ist.

Die auf Pheromonen basierende Kommunikation ist eine der effektivsten in der Natur verbreiteten Kommunikationsmethoden. Das Pheromon wird von sozialen Insekten wie Bienen, Ameisen und Termiten zur Kommunikation zwischen den Vertretern verwendet. Aufgrund ihrer Machbarkeit wurden künstliche Pheromone in Multi-Roboter- und Schwarmrobotersystemen eingesetzt.

Wie können wir verstehen, dass unsere Ameisen wirklich den kürzesten Weg gefunden haben? Dafür gibt es einen guten Testfall: Punkte, die in einem Kreis angeordnet sind. Für sie wird der kürzeste Weg immer derselbe sein - ein Kreis.  

Der erste ACO-Algorithmus wurde als Ameisensystem bezeichnet und diente der Lösung des Problems des Handlungsreisenden, bei dem es darum geht, den kürzesten Weg zwischen mehreren Städten zu finden. Der allgemeine Algorithmus ist relativ einfach und basiert auf einer Gruppe von Ameisen, von denen jede eine der möglichen Städterunden macht. In jeder Phase wählt die Ameise nach bestimmten Regeln einen Weg von einer Stadt zur anderen:

1. Sie sollte jede Stadt genau einmal besuchen;
2. Die Wahrscheinlichkeit, dass eine weit entfernte Stadt ausgewählt wird, ist geringer (Sichtbarkeit);
3. Je intensiver die Pheromonspur ist, die an der Grenze zwischen zwei Städten gelegt wird, desto wahrscheinlicher ist es, dass diese Grenze gewählt wird;
4. Wenn die Ameise ihren Weg beendet hat, deponiert sie weitere Pheromone an allen Kanten, die sie passiert hat, wenn der Weg kurz ist;
5. Nach jeder Iteration verflüchtigen sich die Pheromonspuren.

Abb. 1. Ein Beispiel für mögliche Pfade an fünf Knotenpunkten

3. Geänderte Version

Es sind mehrere der beliebtesten Varianten von ACO-Algorithmen bekannt. Schauen wir sie uns an:

Ameisensystem (AS).
Das Ameisensystem ist der erste ACO-Algorithmus.

Ameisenkolonie-System (ACS).
Beim Algorithmus des Ameisensystems wurde das ursprüngliche Ameisensystem in dreierlei Hinsicht verändert:
1. Die Kantenauswahl ist auf Ausbeutung ausgerichtet (d. h. zugunsten der Wahrscheinlichkeit, dass die kürzesten Kanten mit mehr Pheromonen ausgewählt werden);
2. Beim Aufbau einer Lösung ändern die Ameisen den Pheromonpegel an den von ihnen gewählten Kanten, indem sie eine lokale Pheromonaktualisierungsregel anwenden;
3. Am Ende jeder Iteration kann nur die beste Ameise die Spuren aktualisieren, indem sie die modifizierte globale Pheromon-Aktualisierungsregel anwendet.

Elite-Ameisensystem.
Bei diesem Algorithmus deponiert die global beste Lösung das Pheromon nach jeder Iteration auf ihrer Spur (auch wenn die Spur nicht wieder besucht wurde) zusammen mit allen anderen Ameisen. Das Ziel der Elitestrategie ist es, die Suche aller Ameisen so zu lenken, dass eine Lösung entsteht, die die Links der aktuell besten Route enthält.

Max-Min-Ameisen-System (MMAS).
Dieser Algorithmus kontrolliert die maximale und minimale Anzahl von Pheromonen auf jeder Spur. Nur die beste, globale Tournee oder die beste Wiederholungstournee kann ihrer Spur Pheromone hinzufügen. Um eine Stagnation des Suchalgorithmus zu vermeiden, wird der Bereich der möglichen Pheromonmengen auf jeder Spur durch das Intervall [τ max, τ min] begrenzt. Alle Kanten werden mit τ max initialisiert, um die Erkundung der Lösung zu beschleunigen. Die Kurven werden auf τ max reinitialisiert, wenn sie sich der Stagnation nähern.

Ameisensystem auf der Grundlage von Rängen (Asrank).
Alle Lösungen werden nach ihrer Länge gereiht. Nur eine bestimmte Anzahl der besten Ameisen in dieser Iteration kann ihre Herausforderungen aktualisieren. Die Menge des abgegebenen Pheromons wird für jede Lösung gewogen, sodass Lösungen mit kürzeren Wegen mehr Pheromon abgeben als Lösungen mit längeren Wegen.

Parallele Ameisenkolonie-Optimierung (PACO).
Ameisenkolonie-System (ACS) mit Kommunikationsstrategien.
Künstliche Ameisen werden in mehrere Gruppen unterteilt. Es werden sieben Kommunikationsmethoden vorgeschlagen, um die Pheromonlevel zwischen den Gruppen im ACS zu aktualisieren, die mit dem Traveling-Salesman-Problem arbeiten.

Kontinuierliche orthogonale Ameisenkolonie (COAC).
Der Mechanismus der COAC-Pheromondeposition ermöglicht es den Ameisen, gemeinsam und effizient nach Lösungen zu suchen. Durch den Einsatz der orthogonalen Entwurfsmethode können die Ameisen im zulässigen Bereich schnell und effizient die von ihnen gewählten Gebiete mit verbesserten globalen Suchmöglichkeiten und höherer Genauigkeit erkunden. Die orthogonale Entwurfsmethode und die adaptive Radiusabstimmung können auch auf andere Optimierungsalgorithmen ausgeweitet werden, um weitere Vorteile bei der Lösung praktischer Probleme zu bieten.

Rekursive Optimierung einer Ameisenkolonie.
Dabei handelt es sich um eine rekursive Form eines Ameisenvolkes, das das gesamte Suchgebiet in mehrere Teilgebiete unterteilt und das Problem in diesen Teilgebieten löst. Die Ergebnisse aller Subdomains werden verglichen, und die wenigen besten kommen in die nächste Ebene. Die Teilbereiche, die den ausgewählten Ergebnissen entsprechen, werden weiter unterteilt und der Vorgang wird so lange wiederholt, bis die gewünschte Genauigkeit erreicht ist. Diese Methode wurde an fehlerhaften geophysikalischen Inversionsproblemen getestet und ihre Effizienz bewiesen.

Die oben genannten Ameisenkolonie-Algorithmen wurden ursprünglich für die Lösung von Optimierungsproblemen auf Graphen entwickelt. Das Problem wird in solche Algorithmen integriert, und die Problembedingungen werden als Algorithmusparameter - die Koordinaten der Graphknoten - angegeben. Daher sind die auf den ACO-Prinzipien basierenden Algorithmen hoch spezialisiert. Solche Algorithmen sind für unsere Aufgaben nicht geeignet, da wir keine festen Koordinaten verwenden. Wir können alle Koordinaten haben, auch die ähnlichen. Um eine breite Palette von Optimierungsproblemen im Bereich des Handels mit Finanzinstrumenten zu lösen, einschließlich des Trainings neuronaler Netze, müssen wir einen neuen universellen Algorithmus entwickeln, der unsere speziellen Tests bestehen kann, d.h. es sollte ein ganz neuer ACO sein.

Lassen Sie uns das Grundkonzept des Algorithmus überdenken. Genau wie in der kanonischen Version werden wir eine Ameisenkolonie haben. Wir können die zurückgelegten Wege nicht mit Pheromonen markieren, sie können überall in einem mehrdimensionalen Raum hingehen, sich Routen merken und speichern. Bei einem kontinuierlichen Schritt erscheint dies nicht sinnvoll, da die Wahrscheinlichkeit, denselben Weg zu gehen, gegen Null tendiert. Außerdem braucht man sich die Knoten gar nicht zu merken, da es kein Problem der sequentiellen Passage ohne Wiederholungen gibt - man muss das Problem aus dem Algorithmus herausnehmen. Was sollten wir also tun? Zum jetzigen Zeitpunkt ist völlig unklar, in welche Richtung die Entwicklung des Konzepts gehen soll.

Nun, dann notieren wir noch einmal die wichtigsten Punkte, die unseren neuen Algorithmus von dem kanonischen unterscheiden:

1. Es gibt keine festen Punkte im Raum.

2. Es ist nicht notwendig, den Weg in einer bestimmten Reihenfolge zu durchlaufen.

3. Da es keine Wege gibt, gibt es auch nichts, was man mit Pheromonen markieren könnte.

Finden wir also heraus, was wir haben, wenn wir uns die Idee eines Ameisenvolkes vor Augen halten. Wir können mit Pheromonen genau die Punkte markieren, an denen die Ameisen gelaufen sind, nicht den Weg, den sie zurückgelegt haben. Setzen wir den Wert der Fitnessfunktion als die Anzahl der Pheromone am Standort der Ameise in der aktuellen Iteration. Dann müssen sich die Ameisen zu den Koordinaten bewegen, an denen sich die meisten Pheromone befinden. Es kann jedoch zu einem Problem kommen, wenn alle Ameisen einfach zu einem Punkt laufen - dem, der die meisten Pheromone hat. Dies ist nicht unbedingt die beste Lösung für das Problem, da die Punkte die Variablen der optimierten Funktion sind. Wir erinnern uns, dass beim klassischen ACO auch die Länge des Pfades zum Knoten eine Rolle spielt. Je kürzer der gewählte Weg ist, desto besser. Wir müssen also die Entfernung zwischen dem aktuellen Standort und dem Ort, an den die Ameise gehen soll, berechnen. Der nächste Ort ist dort, wo die anderen Ameisen sind, d. h. wir akzeptieren das Konzept, dass sich die Ameisen mit einem gewissen Maß an Zufälligkeit aufeinander zu bewegen.

Welche Art von Zufälligkeit können wir der Bewegung hinzufügen?

• Fügen wir zunächst den Zufallsfaktor bei der Auswahl der nächsten Position PheromoneEffect_P hinzu.
• Zweitens fügen wir einen Zufallsfaktor hinzu, der die Entfernung zur nächsten Position PathLengthEffect_P berücksichtigt (je kleiner die Entfernung, desto besser die Wahl).

Es gibt also zwei Kriterien für die Wahl der nächsten Position - die Menge an Pheromonen an jeder spezifischen Position, an der sich die Ameisen befinden, und der Abstand zwischen all diesen Punkten in Paaren. Aber auch wenn wir nur diese beiden Auswahlkriterien verwenden, bewegen sich die Ameisen im Raum entlang der Kanten einer imaginären Figur, deren Knotenpunkte ihr eigener Standort sind. Es wird also keine Fortschritte bei der Suche nach einem besseren Ort geben.

In diesem Fall addieren wir den Einflussradius des Pheromons PheromoneRadius_P (Verhältnis der Entfernung zwischen den Punkten), innerhalb dessen die Ameisen das Pheromon spüren können. Dann können die Ameisen an der Stelle vorbeischlüpfen, zu der sie sich bewegt haben. Dadurch erhalten die Ameisen einen zusätzlichen Freiheitsgrad bei der Bewegung im mehrdimensionalen Raum.

Damit die Ameisen neue Gebiete erkunden können, müssen sie die Möglichkeit haben, entlang einer beliebigen Koordinate vom Richtungsvektor abzuweichen. Führen wir das Verhältnis PathDeviation_P ein, das die Abweichung vom Inkrement an einer bestimmten Koordinate angibt. Da es sich um einen mehrdimensionalen Raum handelt, der dem Verschiebungsvektor folgt, können einige Koordinaten ein positives Inkrement haben, während andere ein negatives haben können, und die Inkremente können unterschiedliche Modulo-Werte haben. Dieses Verhältnis ermöglicht es, all dies zu berücksichtigen, und gibt den Ameisen einen gewissen Freiheitsgrad bei der Suche nach Nahrung (das Extremum der Funktion).

Was ist also der Verschiebungsvektor und wie messen wir die Entfernung, die die Ameise zurücklegen muss? Um diese Fragen zu beantworten, verwenden wir die Gleichung zur Berechnung des Abstands zwischen zwei Punkten im dreidimensionalen Raum:

Eine visuelle Darstellung des Verschiebungsvektors ist in Abbildung 2 zu sehen.

Abb. 2. Bewegungsvektor der Ameise

Für n-dimensionale Räume ist die Berechnung ähnlich.

Eine Ameise bewegt sich in einer Iteration (Epoche) von Punkt A zu Punkt B mit möglichem Schlupf zu Punkt R. Die Entfernung zu Punkt R von Punkt B hängt vom Verhältnis PheromonRadius_P ab und kann als BR = AB x PheromonRadius_P berechnet werden.

Die Wahrscheinlichkeit eines neuen Standorts auf der AR-Linie ist in Abbildung 2 als graue Fläche schematisch dargestellt (nicht maßstabsgerecht). Daher ist es wahrscheinlicher, dass der neue Standort der Ameise zum Punkt B tendiert. Das Prinzip der Wahrscheinlichkeitsverschiebung wurde im vorherigen Artikel erörtert.

Der Algorithmus umfasst bei jeder Iteration die folgenden Schritte:

1) Zufällige Anordnung der Ameisen im Raum.
2) Bestimmung des Wertes der Pheromonmenge (Fitnessfunktion) für die Ameisen.
3) Berechnung der Entfernung von einer Ameise zur anderen.
4) Die Wahl des bevorzugten Ortes, an den die Ameise ziehen wird.
5) Berechnung der Wahrscheinlichkeit eines Punktes auf dem AR-Vektor.
6) Berechnung der Koordinaten des auf dem AR-Vektor erhaltenen Punktes.
7) Wiederholen wir den Vorgang ab Schritt 2, bis die Stoppbedingung erfüllt ist.

Fahren wir mit der Beschreibung des Algorithmus-Codes fort. Zuerst schreiben wir eine Struktur, die eine Beschreibung der Ameise enthält, wobei:

• c [] - Ameisenkoordinaten, 
• cLast [] - vorherige Koordinaten,
• cB [] - beste Koordinaten für alle Iterationen,
• f - aktueller Pheromonwert,
• fB - maximaler Pheromonwert, der in allen Iterationen erreicht wird.

Im Konstruktor der Ameisenstruktur initialisieren wir den Wert von f und fB mit dem kleinstmöglichen Wert, der durch den Typ „double“ dargestellt werden kann.

//——————————————————————————————————————————————————————————————————————————————
struct S_Ants
{
    double cLast  []; //last coordinates
    double c      []; //coordinates
    double cB     []; //best coordinates

    double f;     //pheromone of the current coordinates
    double fB;    //pheromone of the best coordinates

    S_Ants ()
    {
      f  = -DBL_MAX;
      fB = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Wir brauchen eine Struktur, deren Array uns erlaubt, paarweise Abstände zwischen allen Ameisen zu speichern.

struct S_Paths
{
    double a [];
};

Ich werde unseren modifizierten ACO-Algorithmus als Klasse schreiben, in der es nur noch drei öffentliche Methoden gibt, die im Rahmen des entwickelten Konzepts der Konstruktion von Optimierungsalgorithmen, das in früheren Artikeln betrachtet wurde, ausreichend und notwendig sind - InitAnts (), Preparation () und Dwelling (). Außerdem gibt es die privaten Methoden GenerateRNDants () und AntsMovement () sowie weitere private Methoden, die für unsere Algorithmen bereits zum Standard geworden sind. Das Array der Struktur ants [] ist eine Ameisenkolonie.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ACO
{
  public:
  //----------------------------------------------------------------------------
  S_Ants ants      []; //ants
  double rangeMax  []; //maximum search range
  double rangeMin  []; //manimum search range
  double rangeStep []; //step search
  double cB        []; //best coordinates
  double fB;           //pheromone of the best coordinates

  void InitAnts (const int    coordinatesP,       //number of opt. parameters
                 const int    antHillSizeP,
                 double       pheromoneEffectP,
                 double       pathLengthEffectP,
                 double       pheromoneRadiusP,
                 double       pathDeviationP);

  void Preparation ();
  void Dwelling ();

  private:
  //----------------------------------------------------------------------------
  S_Paths paths [];
  int coordinates;        //number of coordinates
  int antHillSize;        //ant hill size

  double goals     [];

  double pheromoneEffect;
  double pathLengthEffect;
  double pheromoneRadius;
  double pathDeviation;
  bool   dwelling;

  void   GenerateRNDants ();
  void   AntsMovement    ();

  double SeInDiSp             (double in, double inMin, double inMax, double step);
  double RNDfromCI            (double min, double max);
  double Scale                (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

In der Initialisierungsmethode weisen wir den Variablen und der Array-Größe Anfangswerte zu.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::InitAnts (const int    coordinatesP,       //number of opt. parameters
                         const int    antHillSizeP,
                         double       pheromoneEffectP,
                         double       pathLengthEffectP,
                         double       pheromoneRadiusP,
                         double       pathDeviationP)
{
  fB = -DBL_MAX;

  coordinates      = coordinatesP;
  antHillSize      = antHillSizeP;
  pheromoneEffect  = pheromoneEffectP;
  pathLengthEffect = pathLengthEffectP;
  pheromoneRadius  = pheromoneRadiusP;
  pathDeviation    = pathDeviationP;

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);

  dwelling = false;

  ArrayResize (ants,  antHillSize);
  ArrayResize (paths, antHillSize);

  for (int i = 0; i < antHillSize; i++)
  {
    ArrayResize (ants  [i].c,      coordinates);
    ArrayResize (ants  [i].cLast,  coordinates);
    ArrayResize (ants  [i].cB,     coordinates);
    ArrayResize (paths [i].a,      antHillSize);
  }

  ArrayResize (cB,    coordinates);
  ArrayResize (goals, antHillSize);
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode Vorbereitung () wird bei jeder Iteration zuerst aufgerufen.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::Preparation ()
{
  if (!dwelling)
  {
    fB = -DBL_MAX;
    GenerateRNDants ();
    dwelling = true;
  }
  else AntsMovement ();
}
//——————————————————————————————————————————————————————————————————————————————

Die Methode GenerateRNDants () ist für die Erstellung einer zufälligen Ameisenkolonie zuständig. Die Ameisenkoordinaten werden innerhalb der vorgegebenen Grenzen zufällig zugewiesen.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::GenerateRNDants ()
{
  for (int s = 0; s < antHillSize; s++)
  {
    for (int k = 0; k < coordinates; k++)
    {
      ants [s].c     [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      ants [s].c     [k] = SeInDiSp (ants [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      ants [s].cLast [k] = ants [s].c [k];
      ants [s].cB    [k] = ants [s].c [k];
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Wir merken uns die aktuellen Koordinaten der Ameisen in der Methode Dwelling()und aktualisieren gleichzeitig die zum Zeitpunkt der aktuellen Iteration ermittelten maximalen Pheromonwerte.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::Dwelling ()
{
  for (int i = 0; i < antHillSize; i++)
  {
    ArrayCopy (ants [i].cLast, ants [i].c, 0, 0, WHOLE_ARRAY);

    //remember the best coordinates for the ant
    if (ants [i].f > ants [i].fB)
    {
      ants [i].fB = ants [i].f;
      ArrayCopy (ants [i].cB, ants [i].c, 0, 0, WHOLE_ARRAY);
    }

    //remember the best coordinates for the anthill
    if (ants [i].f > fB)
    {
      fB = ants [i].f;
      ArrayCopy (cB, ants [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Die Hauptmethode des Algorithmus AntsMovement (). Es führt folgende Aktionen durch: Berechnung der Entfernung von einer Ameise zur anderen, Berechnung der Wahl eines bevorzugten Punktes, an den sich die Ameise bewegen wird, Berechnung der Wahrscheinlichkeit eines Punktes auf dem AR-Vektor. Berechnung der Koordinaten des auf dem AR-Vektor erhaltenen Punktes.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::AntsMovement ()
{
  double rndPh;
  double rndPt;
  double summCoordinates = 0.0;
  double scores [];
  ArrayResize (scores, antHillSize);

  double maxPh = -DBL_MAX;
  double minPh =  DBL_MAX;
  double maxPt = -DBL_MAX;
  double minPt =  DBL_MAX;
  double goal;
  double goalBest = -DBL_MAX;
  int    goalInd  = 0;

  //measure the distance between all the ants-----------------------------------
  for (int i = 0; i < antHillSize; i++)
  {
    for (int k = 0; k < antHillSize; k++)
    {
      if (i == k)
      {
        paths [i].a [k] = DBL_MAX;
        continue;
      }
         
      for (int c = 0; c < coordinates; c++) summCoordinates += pow (ants [i].cLast [c] - ants [k].cLast [c], 2.0);

      paths [i].a [k] = pow (summCoordinates, 0.5);

      if (maxPt < paths [i].a [k]) maxPt = paths [i].a [k];
      if (minPt > paths [i].a [k]) minPt = paths [i].a [k];
    }
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < antHillSize; i++)
  {
    maxPh = -DBL_MAX;
    minPh =  DBL_MAX;

    for (int k = 0; k < antHillSize; k++)
    {
      if (i != k)
      {
        if (maxPh < ants [k].f) maxPh = ants [k].f;
        if (minPh > ants [k].f) minPh = ants [k].f;
      }
    }

    goalBest = -DBL_MAX;
    goalInd  = 0;

    for (int k = 0; k < antHillSize; k++)
    {
      if (i != k)
      {
        rndPh = RNDfromCI (0.0, pheromoneEffect);
        rndPt = RNDfromCI (0.0, pathLengthEffect);

        goal = Scale (ants  [k].f,     minPh, maxPh, 0.0, 1.0, false) * rndPh *
               Scale (paths [i].a [k], minPt, maxPt, 0.0, 1.0, true)  * rndPt;

        if (goalBest < goal)
        {
          goalBest = goal;
          goalInd  = k;
        }
      }
    }
    
    double wayToGoal      = paths [i].a [goalInd];
    double radiusNearGoal = wayToGoal * pheromoneRadius;
    double endWay         = wayToGoal + radiusNearGoal;

    double x = RNDfromCI (-1.0, 1.0);
    double y = x * x;
    
    if (x > 0.0) y = Scale (y, 0.0, 1.0, wayToGoal, endWay,    false);
    else         y = Scale (y, 0.0, 1.0, 0.0,       wayToGoal, true);

    for (int j = 0; j < coordinates; j++)
    {
      double incrementFactor = y / wayToGoal;
      double coordDistance = ants [goalInd].cLast [j] - ants [i].cLast [j];
      
      ants [i].c [j] =  ants [i].cLast [j] + (coordDistance * incrementFactor);
      double w = coordDistance * RNDfromCI (-1.0, 1.0) * pathDeviation;
      ants [i].c [j] += w;
      
      ants [i].c [j] = SeInDiSp (ants [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Es lohnt sich, auf die Funktion der Skalierung einer Zahl von einem Zahlenbereich in einen anderen zu achten. Ich habe bereits in früheren Artikeln darüber nachgedacht. Dieses Mal werde ich seine Funktionsweise erweitern. Wir verwenden den Eingabeparameter revers , um die Skalierungsrichtung zu ändern, wie in der folgenden Abbildung gezeigt.

Abb. 3. Skalierung einer Zahl von einem numerischen Bereich in einen anderen.

1) Direkte Skalierung; 2) Umgekehrte Skalierung

//——————————————————————————————————————————————————————————————————————————————
double C_AO_ACO::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
  else
  {
    if (In < InMIN) return revers ? OutMAX : OutMIN;
    if (In > InMAX) return revers ? OutMIN : OutMAX;

    double res = (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);

    if (!revers) return res;
    else         return OutMAX - res;
  }
}
//——————————————————————————————————————————————————————————————————————————————

4. Testergebnisse

ACO mit der Testfunktion Skin

ACO mit der Testfunktion Forest

ACO mit der Testfunktion Megacity

Es ist also Zeit für Schlussfolgerungen. Zum einen ist der herkömmliche Ameisenkolonie-Algorithmus nicht auf Optimierungsprobleme für den Handel mit Finanzinstrumenten anwendbar. In dem Versuch, die Beschränkungen der konventionellen Version zu umgehen, ist jedoch ein völlig neues Konzept des Ameisenkolonie-Algorithmus entstanden, das eine Weiterentwicklung des ACO ermöglicht. Ein solcher Algorithmus kann bereits auf eine Vielzahl von Problemen angewandt werden, unter anderem auf das Travelling-Salesman-Problem.

Außerdem haben wir jetzt einen neuen Tabellenführer in der Bewertungstabelle. Betrachten wir die Ergebnisse im Detail. Achten Sie zunächst auf die Testergebnisse:

2022.10.27 16:46:28.678    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:46:50.599    Test_AO_ACO (EURUSD,M1)    1 Skin's; Func runs 1000 result: 13.969156176320473; Func runs 10000 result: 13.986949123110085
2022.10.27 16:46:50.599    Test_AO_ACO (EURUSD,M1)    Score1: 0.99502; Score2: 0.99599
2022.10.27 16:47:12.424    Test_AO_ACO (EURUSD,M1)    20 Skin's; Func runs 1000 result: 8.514904198298202; Func runs 10000 result: 11.56159524595023
2022.10.27 16:47:12.424    Test_AO_ACO (EURUSD,M1)    Score1: 0.69826; Score2: 0.86403
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    500 Skin's; Func runs 1000 result: 4.962716036996786; Func runs 10000 result: 6.488619274853463
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    Score1: 0.50498; Score2: 0.58800
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:48:25.999    Test_AO_ACO (EURUSD,M1)    1 Forest's; Func runs 1000 result: 15.805601165115196; Func runs 10000 result: 15.839944455892518
2022.10.27 16:48:25.999    Test_AO_ACO (EURUSD,M1)    Score1: 0.99087; Score2: 0.99302
2022.10.27 16:48:47.897    Test_AO_ACO (EURUSD,M1)    20 Forest's; Func runs 1000 result: 3.568897096569507; Func runs 10000 result: 10.45940001108266
2022.10.27 16:48:47.897    Test_AO_ACO (EURUSD,M1)    Score1: 0.22374; Score2: 0.65571
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    500 Forest's; Func runs 1000 result: 1.3412234994286016; Func runs 10000 result: 2.7822130728041756
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    Score1: 0.08408; Score2: 0.17442
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:50:03.740    Test_AO_ACO (EURUSD,M1)    1 Megacity's; Func runs 1000 result: 11.8; Func runs 10000 result: 11.8
2022.10.27 16:50:03.740    Test_AO_ACO (EURUSD,M1)    Score1: 0.78667; Score2: 0.78667
2022.10.27 16:50:26.002    Test_AO_ACO (EURUSD,M1)    20 Megacity's; Func runs 1000 result: 1.75; Func runs 10000 result: 3.9200000000000004
2022.10.27 16:50:26.002    Test_AO_ACO (EURUSD,M1)    Score1: 0.11667; Score2: 0.26133
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    500 Megacit 's; Func runs 1000 result: 0.6335999999999999; Func runs 10000 result: 1.2312
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    Score1: 0.04224; Score2: 0.08208

2022.10.27 16:49:41.075    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    All score for C_AO_ACO: 0.5468768583006471

Der Algorithmus schnitt bei der kontinuierlichen Skin-Funktion gut ab und zeigte ausgezeichnete Konvergenz und gute Skalierungsfähigkeiten, wobei er bei den Tests mit 20 und 500 Funktionen besonders gut abschnitt. Bei der kontinuierlichen Forest-Funktion mit scharfen Unterbrechungen ist die Trennung noch deutlicher. Der Algorithmus setzt die Suche auch dann fort, wenn er auf lokale Extrema trifft. Bei der diskreten Megacity-Funktion war der Algorithmus nur bei dem Problem mit 500 Funktionen dem Zufalls-RND-Algorithmus überlegen.

AO	Durchläufe	Skin			Forest			Megacity (diskret)			Endgültiges Ergebnis
		2 Parameter (1 F)	40 Parameter (20 F)	1000 Parameter (500 F)	2 Parameter (1 F)	40 Parameter (20 F)	1000 Parameter (500 F)	2 Parameter (1 F)	40 Parameter (20 F)	1000 Parameter (500 F)
ACOm	1000	0.99502	0.69826	0.50498	0.99087	0.22374	0.08408	0.78667	0.11667	0.04224	0.54688
	10,000	0.99599	0.86403	0.58800	0.99302	0.65571	0.17442	0.78667	0.26133	0.08208
RND	1000	0.98744	0.61852	0.49408	0.89582	0.19645	0.14042	0.77333	0.19000	0.14283	0.51254
	10,000	0.99977	0.69448	0.50188	0.98181	0.24433	0.14042	0.88000	0.20133	0.14283
PSO	1000	0.98436	0.72243	0.65483	0.71122	0.15603	0.08727	0.53333	0.08000	0.04085	0.47695
	10,000	0.99836	0.72329	0.65483	0.97615	0.19640	0.09219	0.82667	0.10600	0.04085
PSOm	1000	0.96678	0.64727	0.57654	0.80616	0.13388	0.06800	0.53333	0.08067	0.04211	0.45144
	10,000	0.99505	0.64986	0.57654	0.90401	0.18194	0.07104	0.74667	0.10400	0.04211

Schlussfolgerungen

Der Algorithmus verfügt über eine Vielzahl von Einstellungen, sodass noch bessere Ergebnisse erzielt werden können. Möglichkeit der Anpassung an bestimmte Aufgabentypen. Der erste Parameter PheromoneEffect_P wirkt sich direkt auf die Konvergenzrate aus. Dies ist besonders gut für glatte monotone Funktionen, z. B. eine Parabel. Die Konvergenz liegt bei 100 %, was aber gleichzeitig dazu führt, dass man bei diskreten Funktionen in lokalen Extrema stecken bleibt, wenn man den Wert groß wählt.

Der zweite Parameter PathLengthEffect_P gibt den Grad der Faulheit der Ameisen an. Bei einem hohen Parameterwert werden nähere Ziele für die Bewegung ausgewählt. Um das beste Ergebnis zu erzielen, muss dieser Parameter mit dem ersten abgeglichen werden. Dieser Parameter soll ein Gegengewicht zu dem Bestreben der Ameise bilden, sich zu dem Punkt zu begeben, an dem es mehr Nahrung gibt, und stattdessen manchmal die nächstgelegenen Ziele für eine detailliertere Untersuchung kleinerer Gebiete zu wählen, was sehr nützlich sein kann, wie im Beispiel der Funktion Forest, bei der sich der beste Punkt als sehr nahe liegend erweisen kann.

Die wichtigste Errungenschaft ist, dass es uns gelungen ist, das Hauptproblem des kanonischen ACO zu beseitigen: die Fähigkeit, nur diskrete kombinatorische Probleme zu lösen. Der Ameisenkolonie-Algorithmus kann nun zum Training neuronaler Netze verwendet werden.

Visuell ist der Prüfstand aufgrund einer gewissen Clusterung sehr interessant zu beobachten, die Ameisen konzentrieren sich in den Messungen einer mehrdimensionalen Funktion auf eine bestimmte Art und Weise, die die charakteristischen Gruppen von lokalen Extrema hervorhebt. Vielleicht kann dieser Effekt zur Lösung spezifischer Probleme genutzt werden, aber dazu sind weitere Forschungen erforderlich.

Der Algorithmus hat eine interessante Eigenschaft: Bei der Lösung eines Problems mit zwei Variablen ist die Wahrscheinlichkeit, in einem lokalen Extremum stecken zu bleiben, etwas höher als bei der Optimierung von 40 Variablen. Der Algorithmus sucht weiter nach Lösungen mit mehreren Variablen. Ich nehme an, dass dies der Effekt der Verwendung eines Vektors als Mittel zur Verknüpfung aller Koordinaten des Suchraums ist. Wenn beispielsweise eine Ameise an einen neuen, besseren Ort wechselt, ändern sich alle Koordinaten räumlich zum Besseren, anstatt dass sich einige der Koordinaten einzeln ändern.

Der erstellte Algorithmus ist neu und noch nicht im Detail erforscht, daher wäre ich dankbar, wenn jemand die Einstellungen des Algorithmus mitteilt, bei denen der Prüfstand einen Endwert von mehr als 0,6 anzeigt, sodass ich die Ergebnisse der Tabelle aktualisieren kann. Dieser Antrag bezieht sich auf die bisher berücksichtigten Algorithmen.

Vorteile:
1. Der Algorithmus ist recht schnell.
2. Vielseitigkeit. Der Algorithmus kann für eine Vielzahl von Optimierungsproblemen verwendet werden.
3. Die Fähigkeit, sich nicht nur auf lokale Extrema zu konzentrieren.
4. Ziemlich gute Konvergenz sowohl für kontinuierliche als auch für diskrete Funktionen.
5. Skalierbar.

Nachteile
1. Möglicherweise sind für die Konvergenz mehr Iterationen erforderlich als beim gleichen PSO für glatte Funktionen, aber dies wird teilweise durch die Möglichkeit ausgeglichen, die Suche auch dort fortzusetzen, wo PSO bereits aufgehört hat.
2. Starker Einfluss der Algorithmusparameter auf das Ergebnis.