Parallele adaptive Schwarmsuche für Blackbox-Probleme

Abstract

In der heutigen Wissenschaft und Wirtschaft haben wir es oft mit Systemen zu tun, welche aus Problemen bestehen, die sehr komplex und nicht einfach zu lösen sind. Aufgrund der zunehmenden Komplexität und der teilweise fehlenden Informationen ist es bereits heutzutage nicht mehr möglich, solche Probleme – welche als Blackbox-Probleme klassifiziert werden – per Hand zu lösen. Um das Maximum oder Minimum einer Funktion zu finden, wird auf Optimierungsmethoden zurückgegriffen, die uns ermöglichen, eine optimale Lösung für das Problem zu suchen und ggf. zu finden. Stochastische Methoden haben in den letzten Jahren gezeigt, dass sie sehr gut geeignet sind, solche Probleme zu lösen. Der Vorteil der Verwendung von stochastischen Methoden ist, dass sie nicht den Gradienten des zu optimierenden Problems verwenden, so dass sie sowohl bei großen als auch bei komplexen Optimierungsproblemen erfolgreich angewendet werden können. Diese Vielseitigkeit hat aber ihren Preis. Es gibt hauptsächlich drei wesentliche Aspekte, die die Effizienz der Lösung beeinträchtigen: 1. Die realen Probleme werden immer größer und komplizierter, was erhebliche Ressourcen in Zeit und Hardware erfordert. 2. Optimierungsprobleme sind durch mehrere lokale Optima charakterisiert, die ein Verfahren zur Vermeidung einer zu frühen Konvergenz erfordern. 3. Algorithmen erfordern einige problembedingte Anpassungen ihrer Verhaltensparameter, um bessere Ergebnisse zu erzielen. In dieser Arbeit wird ein Framework (Parallel Adaptive Swarm Search - PASS) vorgestellt, das die Ermittlung der möglichst optimalen Lösung für Black-box Pro- bleme gewährleistet. Durch das Framework kann der Nutzer ein Mapping des Algorithmus an die vorhandene Hardware und Software (Problemart) realisieren. Das Problem der Parallelisierung wird durch die Umwandlung des Algorithmus von seriell zu parallel gelöst. Das Problem des Stillstands wird durch das Benut- zen des Island Models behandelt und für das Problem der Adaptivität wird ein neuer Suchalgorithmus vorgestellt, welcher die Suche der optimalen Parameter beschleunigt. In dieser Arbeit wird PASS mit bekannten Verfahren aus der Literatur (wie z.B. Particle Swarm Optimization, Differential Evolution, Artificial Bee Colony usw.) mit unterschiedlichen Benchmark-Problemen verglichen. Die erste Gruppe der Benchmark-Probleme besteht aus synthetischen Funktionen bekannt aus der Literatur (wie z.B. Rastrigin Funktion, Rosenbrock Funktion) und die zweite Gruppe besteht aus Problemen aus der realen Welt. Untersuchungen in dieser Arbeit haben gezeigt, dass die Anpassungen zu besse- ren Ergebnissen führen. Durch die adaptive Natur des Frameworks, ist es in vielen Rechnerarchitekturen nutzbar und für viele Probleme anwendbar.