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.

Analogie zu natürlichen Schwärmen

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

Algorithmus

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

• eine Trägheit der Bewegung $\omega$
• ein Gedächtnis für die Koordinaten mit dem besten Wert, den er erzielt hat (individueller Bestwert) ${\vec {p}}_{\text{best}}$
• die Kenntnis der Koordinaten des globalen Bestwertes aller Partikel oder die des Bestwerts der Partikel in seiner Umgebung ${\vec {g}}_{\text{best}}$
• einen kognitiven Gewichtungsfaktor $c_{k}$
• einen sozialen Gewichtungsfaktor $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 $n$ in der Bewegung wird für jeden Partikel je ein neuer Geschwindigkeitsvektor ${\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 $r_{i}$ gewichtet.

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