Beobachte live eine echte Ameisenkolonie-Optimierung (ACO), die Lieferdrohnen-Routen entwickelt, mit echter Pheromonspur-Verstärkung, die über aufeinanderfolgende Kolonien hinweg zu kürzeren Mehrstopp-Routen konvergiert.
Diese Simulation setzt einen echten Ameisenkolonie-Optimierungs-Algorithmus (ACO) für ein Mehrstopp-Lieferdrohnen-Routingproblem ein — eine Drohne muss jeden Lieferpunkt genau einmal besuchen und zur Basis zurückkehren, das klassische Problem des Handlungsreisenden. Statt eine Route zu skripten, pflegt die Seite eine echte Pheromonmatrix τ über jedes Paar von Lieferpunkten. In jeder Kolonie baut jede simulierte Ameise eine vollständige Tour, indem sie wiederholt ihren nächsten unbesuchten Stopp mit einer Wahrscheinlichkeit proportional zu τ(i,j)α · η(i,j)β wählt, wobei η(i,j) = 1/Distanz(i,j) die heuristische Attraktivität eines kurzen Sprungs ist. Sobald jede Ameise der Kolonie ihre Tour beendet hat, verdunstet Pheromon um einen Faktor (1 − ρ), und jede Ameise lagert neues Pheromon proportional zu Q / L auf den Kanten der von ihr gebauten Route ab — sodass kürzere Routen ihre Kanten weit stärker verstärken als lange.
Lässt man das über genügend Kolonien laufen, schärft sich die Spurenkarte sichtbar: schwache, selten genutzte Kanten verblassen zu nichts, während eine Handvoll Kanten — jene, die immer wieder in den kürzesten Touren auftauchen — heller werden, und die bisher beste bekannte Routenlänge (im Live-Diagramm verfolgt) sinkt stetig weiter. Du kannst die Anzahl der Lieferpunkte, die Anzahl der Ameisen pro Kolonie und die Verdunstungsrate ρ live anpassen, ebenso wie die Exponenten für Pheromongewicht α und Distanzgewicht β, die steuern, wie stark Ameisen der Kolonieerfahrung gegenüber der reinen Distanz vertrauen. Nichts hier ist skriptet oder vorgefertigt — jede Kolonie leitet ihre Routen wirklich neu aus dem aktuellen Pheromonzustand und zufälligen Ameisenentscheidungen ab, sodass ein Neustart mit einer neuen Karte oder anderen Parametern jedes Mal eine andere Konvergenzkurve erzeugt.
Was ist Ameisenkolonie-Optimierung und welches Problem löst sie hier?
Ameisenkolonie-Optimierung (ACO) ist eine Metaheuristik, die davon inspiriert ist, wie echte Ameisen mithilfe von Pheromonspuren kurze Wege zwischen Nest und Futter finden. In dieser Simulation löst sie ein Mehrstopp-Lieferrouting-Problem: Eine Drohne muss jeden Lieferpunkt genau einmal besuchen und zur Basis zurückkehren — das klassische Problem des Handlungsreisenden (TSP). TSP ist NP-schwer, sodass es bei mehr als einer Handvoll Stopps unpraktikabel ist, jede mögliche Reihenfolge zu prüfen. ACO lässt stattdessen viele simulierte Ameisen laufen, die probabilistisch Kandidatenrouten aufbauen und diejenigen Kanten verstärken, die tendenziell in kurzen Routen vorkommen, sodass sich die Population von Routen über aufeinanderfolgende Kolonien verbessert, ohne jemals Optimalität zu beweisen.
Wie entscheidet die ACO-Übergangswahrscheinlichkeitsregel, wohin jede Ameise als Nächstes geht?
Bei jedem Schritt wählt eine Ameise, die sich am Lieferpunkt i befindet, ihren nächsten unbesuchten Stopp j mit einer Wahrscheinlichkeit proportional zu [τ(i,j)]^α × [η(i,j)]^β, wobei τ(i,j) das Pheromonniveau auf der Kante (i,j) ist und η(i,j) = 1/Distanz(i,j) die heuristische Attraktivität — nähere Punkte wirken attraktiver. α steuert, wie stark die Ameise der akkumulierten Kolonieerfahrung (Pheromon) folgt, während β steuert, wie stark sie der reinen gierigen Distanz folgt. Die Ameise trifft dann eine gewichtete Zufallsauswahl (Roulette-Rad) unter allen unbesuchten Kandidaten anhand dieser kombinierten Werte, sodass sie meist — aber nicht immer — eine vielversprechende Kante wählt, was die Kolonie weiter erkunden lässt.
Warum verdunstet Pheromon, und was steuert die Verdunstungsrate ρ?
Nachdem jede Kolonie ihre Touren abgeschlossen hat, werden alle Pheromonwerte mit (1 − ρ) multipliziert, bevor neue Ablagerungen hinzugefügt werden. Ohne Verdunstung würde sich Pheromon nur ansammeln, und welche Kanten auch immer früh Glück hatten, würden für immer dominieren — die Suche würde in einer mittelmäßigen Lösung gefangen. Verdunstung lässt schwache oder veraltete Spuren verblassen, sodass die Kolonie weiter alternative Routen erkunden kann. Ein hohes ρ vergisst die Geschichte schnell und erkundet mehr, konvergiert aber langsamer und unruhiger; ein niedriges ρ erinnert sich länger und konvergiert schneller, riskiert aber, sich früh auf eine suboptimale Route festzulegen (vorzeitige Konvergenz).
Nach der Verdunstung lagert jede Ameise in der Kolonie Pheromon der Größe Q / L auf jeder Kante der von ihr gebauten Tour ab, wobei L die gesamte Routenlänge dieser Ameise und Q eine feste Konstante ist. Da die Ablagerung umgekehrt proportional zur Länge ist, verstärkt eine Ameise, die eine kurze Route gefunden hat, ihre Kanten viel stärker als eine Ameise, die eine lange, ineffiziente Route gefunden hat. Über viele Kolonien hinweg verwandelt diese differenzielle Verstärkung eine rein zufällige Suche in eine, die Pheromon — und damit zukünftigen Ameisenverkehr — auf den Kanten konzentriert, die wiederholt in kurzen Routen auftauchen.
Setzt man α = 0, ignorieren Ameisen Pheromon vollständig und verhalten sich wie eine gierige, nächster-Nachbar-artige Heuristik, die nur von η (Distanz) getrieben wird, sodass sich kein Koloniegedächtnis bildet und es kaum Verbesserung über die Zeit gibt. Setzt man β = 0, ignorieren Ameisen Distanz vollständig und folgen nur Pheromon, was dazu führen kann, dass die gesamte Kolonie sehr schnell eine frühe, möglicherweise schlechte Route verstärkt (Stagnation). Die klassische Balance verwendet ein moderates α (etwa 1) mit einem stärkeren β (etwa 2–5), sodass frühe Erkundung distanzbewusst ist, während Pheromon weiterhin gute Strukturen über Kolonien hinweg verstärken kann.
Das Diagramm zeigt die bisher beste gefundene Routenlänge, die per Definition nie schlechter werden kann — es ist ein laufendes Minimum. Es stagniert, wenn keine Ameise in den jüngsten Kolonien die aktuelle Champion-Route übertreffen konnte, was zu erwarten ist: Wenn sich Pheromon auf guten Kanten konzentriert, konvergieren die meisten Ameisen zu ähnlichen Touren, und wirklich neue Verbesserungen werden seltener. Lange Plateaus bedeuten meist, dass sich die Kolonie in der Nähe eines lokalen Optimums für die aktuellen Parameter eingependelt hat; eine Erhöhung der Verdunstungsrate, der Ameisenzahl oder des Erkundungsexponenten β kann sie manchmal wieder lösen, um eine kürzere Route zu finden.
Ein exakter Löser (Branch-and-Bound, dynamische Programmierung oder ganzzahlige Programmierung) kann die wahre kürzeste mögliche Route garantieren, aber seine Laufzeit wächst explosionsartig mit der Anzahl der Stopps — dynamische Programmierung benötigt bereits etwa n²·2ⁿ Operationen, was schon vor n = 30 unpraktikabel wird. ACO gibt die Optimalitätsgarantie zugunsten der Skalierbarkeit auf: Es liefert gute, oft nahezu optimale Routen für viel größere Instanzen bei fester Rechenzeit — genau der Kompromiss, den echte Liefer- und Logistiksysteme eingehen, wenn sie Dutzende oder Hunderte von Stopps routen.