Convergence Analysis for Particle Swarm Optimization

Beschreibung

Partikelschwarmoptimierung (PSO) ist eine sehr verbreitete, randomisierte, von der Natur inspirierte Meta-Heuristik zum Lösen von Black-Box-Optimierungsproblemen über einem kontinuierlichen Suchraum. Die Grundidee besteht in der Nachahmung des Verhaltens von in der Natur auftretenden Schwärmen, die vielversprechende Regionen finden, indem sie Informationen austauschen und miteinander kooperieren, anstatt gegeneinander zu konkurrieren. Im daraus gewonnenen Optimierungsverfahren bewegen sich künstliche Partikel durch den D-dimensionalen Raum der reellen Zahlen, wobei die Bewegung eines Partikels nicht nur von dessen eigener Erfahrung, sondern genauso von den Erfahrungen der übrigen Schwarmmitglieder beeinflusst wird.

Obwohl diese Methode in zahlreichen realen Anwendungen verwendet wird, haben theoretische Betrachtungen bisher nur einige wenige Teilaspekte des Algorithmus erklärt. Ein solcher Aspekt, mit dem sich viele Wissenschaftler auseinandersetzen, ist das Phänomen der Konvergenz des Partikelschwarms. Das bedeutet, dass die Partikel gegen einen Punkt im Suchraum konvergieren. Insbesondere konnten notwendige und hinreichende Bedingungen an die Schwarmparameter, bestimmte Parameter die das Verhalten des Schwarms steuern, ermittelt werden, unter denen Konvergenz gewährleistet ist. Allerdings ist bis jetzt kein theoretisches Resultat über die Qualität dieses Grenzwertes bekannt, das für den unmodifizierten PSO-Algorithmus in einer allgemeineren Situation als beispielsweise nur für genau eine Zielfunktion bewiesen werden konnte.

Diese Arbeit befasst sich detailliert mit dem Prozess der Konvergenz. Um zu messen, wie stark der Schwarm bereits konvergiert ist, wird das Potential eines Partikelschwarms eingeführt und analysiert. Das Potential ist so konstruiert, dass es genau dann gegen 0 konvergiert, wenn der Schwarm konvergiert. Im 1-dimensionalen Fall ergeben die Betrachtungen, dass sich das Potential erhöht, solange der Schwarm weit vom nächsten lokalen Optimum entfernt ist. Diese Beobachtung führt zum Beweis des ersten Hauptresultats, nämlich dass im 1-dimensionalen Fall der Schwarm fast sicher gegen ein lokales Optimum konvergiert. Dieses Resultat ist für eine vergleichbar gezeigt werden, dass das Ergebnis des PSO-Algorithmus nach einer Zeit von O(k) mit dem tatsächlichen Optimum in k Bits übereinstimmt. Im allgemeinen D-dimensionalen Fall stellt sich heraus, dass der Schwarm nicht zwangsläufig gegen ein lokales Optimum konvergiert. Stattdessen gerät er in eine Situation, in der manche Dimensionen ein um Größenordnungen geringeres Potential haben als andere. Diese Dimensionen mit zu geringem Potential verlieren ihren Einfluss auf das Verhalten des Algorithmus, und daher werden die entsprechenden Einträge nicht optimiert. Die Konsequenz ist Stagnation des Schwarms, das heißt, der Schwarm konvergiert gegen einen Punkt im Suchraum, der nicht mal ein lokales Optimum ist. Um dieses Problem zu lösen wird eine leicht modifizierte Version der PSO vorgeschlagen, die wiederum eine Garantie für Konvergenz gegen ein lokales Optimum zulässt.