Model-Driven Optimization with a Focus on the Effectiveness and Efficiency of Evolutionary Algorithms

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.