Schwarmverhalten in der Informatik

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

Die Ameise auf Futtersuche

ein Vorbild aus der Natur

 

Für diesen Optimierungsalgorithmus betrachten wir ein Vorbild aus der Natur: Die Ameise. Ähnlich wie der Handlungsreisende im TSP sucht auch die Ameise nach dem kürzesten Weg. Zwar gibt es für sie nur zwei verschiedene Punkte (Nest und Futterquelle), jedoch auch verschiedene Wege, die dort hinführen, die unterschiedlich lang sind und miteinander verglichen werden müssen. Eine Ameise besitzt jedoch nicht das Denkvermögen, um eine solche Aufgabe einzeln zu bewältigen; dies gelingt nur durch kollektive Intelligenz.

 

 

 

 

 

 

 

(Eine Ameise beim „Melken“ von Läusen; Foto von Böhringer Friedrich)

Die wichtigste Fähigkeit der Ameisen ist der Einsatz von Pheromonen. Sie haben eine Drüse am Hinterleib, welche es ihnen ermöglicht, Lockstoffe abzugeben. Dies tun sie während der Futtersuche die gesamte Zeit über. Andere Ameisen können diese Pheromon-Spur  aufnehmen. Wenn eine Ameise sich zwischen zwei Wegen entscheiden muss, die beide mit Pheromonen gekennzeichnet sind, so wird sie sich mit einer hohen Wahrscheinlichkeit für den Weg entscheiden, auf dem sich am meisten Pheromon befindet.
Auf Grund von diesen Fähigkeiten sind die Tiere in der Lage, den schnellsten Weg zu finden. Sie tun dies folgendermaßen:

 

 

 

 

 

 

 

 

 

 

 

(Futtersuche der Ameisen von Johann Dréo)

  1. Einige Ameisen bewegen sich zufällig auf einem der 4 möglichen Wege und finden das Futter; sie wissen jedoch, nicht welcher der Wege der kürzere ist.
  2. Sie sondern Pheromone ab.
  3. Der längste Weg ist doppelt so lang, wie der kürzeste. Ameise A geht den kürzesten Weg. Ameise B geht den längsten Weg. In der Zeit in der B einmal zum Futter und wieder zurück gelangt ist, hat A den Weg schon zweimal zurückgelegt. Daher ist die Pheromon-Spur deutlich stärker auf dem kürzeren Weg.(Fig. 2 gelb = schwache Pheromon-Spur; orange = starke Pheromon-Spur)
  4. Nachfolgende Ameisen werden sich fast alle für den kürzeren Weg entscheiden, da er mit mehr Pheromonen versetzt ist.(Fig.3)

Fazit:
So finden die Ameisen fast immer den kürzesten Weg zu einer Futterquelle. Diese relativ effiziente Futtersuche gelingt ohne großen Aufwand und setzt kaum Denkvermögen auf Seite der Ameisen voraus. Daher ist dies auch das Vorbild für den Ameisenalgorithmus, der ebenfalls, mit möglichst wenig Rechenaufwand, einen nahezu optimalen Weg finden soll.

 

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