Konvergenzanalyse für die Partikelschwarmoptimierung

Particle swarm optimization (PSO) is a very popular, randomized, nature-inspired meta-heuristic for solving continuous black box optimization problems. The main idea is to mimic the behavior of natural swarms like, e. g., bird flocks and fish swarms that find pleasant regions by sharing information. The movement of a particle is influenced not only by its own experience, but also by the experiences of its swarm members. In this thesis, we study the convergence process in detail. In order to measure how far the swarm at a certain time is already converged, we define and analyze the potential of a particle swarm. This potential analysis leads to the proof that in a 1-dimensional situation, the swarm with probability 1 converges towards a local optimum for a comparatively wide range of objective functions. Additionally, we apply drift theory in order to prove that for unimodal objective functions the result of the PSO algorithm agrees with the actual optimum in k digits after time O(k). In the general D-dimensional case, it turns out that the swarm might not converge towards a local optimum. Instead, it gets stuck in a situation where some dimensions have a potential that is orders of magnitude smaller than others. Such dimensions with a too small potential lose their influence on the behavior of the algorithm, and therefore the respective entries are not optimized. In the end, the swarm stagnates, i. e., it converges towards a point in the search space that is not even a local optimum. In order to solve this issue, we propose a slightly modified PSO that again guarantees convergence towards a local optimum.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