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.