Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms

Boids und Schwärme, der PSO-Algorithmus, die drei Komponenten der Geschwindigkeit, ein Lauf auf der Rastrigin-Funktion im Vergleich mit einer Evolutionsstrategie, die Rolle der Trägheit, die Stabilität eines Partikels, die Topologie des Schwarms und das No-free-Lunch-Theorem.

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

Serie KI-Grundlagen Teil 30 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

Ein Starenschwarm über der abendlichen Stadt wogt wie ein einziges Lebewesen — und hat doch keinen Anführer. Jeder Vogel beobachtet nur ein paar seiner nächsten Nachbarn. 1995 stellten sich der Sozialpsychologe James Kennedy und der Elektroingenieur Russell Eberhart eine Frage: Was wäre, wenn die Vögel einander außer der Position der Nachbarn auch mitteilten, wo sie das meiste Futter gefunden haben? Aus ihrer Simulation wurde einer der einfachsten und meistgenutzten Optimierungsalgorithmen überhaupt — die Partikelschwarmoptimierung (particle swarm optimization, PSO).

Sie knüpft an die Teile Evolutionsstrategien und genetische Programmierung und Ameisenkolonieoptimierung an. Wir lassen den Schwarm auf dieselbe Rastrigin-Funktion los wie die Evolutionsstrategie, mit demselben Start und demselben Budget.

1. Schwärme in der Natur und im Computer

Schon 1987 zeigte Craig Reynolds, dass für eine glaubwürdige Schwarmbewegung drei lokale Regeln genügen. Seine „Boids“ weichen Zusammenstößen mit den nächsten Nachbarn aus, richten ihre Flugrichtung an ihnen aus und halten sich nahe der Gruppenmitte. Niemand steuert das Ganze; die Form des Schwarms entsteht aus den lokalen Regeln. Kennedy und Eberhart fügten ein Viertes hinzu — ein Gedächtnis für gute Orte — und aus der Animation wurde ein Optimierer.

Definition — die drei Boid-Regeln (vereinfacht)

Reynolds beschrieb die Regeln in Worten; heute schreibt man sie meist so. Es mögen sich N ≥ 2 Boids im ℝⁿ (n = 2 oder 3) bewegen, und Boid i ∈ {1, …, N} habe die Position x_i ∈ ℝⁿ und die Geschwindigkeit v_i ∈ ℝⁿ. Sei R > 0 der Wahrnehmungsradius und ‖·‖ die euklidische Norm. Die Nachbarschaft von Boid i ist die Menge

S_i = {j ∈ {1, …, N} : j ≠ i ∧ ‖x_j − x_i‖ < R}.

Ist S_i ≠ ∅, bezeichnen wir die mittlere Geschwindigkeit und die mittlere Position der Nachbarn mit

v̄_i = 1/|S_i| ∑_{j ∈ Si} v_j,   x̄_i = 1/|S_i| ∑_{j ∈ Si} x_j.

Das Boid addiert zu seiner Geschwindigkeit v_i die Summe dreier Vektoren, multipliziert mit den Gewichten k₁, k₂, k₃ ≥ 0 (für S_i = ∅ ändert sich die Geschwindigkeit nicht):

1. Separation a_i⁽¹⁾ = −∑_{j ∈ Si} x_j − x_i/‖x_j − x_i‖² — Abstoßung, umso stärker, je näher der Nachbar ist;
2. Ausrichtung a_i⁽²⁾ = v̄_i − v_i — Annäherung der eigenen Geschwindigkeit an die mittlere Geschwindigkeit der Nachbarn;
3. Kohäsion a_i⁽³⁾ = x̄_i − x_i — Zug zur Mitte der Nachbarn.

v_i ← v_i + k₁ a_i⁽¹⁾ + k₂ a_i⁽²⁾ + k₃ a_i⁽³⁾,   x_i ← x_i + v_i.

