Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet

Stigmergie, das Doppelbrückenexperiment, Dorigos Ameisensystem, die Rolle der Parameter α, β und ρ und verbesserte Varianten — auf einer Rundreise durch die Regionalhauptstädte und auf 60 Städten, im Vergleich mit der simulierten Abkühlung.

13 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 29 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Eine einzelne Ameise hat keine Karte, kann nicht rechnen und sieht kaum ein paar Zentimeter weit. Trotzdem findet die Kolonie zuverlässig den kürzesten Weg vom Nest zur Nahrung. Keine Ameise kennt ihn — er entsteht daraus, wie alle gemeinsam das Gelände markieren. Anfang der Neunzigerjahre bemerkte Marco Dorigo vom Politecnico di Milano, dass sich derselbe Trick auf das Problem des Handlungsreisenden anwenden lässt. So entstand die Ameisenkolonieoptimierung und mit ihr das ganze Gebiet der Schwarmintelligenz.

Der Artikel knüpft an Lokale Suche und simulierte Abkühlung an. Wir lösen dieselbe Aufgabe — eine Rundreise durch die Regionalhauptstädte mit dem Optimum 1 060,4 km —, und so sehen wir, wie sich die Ameisen gegen die simulierte Abkühlung schlagen.

1. Kommunikation über Spuren

Definition — Stigmergie

Eine Gruppe von Individuen (z. B. die Ameisen einer Kolonie) teile eine gemeinsame Umgebung, deren Zustand sich ändern kann. Stigmergie ist eine Art der Koordination dieser Individuen, bei der alle drei Bedingungen gelten:

1. ein Individuum verändert durch seine Tätigkeit den Zustand der Umgebung — es hinterlässt darin eine Spur (z. B. Pheromon);
2. der veränderte Zustand der Umgebung beeinflusst, was die anderen Individuen oder es selbst später tun;
3. die Individuen geben einander Information nicht direkt weiter (durch ein Signal von Individuum zu Individuum), sondern nur über den Zustand der Umgebung.

Stigmergie ist also indirekte Kommunikation über die Umgebung. Den Begriff prägte Pierre-Paul Grassé 1959 bei der Untersuchung des Termitenbaus.

2. Das Doppelbrückenexperiment

1989 bauten Goss, Deneubourg und ihre Kollegen Argentinischen Ameisen zwischen Nest und Nahrung zwei Brücken — eine doppelt so lang wie die andere. Nach einer Weile lief der Großteil der Kolonie über die kürzere. Warum? Eine Ameise, die den kurzen Zweig wählt, erreicht die Nahrung früher, und wenn sie zurückkehrt, ist der kurze Zweig an der Nahrung schon markiert. Der kurze Weg wird schneller markiert und beginnt zu gewinnen.

Definition — Modell der Zweigwahl (Deneubourg u. a.)

Zwischen Nest und Nahrung mögen zwei Zweige führen, ein kurzer und ein langer. Seien A ≥ 0 und B ≥ 0 die Pheromonmengen am Anfang des kurzen und des langen Zweigs in dem Moment, in dem eine Ameise an die Gabelung kommt, und seien k > 0 und h > 0 Parameter des Modells. Die Ameise wählt den kurzen Zweig mit der Wahrscheinlichkeit

P(A, B) = (k + A)^h/(k + A)^h + (k + B)^h

und den langen Zweig mit der Wahrscheinlichkeit 1 − P(A, B). Die Ameise legt eine Einheit Pheromon an den Anfang des gewählten Zweigs und eine weitere an sein Ende, wenn sie dort ankommt.

Der Parameter k bestimmt also, wie stark eine Ameise auf eine schwache Spur reagiert (je größer k, desto weniger), und h > 1 verstärkt Unterschiede zwischen den Zweigen; bei A = B ist P = 1/2.

P = (k + A)^h/(k + A)^h + (k + B)^h

P

die Wahrscheinlichkeit, dass die nächste Ameise den kurzen Zweig nimmt — die Ameise entscheidet nicht sicher, nur mit einem Gewicht; der lange Zweig bekommt den Rest 1 − P

A

Pheromon auf dem kurzen Zweig — das Einzige, was die Ameise über den Weg „weiß“; je mehr davon dort liegt, desto stärker zieht der kurze Zweig

B

