Die Partikelschwarm-Optimierung (englisch Particle Swarm Optimization, kurz PSO) ist ein Optimierungsverfahren, das die Schwarmintelligenz von Vogelschwärmen oder Fischschwärmen nachahmt. Kennedy und Eberhart stellten den Algorithmus 1995 vor. Statt eine Lösung gezielt zu verbessern, lässt man viele Kandidatenlösungen gleichzeitig durch den Suchraum fliegen und sich gegenseitig beeinflussen.
Wie der Algorithmus funktioniert
Jedes Partikel repräsentiert eine Kandidatenlösung und hat eine Position x sowie eine Geschwindigkeit v im Suchraum. Zusätzlich merkt sich jedes Partikel seine bisher beste Position (pbest), und der gesamte Schwarm kennt die beste je gefundene Position (gbest).
In jedem Schritt werden Geschwindigkeit und Position nach folgenden Formeln aktualisiert:
v = w · v + c1 · r1 · (pbest − x) + c2 · r2 · (gbest − x)
x = x + vDie Parameter haben folgende Bedeutung:
w: Trägheitsgewicht — steuert, wie stark ein Partikel seine bisherige Richtung beibehältc1: kognitiver Faktor — wie stark ein Partikel zu seiner eigenen besten Position gezogen wirdc2: sozialer Faktor — wie stark es zum Schwarm-Besten gezogen wirdr1,r2: gleichverteilte Zufallswerte zwischen 0 und 1, die für Erkundung sorgen
Das Verfahren ist eine Metaheuristik: Es garantiert kein globales Optimum, findet aber in der Praxis meist sehr gute Lösungen, ohne dass die Zielfunktion abgeleitet werden muss.
Einsatzgebiete
- Hyperparameter-Tuning für Modelle des maschinellen Lernens
- Netzwerk-Routing und Lastverteilung
- Produktions- und Ablaufplanung (Scheduling)
- Pfadplanung in der Robotik
- Entwurf von Antennen und elektronischen Schaltungen
Abgrenzung zu verwandten Verfahren
Im Gegensatz zum Genetischen Algorithmus arbeitet PSO ohne Crossover und Mutation — die Partikel fliegen durch den Raum, statt Lösungen zu kombinieren und zu verändern. Der Ameisenalgorithmus nutzt ebenfalls Schwarmintelligenz, kommuniziert aber indirekt über Pheromonspuren statt über direkte Positionsinformation. Hill-Climbing und Simulated Annealing verbessern dagegen nur eine einzige Lösung; PSO erkundet viele Lösungen parallel. Für lineare Probleme mit garantiertem Optimum ist dagegen das Simplex-Verfahren das Verfahren der Wahl — PSO glänzt dort, wo die Zielfunktion nichtlinear, diskret oder verrauscht ist. Ein Spezialfall mit kontinuierlichen Zielfunktionen ist der Gradient Descent, der die Ableitung ausnutzt.