Jedes Boid nutzt also nur Informationen aus seiner Nachbarschaft. Die PSO-Gleichungen unten haben dieselbe Form „Geschwindigkeit ← Geschwindigkeit + Zug zu Zielen“, nur sind die Ziele nicht Nachbarn, sondern die besten bisher gefundenen Orte.

2. Der Algorithmus

Definition — Partikelschwarmoptimierung

Eingabe: eine Zielfunktion f : ℝⁿ → ℝ, die wir minimieren (n ≥ 1); die Anzahl der Partikel N ∈ ℕ, N ≥ 1; die Anzahl der Iterationen T ∈ ℕ; die Trägheit w ∈ ℝ und die Koeffizienten c₁, c₂ ≥ 0; Anfangspositionen x₁, …, x_N ∈ ℝⁿ und Geschwindigkeiten v₁, …, v_N ∈ ℝⁿ (meist zufällig im Suchgebiet).

Ausgabe: ein Punkt g ∈ ℝⁿ — die beste gefundene Position — und der Wert f(g).

Der Schwarm besteht aus N Partikeln; Partikel i ∈ {1, …, N} hat eine Position x_i, eine Geschwindigkeit v_i und seine bisher beste Position p_i; g ist die beste Position des ganzen Schwarms. Die Koordinaten des Vektors x_i bezeichnen wir mit x_id, d = 1, …, n.

1. Initialisierung: p_i ← x_i für i = 1, …, N und g ← p_k, wobei k = arg min_{i ∈ {1, …, N}} f(p_i).
2. Iteration t = 1, …, T: für jedes Partikel i = 1, …, N der Reihe nach
   1. ziehe für jede Koordinate d = 1, …, n die Zahlen r₁, r₂ unabhängig und gleichverteilt aus [0, 1) und setze v_id ← w · v_id + c₁ r₁ (p_id − x_id) + c₂ r₂ (g_d − x_id);
   2. x_i ← x_i + v_i;
   3. ist f(x_i) < f(p_i), setze p_i ← x_i; ist zudem f(p_i) < f(g), setze g ← p_i.
3. Abbruch: nach T Iterationen gib g und f(g) zurück.

In Vektorschreibweise (mit Zufallszahlen r₁, r₂ für jede Koordinate einzeln) sind die ersten beiden Teilschritte der Iteration

v_i ← w · v_i + c₁ r₁ (p_i − x_i) + c₂ r₂ (g − x_i),   x_i ← x_i + v_i.

Jedes Partikel ändert also seine Geschwindigkeit nach der Trägheit, seinem besten Ort und dem besten Ort des Schwarms. Übliche Werte (Clerc und Kennedy, 2002): w = 0,7298, c₁ = c₂ = 1,49618.

v_i ← w · v_i + c₁ r₁ (p_i − x_i) + c₂ r₂ (g − x_i)

v_i links

die neue Geschwindigkeit — um so viel bewegt sich das Partikel in diesem Schritt (x_i ← x_i + v_i); der Schwarm steuert die Position nicht direkt, sondern über die Geschwindigkeit, und dadurch ist die Bewegung flüssig

w · v_i

Trägheit — ein Teil der alten Geschwindigkeit bleibt; w < 1 dämpft sie zugleich, damit sich die Bewegung mit der Zeit beruhigt

c₁ r₁, c₂ r₂

Stärke des Zugs — c legt die mittlere Stärke fest, das zufällige r aus [0, 1) kürzt sie jedes Mal anders, sodass das Partikel nicht genau im Ziel landet und unterwegs auch die Orte ringsum kostet

p_i − x_i

der Vektor vom Partikel zu seinem besten Ort — je weiter weg, desto stärker zieht es das Partikel zurück (wie eine Feder)

g − x_i

der Vektor zum besten Ort des Schwarms — der einzige Kanal, über den fremde Erfahrung das Partikel erreicht

Definition — Geschwindigkeitsbegrenzung

Sei v_max > 0. Die Geschwindigkeitsbegrenzung ist eine Anpassung des PSO-Algorithmus: Im Iterationsschritt wird gleich nach der Berechnung der neuen Geschwindigkeit v_i ∈ ℝⁿ (und vor der Verschiebung der Position) jede ihrer Koordinaten d = 1, …, n ersetzt durch

