¶ Ant Colony Optimization
Ant Colony Optimization ist eine Metaheuristik, mit dessen Hilfe sich komplexe Probleme graphbasiert annähernd lösen lassen. Sie basiert auf Ameisenkolonien und deren Verhalten bei der Suche nach Futterquellen.
¶ Kürzeste Wege durch Pheromonspuren
Ameisenkolonien finden ohne fremde Hilfe kürzeste Wege zu Futterquellen. Ameisen hinterlassen Pheromonspuren während sie sich bewegen. Dadurch, dass kürzere Wege schneller zurückgelegt werden, reichert sich der Pheromonwert schneller an als bei längeren Wegen. Dies führt dazu, dass neu startende Ameisen dazu verleitet werden, eben diesen kürzeren Pfad einzuschlagen.
Die Grafik von Jabbarpour et al[1] veranschaulicht das Prinzip: der untere Pfad ist doppelt so lang wie der obere Pfad. Wenn zwei Ameisen zeitgleich über jeweils einen Pfad starten, ist die des oberen Pfads bereits wieder im Nest angekommen, während die andere erst die Futterstelle erreicht. Dadurch hat der obere Pfad bereits die doppelte Pheromonkonzentration.
¶ Pheromonmatrix
Eben dieses Prinzip versuchen Ant Colony Optimization-Algorithmen zu replizieren. Hierfür wird eine globale Pheromonmatrix genutzt, auf denen die verschiedenen Ameisen während den Algorithmeniterationen Zugriff haben und die Entscheidungsfindung der Ameisen leitet. Die Werte der Pheromone verändern sich mit der Zeit, beispielsweise werden Elemente von guten Lösungskandidaten mit extra Pheromonen belohnt. Um frühe Konvergenzen zu vermeiden, gibt es verschiedene Verdampfungsmethoden, die Pheromonwerte reduzieren.
¶ Weiterführende Informationen
Marco Dorigo, der sich als erster wissenschaftlich mit Ant Colony Optimization-Algorithmen beschäftigt hat, hat einen ausführlicheren Artikel in der Scholarpedia verfasst. Das Buch Ant Colony Optimization von Marco Dorigo und Thomas Stützle ist eines der Standardwerke. Ein sehr häufig zitiertes, zwölfseitiges Paper von Marco Dorigo, Thomas Stützle und Mauro Birattari aus IEEE computational intelligence magazine 1.4 (2006): 28-39, ist hier verfügbar.