Der Ameisenalgorithmus, in der Literatur auch häufig Ant Colony Optimization (ACO) genannt, ist ein Algorithmus zur näherungsweisen Lösung von komplexen Optimierungsproblemen. Dieses, auch als Metaheuristik bezeichnete Verfahren der kombinatorischen Optimierung orientiert sich dabei an Verhaltensweisen von Ameisen bei ihrer Futtersuche.

Inspiriert ist das Modell, wie der Name schon sagt, von der Natur. Die Ameise läuft einfach los und sucht nach Futter. Ihren Weg markiert sie dabei mit flüchtigen Duftstoffen, zum einen, damit Sie den Rückweg wiederfindet, zum anderen, dass andere Ameisen bei Erfolgsmeldung ihrem Weg zum Futter folgen können. Findet eine andere Ameise jetzt einen kürzeren Weg, sind die Duftstoffe auf deren Route entsprechend intensiver, da die Freisetzung weniger lange zurück liegt. Folglich orientieren sich nachfolgende Ameisen an diesem Pfad, was die Duftspur zusätzlich intensiviert.
Ist der ursprünglich schnellste Weg plötzlich blockiert, kann anhand der zurückkehrenden Ameisen und der Intensität deren Duftspuren wieder der schnellste Weg ermittelt werden. So kann innerhalb kurzer Zeit der beste Weg gefunden und für alle nachvollziehbar kommuniziert werden – ohne eine übergeordnete Koordination.

Von der Natur in die Industrie

Bereits in den neunziger Jahren beschäftigten sich Forscher damit, dieses Know-how der Natur in die Industrie zu überführen. Heute kommt der Ameisenalgorithmus in vielen Szenarien zum Einsatz, wie beispielsweise der Routenoptimierung in Produktion und Intralogistik, der Schaltung von Kommunikationskanälen wie Telefon und Internet oder dem Transportmanagement in der Logistik.

 

 

Gemein haben alle diese Einsatzgebiete, dass die hochkomplexe Routenplanung nicht aufwändig berechnet und zentral koordiniert wird, sondern jedes involvierte Objekt selbstständig entscheidungs- und handlungsfähig ist und sich auf Grundlage des Algorithmus und der aktuellen Daten der anderen Objekte für die optimale Lösung entscheidet.

Ameisenalgorithmus in Intralogistik und Produktion

Der innerbetriebliche Materialfluss ist ein komplexes Geflecht mit unzähligen Einflussfaktoren wie beispielsweise Auftragseingang, Streckenbelegung, Cut-off-Zeit, Warenverfügbarkeit oder Maschinen- und Personalverfügbarkeit. Je mehr Variablen und Parameter in einen Steuerungsablauf einfließen, desto komplexer wird dessen mathematische Berechnung.

Verschiedene mathematische Methoden erlauben diese Berechnungen, wobei hier zwischen exakten Berechnungen und Heuristiken (analytisches Vorgehen auf Grundlage von wahrscheinlich eintretenden Szenarien) unterschieden werden kann. Während die exakten Berechnungen ein hundertprozentig zuverlässiges Ergebnis liefern, ermöglichen sogenannte Metaheuristiken, wie der Ameisenalgorithmus, nur ein wahrscheinlich bestes Ergebnis. Vorteil der heuristischen Methode ist allerdings der wesentlich geringere Berechnungsaufwand, der nur den Bruchteil des Aufwands einer exakten Berechnung erfordert.

„In der Planungsphase eines Logistikprozesses, in der Zeit nicht die größte Rolle spielt, kann und sollte man mit so vielen exakten Methoden wie möglich arbeiten“, erklärt Mathematiker Thomas Runkler in einem Interview mit der brand eins. Treten im Betrieb jedoch unvorhergesehene Situationen auf, gehe es darum, möglichst schnell zu reagieren. „Und da sind die Ameisen eben näher am realen Leben.“

So ermöglichen diese Verfahren der kombinatorischen Optimierung einen dynamischen Materialfluss, der sich den aktuellen Begebenheiten selbstständig anpasst. Speziell im Kontext der Industrie 4.0-Entwicklungen geht der Trend daher in einigen Bereichen hin zu einer dezentralen Steuerungsintelligenz, die auch eine Grundlage für die Smart Factory und verschiedene cyber-physische Systeme bietet.

Informationen zur Simulation von intralogistischen Systemen finden Sie unter Materialflusssimulation.

 

Bildquelle: © fdecomite / Lizenz (CC BY 2.0)

Also available in English (Englisch)