Pheromon auf dem langen Zweig — im Nenner konkurriert es mit dem kurzen, also entscheidet das Verhältnis der Spuren, nicht ihre absolute Menge

k

eine „Aufmerksamkeitsschwelle“ — wird zu beiden Zweigen gleich addiert, sodass die ersten paar Pheromonmoleküle das Verhältnis kaum ändern; ohne sie würde die erste Ameise über die ganze Kolonie entscheiden

h

der Verstärker — eine Potenz größer als 1 übertreibt den Unterschied; gerade sie macht aus einem kleinen zufälligen Vorteil eine positive Rückkopplung

Beispiel — wie k = 30 und h = 2 entscheiden

Auf dem kurzen Zweig liegen A = 20, auf dem langen B = 10 Einheiten Pheromon:

P = (30 + 20)²/(30 + 20)² + (30 + 10)² = 2 500/2 500 + 1 600 = 2 500/4 100 ≈ 0,610

(Farben nach der Formel oben.)

• Gleiche Spuren (A = B, etwa beide null): P = 0,500 — reiner Zufall.
• Fünf Einheiten gegen null: P = (30 + 5)²/(30 + 5)² + (30 + 0)² = 35²/35² + 30² ≈ 0,576 — eine kleine Spur entscheidet kaum etwas, das ist das Werk von k.
• A = 60, B = 10: P = 8 100/8 100 + 1 600 ≈ 0,835 — schon eine klare Überlegenheit.
• Ohne Verstärkung (h = 1) ergäbe sich bei A = 20, B = 10 nur 50/90 ≈ 0,556 statt 0,610.

Eine Simulation des Modells (k = 30, h = 2, zehn Ameisen pro Schritt, kurzer Zweig 5 Schritte, langer 10) zeigt den Pheromonanteil auf dem kurzen Zweig bei acht Kolonien:

Sieben Kolonien pendelten sich auf dem kurzen Zweig ein, eine auf dem langen: Die ersten paar Ameisen wählten zufällig den langen Zweig, und die positive Rückkopplung hat ihn „verriegelt“. Von hundert Kolonien endeten 85 auf dem kurzen Zweig und 9 auf dem langen. Sind beide Zweige gleich lang, teilen sich die Kolonien ungefähr zur Hälfte auf (46 und 42) — die Symmetrie bricht der Zufall. Die Länge des Weges verschiebt also das Ergebnis, garantiert es aber nicht. Dieselbe Schwäche werden wir beim Algorithmus sehen.

3. Das Ameisensystem

Dorigos Ameisensystem (Ant System, 1992) schickt virtuelle Ameisen über einen Graphen von Städten. Jede baut eine vollständige Rundreise und legt, je nachdem wie kurz sie ist, Pheromon auf deren Kanten.

Definition — Rundreise und ihre Länge

Sei n ∈ ℕ, n ≥ 3, die Anzahl der Städte; wir bezeichnen die Städte mit den Zahlen 1, …, n, und für alle i, j ∈ {1, …, n}, i ≠ j, sei eine Entfernung d_ij ∈ ℝ gegeben mit d_ij = d_ji > 0.

1. Eine Rundreise ist ein geordnetes n-Tupel π = (π₁, …, π_n), in dem jede Stadt genau einmal vorkommt, d. h. {π₁, …, π_n} = {1, …, n} (π ist eine Permutation der Städte). Zur kürzeren Schreibweise setzen wir π_n+1 = π₁.
2. Die Länge der Rundreise π ist die Zahl L(π) = ∑_k=1ⁿ d_πkπk+1 = d_π1π2 + d_π2π3 + … + d_πnπ1; der letzte Term bringt den Reisenden nach Hause zurück.
3. Eine Kante (i, j) gehört zur Rundreise π genau dann, wenn es ein k ∈ {1, …, n} gibt mit {π_k, π_k+1} = {i, j}.
4. Das Problem des Handlungsreisenden ist die Aufgabe, eine Rundreise π^* zu finden, sodass L(π^*) ≤ L(π) für jede Rundreise π.

Eine Rundreise durchläuft also jede Stadt genau einmal und kehrt zur Ausgangsstadt zurück; eine Kante gehört zu ihr genau dann, wenn ihre beiden Städte darin direkt aufeinander folgen.

Definition — Übergangsregel

