Was ist Partikelschwarmoptimierung?
Die Partikelschwarmoptimierung ist ein populationsbasierter Algorithmus, bei dem sich eine Ansammlung einzelner Partikel schrittweise durch eine Region bewegt. Eine Ansammlung von Individuen, sogenannte Partikel, bewegt sich schrittweise durch ein Gebiet. In jedem Schritt wertet der Algorithmus die Zielfunktion an jedem Partikel aus. Nach dieser Auswertung ermittelt der Algorithmus die neue Geschwindigkeit jedes Partikels. Die Partikel bewegen sich, dann berechnet der Algorithmus ihre Zielfunktionen neu.
Die Inspiration für den Algorithmus ist ein Vogelschwarm oder ein Insektenschwarm. Jedes Partikel wird von dem besten Ort angezogen, den es bisher gefunden hat, und außerdem von dem besten Ort, den irgendein Mitglied des Schwarms gefunden hat. Nach einigen Schritten sammelt sich die Population um einen Ort, oder um wenige Orte, oder sie zieht weiter.
Der Algorithmus basiert auf einer Population, nicht auf einem einzelnen aktuellen Punkt. In dieser Hinsicht ist particleswarm dem genetischen Algorithmus ähnlich (siehe Was ist ein genetischer Algorithmus?).
In der Iteration n des Algorithmus hat ein Partikel eine Geschwindigkeit v(n), die von folgenden Werten abhängt:
Die Position des besten Zielfunktionswertes, der gefunden wurde, s(n).
Die Position des besten Zielfunktionswertes unter seinen Nachbarn, g(n).
Die vorherige Geschwindigkeit v(n – 1).
Die Position eines Partikels x(n) wird entsprechend seiner Geschwindigkeit aktualisiert:
angepasst, um innerhalb der Grenzen zu bleiben.
Die Geschwindigkeit eines Partikels ändert sich näherungsweise gemäß dieser Gleichung:
Hierbei sind r(1) und r(2) zufällige Skalarwerte zwischen 0 und 1, und W(n) ist ein Trägheitsfaktor, der sich während der Iterationen anpasst. Der vollständige Algorithmus verwendet zufällig variierende Nachbarschaften und beinhaltet Modifikationen, wenn er auf einen Verbesserungspunkt stößt. Siehe Algorithmus zur Partikelschwarmoptimierung.
Wie in dieser Abbildung dargestellt, scheinen die Anfangsgeschwindigkeiten der Partikel zufällig zu sein, aber nach einigen Iterationen kann der Schwarm zu einer lokalen oder sogar globalen Lösung konvergieren.
