Matheseitenüberblick

Der Ameisenalgorithmus

Auf dieser Seite finden Sie eine animierte Simulation zum sogenannten Ameisenalgorithmus. Bekanntlicherweise laufen Ameisen auf selbstgewählten Straßen. Höchstwahrscheinlich bilden sich diese Straßen heraus, weil Ameisen spezielle Duftstoffe (Pheromone) am Boden hinterlassen, durch die andere Exemplare dann verleitet werden, den gleichen Weg einzuschlagen. Diese Pheromone verlieren nach einiger Zeit (hier angenommen exponentiell) die Wirkung, so daß die Ameisen bevorzugt einen Weg einschlagen, den zuvor möglichst viele andere gegangen sind.

Man kann hier ein Feld mit 4 bis 16 Stationen bzw. Knotenpunkten erzeugen lassen oder die Koordinaten der Stationen selbst eingeben. Dazu mit der rechten Maustaste auf die Schaltfläche [Neues Feld] klicken. Diese Knotenpunkte lassen sich dann mit der Maus einzeln oder zusammen verschieben. Die wählbar 100 bis 10000 Ameisen starten entweder alle vom gleichen Feld oder verteilt und laufen dann jeweils auf gerader Verbindungslinie von einem Knoten zu einem anderen. Setzen Sie den Haken bei Krabbeln zum Starten der Animation. Jede Ameise hat ihr eigenes Tempo (zufällig mit einstellbarer Standardabweichung um den Mittelwert von 1 px/step gestreut) und ihre eigene Farbe und darf erst dann wieder zu ihrem Startplatz zurückkehren, wenn sie vorher alle anderen Stationen abgewandert hat. (Das Animationstempo kann bis 50 px/step gesteigert werden. Der Pheromonkonzentrationsabbau wird dabei entsprechend angeglichen.) Nach nicht allzulanger Zeit bildet sich ein gemeinsamer Rundweg heraus, der bei günstigen Einstellungen auch der tatsächlich kürzeste ist oder jedenfalls nahe daran. (Das kann als Resultat einer durch einen primitiven Regelmechanismus erzeugten Schwarmintelligenz betrachtet werden.)

Der Ameisenalgorithmus bietet insofern eine Lösung des sogenannten Handlungsreisendenproblems. Jener gedachte Handlungsreisende muß eine Rundreise zu n-1 Zielen und zurück unternehmen und möchte dabei nach Möglichkeit die kürzeste Route wählen.

Der Wert bei Anarchie ist die Wahrscheinlichkeit, mit der sich eine Ameise an einem Knoten völlig zufällig für einen Weg entscheidet. Andernfalls wird sie von den Pheromonkonzentrationen an den einzelnen Pfaden beeinflußt und zwar in einem einstellbaren Zusammenhang. Man kann beobachten, daß ein proportionaler Wirkzusammenhang zwischen Konzentration und Entscheidungswahrscheinlichkeit nicht den erwünschten Effekt hat. Wie schnell die Pheromone verfliegen, kann über deren Halbwertszeit bestimmt werden. (Wie oben bereits erwähnt, wurde hier ein einfaches exponentielles Modell des Konzentrationsrückgangs gewählt, das vermutlich nicht vollkommen unrealistisch ist, wenngleich in der Wirklichkeit der Rückgang zu Beginn eher flacher sein dürfte.) Die jeweiligen Pheromonkonzentration der Pfade werden an den Knotenpunkten durch grüne Streifen repräsentiert, je größer der Streifen, desto mehr Pheromon ist da. Geht man mit dem Mauszeiger auf den Knoten (nicht klicken), wird unten links ein Histogramm der Verteilung von Pheromonen (blaue Balken) und Wahrscheinlichkeiten für diesen Knoten angezeigt.