Gegeben seien die Städte 1, …, n mit Entfernungen d_ij > 0 (siehe die Definition der Rundreise oben), auf jeder Kante (i, j) Pheromon τ_ij > 0 und Parameter α ≥ 0, β ≥ 0. Die Sichtbarkeit der Kante (i, j) ist die Zahl

η_ij = 1/d_ij.

Eine Ameise stehe in der Stadt i, und N_i ⊆ {1, …, n} sei die nichtleere Menge der Städte, die sie auf ihrer Rundreise noch nicht besucht hat. Die Ameise geht in die Stadt j mit der Wahrscheinlichkeit

p_ij = τ_ij^α · η_ij^β/∑_{l ∈ Ni} τ_il^α · η_il^β   für j ∈ N_i,   p_ij = 0   für j ∉ N_i.

Die Ameise wählt also nur unter den unbesuchten Städten, und zwar mit einem Gewicht proportional zum Produkt aus der Spur τ_ij^α und der Sichtbarkeit η_ij^β (nahe Städte sind verlockender); die Parameter α und β gewichten die Spur gegen die Entfernung. Die Wahrscheinlichkeiten p_ij über j ∈ N_i haben die Summe 1.

p_ij = τ_ij^α · η_ij^β/∑_{l ∈ Ni} τ_il^α · η_il^β

p_ij

die Wahrscheinlichkeit eines Schritts von i nach j — wir losen, statt das Beste zu nehmen, damit die Kolonie immer auch andere Rundreisen ausprobiert

τ_ij^α

das Gedächtnis der Kolonie — Pheromon trägt die Erfahrung früherer Ameisen; der Exponent α sagt, wie sehr man ihr traut (α = 0 schaltet sie ganz ab)

η_ij^β

Gier — η = 1/d bevorzugt nahe Städte; ein Rat, den wir gratis gleich ab der ersten Iteration haben, wenn das Pheromon noch nichts weiß

∑ … über N_i

die Summe der Gewichte aller noch unbesuchten Städte — durch die Division werden aus Gewichten Wahrscheinlichkeiten mit Summe 1; besuchte Städte sind nicht darin, also kehrt die Ameise nicht zu ihnen zurück

Beispiel — eine Entscheidung einer Ameise

Eine Ameise steht in der Stadt i und hat noch drei Städte übrig: in 50, 100 und 150 km Entfernung, mit Pheromon τ = 1, 3 und 2. Die Konstante in der Sichtbarkeit kürzt sich im Bruch weg, rechnen wir also mit η = 100/d, also 2, 1 und 2/3. Mit α = 1 und β = 3 (Farben nach der Formel oben):

• Gewichte τ^α · η^β: 1 · 2³ = 8,000, 3 · 1³ = 3,000, 2 · (2/3)³ ≈ 0,593;
• ihre Summe 11,593;
• Wahrscheinlichkeiten p = 8,000/11,593 ≈ 0,690, 3,000/11,593 ≈ 0,259 und 0,593/11,593 ≈ 0,051.

Die nächstgelegene Stadt gewinnt, obwohl sie am wenigsten Pheromon hat. Mit β = 1 ergäbe sich 0,316, 0,474 und 0,211 — das Pheromon führt. Und mit β = 0 entscheidet nur die Spur: 0,167, 0,500 und 0,333 (Verhältnis 1 : 3 : 2).

Definition — Pheromon-Aktualisierung

Sei ρ ∈ (0, 1) die Verdunstungsrate und Q > 0 eine Konstante. In einer Iteration mögen M ≥ 1 Ameisen die Rundreisen π⁽¹⁾, …, π^(M) gebaut haben (Rundreise m ist π^(m)) mit den Längen L_m = L(π^(m)), m = 1, …, M. Nach der Iteration wird das Pheromon auf jeder Kante (i, j) ersetzt durch

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ Rundreise m} Q/L_m,

wobei über alle m ∈ {1, …, M} summiert wird, für die die Kante (i, j) zur Rundreise π^(m) gehört (eine leere Summe ist 0). Das Pheromon verdunstet also überall um den Anteil ρ, und jede Ameise m fügt auf den Kanten ihrer Rundreise die Menge Q/L_m hinzu, umgekehrt proportional zur Länge der Rundreise.

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ Rundreise m} Q/L_m

τ_ij links

