Abstract:
In letzter Zeit hat die Komplexität von Optimierungsproblemen drastisch zugenommen, was zu nichtlinearen, multimodalen, komplex beschränkten und nicht konvexen Suchräumen führt. Im Allgemeinen können deterministische oder konventionelle Optimierungsmethoden solche Probleme nicht ohne Vereinfachungen lösen, was wiederum eine komplexe Aufgaben darstellt. Populationsbasierte Metaheuristiken - wie evolutionäre Algorithmen - sind überzeugende Alternativen zur Lösung komplexer und großskaliger Optimierungsprobleme. Sie stellen kaum Anforderungen an die Formulierung des Optimierungsproblems, da sie keine Konvexität, Linearität, Stetigkeit oder Differnzierbarkeit erfordern. ... mehr Sie sind in der Lage, lokale Optima zu vermeiden und Zielfunktionen mit Rauschen zu behandeln. Darüber hinaus stehen populationsbasierte Metaheuristiken über eine generische Implementierung zur Verfügung, die ihre Anpassung zur Lösung beliebiger neuer Optimierungsprobleme erleichtert. Diese vorteilhaften Eigenschaften sind jedoch nicht ohne Nachteile, wie der Verlust der Garantie für das Auffinden des globalen Optimums und der hohe Rechenaufwand für die zeitnahe Lösung komplexer Probleme.
Um diese Einschränkungen zu überwinden, ist es von großer Bedeutung, die inhärente Parallelität von populationsbasierten Metaheuristiken und ihre Fähigkeit, hybride Methoden zusammen mit anderen algorithmischen Ansätze zu formulieren, zu nutzen.
Im Zusammenhang mit der Parallelisierung und Hybridisierung von populationsbasierten Metaheuristiken hat das Interesse am Einsatz robuster und moderner Softwaretechnologien zur Nutzung der gestiegenen Rechenkapazitäten moderner Hardware wie Cluster und Cloud-Umgebungen gewachsen. Trotz dieser Entwicklungen gibt es immer noch offene Herausforderungen, wie man den Parallelisierungsprozess bereits entwickelter populationsbasierter Metaheuristiken in Cluster-Computing-Umgebungen und die Hybridisierung mit anderen Algorithmen erleichtern kann und wie man die parallele Leistung der evolutionären Algorithmen verbessern kann.
In dieser Dissertation wird ein generisches, flexibles und skalierbares Verfahren zur Nutzung bestehender populationsbasierter Metaheuristiken im Allgemeinen und evolutionärer Algorithmen im Besonderen in Cluster-Computing-Umgebungen konzipiert und entwickelt. Um mehr Effizienz bei der Parallelisierung und Hybridisierung von evolutionären Algorithmen zu gewährleisten, ist unsere Lösung im Gegensatz zu modernen monolithischen komplexen Softwarearchitekturen hochgradig modular aufgebaut. In unserer Lösung behandeln wir das Problem der Parallelisierung von evolutionären Algorithmen durch die Einführung zweier Methoden. In beiden Methoden stellen wir eine neue Perspektive für die Realisierung und den Einsatz verschiedener paralleler Modelle evolutionärer Algorithmen in Cluster-Computing-Umgebungen vor, indem wir zwischen Funktionalitäten, die mit den evolutionären Algorithmen zusammenhängen, und solchen, die mit den Parallelisierungsmodellen zusammenhängen, unterscheiden. Wir entkoppeln die grundlegenden Bausteine jeder Funktionalität und kapseln sie in separater und autonomer Software, die als Service bezeichnet wird. Dies ermöglicht es den Entwicklern von evolutionären Algorithmen, die Bausteine einfach zu kombinieren, um eine der grundlegenden Parallelisierungsmodelle umzusetzen. Während sich die erste Methode darauf fokussiert, bestehende evolutionäre Algorithmen auf eines der grundlegenden Parallelisierungsmodelle wie das Global Modell und das Coarse-Grained Modell abzubilden, fokussiert sich die zweite Methode darauf, zwei oder mehr der grundlegenden Parallelisierungsmodelle in einer hierarchischen Form zu kombinieren, um die parallele Leistung des EA zu verbessern, indem die Nachteile jedes Modells reduziert und die Vorteile genutzt werden.
Um die Leistung und die Anwendbarkeit der evolutionären Algorithmen in einem breiten Spektrum von Anwendungsszenarien zu verbessern, ist ein Hybridisierungsprozess zwischen bestehenden evolutionären Algorithmen und anderen Algorithmen in Cluster-Computing-Umgebungen erforderlich. Um eine solche Hybridisierung zu ermöglichen, wird unsere Lösung weiterentwickelt, wobei zwei neue Hybridisierungsansätze für das partielle Seeding der initialen Population von evolutionären Algorithmen durch den Einsatz von maschinellen Lernen untersucht werden. In dieser Arbeit stellen wir Mechanismen vor, die die Zusammenarbeit von evolutionären Algorithmen mit anderen Algorithmen und Werkzeugen wie Simulatoren und Vorhersage-Frameworks erleichtern. Unsere Benchmark-Experimente mit realen Optimierungsproblemen zeigen, dass die vorgeschlagene Methode nicht nur die Skalierbarkeit und die Leistung von evolutionären Algorithmen erhöht, sondern auch deren Anwendbarkeit, indem sie neue Perspektiven für die Anwendung evolutionärer Algorithmen auf ein breites Spektrum von realen Optimierungsproblemen eröffnet.
Abstract (englisch):
Recently, the complexity of optimization problems has dramatically increased leading to non-linear, multimodal, constrained and non-convex search spaces. Generally, deterministic or conventional optimization methods cannot tackle such problems without simplifications which in turn are not trivial tasks. Among others, population-based metaheuristics - such as evolutionary algorithms - are convincing alternatives to solve complex and large-scale optimization problems. They make hardly any demands on the formulation of the optimization problem since they do not require convexity, linearity, continuity or derivability. ... mehr They are able to escape from local optima and handle objective functions with noise. Additionally, population-based metaheuristics have a generic implementation which facilitates their adaptation to solve any new optimization problems. These beneficial traits do not exclude some drawbacks such as the absence of guarantee for finding the global optimum and the high computational demands for solving complex and large-scale problems in a timely manner. To overcome these limitations, it is of great importance to leverage the advantage of the inherent parallel nature of population-based metaheuristics and their ability to formulate hybrid methods along with other algorithmic approaches. In the context of parallelizing and hybridizing population-based metaheuristics, the interest in using robust and modern software technologies for exploiting the enormous computational capabilities of modern hardware such as clusters and cloud environments has increased. But despite that, there are still some open challenges to be faced. For example, which software design can be used to facilitate the parallelization process of already developed population-based metaheuristics and increase the flexibility to hybridize them with other algorithms to solve more complex tasks in cluster computing environments. In the present thesis, a generic, flexible and scalable method for using existing population-based metaheuristics such as evolutionary algorithms in cluster computing environments is conceptualized and developed. To ensure more efficiency in parallelizing and hybridizing evolutionary algorithms, our solution is developed in a highly modular manner in contrast to state-of-the-art monolithic complex software architectures. In this solution, we handle the problem of parallelization of evolutionary algorithms by proposing two methods. For both of them, we introduce a new perspective to realize and deploy several parallel models of evolutionary algorithms in cluster computing environments by distinguishing between functionalities related to the evolutionary algorithms and the ones related to the parallelization models. We decouple the basic building blocks of each functionality and encapsulate them in separate small and autonomous software; known as service. This enables the developers of evolutionary algorithms to easily combine the building blocks to form one of the well-known parallelization models. While the first method focuses on mapping existing evolutionary algorithms to the basic parallelization models such as the Global Model and the Coarse-Grained Model, the second one combines two or more of the basic parallelization models in a hierarchical form to enhance the parallel performance by reducing the disadvantages of each model and leveraging the advantages. For enhancing the performance and the applicability of the evolutionary algorithms on a wide range of application scenarios, a hybridization process between existing evolutionary algorithms and other algorithms in cluster computing environments is required. To facilitate such hybridization, further development of our solution is achieved whereby two new hybridization approaches based on machine learning techniques for the partial seeding of the initial populations of evolutionary algorithms are proposed. In the present thesis, we introduce simple mechanisms to facilitate the collaboration of evolutionary algorithms with other algorithms and tools like simulators and forecasting frameworks. Our benchmark experiments on real-world optimization problems indicate that the proposed solution is promising not only in increasing the scalability and enhancing the performance of evolutionary algorithms but also in extending the applicability of them, hence opening new perspectives for applying evolutionary algorithms on a wide spectrum of real-world optimization problems.