Die zusätzliche Option, daß ein langer gerade zurückgelegter Weg nachteiligen Einfluß auf die Pheromonausschüttung am erreichten Knoten habe, entspricht vermutlich nicht der Wirklichkeit. Ich habe das hier dennoch eingebaut, denn man kann ja vermuten, daß es auch so funktioniert... Vielleicht freut sich übrigens eine Ameise eher umso mehr, wenn sie nach langem Marsch zum Ziel gelangt. Daher sind auch negative Werte möglich, so daß ein längerer Weg zu höherer Pheromonausschüttung führt und die Artgenossen auf diese Fährte lockt. Kontraproduktiv, will man meinen.

Im unteren Teil des Einstellungsfensters befinden sich Statistiken über die durchschnittlich pro Ameise zurückgelegte Länge eines Rundgangs und das im Vergleich zur berechneten oder geschätzten tatsächlich optimalen Route, die auch eingeblendet werden kann. Bis n=9 oder n=10 (je nach Tempo des Rechners) werden diese Routen automatisch berechnet, ansonsten kann man das manuell veranlassen, wobei Sie vorher noch über die geschätzte Berechnungszeit informiert werden und das dann nochmal bestätigen müssen. Der Algorithmus für eine zumindest gute Streckenführung ohne brute-force Durchrechnung aller Möglichkeiten (die unternommen wird, wenn man die Schaltfläche betätigt) ist meinem Hirn entsprungen und scheint gar nicht so schlecht zu sein :-). Wie auch immer: Wenn die per Option anzeigen eingeblendete beste Route nur gelb hinterlegt ist, ist es die auf diese Weise gefundene, nur wenn sie einen grünen Mittelstreifen aufweist, ist sie definitiv optimal kurz.

 
6 Stationen
ringförmig

1000 Ameisen
Start: verteilt
Tempostreuung σ=0,1

Krabbeln  

Animation: 10 px/step

Anarchie: 5%

Halbwertszeit der Pheromone:
50 steps

Pher.-Konzentr. → Wirkung:
proportional quadratisch
3. Potenz

Langer Weg als Nachteil: 0%

∅ Länge: ?
  t13

Beste Route
  anzeigen
   

graphisch

Anmerkungen

Man exerimentiere mit verschiedenen Einstellungen, um herauszufinden, wie der optimale Rundgang am schnellsten (oder überhaupt) gefunden wird. Die Starteinstellung ist bewußt nicht optimal, insbesondere stellte sich bei vielen Experimenten selbst ein quadratischer Einfluß der jeweiligen Pheromonkonzentrationen auf die Entscheidungswahrscheinlichkeitsverteilung als viel zu schwach heraus. (Bei negativen Exponenten haben die Pheromone abweisende Wirkung.) Daß sehr lange Halbwertszeiten nicht vorteilhaft sein können, versteht sich, denke ich, von selbst. Auch eine zu große Zahl umherschweifender Ameisen scheint nicht vorteilhaft. Am interessantesten finde ich, wie sich Individualismus (einstellbar mit Anarchie und Tempostreuung, letzteres nur vor dem Start) auf die Schwarmintelligenz auswirkt. Es ist eine Herausforderung, optimale Werte zu finden und den mit den evolutionär optimierten Gegebenheiten der Natur zu vergleichen, soweit die hier implementierten mathematischen Modelle, etwa das exponentielle Verduften der Pheromone, einen Vergleich mit natürlichen Gegebenheiten zulassen.

Ich schrieb das Programm vor einigen Jahren (2016) in Visual-Basic 5 für eine Projektwochenaufbereitung eines Biologie-Leistungskurses. Leider hat die Lehrerin das Programm meines Wissens nicht eingesetzt. Die Übersetzung nach html5 rettet es zumindest in die Gegenwart, da auf den meisten aktuellen Rechnern VB5-Programme nicht mehr ohne weiteres laufen, und ermöglicht ihm so vielleicht noch ein paar Jahre, auf daß eventuell ein paar Menschen daran Gefallen finden und mir das gerne auch entsprechend mitteilen dürfen.

© Arndt Brünner, 18. 10. 2020
Version: 19. 10. 2020
(Ursprüngliche VB5-Version: 26. 10. 2016)