das neue Pheromon auf der Kante — das, wonach sich die Ameisen der nächsten Iteration richten werden

(1 − ρ)

Verdunstung — jede Iteration nimmt jeder Spur denselben Anteil ρ weg; alte Erfahrung verblasst so geometrisch, und die Kolonie kann umlernen

τ_ij rechts

das bisherige Pheromon — das Gedächtnis wird nur korrigiert, man fängt nicht bei null an

∑_m

Summe über die Ameisen, die die Kante benutzt haben — jede Ameise fügt nur auf den Kanten ihrer Rundreise hinzu; eine Kante, die mehr Ameisen benutzen, bekommt mehr — hier wird die „Abstimmung“ der Kolonie ausgezählt

Q/L_m

eine Belohnung umgekehrt proportional zur Länge der Rundreise — kürzere Rundreise = stärkere Spur; die Konstante Q legt nur den Maßstab fest

Beispiel — eine Aktualisierung

Eine Kante hat τ = 1, ρ = 0,3, Q = 1 000, und zwei Ameisen mit 1 100 und 1 300 km langen Rundreisen sind über sie gelaufen (Farben nach der Formel oben):

τ ← 0,7 · 1 + 1 000/1 100 + 1 000/1 300 ≈ 0,700 + 0,909 + 0,769 = 2,378

Eine Kante, die niemand benutzt hat, hat nach derselben Iteration nur 0,7. Die Ameise mit der kürzeren Rundreise hat mehr hinzugefügt (0,909 gegenüber 0,769).

import random

def postav_okruh(start, n, tau, d, alfa=1, beta=3):
    okruh, volna = [start], set(range(n)) - {start}
    while volna:
        i = okruh[-1]
        kandidati = list(volna)
        vahy = [tau[i][j] ** alfa * (1 / d[i][j]) ** beta for j in kandidati]
        j = random.choices(kandidati, weights=vahy)[0]
        okruh.append(j)
        volna.remove(j)
    return okruh

def aktualizuj(tau, okruhy, delka, rho=0.3, Q=1.0):
    for radek in tau:
        for j in range(len(radek)):
            radek[j] *= 1 - rho                 # Verdunstung
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # kürzere Rundreise, stärkere Spur
            tau[b][a] += Q / L

Das ganze Ameisensystem wechselt dann nur zwischen dem Bau der Rundreisen und der Aktualisierung ab und merkt sich die beste Rundreise, die je jemand gebaut hat:

def mravenci_system(n, d, mravencu, iteraci, tau0):
    tau = [[tau0] * n for _ in range(n)]      # am Anfang überall gleich
    nejlepsi = None
    for it in range(iteraci):
        okruhy = [postav_okruh(m % n, n, tau, d) for m in range(mravencu)]
        aktualizuj(tau, okruhy, delka)        # Verdunstung + neue Spur
        kandidat = min(okruhy, key=delka)
        if nejlepsi is None or delka(kandidat) < delka(nejlepsi):
            nejlepsi = kandidat
    return nejlepsi

4. Ameisen auf den Regionalhauptstädten

Lassen wir 13 Ameisen (aus jeder Stadt eine) 100 Iterationen lang laufen, mit α = 1, β = 3 und ρ = 0,3. Die Karte zeigt das Pheromon auf den Kanten nach der 1., 5., 20. und 100. Iteration — je dicker die Linie, desto mehr Pheromon:

In der ersten Iteration ist die Spur fast überall verteilt, und die beste Rundreise misst 1 292,6 km. Schon in der fünften Iteration findet eine der Ameisen das Optimum von 1 060,4 km. Das Pheromon konzentriert sich dann auf die Kanten guter Rundreisen — schwache Linien verschwinden, starke bleiben —, und die durchschnittliche Ameise baut eine Rundreise von etwa 1 250 km. Die Kolonie konvergiert nicht vollständig, sie probiert immer ein wenig.

Verlauf des Laufs nach Iterationen — die bisher beste gefundene Rundreise und die durchschnittliche Rundreise der dreizehn Ameisen in der jeweiligen Iteration:

Die beste Rundreise verbessert sich sprunghaft (die dritte Iteration brachte nichts Neues, die vierte nahm 111 km weg), der Durchschnitt sinkt langsamer und ungleichmäßig: Die Ameisen losen, also bauen manche auch in einer guten Iteration schwache Rundreisen. Der Unterschied zwischen Durchschnitt und Bester ist genau die Erkundung, die die Kolonie vor dem völligen Erstarren bewahrt.

