Der Ameisenalgorithmus

Ameisenalgorithmus in der Logistik 

Neben vielen anderen Verfahren zur Optimierung betrieblicher Abläufe hat sich der Ameisenalgorithmus als besonders effektiv erwiesen. Er wird vor allem in der Logistik genutzt, um effektive Wege zu finden und dadurch Kosten einzusparen.

Was ist der Ameisenalgorithmus?

Der Ameisenalgorithmus gehört zu den Verfahren der kombinatorischen Optimierung. Dabei gehört er zu den fortgeschrittenen Verfahren und ist deutlich komplexer und genauer als übliche Verfahren der linearen Optimierung. Vorrangig wird er für die Optimierung der Wege eingesetzt. Die meisten aktuellen Ameisenalgorithmen basieren auf der ACO-Metaheuristik von Marco Dorigo. Hierbei machte er sich das Verhalten von Ameisen bei ihrer Suche nach Futter zum Vorbild. Der gesamte Algorithmus ist stark an dieses natürliche Phänomen angelehnt.

Grundlage des Algorithmus

Ameisen scheiden bei ihrer Suche nach Futter Duftstoffe (Pheromone) aus, um ihren Weg zu markieren. Andere Ameisen bevorzugen Wege mit mehr Pheromonen und wählen daher mit einer höheren Wahrscheinlichkeit an einer Wegegabelung den Weg mit einer höheren Konzentration an Pheromonen aus. In zahlreichen Experimenten hat sich gezeigt, dass Ameisen ein neues Terrain gleichmäßig erkunden. Verbindet man also ein Ameisennest mit einer Futterquelle durch zwei unterschiedlich lange Wege, so werden anfangs beide Wege etwa gleich häufig genutzt. Sämtliche Ameisen bewegen sich mit derselben Geschwindigkeit fort. Daher sind jene Ameisen auf dem kürzeren Weg deutlich schneller am Ziel. Sie wählen für den Rückweg denselben Weg, auf dem sie gekommen sind. Dabei stoßen sie natürlich auch auf dem Rückweg die Pheromone aus. Wenn der längere Weg doppelt so lang wie der kürzere Weg ist, sind die Ameisen des kürzeren Wegs bereits im Nest angekommen, wenn die Ameisen des längeren Weges die Futterquelle gerade erreichen. Dadurch befinden sich auf dem kürzeren Weg doppelt so viele Pheromone wie auf dem längeren. Die nächste Truppe von Ameisen wird also nicht zu gleichen Teilen den kurzen und den langen Weg wählen. Je mehr Zeit vergangen ist, umso wahrscheinlicher ist es, dass eine Ameise den kurzen Weg bevorzugt. Daraus resultiert, dass man nach einiger Zeit beobachten kann, dass sich keine Ameise mehr auf dem längeren Weg befindet und auf dem kurzen Weg eine sogenannte Ameisenstraße entstanden ist. Diese herausragende Wege-Optimierung der Natur wurde bereits 1940 von dem späteren Nobelpreisträger Richard Feynman beobachtet und in einem sehr populären Buch anschaulich beschrieben.

Wie funktioniert der Ameisenalgorithmus?

Dieses natürliche Phänomen überträgt man auf Probleme der Optimierung von Wegen. Man erstellt entweder virtuell auf einem Computer oder manuell auf dem Papier mehrere einfache Akteure. Um das Verfahren etwas zu vereinfachen, hat es sich bewährt, keine genaue Anzahl von Akteuren im Vorfeld zu definieren. Man legt sich eine variabel große Grundmenge an und verteilt die Akteure prozentual gleichmäßig auf die verschiedenen Wege. Als Nächstes legt man eine bestimmte Geschwindigkeit fest, mit welcher sich die Akteure bewegen und ermittelt die Länge aller einzelnen Wege. Letztlich muss man sich Zeitperioden überlegen, welche als kleinste betrachtete Zeiteinheit fungieren. Je kleiner die Zeiteinheit, umso genauer wird der Algorithmus. Das Endergebnis ist jedoch in jedem Fall gleich. Nach einer Zeiteinheit überprüft man, wie viele Akteure auf einem Weg gelaufen sind und wie viele Pheromone sich demzufolge auf den Weg befinden. Der Einfachheit halber wird angenommen, dass jeder Akteur gleichberechtigt ist und dieselbe Menge an Pheromonen hinterlässt. Nach einer gewissen Zeit stellt sich das gleiche Phänomen wie bei den Ameisen ein. Sofern bei einer Wegegabelung die alternativen Wege unterschiedliche Mengen an Pheromonen besitzen, erhöht sich die Menge an Akteuren, die den Weg mit mehr Pheromonen wählen. Nach mehreren Durchgängen tritt das gleiche Ergebnis wie bei den Ameisen auf. Sämtliche Akteure nutzen den gleichen Weg und die Anzahl an Pheromonen steigt ausschließlich auf diesem einen Weg noch an. An diesem Punkt kann man den Algorithmus beenden. Der kürzeste Weg ist gefunden.

Vor- und Nachteile dieses Modells

Der Ameisenalgorithmus hat großen Nutzen für die Logistik. Neben einigen Nachteilen überwiegen die Vorteile besonders für den täglichen Gebrauch. Die größten beiden Nachteile des Ameisenalgorithmus sind seine Komplexität und seine Ungenauigkeit. Im direkten Vergleich mit anderen Verfahren ist er besonders schwierig manuell durchzuführen. Es ist in jedem Fall angeraten, einen Computer als Hilfe zu verwenden. Darüber hinaus kann das Auffinden der idealen Lösung mit diesem Algorithmus nicht garantiert werden. Vielmehr wird lediglich eine der besten Lösungen gefunden. Mehrere Durchgänge können zu unterschiedlichen Ergebnissen führen.

Dennoch reicht die Genauigkeit aus, um vor allem in der Logistik hohe Kosten einzusparen. Der ermittelte Weg ist für den tagtäglichen Einsatz optimal genug, sodass die Kosten der Ermittlung eines besseren Wegs nicht durch die zusätzliche Einsparung aufgewogen werden. Man kann sich also sicher sein, dass es nur wenig Verbesserungspotenzial zum ermittelten Weg gibt.