v_id ← min(v_max, max(−v_max, v_id)),

d. h. die Koordinate wird auf das Intervall [−v_max, v_max] beschnitten (Werte innerhalb des Intervalls ändern sich nicht). Unsere Implementierung nimmt v_max = 5,12, also die halbe Breite des Suchquadrats [−5,12; 5,12]² — ein Partikel fliegt in einem Schritt nicht weiter als über die halbe Karte.

Beispiel — ein Schritt eines Partikels

Ein Partikel steht bei x = (4,2; −3,8) mit der Geschwindigkeit v = (0,5; 0,4). Sein bester Ort ist p = (4,0; −3,1), der beste Ort des Schwarms g = (1,1; −2,0). Gezogen wurden die Zufallszahlen r₁ = (0,6; 0,3) und r₂ = (0,5; 0,8). Erste Koordinate (Farben nach der Formel oben):

• Trägheit 0,7298 · 0,5 = 0,365,
• kognitiv 1,49618 · 0,6 · (4,0 − 4,2) = −0,180,
• sozial 1,49618 · 0,5 · (1,1 − 4,2) = −2,319,
• neue Geschwindigkeit 0,365 − 0,180 − 2,319 = −2,134, neue Position 4,2 − 2,134 = 2,066.

Die zweite Koordinate genauso: 0,292 + 0,314 + 2,154 = 2,761, neue Position −3,8 + 2,761 = −1,039. Beide Geschwindigkeitskomponenten liegen unter v_max, die Begrenzung greift nicht. Der Funktionswert (der Rastrigin-Funktion, siehe unten) sank von 45,90 auf 6,51. Die soziale Komponente ist hier die größte, weil g weit weg ist; die kognitive ist klein, weil p nur ein Stück vom Partikel entfernt liegt.

import random

def pso(f, n, castic=40, iteraci=200, w=0.7298, c1=1.49618, c2=1.49618):
    x = [[random.uniform(-5, 5) for _ in range(n)] for _ in range(castic)]
    v = [[0.0] * n for _ in range(castic)]
    p = [xi[:] for xi in x]                              # bester Ort jedes Partikels
    g = min(p, key=f)[:]                                 # bester Ort des Schwarms
    for _ in range(iteraci):
        for i in range(castic):
            for d in range(n):
                v[i][d] = (w * v[i][d]
                           + c1 * random.random() * (p[i][d] - x[i][d])
                           + c2 * random.random() * (g[d] - x[i][d]))
                x[i][d] += v[i][d]
            if f(x[i]) < f(p[i]):
                p[i] = x[i][:]
                if f(p[i]) < f(g):
                    g = p[i][:]
    return g

Die Kosten des Algorithmus misst man in der Zahl der Auswertungen von f — bei echten Aufgaben ist jede teuer (eine Simulation, das Training eines Modells). Jedes Partikel wird beim Start ausgewertet und dann einmal pro Iteration, insgesamt N + N · T = 40 + 40 · 200 = 8 040 für N = 40 Partikel und T = 200 Iterationen. (Der Pseudocode oben ruft f der Übersichtlichkeit halber mehrfach auf; die echte Implementierung merkt sich die Werte f(p_i).)

3. Drei Kräfte

• Trägheit w · v — das Partikel will die Richtung nicht abrupt ändern. Dank ihr überfliegt der Schwarm flache Mulden, statt in jede hineinzufallen.
• Kognitive Komponente c₁ r₁ (p − x) — eigene Erfahrung: „Dort ging es mir gut.“ Sie erhält die Vielfalt, weil sich jedes Partikel an etwas anderes erinnert.
• Soziale Komponente c₂ r₂ (g − x) — Erfahrung des Schwarms: „Dort ist das Beste, was irgendwer gefunden hat.“ Sie hält den Schwarm zusammen.

