Benutzer:Talisca/Artikelentwurf

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Talisca auf.

Particle Swarm Optimization (englisch für "Teilchenschwarmoptimierung") ist ein heuristisches Optimierungsverfahren der Unterkategorie Schwarmintelligenzen (siehe auch Ameisenalgorithmus, Intelligent Water Drops) zur näherungsweisen Lösung von Minimierung- bzw. Maximierungsproblemen.

Ursprung

Im Jahre 1986 entwickelte Craig W. Reynold ein Modell zur Beschreibung vom Flugverhalten der Vögel und veröffentlichte u. a. erste Simulationen[, 4]. Dieses Modell zeigte eine mögliche Umsetzung des natürlichen Verhaltens einer künstlichen Lebensform, basierend auf Vögeln, welche von ihm Boids (andere Aussprache für „birds“ - New Yorker Akzent) genannt wurden. Dadurch bestimmen virtuelle Figuren ihr Verhalten bis zu einem gewissen Grad selbst, können sich somit selbst verbessern und befreien den Entwickler von der Umsetzung vieler Details einer Bewegung. Darauf folgten zahlreiche Publikationen und Animationen in Filmen und Spielen, was zu einer Entwicklung von drei wesentlichen Regeln führte: Orientierung, Zusammenhalt und Aufteilung.

1990 entwickelte Frank Heppner (Biologe), unter Verwendung von Reynolds Artikel, sein eigenes Modell. Er betrachtete in seiner Arbeit das Verhalten von Vogelschwärmen bei der Futter- und Rastplatzsuche[2, 3]. Simulationen zeigten, dass die Vögel zu Beginn ohne Ziel fliegen und instinktiv Schwärme bilden, bis einer der Vögel einen Rastplatz gefunden hat. Da jeder Vogel die eigene Geschwindigkeit und das Ziel ändern kann, folgen Vögel in unmittelbarer Umgebung eines Artgenossen diesem, sollte sich dieser vom Schwarm trennen und zum Rastplatz fliegen. Vögel die sich bereits dort befinden, verleiten andere dazu, sich ebenfalls dort zu versammeln. Die Art und Weise wie ein Vogel seine Nachbarn dazu verleitet ihm zu einem Ort zu folgen, erhöht auch die Chance, dass sich andere Vögel anschließen. Sie lernen also primär vom Erfolg ihrer Nachbarn4. Auf Grund der Einsatzmöglichkeiten, entwickelten 1995 Dr. Russell C. Eberhart (Elektrotechniker) und Dr. James Kennedy (Sozialpsychologe) das von Heppner entwickelte Modell auf Grund eigener Inspiration von sozialen Verhaltensmetaphern der Vögel weiter, indem sie die Zusammenarbeit der Vögel im Schwarm mit einbezogen haben, genannt: Particle Swarm Optimization. Sie verbesserten im wesentlichen Heppners Methode und wandten diese anschließend zum Lösen von Optimierungsproblemen an.

Formal

Jedes Partikel kennt seine eigene Geschwindigkeit, die aktuelle Position, die Flugrichtung und die persönlich beste gefundene Position. Der Schwarm kennt zusätzlich die global beste, von allen Partikeln gefundene Position. Somit wird jedes Partikel charakterisiert durch:

$x_{i}$:	Partikelposition,im Definitionsbereich der zu optimierenden Variablen
$x_{lbest,i}$:	Beste gefundene Position des Partikels (lokal)
${\vec {\nu }}_{i}$:	Geschwindigkeit und Flugrichtung des Partikels

Weitere Parameter für die Partikel und den Schwarm:

$x_{gbest}$:	Beste gefundene Position des Schwarms (global)
$\alpha _{1},\alpha _{2}$:	Beschleunigungskoeffizienten
${\hat {r}}_{1},{\hat {r}}_{2}$:	Gleichverteilte Zufallsvariablen mit oberer Grenze
$\nu _{max}$:	Maximale Geschwindigkeit

Die Geschwindigkeit der Partikel im n-dimensionalen Suchraum sollte auf einen maximalen Wert beschränkt sein, da sie während des Zeitablaufs schnell anwächst: $\nu _{i}^{n}\epsilon [-\nu _{max}^{n},\nu _{max}^{n}]$. Zudem müssen sich die Positionen der einzelnen Partikel im Definitionsbereich der zu optimierenden Variablen befinden, welche durch die minimalen und maximalen Schranken der Dimension eingeschränkt werden: $x_{i}^{n}\epsilon [{left}^{n},{right}^{n}]$. Allerdings wird selbst durch Verwendung von Kontrollparametern nicht garantiert, dass die Partikel im Lösungsraum verbleiben. Darum wurden drei wesentliche Verfahren eingeführt5:

Datei:PSO-Partikel-Grenzen.png

