18. Januar 2016

Ameisenalgorithmus

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)

Tags:

Über TUP - Redaktion

TUP - Redaktion

Die Redaktion der DR. THOMAS + PARTNER GmbH & Co. KG hat die Plattform Logistik KNOWHOW ins Leben gerufen, administriert und koordiniert die Beiträge und erstellt selbst Inhalte zu verschiedenen Kategorien. Die Software-Manufaktur DR. THOMAS + PARTNER aus dem Raum Karlsruhe realisiert seit über 35 Jahren maßgeschneiderte Intralogistik-IT-Systeme für nationale und internationale Unternehmen unterschiedlicher Größe und Branche.

  • Website
  • Email

2 Kommentare

  • Kurzmann
    2016-02-15 22:45

    Gratuliere zu diesem spannenden Artikel. Ich habe selbst – gemeinsam mit einem jungen Ameisenforscher – die Absicht, anhand von Ameisenkolonien, einige moderne Methoden in der Logistik und im SCM auszuprobieren. Ich erwarte mir davon einige spezielle Probleme- insbesondere im Bereich komplexer Steuerungsanforderungen – lösen zu können.

    • Andreas Plöger
      2016-02-16 09:29

      Hallo Herr Kurzmann,
      vielen Dank für Ihr positives Feedback. Sollten Ihre Recherchen spannende Erkenntnisse liefern, freuen wir uns auf Ihren Erfahrungsbericht.

Fügen Sie einen Kommentar hinzu

Bitte füllen Sie alle Eingabefelder aus. Die mit Stern markierten Felder sind Pflichtfelder. *