Anders als bei genetischen Algorithmen stirbt hier niemand und nichts wird gekreuzt. Information verbreitet sich nur dadurch, dass Partikel den Erfolg anderer sehen. Und anders als bei Evolutionsstrategien hat ein Partikel eine Geschwindigkeit — einen Schwung, der es weiterträgt, auch wenn es gerade nicht gut läuft.

4. Der Schwarm auf der Rastrigin-Funktion

Die Rastrigin-Funktion aus dem letzten Teil: eine Schüssel mit einem regelmäßigen Gitter von Mulden, das globale Minimum im Ursprung. 40 Partikel starten um den Punkt (4,2; −3,8), wo f ≈ 45,9 ist — dort, wo die Evolutionsstrategie startete:

Definition — die Rastrigin-Funktion

Sei n ∈ ℕ, n ≥ 1. Die Rastrigin-Funktion ist die Funktion f : [−5,12; 5,12]ⁿ → ℝ, die dem Punkt x = (x₁, …, x_n) den Wert

f(x) = 10n + ∑_d=1ⁿ (x_d² − 10 cos(2πx_d))

zuordnet. Sie ist eine Summe von n gleichen Funktionen einer Variablen, um 10n verschoben. Das globale Minimum ist f(0, …, 0) = 0; lokale Minima liegen nahe jedem Punkt mit ganzzahligen Koordinaten, innerhalb des Quadrats gibt es in zwei Dimensionen 11 · 11 = 121 davon.

f(x) = 10n + ∑_d (x_d² − 10 cos(2πx_d))

f(x)

der Wert, den der Schwarm minimiert — eine Testlandschaft, deren Minimum wir kennen, sodass wir Erfolg erkennen können

10n

eine Verschiebung — im Ursprung ist der Kosinus 1 und jede Koordinate liefert −10; dieser Term gleicht das aus, damit das Minimum genau den Wert 0 hat

∑_d

eine Summe über die Koordinaten — jede trägt unabhängig bei, sodass die Zahl der Mulden mit der Dimension exponentiell wächst (11ⁿ)

x_d²

die Schüssel — die Gesamtneigung zum Ursprung; ohne sie wären alle Mulden gleich tief und es gäbe kein globales Minimum

− 10 cos(2πx_d)

eine Welligkeit mit Periode 1 — sie gräbt bei jeder ganzen Zahl eine Mulde und macht sie mit der Amplitude 10 tief genug, dass ein lokales Verfahren darin stecken bleibt

Beispiel — der Wert im Startpunkt

Für x = (4,2; −3,8): cos(2π · 4,2) = cos(8,4π) = cos(0,4π) ≈ 0,309 und cos(2π · (−3,8)) = cos(7,6π) = cos(1,6π) ≈ 0,309. Also (Farben nach der Formel oben, n = 2)

f = 20 + (17,64 − 3,090) + (14,44 − 3,090) = 20 + 14,550 + 11,350 ≈ 45,9.

Der Start liegt am Hang der Mulde bei (4; −4), wo f = 20 + (16 − 10) + (16 − 10) = 32 ist; der tatsächliche Boden liegt ein Haar näher am Ursprung, mit einem Wert von etwa 31,84. Der Wert 31,9 nach der ersten Iteration (unten) bedeutet also, dass der Schwarm fast auf den Boden der Startmulde gerutscht ist. Weiter zum Minimum kommt er nur über die Grate zwischen den Mulden.

Nach der ersten Iteration hat der beste Ort des Schwarms den Wert 31,9. Dann geschieht etwas, was die Evolutionsstrategie nicht tat: Der Schwarm fliegt auseinander. Die Streuung der Partikel steigt von 0,7 auf 1,3 in der zehnten Iteration — die Partikel schießen über ihre besten Orte hinaus und entdecken unterwegs neue Mulden. In der 25. Iteration liegt der beste Ort beim Wert 1,06, eine Mulde neben dem Minimum, und in der 50. Iteration findet der Schwarm das globale Minimum. Danach zieht er sich um es zusammen.

Definition — Streuung des Schwarms und erfolgreicher Lauf

