Partikelschwarmoptimierung

Ein Partikelschwarm sucht ein globales Minimum einer Funktion

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.^[1][2]

Analogie zu natürlichen Schwärmen

(c) Walter Baxter, CC BY-SA 2.0

Ein Schwarm von Staren

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.^[3] Die Suche nach einem optimalen Rastplatz eines Vogelschwarms kann somit als eine Art Partikelschwarmoptimierung betrachtet werden.

Algorithmus

Die Startpositionen der Partikel ${\displaystyle {\vec {p}}_{0}}$ 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 ${\displaystyle {\vec {v}}_{0}}$ zugewiesen, der zufällig gewählt werden kann. Außerdem hat jeder Partikel:

• eine Trägheit der Bewegung ${\displaystyle \omega }$
• ein Gedächtnis für die Koordinaten mit dem besten Wert, den er erzielt hat (individueller Bestwert) ${\displaystyle {\vec {p}}_{\text{best}}}$
• die Kenntnis der Koordinaten des globalen Bestwertes aller Partikel oder die des Bestwerts der Partikel in seiner Umgebung ${\displaystyle {\vec {g}}_{\text{best}}}$
• einen kognitiven Gewichtungsfaktor ${\displaystyle c_{k}}$
• einen sozialen Gewichtungsfaktor ${\displaystyle c_{s}}$

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 ${\displaystyle n}$ in der Bewegung wird für jeden Partikel je ein neuer Geschwindigkeitsvektor ${\displaystyle {\vec {v}}_{n+1}}$ 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 ${\displaystyle r_{i}}$ gewichtet.^[3]

${\displaystyle {\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})}$

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

Commons: Particle swarm optimization – Sammlung von Bildern, Videos und Audiodateien

• Particle Swarm Optimization — eine Homepage zum Thema von Xiaohui Hu, Ph.D. (engl.)

Einzelnachweise

1. ↑ Eberhart, Russell C.; Shi, Yuhui: Computational Intelligence: Concepts to Implementations, Seite 87.
2. ↑ Russell Eberhart, James Kennedy: A New Optimizer Using Particle Swarm Theory. (PDF) 1995, abgerufen am 12. Januar 2016 (englisch). 
3. ↑ ^{a b} Marcel Röber: Multikriterielle Optimierungsverfahren für rechenzeitintensive technische Aufgabenstellungen. (PDF) 31. März 2010, abgerufen am 26. Mai 2021.