Partikelschwarmoptimierung

Als Partikelschwarmoptimierung (PSO) wird ein naturanaloges Optimierungsverfahren bezeichnet, das nach dem Vorbild des biologischen Schwarmverhaltens eine Lösung für ein Optimierungsproblem sucht.

Ein Partikelschwarm sucht ein globales Minimum einer Funktion

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ärmenBearbeiten

 
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.

AlgorithmusBearbeiten

Die Startpositionen der Partikel   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   zugewiesen, der zufällig gewählt werden kann. Außerdem hat jeder Partikel:

  • eine Trägheit der Bewegung  
  • ein Gedächtnis für die Koordinaten mit dem besten Wert, den er erzielt hat (individueller Bestwert)  
  • die Kenntnis der Koordinaten des globalen Bestwertes aller Partikel oder die des Bestwerts der Partikel in seiner Umgebung  
  • einen kognitiven Gewichtungsfaktor  
  • einen sozialen Gewichtungsfaktor  

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   in der Bewegung wird für jeden Partikel je ein neuer Geschwindigkeitsvektor   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   gewichtet.[3]

 

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.

WeblinksBearbeiten

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

EinzelnachweiseBearbeiten

  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 11. Januar 2017.