Grenzverhalten Unsichtbare Wände: Die Partikel können sich in allen Dimensionen bewegen. Nur bei der Überschreitung des Definitionsbereichs wird hierbei auf die Berechnung der Fitness-Funktion verzichtet. Reflektierende Wände: Versucht ein Partikel die Grenzen des Lösungsraums zu verlassen, wird das Vorzeichen der Richtung geändert. Absorbierende Wände: Wenn ein Partikel den Lösungsraum verlassen würde, wird die Geschwindigkeit auf den zulässigen Grenzwert geändert (Energie wird weggenommen).

Zu Beginn werden die n-dimensionalen Vektoren der Geschwindigkeit ${\vec {\nu }}_{i}=(\nu _{i}^{1},\nu _{i}^{2},...,\nu _{i}^{n})$ und der Position $x_{i}=(x_{i}^{1},x_{i}^{2},...,x_{i}^{n})$ von jedem Partikel gleichverteilt zufällig im Definitionsbereich mit ${\vec {\nu }}_{i}=rand(-\nu _{max},\nu _{max})$ und $x_{i}=rand(left,right)$ initialisiert. Anschließend wird die Geschwindigkeit und dann die Position von jedem Partikel zum Zeitpunkt $t$ aktualisiert.

Die aktuelle Geschwindigkeit und die aktuelle Position eines Partikels wird festgelegt durch:

$\nu _{i}(t+1)=\nu _{i}(t)+\overbrace {\alpha _{1}*{\hat {r}}_{i}*({x}_{lbest,i}-{x}_{i}(t))} ^{eigenes\ Gedaechtnis}+\overbrace {\alpha _{2}*{\tilde {r}}_{i}*({x}_{gbest,i}(t)-{x}_{i}(t))} ^{globales\ Gedaechtnis}$

$x_{i}(t+1)=x_{i}(t)+\nu _{i}(t+1)$

Die Beschleunigungskoeffizienten $\alpha _{1}$ und $\alpha _{2}$ sorgen für eine Gewichtung des sozialen Einflusses anderer Partikel als auch der kognitiven Komponente im Verhältnis zur aktuellen Flugrichtung des Partikels. Die Variablen ${\hat {r}}_{i}$ und ${\tilde {r}}_{i}$ sind gleichverteilte Zufallsvariablen zwischen 0 und 1, die für jedes Partikel erzeugt werden. Unter Berücksichtigung der vorherigen Geschwindigkeit sowie der besten Position des Partikels, als auch der besten Position des Schwarms, wird die aktuelle Geschwindigkeit berechnet.

Für die persönlich beste Position (lokales Gedächtnis) ergibt sich mit der Funktion $f$ eines zu optimierenden Maximierungsproblems:

$x_{lbest,i}(t+1)={\begin{cases}{x_{lbest,i}(t)}&{{;\ }f\left(x_{i}(t+1)\right)<f\left(x_{lbest,i}(t)\right)}\\{x_{i}(t+1)}&{{;\ }f\left(x_{i}(t+1)\right)\geq f\left(x_{lbest,i}(t)\right)}\end{cases}}$

Mit $0..i\ =\ {\text{Anzahl der Partikel}}$ ergibt sich für die global beste Position (globale Gedächtnis) dementsprechend:

$x_{gbest}(t)\ =\ arg\ max\ f(x_{lbest,0..i})$

Pseudocode

Eine einfache Umsetzung der PSO als Pseudocode kann wie folgt aussehen:

${repeat}$:
	${for\ each\ particle\ i\ in\ [0..s]}$
		${if\ f(x_{i})>f(x_{lbest,i})\ then\ x_{lbest,i}=x_{i}}$
		${if\ f(x_{lbest,i})>f(x_{gbest})\ then\ x_{gbest}=x_{lbest,i}}$
		$\nu _{i}(t+1)=\nu _{i}(t)+\alpha _{1}*{\hat {r}}_{i}*({x}_{lbest,i}-{x}_{i}(t))+\alpha _{2}*{\tilde {r}}_{i}*({x}_{gbest,i}(t)-{x}_{i}(t))$
		$x_{i}(t+1)=x_{i}(t)+\nu _{i}(t+1)$
	${end\ for}$
${until\ stopping\ condition\ is\ true}$

Abbruchkriterien

Wichtig für den Erfolg einer Suche ist die Wahl des passenden Abbruchkriteriums. Die O-Laufzeit sollte dabei ein Minimum erreichen, indem die Fitness-Funktion nur so oft wie nötig verwendet wird.

• Abbruch nach n Iterationen

Hier besteht die Gefahr, dass die Suche zu einem Zeitpunkt terminiert, an dem noch keine gute Lösung gefunden wurde. Für gewöhnlich wird dieses Kriterium nur eingesetzt um den Abbruch zu erzwingen, sollte der Algorithmus nicht konvergieren.

• Abbruch bei akzeptabler Lösung