Nicht immer geht es so gut aus. Von zwanzig Läufen mit verschiedenen Seeds fanden nur 7 das Optimum, der Durchschnitt lag bei 1 073,9 km und das schlechteste Ergebnis bei 1 083,0 km. Die simulierte Abkühlung war auf derselben Aufgabe mit 98 von 100 zuverlässiger. Zum Vergleich: Der gierige „nächste Nachbar“, der immer in die nächstgelegene unbesuchte Stadt geht, liefert je nach Start 1 120 bis 1 336 km. Die Ameisen sind deutlich besser, aber das einfache Ameisensystem allein ist kein Champion — deshalb entstanden seine verbesserten Varianten.

5. Wozu α, β und ρ da sind

Auf dreizehn Städten lässt sich auch ohne Pheromon viel lösen. Den Unterschied zeigt erst eine größere Aufgabe — dieselben 60 zufälligen Städte wie im Artikel über simulierte Abkühlung, 30 Ameisen, 150 Iterationen, Durchschnitt aus drei Läufen:

• Ohne Pheromon (α = 0) sind die Ameisen nur zufällige gierige Reisende und lernen nichts — Rundreisen um ein Drittel länger.
• Ohne Entfernungen (β = 0) hat die Kolonie nichts, wovon sie sich abstoßen kann: Die ersten Rundreisen sind völlig zufällig, und das Pheromon aus ihnen führt zu weiteren zufälligen.
• Langsame Verdunstung hält die Spuren der ersten, schlechten Rundreisen zu lange, und die Kolonie lernt langsam. Schnelle Verdunstung vergisst dagegen auch das Gute.

Wie lange sich die Kolonie erinnert, lässt sich genau ausrechnen. Es genügt, eine einzige Kante zu verfolgen.

Satz — stationäres Pheromon und Halbwertszeit der Verdunstung

Seien ρ ∈ (0, 1), Δ ≥ 0 und τ₀ ∈ ℝ. Die Folge (τ_t)_{t = 0, 1, 2, …} (das Pheromon einer Kante nach t Iterationen, die in jeder Iteration denselben Zuwachs Δ erhält) erfülle für jedes t ≥ 0

τ_t+1 = (1 − ρ) τ_t + Δ.

Dann gilt

1. für jedes t ≥ 0 ist τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ),
2. lim_{t → ∞} τ_t = Δ/ρ,
3. ist Δ = 0 und τ₀ > 0, so ist τ_t = (1 − ρ)^t τ₀, und für reelles t ≥ 0 gilt (1 − ρ)^t τ₀ = τ₀/2 genau dann, wenn t = t_½, wobei t_½ = ln 2/−ln(1 − ρ) die Halbwertszeit der Verdunstung ist (im Allgemeinen keine ganze Zahl).

Beweis. Bezeichne e_t = τ_t − Δ/ρ die Abweichung von Δ/ρ. Da (1 − ρ) · Δ/ρ + Δ = Δ/ρ, erhalten wir durch Abziehen von Δ/ρ auf beiden Seiten der Rekursion e_t+1 = (1 − ρ) e_t und durch Induktion e_t = (1 − ρ)^t e₀; das ist Punkt 1. Da 1 − ρ ∈ (0, 1), gilt (1 − ρ)^t → 0 und damit e_t → 0; das ist Punkt 2. Für Δ = 0 ist τ_t = (1 − ρ)^t τ₀, also τ_t = τ₀/2 genau dann, wenn (1 − ρ)^t = 1/2, d. h. t · ln(1 − ρ) = −ln 2; da ln(1 − ρ) < 0, ist die einzige Lösung t = ln 2/−ln(1 − ρ). ∎

τ^* = Δ/ρ

τ^*

das Niveau, auf dem sich das Pheromon der Kante einpendelt — Hinzufügen und Verdunstung sind im Gleichgewicht

Δ

wie viel die Kante pro Iteration bekommt — Kanten aus häufigen und kurzen Rundreisen haben ein großes Δ und deshalb auch ein hohes Niveau

ρ

