Partikelschwarmoptimierung
Als Partikelschwarmoptimierung (PSO) wird ein naturanaloges Optimierungsverfahren bezeichnet, das nach dem Vorbild des biologischen Schwarmverhaltens eine Lösung für ein Optimierungsproblem sucht.
Analog zum natürlichen Phänomen wird eine Population von Lösungskandidaten durch den Suchraum bewegt, um eine gute Lösung für das Problem zu erhalten. In jedem Rechenschritt wird dazu die Position jedes Individuums neu berechnet. Die PSO ist eine Metaheuristik, sie wurde 1995 von James Kennedy und Russell Eberhart vorgeschlagen.<ref>Eberhart, Russell C.; Shi, Yuhui: Computational Intelligence: Concepts to Implementations, Seite 87.</ref><ref>Russell Eberhart, James Kennedy: A New Optimizer Using Particle Swarm Theory. (PDF) 1995, abgerufen am 12. Januar 2016 (Lua-Fehler in Modul:Multilingual, Zeile 153: attempt to index field 'data' (a nil value)).</ref>
Analogie zu natürlichen Schwärmen[Bearbeiten]
Das Verhalten natürlicher Schwärme von Tieren unterliegt gewissen Gesetzmäßigkeiten. So versuchen die Individuen innerhalb eines Schwarms, stets bei der Gruppe zu bleiben, der Gruppenbewegung zu folgen und einen gewissen Mindestabstand zu anderen Individuen einzuhalten. Diese Gesetzmäßigkeiten setzte Craig Reynolds zur Simulation von Tierschwärmen in Filmen und Computerspielen ein. Die einzelnen Individuen eines Schwarms nannte er Boids. Frank Heppner und Ulf Grenander erweiterten das Modell von Reynolds um das Bedürfnis der Boids, einen Rastplatz zu finden. Das Bedürfnis zu rasten steigt dabei mit Annäherung an einen Rastplatz. Somit wird das Schwarmverhalten auch durch die Eigenschaften des Raums beeinflusst.<ref name="Roeber">Marcel Röber: Multikriterielle Optimierungsverfahren für rechenzeitintensive technische Aufgabenstellungen. (PDF) 31. März 2010, abgerufen am 26. Mai 2021.</ref> Die Suche nach einem optimalen Rastplatz eines Vogelschwarms kann somit als eine Art Partikelschwarmoptimierung betrachtet werden.
Algorithmus[Bearbeiten]
Die Startpositionen der Partikel <math>\vec p_0</math> werden über den zu untersuchenden Raum verteilt. Die statistische Versuchsplanung bietet dabei Möglichkeiten, eine günstige Verteilung zu finden. Zusätzlich zu der Startposition wird jedem Partikel auch ein initialer Geschwindigkeitsvektor <math>\vec v_0</math> zugewiesen, der zufällig gewählt werden kann. Außerdem hat jeder Partikel:
- eine Trägheit der Bewegung <math>\omega</math>
- ein Gedächtnis für die Koordinaten mit dem besten Wert, den er erzielt hat (individueller Bestwert) <math>\vec p_\text{best}</math>
- die Kenntnis der Koordinaten des globalen Bestwertes aller Partikel oder die des Bestwerts der Partikel in seiner Umgebung <math>\vec g_\text{best}</math>
- einen kognitiven Gewichtungsfaktor <math>c_k</math>
- einen sozialen Gewichtungsfaktor <math>c_s</math>
Die Partikel bewegen sich mittels dieser Informationen durch den Suchraum. Die Bestwerte werden dabei stetig aktualisiert, indem sie mit dem aktuellen Wert des Partikels verglichen werden. Für jeden Schritt <math>n</math> in der Bewegung wird für jeden Partikel je ein neuer Geschwindigkeitsvektor <math>\vec v_{n+1}</math> aus der Trägheit, dem individuellen Bestwert und dem globalen Bestwert errechnet. Diese einzelnen Terme werden zusätzlich mit für jeden Schritt zufälligen Faktoren <math>r_{i}</math> gewichtet.<ref name=Roeber></ref>
- <math>\vec v_{n+1} = \omega \cdot \vec v_n + c_k \cdot r_1 \cdot (\vec p_\text{best}-\vec p_n) + c_s \cdot r_2 \cdot (\vec g_\text{best}-\vec p_n)</math>
Für den Abbruch des Algorithmus muss eine Abbruchbedingung definiert werden. Beispielsweise kann der Algorithmus beendet werden, wenn sich der globale Bestwert nach einer bestimmten Anzahl an Schritten nicht wesentlich ändert.
Der Algorithmus kann iterativ mit unterschiedlichen Parametern (Startpositionen, Partikeleigenschaften) ausgeführt werden, um die statistische Signifikanz des gefundenen Extremalwerts zu überprüfen.
Weblinks[Bearbeiten]
- Particle Swarm Optimization – eine Homepage zum Thema von Xiaohui Hu, Ph.D. (engl.)
Einzelnachweise[Bearbeiten]
<references />