Ameisenalgorithmen gehören zur Klasse der populationsbasierten Metaheuristiken für Probleme der kombinatorischen Optimierung. Es wird modellhaft nachgebildet, wie Ameisenkolonien in der Natur in der Lage sind, kürzeste Wege zwischen Nest und Futterstellen zu finden und gleichzeitig die Umgebung zu explorieren.
Natürliches Vorbild
Ameisen scheiden bei der Futtersuche bzw. am Heimweg von einer Futterquelle Duftstoffe (Pheromone) aus. Bei der Futtersuche laufen die Ameisen teils zufällig umher (Exploration der Umgebung) folgen aber mit erhöhter Wahrscheinlichkeit den Pheromonspuren anderer Ameisen. Auf diese Weise können sie gemeinsam den kürzesten Pfad zwischen Nest und Futterquelle finden.
Funktionsweise
Ant Colony Optimization (ACO) ist eine populationsbasierte Metaheuristik, bei der künstlichen Ameisen kombinatorische Optimierungsprobleme näherungsweise lösen.
Jede künstliche Ameise konstruiert eine vollständige Lösung, wobei sie durch heuristische Informationen (Prioritätsregel) sowie die historische Erfahrung der Ameisenkolonie geleitet wird. Letztere ist in einer künstlichen Pheromonmatrix abgespeichert und wird meist multiplikativ mit der Prioritätsregel verknüpft. Auf diese Weise ergibt sich die Auswahlwahrscheinlichkeit für die nächste Entscheidung (Roulette Wheel).
Nachdem alle Ameisen ihre Lösungen konstruiert haben, werden diese anhand der Zielfunktion evaluiert. Gute Entscheidungen werden in der Pheromonmatrix verstärkt; andere Pheromonwerte werden reduziert (Verdampfung). Die diversen Ameisenalgorithmen unterscheiden sich in der Art und Weise der Lösungskonstruktion und insbesondere des Pheromonupdates.
Varianten
Nachdem Marco Dorigo [Dorigo 1992] den ersten Ameisenalgorithmus (Ant System, AS) vorgestellte, wurde eine Reihe von verbesserten Varianten entwickelt. Die rascheste Variante ist das Ant Colony System (ACS), bei dem das Roulette Wheel meist durch die wahrscheinlichste Wahl ersetzt wird, und die Exploration durch lokale Verdampfung gewährleistet wird. Die besten Ergebnisse erzielt tendenziell das Max-Min Ant System (MMAS), bei dem Ober- und Untergrenzen für die Pheromonwerte die Balance zwischen Exploration und zielgerichteter Suche sicherstellen [Stützle/Hoos 2000]. Das rank based AS bietet einen guten Kompromiss zwischen Geschwindigkeit und Lösungsgüte [Bullnheimer/Hartl/Strauss 1999]. Einen aktuellen Überblick über findet man in [Dorigo/Stützle 2004]
Literatur
Bullnheimer, Bernd; Hartl, Richard F.; Strauss, Christine: An improved Ant System algorithm for the Vehicle Routing Problem, Annals of Operations Research 89, 319–328, 1999.
Dorigo, Marco: Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italien, 1992.
Dorigo, Marco; Gambardella, Luca Maria: Ant Colony System.
IEEE Transactions on Evolutionary Computation 1(1), 53–66, 1997.
Dorigo, Marco; Stützle, Thomas:
Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
Stützle, Thomas; Hoos, H.H.: MAX–MIN Ant System.
Future Generation Computer Systems, 16(8), 889–914, 2000.
