Particle Swarm Optimization (PSO)


(Contents)(Previous)(Next)

Betrachten wir einen Schwarm von Vögeln, Fischen oder andern Lebewesen, so können wir diesem Schwarm beispielsweise die Aufgabe erteilen, die Landschaft zu erkunden und den höchsten oder tiefsten Punkt zu finden. Der Schwarm erhält zunächst eine Übersicht, weil sich die einzelnen Individuen an unterschiedlichen Orten befinden. Durch Bewegung der Individuen wird das Wissen über die Landschaft kontinuierlich verbessert. Zur Steuerung der Bewegung ist nicht nur die Erfahrung eines einzelnen Individuums hilfreich, sondern diejenige des gesamten Schwarms, was natürlich eine gewisse Kommunikation voraussetzt. Jedes Individuum könnte damit seine Bewegung unter Verwendung der gesamten bisherigen Kenntnis des Schwarms über die Landschaft steuern. Der Einfachheit halber wird bei praktischen PSO Implementierungen die Informationsmenge allerdings drastisch reduziert. Dabei gibt es viele verschiedene Möglichkeiten. Wir betrachten im folgenden eine davon.

Zunächst wird jedes Individuum wird durch einen aktuellen Ort rIaktuell im Suchraum und eine aktuelle Geschwindigkeit vaktuell beschrieben, wobei sich aus der Geschwindigkeit der nächstfolgende Ort errechnet. Zu Beginn der Suche werden diese Grössen zufällig initialisiert. Für jedes Individuum wird nun fIaktuell=f(rIaktuell) berechnet. Je nach Problemstellung werden Minima oder Maxima von f gesucht. Wir nehmen im folgenden an, es werden Maxima gesucht. Jedes Individuum speichert nun den Ort mit dem bisher besten Funktionswert fIbest. Ausserdem speichert der gesamte Schwarm Position rbest und Wert des besten Individuums fbest=f(rbest). Für den nächsten Schritt werden die Geschwindigkeiten aller Individuen so modifiziert, dass jedes Individuum einerseits eher in Richtung des besten Individuums (Schwarmziel) und andererseits eher in Richtung seiner bisher besten Position (individuelles Ziel) fliegt. Die neuen Geschwindigkeitsvektoren sind dann (der Einfachheit halber) Linearkombinationen der bisherigen Geschwindigkeitsvektoren und der Richtungsvektoren in Richtung beste Position des Schwarms und in Richtung bisher beste Position des Individuums. Dabei werden Gewichtsfaktoren eingeführt, welche den Suchablauf beeinflussen. Um nicht zu stark zielgerichtet zu werden, können die Gewichtsfaktoren einen Zufallsanteil erhalten.

Typischerweise ist der Schwarm zu Beginn über die gesamte Landschaft verteilt, formiert und konzentriert sich dann aber zunehmend. Wenn diese Konzentration rasch zustande kommt, ist die Suche sehr zielgerichtet und die Chance, das globale Optimum zu finden klein. Andernfalls kann auch dieser Algorithmus recht langsam sein.

Übungsaufgabe: Konkretisiere den skizzierten PSO Algorithmus und überlege, wie die Suche im zweidimensionalen Fall eines Langgestreckten Tales verläuft.

Übungsaufgabe: Suche nach Verallgemeinerungen. Welche Schwierigkeiten ergeben sich daraus?

Übungsaufgabe: Versuche PSO mit SA zu kombinieren.


(Contents)(Previous)(Next)