Die Suche wird abgebrochen, sollte ein $x_{i}$ gefunden werden, so dass gilt:

$f(x_{i})<\left|f(x_{gbest})-\varepsilon \right|$

Ist der Wert $\varepsilon$ zu groß, so stoppt der Algorithmus evtl. bei einer schlechten Lösung. Ist der Wert zu klein, terminiert der Algorithmus unter Umständen gar nicht.

Topologien

Durch Variation der Topologien der Schwärme wurde ebenfalls versucht die PSO zu verbessern[12, 13]. Robert R. Mendez und Kennedy untersuchten verschiedene Topologien der Schwärme. Ponnuthurai Nagaratnam Suganthan untersuchte ein dynamisches Konzept der Nachbarschaften. So verändern sich die Schwärme im Laufe der Zeit in zwei Arten: Die Anzahl der Nachbarn mit denen ein Partikel initialisiert wird, hat die Größe 1, d. h. das Partikel ist sein eigener Nachbar. Die Nachbarschaftsgröße erhöht sich nun im Laufe der Zeit, wodurch die sich die Topologie von lokal zu global abändert. Außerdem werden, basierend auf dem Hamming-Abstand, die potenziellen Nachbarn für ein Partikel bei jeder Iteration neu berechnet.

Abbildung

In der originalen PSO wurden zwei verschiedene Arten von Topologien definiert:

GBest

Alle Partikel sind Nachbarn voneinander, womit die Aktualisierungsregel der Geschwindigkeiten durch die beste Position aller Partikel im Schwarm abgeändert wird. Es wird angenommen, dass solche Schwärme schnell konvergieren, da sich die Informationen über ein Optima schnell verbreiten und alle Partikel somit sofort von der besten Position des Suchraums angezogen werden und dessen Gegend erkunden. Sollte das globale Optimum allerdings nicht in der Nähe des besten Partikels sein, wird der Schwarm wahrscheinlich nicht andere Regionen erkunden – soll heißen, der Schwarm bleibt in einem lokalen Optima gefangen.

LBest

Nur eine gewisse Anzahl an Partikeln (Nachbarschaftsgröße) kann die Geschwindigkeitsaktualisierungsregel eines bestimmten Partikels beeinflussen und der Suchraum wird von mehreren Gruppen erkundet und somit besser abgedeckt. Jedes Partikel enthält somit nur Informationen über sich selbst und über seine unmittelbaren Nachbarn. Die Konvergenz findet langsamer statt, das globale Optimum kann aber mit höherer Wahrscheinlichkeit gefunden werden.

Bei der Wahl einer Topologie ist also schnelle (GBest) und langsame – dafür jedoch robustere Suche - (LBest) Konvergenz abzuwägen. Bei verschiedensten Versuchen hat sich jedoch rausgestellt, dass die LBest und Von-Neumann-Nachbarschaft am besten geeignet sind.

Erweiterungen

Um bessere Konvergenzgeschwindigkeiten und gleichzeitig qualitativ hochwertige Lösungen zu erreichen, wurden im Laufe der Zeit viele Erweiterungen für die PSO erarbeitet. So zum Beispiel eine der ersten Varianten: die Inertia Weight.

Inertia Weight

Die Inertia Weight (Trägheit) wurde von Eberhart und Yuhui Shi mit dem Parameter $\omega$ vorgestellt, welches die Geschwindigkeit des vorherigen Schrittes und damit das Verhalten der Partikel beeinflusst.

$\nu _{i}(t+1)={\color {Red}\omega }*\nu _{i}(t)+\alpha _{1}*{\hat {r}}_{i}*({x}_{lbest,i}-{x}_{i}(t))+\alpha _{2}*{\tilde {r}}_{i}*({x}_{gbest,i}(t)-{x}_{i}(t))$

Dabei tendiert ein Schwarm mit einem sehr kleinen $\omega$ zu einer lokalen Suche, da diese somit sehr schnell in einem lokalen Optimum konvergiert. Bei einem großen Wert hingegen, tendiert der Schwarm zu einer globalen und damit erschwerten Suche. Darum kam der Vorschlag, dass die inertia weight im Laufe der Suche verringert wird. Dadurch erkundet der Schwarm zunächst den gesamten Lösungsraum und entwickelt sich mit der Zeit zu einer lokalen Suche.

Constriction Factor

$\nu _{i}(t+1)={\color {Red}\mathrm {K} }*\left[\nu _{i}(t)+\alpha _{1}*{\hat {r}}_{i}*({x}_{lbest,i}-{x}_{i}(t))+\alpha _{2}*{\tilde {r}}_{i}*({x}_{gbest,i}(t)-{x}_{i}(t))\right]$

Anwendungsgebiete

• Training neuronaler Netze
• Mustererkennung
• Betriebswirtschaftliche Problemstellungen u. a. das bekannte Traveling Salesman Problem