Model-Driven Optimization with a Focus on the Effectiveness and Efficiency of Evolutionary Algorithms
Loading...
Files
Date
Publisher
Philipps-Universität Marburg
Abstract
Optimization problems are ubiquitous in software engineering. They arise, for example, when searching for a modular software design or planning a cost-efficient development process. Search-based software engineering (SBSE) is concerned with solving optimization problems by applying search-based algorithms. Among the most popular are evolutionary algorithms, which are the focus of this thesis. Following the example of natural evolution, they use selection, mutation, and crossover operators to evolve existing solutions.
In the hope of enabling the use of SBSE without optimization expertise, model-driven optimization (MDO) relies on model-driven engineering (MDE); models and model transformations are used to specify optimization problems and solution algorithms. Two ways of representing solutions, the model-based approach (MB-MDO) and the rule-based approach, have established. However, the implications of choosing one over the other are not clear. Therefore, we compare both approaches qualitatively and quantitatively and pursue MB-MDO as the more promising approach in the rest of the thesis.
How to design efficient and effective evolutionary algorithms is a central question in MB-MDO. Moreover, how to perform crossover there is not yet known. We first present a framework that highlights and explains the core concepts of evolutionary algorithms in MB-MDO and formalizes them based on graph transformation theory. It not only contributes to the understanding of evolutionary algorithms in MB-MDO, but in particular facilitates their precise specification, analysis, and evaluation. The framework is used to define important properties of mutation operators and to evaluate their impact on the efficiency and effectiveness of evolutionary algorithms. Furthermore, a general, graph-based approach for the construction of crossover operators in MB-MDO is presented. The general approach is also concretized for the Eclipse Modeling Framework (EMF). Finally, an evaluation of a prototypical implementation shows the relevance of crossover operators for evolutionary algorithms in MB-MDO.
Optimierungsprobleme sind in der Softwareentwicklung allgegenwärtig. Sie treten beispielsweise bei der Suche nach einem modularen Softwaredesign oder der Planung eines kosteneffizienten Entwicklungsprozesses auf. Die suchbasierte Softwaretechnik (SBSE, von engl. search-based software engineering) befasst sich mit der Lösung von Optimierungsproblemen durch Anwendung suchbasierter Optimierungsverfahren. Zu den beliebtesten gehören evolutionäre Algorithmen, die im Mittelpunkt dieser Arbeit stehen. Angelehnt an die natürliche Evolution werden bei diesen Selektions-, Mutations- und Kreuzungoperatoren verwendet, um bestehende Lösungen weiterzuentwickeln.
In der Hoffnung, den Einsatz von SBSE ohne tiefere Optimierungskenntnisse zu ermöglichen, setzt die modellgetriebene Optimierung (MDO, von engl. model-driven optimization) auf modellgetriebene Entwicklung (MDE, von engl. model-driven engineering); Modelle und Modelltransformationen werden zur Spezifikation von Optimierungsproblemen und Lösungsalgorithmen herangezogen. Dabei haben sich zwei Arten Lösungen zu repräsentieren etabliert, der modellbasierte (MB-MDO, von engl. model-based MDO) und der regelbasierte Ansatz. Es ist jedoch nicht klar, welche Auswirkungen die Entscheidung für den einen oder anderen Ansatz hat. Daher vergleichen wir beide Ansätze sowohl qualitativ als auch quantitativ und verfolgen im weiteren Verlauf der Arbeit MB-MDO als den vielversprechenderen Ansatz.
Wie sich effiziente und effektive evolutionäre Algorithmen entwickeln lassen, ist in MB-MDO eine zentrale Frage. Darüberhinaus ist dort noch kein Ansatz zur Umsetzung von Kreuzungsoperatoren bekannt. Wir stellen zunächst ein Framework vor, welches die Kernkonzepte evolutionärer Algorithmen in MB-MDO herausstellt, erklärt und diese auf Grundlage der Graphentransformationstheorie formalisiert. Es trägt damit nicht nur zum Verständnis evolutionärer Algorithmen in MB-MDO bei, sondern ermöglicht insbesondere deren präsize Spezifikation, Analyse und Evaluation. Mit Hilfe des Frameworks werden zwei wichtige Eigenschaften von Mutationsoperatoren definiert und deren Einfluss auf die Effizienz und Effektivität evolutionärer Algorithmen evaluiert. Desweiteren wird ein genereller, graphbasierter Ansatz zur Konstruktion von Kreuzungsoperatoren in MB-MDO vorgestellt. Der generelle Ansatz wird zudem für das Eclipse Modeling Framework (EMF) konkretisiert. Die Evaluation einer prototypischen Implementierung zeigt abschließend die Relevanz von Kreuzungsoperatoren für evolutionäre Algorithmen in MB-MDO.
Review
Metadata
License
This item has been published with the following license: In Copyright