im Nenner: Langsame Verdunstung lässt die Spuren hoch anwachsen, und Unterschiede zwischen Kanten gleichen sich lange aus; schnelle hält sie niedrig und nur von den letzten paar Iterationen abhängig

Zwei Kanten mit τ₀ = 1 und ρ = 0,3: Die eine bekommt in jeder Iteration Δ = 1, die andere benutzt niemand.

Die benutzte Kante nähert sich τ^* = 1/0,3 ≈ 3,33 (Farben nach der Formel oben), die unbenutzte fällt in zehn Iterationen unter drei Hundertstel. Die Halbwertszeit der Verdunstung für die Zeilen der Tabelle oben: Mit ρ = 0,3 sind es 1,94 Iterationen, mit ρ = 0,02 ganze 34,31 Iterationen — die Spuren der ersten zufälligen Rundreisen herrschen also noch Dutzende Iterationen lang — und mit ρ = 0,9 nur 0,30 Iterationen, sodass sich die Kolonie praktisch nur an die letzte Runde erinnert.

Die beste Einstellung ergab 2 194 bis 2 314 km — vergleichbar mit der simulierten Abkühlung aus dem vorigen Artikel, die auf denselben Städten zwischen 2 210 und 2 270 km endete.

6. Bessere Ameisen

• Die Elitestrategie legt zusätzliches Pheromon auf die bisher beste Rundreise, damit sie nicht verloren geht.
• MAX–MIN Ant System (Stützle und Hoos, 2000) lässt nur die beste Ameise Pheromon legen und hält τ zwischen einer unteren und einer oberen Schranke. Die untere Schranke garantiert, dass keine Kante ganz verschwindet, und so erstarrt die Kolonie nicht vorzeitig — wie jene, die im Brückenexperiment auf dem langen Zweig endete.
• Ant Colony System (Dorigo und Gambardella, 1997) wählt mit einer gewissen Wahrscheinlichkeit direkt die beste Kante und nimmt Pheromon schon während des Baus der Rundreise weg, damit die anderen Ameisen es woanders versuchen.
• Lokale Suche. In der Praxis wird jede von einer Ameise gebaute Rundreise noch mit 2-opt-Zügen aus dem Artikel über simulierte Abkühlung nachgeschliffen. Die Ameisen finden ein gutes Gebiet, der Bergsteigeralgorithmus verfeinert es — diese Kombination gehörte in den Neunzigerjahren zu den besten Methoden für den Handlungsreisenden.

Definition — Elitestrategie und MAX–MIN Ant System

Seien ρ ∈ (0, 1) und Q > 0 wie in der Pheromon-Aktualisierung des Ameisensystems, und sei π^best die beste seit Beginn des Laufs gefundene Rundreise mit der Länge L^best = L(π^best).

1. Die Elitestrategie mit dem Parameter e ∈ ℕ (Anzahl der „Eliteameisen“) führt die übliche Aktualisierung des Ameisensystems durch und fügt dann auf jeder Kante (i, j), die zur Rundreise π^best gehört, noch e · Q/L^best hinzu; die übrigen Kanten betrifft dieser Schritt nicht.
2. Das MAX–MIN Ant System mit den Schranken 0 < τ_min < τ_max legt Pheromon nur nach der einen besten Rundreise π^best (je nach Variante der besten der jeweiligen Iteration oder der besten seit Beginn des Laufs) und beschneidet das Ergebnis auf das Intervall [τ_min, τ_max]: für jede Kante (i, j) τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), wobei Δ_ij = 1/L^best, falls (i, j) zu π^best gehört, und Δ_ij = 0 sonst.

Die Elitestrategie verstärkt also die bisher beste Rundreise zusätzlich, das MAX–MIN Ant System erlaubt dagegen nur sie zu verstärken und lässt keine Kante unter τ_min fallen oder über τ_max steigen.

Die obere Schranke wählen Stützle und Hoos als τ_max = 1/ρ L^best — genau der stationäre Wert Δ/ρ aus dem Satz oben für eine Kante, die jedes Mal in der besten Rundreise liegt. Die untere Schranke ist ein kleiner Bruchteil der oberen; außerdem wird das Pheromon am Anfang auf τ_max gesetzt, damit die ersten Iterationen möglichst breit erkunden.

Definition — Regeln des Ant Colony System

