
Ameisenpfade
Insekten ohne Karte, die Computern das Wegfinden beibringen
✦ Bestätigt
Keine Ameise kennt eine Karte. Trotzdem findet die ganze Kolonie den kürzesten Weg zum Futter. Ein junger Italiener machte aus diesem Trick ein Computerprogramm.
Wer: Jean-Louis Deneubourg, Marco Dorigo · Wann: 1989–1992 · Wo: Brüssel, Belgien und Mailand, Italien
Natur und Erfindung
Ameisen markieren den Weg mit einem Duftstoff, dem Pheromon. Auf dem kürzeren Pfad kehren die Ameisen schneller zurück, also verdichtet sich der Duft und lockt weitere an. Der längere Weg verfliegt langsam.
Ameisenalgorithmen, also Programme, in denen virtuelle Ameisen gute Routen für Lastwagen, Produktionspläne und den Verkehr in Computernetzen suchen.
Die Erzählung
Ende der 1980er-Jahre stellte das belgische Team um Jean-Louis Deneubourg Argentinischen Ameisen eine Aufgabe: Vom Nest zum Futter führten zwei Brücken, eine kurze und eine lange. Anfangs gingen die Ameisen beide Wege gleich oft.
Nach wenigen Minuten hatte fast die ganze Kolonie die kürzere Brücke gewählt. Niemand hatte das angeordnet. Es genügte, dass die Ameisen auf dem kürzeren Weg schneller zurückkehrten und ihn öfter markierten.
Marco Dorigo, Doktorand am Politecnico di Milano, erkannte darin ein fertiges Rezept für schwierige mathematische Aufgaben. 1992 beschrieb er in seiner Doktorarbeit den ersten Ameisenalgorithmus: Virtuelle Ameisen laufen über eine Karte von Städten, hinterlassen einen digitalen Duft, und der Duft verdunstet.
Heute sind Ameisenalgorithmen eine Familie von Optimierungsverfahren. Sie werden für die Planung von Lieferrouten, die Aufgabenverteilung und die Forschung zum Routing in Computernetzen eingesetzt.
Wie es funktioniert
- Geruch: Jede Ameise, die mit Futter zurückkehrt, markiert den Weg. Die nächsten Ameisen bevorzugen Pfade, die stärker riechen.
- Verstärkung: Der kurze Weg wird schneller zurückgelegt, also bekommt er in derselben Zeit mehr Duft. Eine gute Route verstärkt sich selbst.
- Verdunstung: Im Programm verschwindet der Duft langsam. So bleiben die virtuellen Ameisen nicht an der ersten, zufälligen Route hängen und suchen weiter nach einer besseren.
Prüf selbst nach
- Zwei Wege zum Zucker: Lege im Sommer in zwei Entfernungen vom Ameisenpfad einen Tropfen Honig, mit zwei Stöckchen als Brücken: einem kurzen und einem langen. Zähle nach einer Viertelstunde die Ameisen auf jeder Brücke.
- Wisch die Spur weg: Wische mit dem Finger quer über einen Ameisenpfad auf einer Gehwegplatte. Sieh zu, wie die Ameisen an dieser Stelle die Orientierung verlieren und nach dem Duft suchen.
- Ameisen auf Papier: Zeichne fünf Städte auf ein Blatt und suche den kürzesten Weg durch alle. Zähle, wie viele mögliche Routen es gibt. Bei zwanzig Städten sind es mehr als Sandkörner an einem Strand.
Was sicher bekannt ist
Die Brückenversuche beschrieben Goss, Aron, Deneubourg und Pasteels 1989. Den Ameisenalgorithmus schlug Marco Dorigo 1992 vor, und seitdem ist er ein weit verbreitetes Verfahren zur näherungsweisen Lösung von Routenaufgaben. Er liefert nicht immer das beste Ergebnis, aber meist ein gutes, und das schnell.