Seien x₁, …, x_N ∈ ℝⁿ (N ≥ 1) die Positionen der Partikel des Schwarms in einer Iteration und ‖·‖ die euklidische Norm. Der Schwerpunkt des Schwarms ist der Punkt

x̄ = 1/N ∑_i=1^N x_i

und die Streuung des Schwarms ist die Zahl

σ = √1/N ∑_i=1^N ‖x_i − x̄‖² ≥ 0,

also die Wurzel aus dem mittleren quadrierten Abstand der Partikel vom Schwerpunkt.

Sei g der beste Ort des Schwarms nach der letzten Iteration eines Laufs auf der Rastrigin-Funktion f. Der Lauf hat das globale Minimum gefunden genau dann, wenn f(g) < 0,01 (die Schwelle ist unsere Wahl für diesen Teil). Die nächsten lokalen Minima haben Werte um 1 (deshalb bedeutet 1,06 in der 25. Iteration „die Nachbarmulde“), sodass diese Schwelle sie klar unterscheidet.

σ = √1/N ∑_i ‖x_i − x̄‖²

σ

eine einzige Zahl für „wie weit der Schwarm auseinandergeflogen ist“ — in Koordinateneinheiten, sodass man sie mit dem Abstand der Mulden (1) vergleichen kann

1/N ∑_i

ein Mittel über die Partikel — das Ergebnis hängt nicht von der Größe des Schwarms ab

‖x_i − x̄‖²

der quadrierte Abstand vom Schwerpunkt — wir messen von der Mitte des Schwarms, nicht vom Minimum, weil uns die Form des Schwarms interessiert, nicht wo er ist; das Quadrat gewichtet abgelegene Kundschafter stärker und die Wurzel stellt dann die ursprünglichen Einheiten wieder her

Verlauf desselben Laufs nach Iterationen:

Vier Iterationen lang rührt sich der beste Wert nicht, und der Schwarm zieht sich währenddessen in die Startmulde zusammen (in der dritten Iteration ist σ nur 0,53); dann ziehen ihn Trägheit und der Zug zu g wieder auseinander, und der beste Wert fällt Mulde um Mulde — 31,9, 25,6, 5,9, 1,06. Das Minimum ist in der 50. Iteration gefunden, aber σ beträgt da noch 0,96: Um das Minimum zieht sich der Schwarm erst danach zusammen.

Von hundert Läufen mit verschiedenen Seeds fand der Schwarm das globale Minimum in 97 — mit einem Budget von 8 040 Auswertungen. Die Evolutionsstrategie (15, 100) mit 8 000 Auswertungen derselben Aufgabe war in 32 Fällen erfolgreich. Startet der Schwarm statt in einer Ecke über das ganze Quadrat verteilt, gelingt es ihm in allen hundert.

5. Trägheit und das Gleichgewicht der Kräfte

Was passiert, wenn wir nur die Trägheit ändern? Das Diagramm zeigt, wie weit die Partikel voneinander entfernt sind (die senkrechte Achse ist logarithmisch):

Mit w = 0,4 fällt der Schwarm in einen einzigen Punkt zusammen, bevor er sich umsehen kann — er bleibt in einer Mulde mit dem Wert 24,9 stecken. Mit w = 0,9 bleibt er die ganze Zeit auseinandergeflogen: Das Minimum findet er, zieht sich aber nie darum zusammen und verfeinert es nicht. Von hundert Läufen je Einstellung:

Ohne die soziale Komponente ist der Schwarm nur eine Gruppe von vierzig einsamen Bergsteigern, die nichts voneinander wissen — keiner kommt aus der Ecke heraus. Ohne die kognitive jagen alle einem einzigen Anführer nach und bleiben die Hälfte der Zeit mit ihm stecken. Erst beide Komponenten zusammen ergeben das Gleichgewicht zwischen Erkundung und Ausnutzung, das uns schon bei der simulierten Abkühlung begegnet ist.

6. Warum der Schwarm nicht verrücktspielt

