ANT COLONY SIMULATIONA. Gebert / A. Henke
INHALT
1. Ameisenkolonien in der Natur2. Was ist ACO?3. Anwendungsgebiete4. Algorithmus im Detail5. ACO Live-Demo
AMEISENKOLONIEN IN DER NATUR
Ameisen hinterlassen eine Pheromonspur auf ihrem Weg
Ameisen verwenden die Pheromonspuren zur Wegfindung
Verdichtete Pheromonspuren deuten auf „bessere Wege“ hin
Die einzelne Ameise hat limitierte kognitive Fähigkeiten, die Kolonie besitzt jedoch eine gewisse „Intelligenz“
WAS IST „ACO“ ?
Ant Colony Optimization / Ameisenalgorithmus
Generisches Algorithmus Framework basierend auf dem Verhalten echter Ameisen
Schwarmintelligenz Verschiedene Implementierungen
ANWENDUNGSGEBIETE
Alle diskreten Optimierungsprobleme, für die es einen Mechanismus gibt, der auf Teillösungen aufbauend Schritt für Schritt zur vollständigen Lösung führt.
Statische Probleme TSP (Travelling Salesman Problem) QAP (Quadratic Assignment Problem)
Dynamische Probleme Network Routing
ALGORITHMUS IM DETAIL
Gefundene Lösung ist immer nur eine Annäherung – keine exakte Lösung
Keine Umwelteinflüsse (Algorithmus ist blind)
Ablauf erfolgt in separaten Iterationen von je einer fixen Anzahl Ameisen
Pheromon wird nicht kontinuierlich abgelegt Abgegebene Pheromonmenge abhängig
von der Güte der gefundenen Lösung
ALGORITHMUS IM DETAIL
Enthält Nodes und Node Connections
Connections haben jeweils ein Pheromon Level
Jede Ameise liefert jeweils eine Lösung Lösungen aller Ameisen ergeben eine
Iteration
ALGORITHMUS IM DETAIL
Eine Iteration umfasst: Alle Ameisen suchen einen Weg
Weg-Entscheidung anhand Pheromon, Wegstrecke und Zufallswert
Die gefundene Lösung besteht aus Forward- und Backward Path
Backward Path ist optimiert (loop elimination) Pheromon Update
Alle gefundenen Lösungen werden bewertet Auf den Connections der Lösung wird Pheromon
abgelegt (antiproportional zur Tourlänge bzw. Kosten)
Pheromon Verdunstung
WEG-ENTSCHEIDUNG
?𝒑𝒊𝒋 = ൫𝝉𝒊,𝒋𝜶൯ቀ𝜼𝒊,𝒋𝜷ቁσ൫𝝉𝒊,𝒋𝜶൯ቀ𝜼𝒊,𝒋𝜷ቁ
𝜏𝑖,𝑗 = 𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛 𝐿𝑒𝑣𝑒𝑙 𝑎𝑢𝑓 𝑑𝑒𝑟 𝐶𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑜𝑛 𝑖,𝑗 𝛼 = 𝐺𝑒𝑤𝑖𝑐ℎ𝑡𝑢𝑛𝑔 𝑑𝑒𝑠 𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑠 𝜂𝑖,𝑗 = 𝐾𝑜𝑠𝑡𝑒𝑛 𝑑𝑒𝑟 𝐶𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑜𝑛 𝑖,𝑗 𝛽 = 𝐺𝑒𝑤𝑖𝑐ℎ𝑡𝑢𝑛𝑔 𝑑𝑒𝑟 𝐾𝑜𝑠𝑡𝑒𝑛
PHEROMON UPDATE𝝉𝒊,𝒋 ← 𝝉𝒊,𝒋+ 𝚫 𝝉𝒊,𝒋 ∀ 𝒍𝒊,𝒋 ∈𝝍𝒌 𝑚𝑖𝑡 Δ 𝜏𝑖,𝑗 = Δ 𝜏𝑖,𝑗𝑘 𝑚
𝑘=1 𝑢𝑛𝑑 Δ 𝜏𝑖,𝑗𝑘 = 1𝐽𝜓𝑘 𝑢𝑛𝑑 𝐽𝜓𝑘 = 𝐿ä𝑛𝑔𝑒 𝑑𝑒𝑟 𝑇𝑜𝑢𝑟 𝜓 𝑘 𝑣𝑜𝑛 𝐴𝑚𝑒𝑖𝑠𝑒 𝑘
PHEROMON VERDUNSTUNG𝝉𝒊,𝒋 ← ሺ𝟏 − 𝝆ሻ𝝉𝒊,𝒋 𝒎𝒊𝒕 𝝆∈[𝟎,𝟏] 𝜌 = 𝑉𝑒𝑟𝑑𝑢𝑛𝑠𝑡𝑢𝑛𝑔𝑠𝑓𝑎𝑘𝑡𝑜𝑟 𝜏𝑖,𝑗 = 𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛 𝐿𝑒𝑣𝑒𝑙 𝑎𝑢𝑓 𝑑𝑒𝑟 𝐶𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑜𝑛 𝑖,𝑗
Verhindert schnelles konvergieren hin zu einer suboptimalen Lösung
LIVE-DEMO
Implementierung eines simplen ACO Algorithmus
Lösung des Shortest-Path Problems GUI mit 2D/3D Visualisierung
FRAGEN??
??? :)
ACO PERFORMANCE #1
ACO PERFORMANCE #2
ACO PERFORMANCE #3
ITERATIONS VS. SETTINGS
Recommended
