A. Gebert / A. Henke. 1. Ameisenkolonien in der Natur 2. Was ist ACO? 3. Anwendungsgebiete 4....

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“

AMEISENKOLONIEN IN DER NATUR

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