Die Geschwindigkeit wird ständig aufaddiert. Warum wächst sie nicht ins Unendliche? Die Antwort liefert die Analyse eines einzigen Partikels, wenn wir den Zufall für einen Moment vergessen.

Satz — Stabilität eines Partikels

Betrachten wir ein eindimensionales Partikel ohne Zufall. Seien p, g ∈ ℝ die festen besten Orte (des Partikels und des Schwarms), w ∈ ℝ die Trägheit und φ₁, φ₂ ∈ ℝ feste Zahlen anstelle von c₁r₁, c₂r₂, wobei φ = φ₁ + φ₂ ≠ 0. Bezeichne

P = φ₁p + φ₂g/φ

(das gewichtete Mittel von p und g). Die Positionen x₀, x₁, x₂, … ∈ ℝ mögen für jedes t ≥ 1 die lineare Rekursion

x_t+1 = (1 + w − φ) x_t − w x_t−1 + φP

erfüllen. Dann gilt lim_{t → ∞} x_t = P für jede Wahl der Anfangspositionen x₀, x₁ ∈ ℝ genau dann, wenn

1. |w| < 1   und
2. 0 < φ < 2(1 + w).

Beweis — woher die Rekursion und die Bedingungen kommen

Ohne Zufall ist der eindimensionale Schritt v_t+1 = wv_t + φ₁(p − x_t) + φ₂(g − x_t) und x_t+1 = x_t + v_t+1. Mit φ = φ₁ + φ₂ und P = φ₁p + φ₂g/φ aus dem Satz ist φ₁(p − x) + φ₂(g − x) = φ(P − x), und nach Einsetzen von v_t = x_t − x_t−1:

x_t+1 = (1 + w − φ) x_t − w x_t−1 + φP.

Die Abweichung e_t = x_t − P erfüllt dieselbe Rekursion ohne Konstante, also e_t = C₁λ₁^t + C₂λ₂^t, wobei λ_1,2 die Wurzeln der charakteristischen Gleichung λ² − (1 + w − φ)λ + w = 0 sind (bei einer doppelten Wurzel e_t = (C₁ + C₂t)λ₁^t), und die Konstanten C₁, C₂ lassen sich durch die Wahl von x₀, x₁ beliebig einstellen. Daher gilt e_t → 0 für alle Anfangspositionen genau dann, wenn |λ₁| < 1 und |λ₂| < 1. Für eine quadratische Gleichung λ² + aλ + b = 0 mit reellen a, b tritt das genau dann ein, wenn |b| < 1 und 1 ± a + b > 0 (Jury-Kriterium). Hier ist b = w, a = −(1 + w − φ):

• |w| < 1,
• 1 − (1 + w − φ) + w = φ > 0,
• 1 + (1 + w − φ) + w = 2(1 + w) − φ > 0. ∎

x_t+1 = (1 + w − φ) x_t − w x_t−1 + φP

x_t+1

die nächste Position — sie hängt von den zwei vorigen ab, weil die Geschwindigkeit die Differenz zweier Positionen ist; deshalb verhält sich das Partikel wie ein schwingender Körper, nicht wie eine Kugel, die einen Hang hinabrollt

(1 + w − φ) x_t

die aktuelle Position, von der Trägheit weitergeschoben (+w) und von der Anziehung zurückgeholt (−φ) — der Kampf „weiterfliegen“ gegen „zurückkehren“

− w x_t−1

das Gedächtnis des letzten Schritts — dieser Term bringt den Schwung; sein Koeffizient w ist das Produkt der Wurzeln, und deshalb bestimmt gerade die Trägheit die Dämpfung

φP

der Anker — die Anziehung des gewichteten Mittels von p und g; um ihn schwingt das Partikel und in ihm kommt es zur Ruhe

Wie schnell kommt es zur Ruhe? Für übliche φ sind beide Wurzeln komplex (das Partikel schwingt) und haben denselben Betrag √w, weil ihr Produkt w ist. Die Amplitude der Abweichung wird also in jeder Iteration mit √w multipliziert und halbiert sich in ln 2/−ln √w Iterationen. Mit dem mittleren φ = c₁ + c₂/2 = 1,49618 (das zufällige r hat den Mittelwert 1/2):