Gegeben seien Städte, Entfernungen, Pheromon τ_ij > 0 und Sichtbarkeit η_ij = 1/d_ij wie in der Übergangsregel oben sowie Parameter q₀ ∈ [0, 1], β ≥ 0, ρ ∈ (0, 1), ξ ∈ (0, 1) und ein Anfangswert des Pheromons τ₀ > 0. Das Ant Colony System unterscheidet sich vom Ameisensystem durch drei Regeln:

1. Pseudozufällige proportionale Regel. Eine Ameise in der Stadt i mit nichtleerer Menge unbesuchter Städte N_i zieht q gleichverteilt aus [0, 1), unabhängig von früheren Ziehungen. Ist q ≤ q₀, geht sie in die Stadt j = arg max_{l ∈ Ni} τ_il · η_il^β; ist q > q₀, wählt sie j ∈ N_i per Los nach der Übergangsregel des Ameisensystems mit α = 1.
2. Lokale Aktualisierung. Gleich nachdem die Ameise über die Kante (i, j) gegangen ist, wird τ_ij ← (1 − ξ) τ_ij + ξ τ₀.
3. Globale Aktualisierung. Sei π^best die beste bisher gefundene Rundreise und L^best ihre Länge. Nach jeder Iteration wird nur für die Kanten (i, j), die zu π^best gehören, τ_ij ← (1 − ρ) τ_ij + ρ/L^best ausgeführt; das Pheromon der übrigen Kanten ändert sich nicht.

Mit der Wahrscheinlichkeit q₀ nimmt die Ameise also direkt die beste Kante; eine benutzte Kante schwächt sich nach Regel 2 ein wenig in Richtung des Anfangswerts τ₀ ab, sodass weitere Ameisen es woanders versuchen, und Verdunstung wie Verstärkung betreffen nur die beste Rundreise.

Dorigo und Gambardella (1997) verwenden im Originalartikel q₀ = 0,9, β = 2 und ρ = ξ = 0,1 — in neun von zehn Schritten nimmt die Ameise also die beste Kante und nur im zehnten probiert sie.

7. Wo Ameisen arbeiten

• Routing in Netzen. Der Algorithmus AntNet (Di Caro und Dorigo, 1998) schickt kleine Ameisenpakete durchs Netz, die Verzögerungen messen und die Routingtabellen aktualisieren. Das Netz passt sich so laufend an Überlastung an.
• Tourenplanung und Ablaufpläne. Warenauslieferung, Müllabfuhr oder die Reihenfolge von Aufträgen in der Fertigung — Aufgaben, die mit dem Handlungsreisenden verwandt sind und bei denen Ameisenalgorithmen zusammen mit lokaler Suche eingesetzt werden.
• Schwarmintelligenz. Eine Ameisenkolonie ist eines der Beispiele dafür, wie aus einfachen Individuen und lokalen Regeln ein kluges Verhalten des Ganzen entsteht. Ein weiteres, der Partikelschwarm, ist Thema des nächsten Artikels.

8. Zusammenfassung

• Ameisen kommunizieren über Spuren in der Umgebung (Stigmergie): Ein kürzerer Weg wird schneller markiert, und positive Rückkopplung verstärkt ihn.
• Im Doppelbrückenmodell pendeln sich 85 von 100 Kolonien auf dem kurzen Zweig ein — der Zufall kann aber auch den langen verriegeln.
• Das Ameisensystem wählt die nächste Stadt nach dem Pheromon τ^α und der Entfernung η^β; Pheromon verdunstet mit der Rate ρ, und kurze Rundreisen fügen mehr davon hinzu.
• Auf den Regionalhauptstädten fand es das Optimum, aber nur in 7 von 20 Läufen; auf 60 Städten schnitt es vergleichbar mit der simulierten Abkühlung ab. Ohne Pheromon wie ohne Entfernungen deutlich schlechter.
• Die in der Praxis genutzten Varianten (MAX–MIN, ACS) verhindern vorzeitiges Erstarren und kombinieren Ameisen mit lokaler Suche.

Möchtest du es selbst ausprobieren? Lass einen KI-Agenten eine Simulation der Doppelbrücke schreiben, und probier aus, was passiert, wenn du den kurzen Zweig mitten im Versuch „schließt“ — schafft es die Kolonie, zurück auf den langen zu wechseln?

Siehst du das anders? Schreib an support@coden-app.com.