Schwarmverhalten in der Informatik

Nutzen von Schwarmverhalten in Alogrithmen zur Lösung von Problemen in der Informatik

Der Alogorithmus

Von der Natur zum Algorithmus

 

Ich werde im Folgenden den Ameisenalgorithmus(ACO) als heuristisches Lösungsverfahren für  das TSP behandeln. Es gibt auch andere Verwendungszwecke mit einer leicht abgeänderten Version des ACO.

Es soll die kürzeste Route berechnet werden, die alle Punkte(Städte) verbindet. Es gibt n verschiedene Städte, auf die m Ameisen verteilt sind. Jede Ameise wird dargestellt durch eine Liste, die alle bisher besuchten Städte enthält. Diese Liste wird als Tabu-Liste bezeichnet, da jede Ameise während eines Durchgangs nur die Städte besuchen darf, die nicht in ihrer Liste stehen, da sie jede Stadt nur einmal besuchen soll. Der erste Eintrag ist der Startpunkt. Der letzte Eintrag ist die aktuelle Position. Die „Karte“ beziehungsweise der Graph wird folgendermaßen realisiert:
Die einzelnen Städte sind gespeichert. Zudem werden alle möglichen Verbindungen (jeder Punkt kann mit jedem verbunden werden, d.h. es gibt n² Verbindungen) zusammen mit ihrer Länge l und einen Variable i, welches die Pheromon-Intensität darstellt, gespeichert. Der Algorithmus läuft nun in folgenden Schritten ab:

  1. In die (leeren) Tabu-Listen der  m Ameisen wird nun jeweils eine zufällige Stadt eingetragen, da kein Startpunkt vorgegeben ist.
  2. Jede Ameise sucht sich eine Verbindung zu einer noch nicht besuchten Stadt aus. Sie wählt den Pfad mit der höchsten Wahrscheinlichkeit p. Diese Wahrscheinlichkeit ergibt sich aus den Attributen l und i der jeweiligen Verbindung, im Verhältnis zu den anderen möglichen Verbindungen mit der Formel:


  3. ∑.. stellt die Summe aus den Teilwahrscheinlichkeiten für alle k = (aus {mögliche Verbindungen}\k aus {Tabu-Liste})dar.
    Alpha und Beta sind Kontrollvariablen, mit denen man Weglänge und Pheromon-Intensität gewichten kann. Wie die Variable i berechnet wird werde ich im nächsten Schritt erläutern.
    Dieser mathematische Hintergrund muss nicht in jeder Einzelheit nachvollzogen werden. Es ist von essentieller Bedeutung, dass p aus dem Verhältnis der Länge einer Verbindung und der auf ihr vorhandenen Pheromon-Intensität resulitert.

  4. Die m Ameisen sind jetzt alle an einer neuen Stadt angekommen. Nun wird diese Stadt in die Tabu-Liste eingetragen und eine neue Pheromon-Intensität i für alle Verbindungen wird errechnet:

     

    C1 und C2 sind Konstanten, C1 ist der Verflüchtigungsfaktor für das Pheromon, welches sich mit der Zeit abschwächt. C2 ist eine Konstante, mit der die Ergebnisse etwas verändert werden können, um den Ameisenalgorithmus für spezielle Fälle anzupass. Mit den beiden Konstanten lassen sich die alte und die neue Pheromon-Spur gewichten. l ist die Länge der Verbindung und a ist die Anzahl der Ameisen, die über die jeweilige Verbindung gelaufen sind. Als Ergebnis ist festzuhalten, dass sich die neue Pheromon-Spur aus der Kombination der Intensität der alten Spur, der Länge der Verbindung und der Anzahl der Ameisen, die diese Verbindung genutzt haben ergibt.

  5. Schritte 2 und 3 werden n mal wiederholt; dann hat jede Ameise ihre Route beendet. Diese ist durch die Städte der Tabu-Liste gespeichert. Nun wird die kürzeste der m Routen berechnet und gespeichert.
  6. Die Schritte 1-4 werden so oft wiederholt wie vorgegeben (je häufiger desto stärker optimiert ist das Ergebnis). Es gibt die Ausnahme, dass alle Ameisen dieselbe Route verwenden(nicht denselben Startpunkt aber die gleichen Verbindungen). In diesem Fall ist die optimalste Lösung, die der Ameisenalgorithmus finden kann, bereits gefunden.

(ACO von Johann Dréo)

Fig1 stellt die Route einer Ameise dar.
Fig2 stellt die Routen aller Ameisen nach einer Iteration dar.
Fig3 stellt die Pheromon-Intensität auf den Verbindungen, nach mehreren Iterationen dar.
Fig4 stellt die gefundene möglichst optimale Lösung dar.

 

<<vorherige Seite || nächste Seite>>