Das passt genau zum Streuungsdiagramm oben: Mit w = 0,4 zieht sich der Schwarm in wenigen Iterationen zusammen, mit w = 0,9 klingen die Schwingungen über Dutzende Iterationen ab. Es ist eine Vereinfachung — die echten r werden in jedem Schritt gezogen, und p, g ändern sich —, aber die Größenordnung stimmt. Und Vorsicht: Mit w = 0,4 ist die Schranke 2(1 + w) = 2,8 kleiner als das größtmögliche φ = c₁ + c₂ ≈ 2,99, sodass ein außergewöhnlich starker zufälliger Zug das Partikel für einen Schritt aufschaukelt (Dämpfung 1,280 > 1).

7. Wer wen hört: Topologie

Definition — Topologie des Schwarms

Der Schwarm bestehe aus N ≥ 3 Partikeln mit den Nummern 1, …, N und den bisher besten Positionen p₁, …, p_N, und f sei die zu minimierende Funktion. Die Topologie des Schwarms ist ein ungerichteter Graph G = ({1, …, N}, E) auf der Menge der Partikel; er bestimmt, wessen beste Orte ein Partikel sieht. Die Nachbarschaft von Partikel i ist die Menge

S(i) = {i} ∪ {j : {i, j} ∈ E}

und der beste Ort der Nachbarschaft ist g_i = p_k, wobei k = arg min_{j ∈ S(i)} f(p_j). In der Geschwindigkeitsregel von Partikel i wird statt g der Ort g_i verwendet. Zwei übliche Topologien:

1. global (gbest): G ist der vollständige Graph, d. h. S(i) = {1, …, N} für jedes i; dann ist g_i = g allen gemeinsam;
2. Ring (lbest): E = {{i, i + 1} : i = 1, …, N} mit Indizes modulo N (N + 1 ≡ 1), d. h. S(i) = {i − 1, i, i + 1} (0 ≡ N).

In der globalen Topologie sieht also jedes Partikel alle, im Ring nur seine zwei Nachbarn im Ring.

Formal hat jedes Partikel i eine Nachbarschaft S(i) und verwendet in der Geschwindigkeitsregel statt des gemeinsamen g g_i = p_k, wobei k = arg min_{j ∈ S(i)} f(p_j). Die globale Topologie hat S(i) = {1, …, N}, die Ring-Topologie S(i) = {i − 1, i, i + 1} (Indizes modulo N). Wie viele Iterationen dauert es, bis die Nachricht von einem neuen Fund alle erreicht? In der globalen Topologie eine. Im Ring rückt sie pro Iteration höchstens um einen Nachbarn in jede Richtung vor, und das entfernteste Partikel in einem Ring aus 40 Partikeln ist 20 Plätze entfernt — die Nachricht erreicht es frühestens nach 20 Iterationen. So lange können entfernte Teile des Schwarms auf eigene Faust erkunden.

Auf unserer zweidimensionalen Aufgabe fand der Ring das Minimum in allen 100 Läufen, die globale Topologie in 97. Deutlicher ist der Unterschied in zehn Dimensionen, wo es astronomisch viele Mulden gibt: Nach 2 000 Iterationen endete die globale Topologie im Mittel beim Wert 5,84, die Ring-Topologie bei 4,57. Das globale Minimum fand keine von beiden — die zehndimensionale Rastrigin-Funktion ist für 40 Partikel wirklich schwer.

8. Vorsicht vor Metaphern

Satz — No Free Lunch (Wolpert und Macready, 1997)

Gemittelt über alle möglichen Zielfunktionen auf einer endlichen Menge haben alle Algorithmen, die denselben Punkt nicht zweimal auswerten, dieselbe erwartete Leistung.

