Summary:
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.