Von DORIGO, MANIEZZO, COLORNI stammt der Ansatz, die Ameisen das TSP lösen zu lassen. Nein, keine richtigen Ameisen, obwohl das wahrscheinlich auch möglich wäre. Es geht um simulierte Ameisen

Aus irgendeinem Grund schaffen es Ameisen, die kürzeste Verbindung zwischen zwei oder mehreren Punkten zu finden. Was liegt dem zu Grunde? Folgendermaßen wird das erklärt:

Ameisen richten sich nicht nur nach örtlichen Gegebenheiten, sondern auch besondes nach Duftspuren, die von ihren Kollegen hinterlassen werden.

Weiterhin laufen Ameisen von einer Stelle (z.B. Futter) zu einer zweiten (z.B. Nest) und zurück. Wenn auf diesem Weg plötzlich ein Hindernis auftaucht, werden die Ameisen, die dieses Hindernis zuerst erreichen, einen zufälligen Weg links oder rechts daran vorbei wählen. Auf beiden Wegen werden es auch die Ameisen von der Gegenseite versuchen. Da die Ameisen auf dem kürzeren Weg eher auf ihre Kollegen von der anderen Seite treffen, addiert sich ihre Duftspur zu der, die diesen Weg in die entgegengesetze Richtung nahmen.

Die von dort folgenden Ameisen richten sich aber jetzt danach, woher der stärkere Duft kommt, und das ist von dem kürzeren Weg. So wird sich die Duftspur des längeren Weges bald verlieren.

Kann man das nicht für das TSP verwenden?
Man stelle sich vor, jede Stadt wird von einigen Ameisen besetzt. In jedem Schritt wird eine Ameise zufällig eine Stadt auswählen, zu der sie marschiert. Sie darf sich jedoch keine Stadt aussuchen, die sie in dieser Runde schon besucht hat. Nachdem jede Stadt besucht wurde, ist diese Runde zu Ende.

Jetzt erfolgt eine Bewertung der verschiedenen Touren. Jede Strecke einer Tour, die zu einer Tour mit niedrigen Kosten führte, bekommt eine bessere Bewertung als Strecken, die zu Touren mit hohen Kosten führten. Jetzt geht es auf zu einer neuen Runde. Nur, daß die Ameisen die Strecken jetzt nicht mehr zufällig aussuchen, sondern lieber die Strecken benutzen, die in den letzten Runden eine höhere Berwertung hatten.

Nach einer gewissen Anzahl von Runden benutzen fast alle Ameisen die selben Strecken. Eine annähernd optimale Tour ist gefunden worden.

Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-12-1996