Genauer: Seien X und Y endliche nichtleere Mengen und 𝓕 = Y^X die Menge aller Funktionen f : X → Y (es gibt |Y|^|X| davon). Ein Algorithmus a wählt in jedem Schritt auf Grundlage der bisher gesehenen Paare (x, f(x)) einen Punkt x ∈ X, den er noch nicht ausgewertet hat, und ermittelt f(x). Sei m ∈ {1, …, |X|} und d_m^y = (y₁, …, y_m) ∈ Y^m die Folge der Werte, die der Algorithmus während der ersten m Auswertungen sieht. Dann gilt für zwei beliebige solche Algorithmen a₁, a₂ und jede Folge d_m^y ∈ Y^m

∑_{f ∈ 𝓕} P(d_m^y | f, m, a₁) = ∑_{f ∈ 𝓕} P(d_m^y | f, m, a₂),

wobei P(d_m^y | f, m, a) die Wahrscheinlichkeit ist, dass der Algorithmus a auf der Funktion f genau die Folge d_m^y sieht (bei einem deterministischen Algorithmus 0 oder 1).

Summiert wird also über alle |Y|^|X| Funktionen. Jedes Leistungsmaß, das nur von den gesehenen Werten abhängt (etwa dem besten gefundenen), hat also über alle Funktionen denselben Mittelwert.

Nach dem Erfolg der Ameisen und des Schwarms kam eine Flut von „naturinspirierten“ Algorithmen: Glühwürmchen, Kuckucke, Fledermäuse, Grauwölfe, Harmonie in einer Jazzband. Kenneth Sörensen wies 2015 darauf hin, dass viele davon alte Ideen in neuem Kostüm sind — die Metapher ersetzte die mathematische Beschreibung und erschwerte den Vergleich. Die richtige Frage bei jedem neuen Algorithmus lautet deshalb nicht „wovon ist er inspiriert“, sondern „was macht er anders als die bekannten, und woran sieht man das“.

9. Schwärme in der Praxis

• Parameterabstimmung. PSO ist dort beliebt, wo es wenige Parameter gibt, der Gradient unbekannt ist und eine Auswertung eine Simulation ist: Einstellung von Reglern, Form von Antennen, Steuerung von Stromnetzen oder Hyperparameter von Modellen des maschinellen Lernens.
• Roboterschwärme. In Harvard setzten 2014 1 024 kleine Kilobot-Roboter nach lokalen Regeln vorgegebene Formen zusammen — ohne zentrale Steuerung, nur durch Kommunikation mit ihren Nachbarn.
• Und die Drohnen bei Feuerwerksshows? Lichtshows mit Tausenden Drohnen sind keine Schwarmintelligenz: Jede Drohne fliegt eine im Voraus berechnete Bahn aus einem zentralen Plan ab. Ein Schwarm im eigentlichen Sinn entscheidet selbst, nach seinen Nachbarn.

10. Zusammenfassung

• Ein Partikel in der PSO ändert seine Geschwindigkeit nach der Trägheit, seinem eigenen besten Ort und dem besten Ort des Schwarms.
• Auf der Rastrigin-Funktion fand der Schwarm das Minimum in 97 von 100 Läufen — die Evolutionsstrategie mit gleichem Start und Budget in 32.
• Die Trägheit steuert, wie lange der Schwarm erkundet: Eine kleine lässt ihn vorzeitig zusammenfallen, eine große lässt ihn das Ergebnis nicht verfeinern. Ohne die soziale wie ohne die kognitive Komponente versagt der Schwarm.
• Ein Partikel ist wie eine gedämpfte Feder; für |w| < 1 und 0 < φ < 2(1 + w) kommt es zur Ruhe.
• Die Ring-Topologie verbreitet Information langsamer und ist bei schweren Aufgaben oft robuster; und nach dem No-free-Lunch-Theorem gibt es keinen Optimierer, der für alles der beste ist.

Willst du es selbst ausprobieren? Lass einen KI-Agenten eine PSO mit Visualisierung des Schwarms schreiben, gib ihr eine eigene Landschaft — etwa eine Funktion mit zwei weit entfernten Tälern — und beobachte, ob sich der Schwarm aufteilt.

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