Benutzer:Talisca/Artikelentwurf
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
[Bearbeiten | Quelltext bearbeiten]Im Jahre 1986 entwickelte Craig W. Reynold ein Modell zur Beschreibung vom Flugverhalten der Vögel und veröffentlichte u. a. erste Simulationen[[1], 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) (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
[Bearbeiten | Quelltext bearbeiten]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:
: | Partikelposition,im Definitionsbereich der zu optimierenden Variablen |
: | Beste gefundene Position des Partikels (lokal) |
: | Geschwindigkeit und Flugrichtung des Partikels |
Weitere Parameter für die Partikel und den Schwarm:
: | Beste gefundene Position des Schwarms (global) |
: | Beschleunigungskoeffizienten |
: | Gleichverteilte Zufallsvariablen mit oberer Grenze |
: | 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: . 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: . Allerdings wird selbst durch Verwendung von Kontrollparametern nicht garantiert, dass die Partikel im Lösungsraum verbleiben. Darum wurden drei wesentliche Verfahren eingeführt5:
Zu Beginn werden die n-dimensionalen Vektoren der Geschwindigkeit und der Position von jedem Partikel gleichverteilt zufällig im Definitionsbereich mit und initialisiert. Anschließend wird die Geschwindigkeit und dann die Position von jedem Partikel zum Zeitpunkt aktualisiert.
Die aktuelle Geschwindigkeit und die aktuelle Position eines Partikels wird festgelegt durch:
Die Beschleunigungskoeffizienten und 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 und 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 eines zu optimierenden Maximierungsproblems:
Mit ergibt sich für die global beste Position (globale Gedächtnis) dementsprechend:
Pseudocode
[Bearbeiten | Quelltext bearbeiten]Eine einfache Umsetzung der PSO als Pseudocode kann wie folgt aussehen:
: | |||
Abbruchkriterien
[Bearbeiten | Quelltext bearbeiten]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 gefunden werden, so dass gilt:
- Ist der Wert 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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]Die Inertia Weight (Trägheit) wurde von Eberhart und Yuhui Shi mit dem Parameter vorgestellt, welches die Geschwindigkeit des vorherigen Schrittes und damit das Verhalten der Partikel beeinflusst.
Dabei tendiert ein Schwarm mit einem sehr kleinen 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
[Bearbeiten | Quelltext bearbeiten]
Comprehensive Learning PSO
[Bearbeiten | Quelltext bearbeiten]Anwendungsgebiete
[Bearbeiten | Quelltext bearbeiten]- Training neuronaler Netze
- Mustererkennung
- Betriebswirtschaftliche Problemstellungen u. a. das bekannte Traveling Salesman Problem
Quellen
[Bearbeiten | Quelltext bearbeiten]- ↑ Buch,Titel,Autor,Jahr,Verlag,Ausgabe,Trallala