Partikelschwarmoptimierung (PSO) ist eine rechnerische Methode in der künstlichen Intelligenz und der Computerwissenschaft, die ein Problem optimiert, indem sie iterativ eine Population von Kandidatenlösungen hinsichtlich eines gegebenen Qualitätsmaßes verbessert. Sie löst ein Problem durch Interaktionen zwischen einer Population von Kandidatenlösungen, sogenannten Partikeln, und bewegt diese im Suchraum gemäß einfacher mathematischer Formeln, die Position und Geschwindigkeit jedes Partikels anpassen. Die Bewegung jedes Partikels wird durch seine eigene bisher beste bekannte Position und durch die beste bekannte Position in seiner topologischen Nachbarschaft beeinflusst, die bei Bedarf die gesamte Population umfassen kann. Vektoren werden aktualisiert, sobald bessere Positionen gefunden werden, und es wird erwartet, dass sich der Schwarm so zu guten Lösungen bewegt.
PSO ist eine Metaheuristik, da sie wenige oder keine Annahmen über das zu optimierende Problem macht und sehr große Räume von Kandidatenlösungen durchsuchen kann. Sie verwendet nicht den Gradienten des Problems, daher erfordert sie nicht, dass das Optimierungsproblem differenzierbar ist, anders als klassische Methoden wie Gradientenabstieg oder Quasi-Newton-Verfahren. Metaheuristiken wie PSO garantieren jedoch nicht, dass jemals eine optimale Lösung gefunden wird.
Ursprünge und Entwicklung
PSO wurde ursprünglich Kennedy und Eberhart zugeschrieben, die es zunächst zur Simulation sozialen Verhaltens als stilisierte Darstellung der Bewegung von Organismen in einem Vogelschwarm oder Fischschwarm oder der Entwicklung von Einstellungen in einer menschlichen Bevölkerung entwarfen. Es wurde beobachtet, dass die Simulation von Prinzipien sozialen Verhaltens in der Lage war, schwierige mathematische Probleme zu lösen. Das Buch von Kennedy und Eberhart beschreibt viele philosophische Aspekte von PSO und Schwarmintelligenz. Eine umfangreiche Übersicht über PSO-Anwendungen wurde von Poli erstellt, und 2017 wurde eine umfassende Überprüfung theoretischer und experimenteller Arbeiten zu PSO von Bonyadi und Michalewicz veröffentlicht.
Algorithmus
Eine grundlegende Variante des PSO-Algorithmus wird mit einer verbundenen Population (einem Schwarm) von Kandidatenlösungen (Partikeln) initialisiert. Eine Kandidatenlösung ist ein Vektor numerischer Werte, der als Koordinaten eines Punktes in einem Suchraum betrachtet werden kann; als sich iterativ bewegender Punkt kann er als Partikel konzeptualisiert werden. Die Partikel bewegen sich gemäß einiger einfacher Formeln im Suchraum. Jedes Partikel hat einige Nachbarn, mit denen es verbunden ist, wobei die Nachbarschaft wenige oder alle anderen Populationsmitglieder umfassen kann. Die nächste Position eines Partikels wird stochastisch durch seine eigene bisher beste Position im Suchraum sowie die bisher beste Position des besten Nachbarn des Partikels bestimmt. Wenn eine verbesserte Position entdeckt wird - eine, die ein besseres Ergebnis in der Zielfunktion erzeugt - wird die bisher beste Position des Partikels aktualisiert. Der Prozess wird wiederholt, und dadurch wird erwartet, aber nicht garantiert, dass schließlich eine zufriedenstellende Lösung entdeckt wird.
Formal sei \( f: \mathbb{R}^n \to \mathbb{R} \) die zu minimierende Kostenfunktion. Die Funktion nimmt eine Kandidatenlösung als Argument in Form eines Vektors reeller Zahlen und erzeugt eine reelle Zahl als Ausgabe, die den Wert der Zielfunktion angibt. Der Gradient von \( f \) ist nicht bekannt. Das Ziel ist es, eine Lösung \( a \) zu finden, für die \( f(a) \le f(b) \) für alle \( b \) im Suchraum gilt, was bedeutet, dass \( a \) das globale Minimum ist.
Sei \( S \) die Anzahl der Partikel im Schwarm, wobei jedes eine Position \( x_i \in \mathbb{R}^n \) und eine Geschwindigkeit \( v_i \in \mathbb{R}^n \) hat. Sei \( p_i \) die beste bekannte Position von Partikel \( i \), und sei \( g \) die beste bekannte Position der Nachbarschaft des Partikels. Ein grundlegender PSO-Algorithmus zur Minimierung der Kostenfunktion ist:
- Für jedes Partikel \( i = 1, \dots, S \):
- Initialisiere die Position des Partikels mit einem gleichverteilten Zufallsvektor: \( x_i \sim U(b_{lo}, b_{up}) \).
- Initialisiere die beste bekannte Position des Partikels auf seine Anfangsposition: \( p_i \leftarrow x_i \).
- Wenn \( f(p_i) < f(g) \), aktualisiere die beste bekannte Position des Schwarms: \( g \leftarrow p_i \).
- Initialisiere die Geschwindigkeit des Partikels: \( v_i \sim U(-|b_{up}-b_{lo}|, |b_{up}-b_{lo}|) \).
- Solange ein Abbruchkriterium nicht erfüllt ist:
- Für jedes Partikel \( i = 1, \dots, S \):
- Für jede Dimension \( d = 1, \dots, n \):
- Wähle Zufallszahlen \( r_p, r_g \sim U(0,1) \).
- Aktualisiere die Geschwindigkeit des Partikels: \( v_{i,d} \leftarrow w v_{i,d} + \phi_p r_p (p_{i,d} - x_{i,d}) + \phi_g r_g (g_d - x_{i,d}) \).
- Aktualisiere die Position des Partikels: \( x_i \leftarrow x_i + v_i \).
- Wenn \( f(x_i) < f(p_i) \), aktualisiere die beste bekannte Position des Partikels: \( p_i \leftarrow x_i \).
- Wenn \( f(p_i) < f(g) \), aktualisiere die beste bekannte Position des Schwarms: \( g \leftarrow p_i \).
Die Werte \( b_{lo} \) und \( b_{up} \) stellen die unteren und oberen Grenzen des Suchraums dar. Der Parameter \( w \) ist das Trägheitsgewicht. Die Parameter \( \phi_p \) und \( \phi_g \) werden oft als kognitiver Koeffizient und sozialer Koeffizient bezeichnet. Das Abbruchkriterium kann die Anzahl der durchgeführten Iterationen oder eine Lösung sein, bei der ein angemessener Wert der Zielfunktion gefunden wird. Die Parameter \( w \), \( \phi_p \) und \( \phi_g \) werden vom Praktiker ausgewählt und steuern das Verhalten und die Wirksamkeit der PSO-Methode.
Parameterauswahl
Die Wahl der PSO-Parameter kann einen großen Einfluss auf die Optimierungsleistung haben. Die Auswahl von Parametern, die gute Leistung erzielen, war Gegenstand vieler Forschung. Um Divergenz („Explosion“) zu verhindern, muss das Trägheitsgewicht kleiner als 1 sein. Die beiden anderen Parameter können mit dem Konstriktionsansatz abgeleitet oder frei gewählt werden, aber Analysen legen Konvergenzbereiche nahe, um sie einzuschränken. Typische Werte liegen im Bereich [1, 3]. Die PSO-Parameter können auch durch einen übergeordneten Optimierer abgestimmt werden, ein Konzept, das als Meta-Optimierung bekannt ist, oder sogar während der Optimierung feinjustiert werden, z. B. mittels Fuzzy-Logik. Parameter wurden auch für verschiedene Optimierungsszenarien abgestimmt.
Nachbarschaften und Topologien
Die Topologie des Schwarms definiert die Teilmenge von Partikeln, mit denen jedes Partikel Informationen austauschen kann. Die grundlegende Version des Algorithmus verwendet die globale Topologie als Kommunikationsstruktur des Schwarms. Diese Topologie erlaubt es allen Partikeln, mit allen anderen Partikeln zu kommunizieren, sodass der gesamte Schwarm dieselbe beste Position \( g \) von einem einzelnen Partikel teilt. Dieser Ansatz kann jedoch dazu führen, dass der Schwarm in einem lokalen Minimum gefangen wird, daher wurden verschiedene Topologien verwendet, um den Informationsfluss zwischen Partikeln zu steuern. Beispielsweise teilen Partikel in lokalen Topologien Informationen nur mit einer Teilmenge von Partikeln. Diese Teilmenge kann eine geometrische sein - zum Beispiel „die \( m \) nächsten Partikel“ - oder häufiger eine soziale, d. h. eine Menge von Partikeln, die nicht von einer Entfernung abhängt. In solchen Fällen wird die PSO-Variante als lokales Best bezeichnet (im Gegensatz zu globalem Best für die grundlegende PSO). Eine häufig verwendete Schwarmtopologie ist der Ring, bei dem jedes Partikel nur zwei Nachbarn hat, aber es gibt viele andere. Die Topologie ist nicht unbedingt statisch; sie kann sich während des Optimierungsprozesses ändern.
Anwendungen und verwandte Methoden
PSO wurde auf eine breite Palette von Optimierungsproblemen in Bereichen wie Ingenieurwesen, Wirtschaft und maschinellem Lernen angewendet. Sie ist besonders nützlich, wenn der Suchraum groß und die Zielfunktion nicht differenzierbar oder verrauscht ist. PSO weist Ähnlichkeiten mit anderen populationsbasierten Metaheuristiken wie genetischen Algorithmen und Ameisenalgorithmen auf, unterscheidet sich jedoch durch ihren Geschwindigkeitsaktualisierungsmechanismus, der von sozialem Verhalten inspiriert ist. Im Kontext des maschinellen Lernens kann PSO zur Hyperparameterabstimmung oder zum Training von neuronalen Netzen verwendet werden, obwohl sie oft mit gradientenbasierten Methoden verglichen wird. Ihre stochastische Natur und das Fehlen von Gradientenanforderungen machen sie zu einem vielseitigen Werkzeug im breiteren Feld der künstlichen Intelligenz.