-Metamodels undergo many changes during the evolution of several software modeling languages and projects. As a consequence, models have to be updated for preserving their conformance with the new metamodel versions. A common practice is to manually define rules for each metamodel evolution to co-evolve the corresponding models. In this paper, we propose a generic automated approach for the metamodel/model coevolution. In our approach, we view the co-evolution as a multiobjective optimization problem, and we solve it using the NSGAII algorithm. Our algorithm search for solutions that minimize (1) the non-conformities with the new metamodel version, (2) the changes to the existing models, and (3) the loss of information. We successfully evaluated our approach on the evolution of the well-known UML state machine metamodel. Index Terms-Metamodel/model co-evolution, Model migration, Coupled evolution, NSGA-II
Model-Driven Engineering (MDE) considers models as
first-class artifacts during the software lifecycle [
The remainder of this paper is structured as follows. Section II provides the background of model co-evolution and demonstrates the challenges addressed in this paper based on a motivating example. In Section III, we give an overview of our proposal and explain how we adapted the NSGA-II algorithm to find optimal new models. Section IV discusses the design and results of the empirical evaluation of our approach. After surveying related work in Section V, we conclude with some pointers to future work in Section VI.
This section introduces the background, namely the basic notions of metamodels and models, the conformsTo relationship, as well as an example to demonstrate the challenges one is facing when dealing with metamodel/model co-evolution.
Metamodels are the means in MDE to specify the abstract
syntax of modeling languages [
To make the conformsTo relationship more concrete, we give an excerpt of the constraints concerning objects in models and their relationship to classes in metamodels. Objects are instantiated from classes. Thus for each referred type of an object in a given model, a corresponding class must exist in the metamodel (name equivalence) and the corresponding class must not be abstract. Such constraints may be formulated in in the following way: context M!Object: inv typeExists: MM!Class.allInstances() -> exists(c|c.name = self.type and not c.abstract)
An example metamodel and corresponding model is shown in Figure 2a and Figure 1a, respectively. This simple language allows to define simple state machines consisting of states having a name and predecessors as well as successor states.
While some metamodels, such as UML, are standardized
and changed rarely, metamodels for Domain-Specific
Modeling Languages (DSMLs) [
As most of the current metamodeling frameworks are
currently strict in the sense that only fully conformed models can
be used, metamodel evolution requires to co-evolve the already
existing model instances, which may no longer conform to the
new metamodel version. In such cases, model migration scripts
have to be provided in current tools [
Figure 2 shows an example of a simplified metamodel evolution, based on the simple State Machine language. The metamodel evolution comprises three steps: extract sub-classes for State class resulting in InitialState, SimpleState, and FinalState, make class State abstract, and push-down, create and refine the cardinalities of the predecessor/successor references for the subclasses. This results in the fact that besides other constraints violations, the constraint shown previously is violated when considering the initial model shown in Figure 1a and its conformance to the new metamodel version in Figure 2b.
To re-establish conformance for the given example, assume for now that only two operations on models are used in this context. Non-conforming objects may either be retyped (reclassified as instances of the concrete classes) or deleted. Thus, the potential solution space for retyping or deleting non-conforming elements contains (c + 1)O solutions (with c=number of candidate classes + 1 for deletion, o=number of nonconforming objects).
This means, in our given example, we would end up with 64 possible co-evolutions while one (probably the preferred one) of these is shown in Figure 1b. This one seems the preferred one due to several reasons such as the number of changes introduced (e.g., loss of information by deleting some model elements) and the number violated conformance constraints.
To this end, we propose in this paper to consider the model co-evolution problem as a multi-objective one to find a balance between the consistency with the previous version of the model and the conformance to the new metamodel.
The goal of our approach is to derive a tentative new version, of an existing model, that conforms to a new version of its original metamodel. We view this derivation as a search in the space of all possible sequences of modifications of the original models. The search is guided by three objectives, which aims at minimizing (1) the number of non conformities with the new version of the metamodel, (2) the number of the changes to the initial model and (3) the loss of information after modifying the initial model. In other words, the generated new revised model has to be similar as much as possible to the initial model while conforming to the new metamodel version. Therefore, we implemented our idea in the form of a multi-objective optimization algorithm that computes an optimal sequence of edit operations representing the best trade-off between the three objectives. More concretely, our algorithm takes as inputs the initial and revised versions of the metamodel, a list of models to update and a list of possible edit operations to apply to the models (retype and delete). It generates as output a sequence of edit operations that should be applied to the initial version of the model to generate a new version compatible with the new metamodel version.
The space of all possible sequences of editing operations
can be very large, especially when dealing with large models.
An exhaustive search method could be inefficient in this cases.
Alternatively, we use a heuristic search with a multi-objective
evolutionary algorithm, NSGA-II [
NSGA-II [
Non-dominated solutions are assigned a rank of 1 and constitute the first layer (Pareto front). After removing solutions of the first layer, the non-dominated solutions form the second layer and so on and so forth until no non-dominated solutions remain. After assigning solutions to fronts, each solution is assigned a diversity score, called crowding distance, inside each front. This distance defines a partial ranking inside the front which aims, later, at favoring solutions that are far from the others in terms of objective values. A solution is then characterized by its layer and its crowding distance inside the layer.
To finish an iteration of the evolution, we perform the environmental selection to form the parent population for the next generation by picking half of the solutions. The solutions are included iteratively from the Pareto front to the lowest layers. If half of the population is reached inside a front than the crowding distance is used to complete the parent population.
1) Problem formulation: The model co-evolution problem involves searching for the best sequence of edit operations to apply among the set of possible ones. A good solution s is a sequence of edit operations to apply to an initial model with the objectives of minimizing the number of non-conformities nvc with the new metamodel version, the number of changes nbOp to the initial model, and the loss of information disIm between the initial and the evolved models. Formally: 8>M inimize f1(s) = nvc(s) <
M inimize f2(s) = nbOp(s) >:M inimize f1(s) = disIm(s)
The first fitness function nvc(s) counts the number of violation constraints w.r.t. the evolved metamodel after applying a sequence s of edit operations.
We used in our experiments the implementation constraints
proposed by Schoenboeck et al. [
For the two remaining objectives, which aims at minimizing the changes to the initial models, we used simple approximations. nbOp(s) is simply the number of editing operations in a sequence s. disIm(s) measure the difference in size between the initial Mi and the revised Mr models. If the difference is negative or null then disIm(s) = 0 (no information loss). Otherwise, disIm(s) = size(Mi) size(Mr).
2) NSGA-II Application : To adapt NSGA-II to our problem, it is necessary to define (1) how to represent a coevolution solution, (2) how to derive new solutions from existing ones, and (3) how to evaluate a solution.
Solution representation. We mentioned earlier that a solution is a sequence of edit operations to be applied to the model to evolve. This can be seen as an inplace transformation. However, as we are dealing with two versions of a metamodel, we decided to represent a solution as an outplace transformation. Rather than editing the initial model, we create a new model. Thus, we only have creation operations, but not retyping ones. Although we are not supposed to delete elements directly in the initial model, we use deletion operations to “repair” candidate solutions during the evolution, i.e., deleting an element that was previously created. A candidate solution (individual) is then represented with a vector whose elements are the creation/deletion operations to create the new version of a model from the initial one. Each edit operation specifies the model element to which it is applied. Consequently, vectors encoding different solution candidates may have different sizes depending on the number of operations in the sequences.
The proposed algorithm first generates a population of random operation sequences (solution candidates), which are used in the subsequent iterations to produce new solutions.
Solution derivation. In a search algorithm, the variation
operators play a key role of moving within the search space
with the aim of driving the search towards better solutions.
In each iteration, we select population size=2 individuals
from the population popi to form population popi+1. These
(population size=2) selected individuals will produce other
(population size=2) new individuals using a crossover and
mutation operators. To select parents for reproduction, we used
the principle of the roulette wheel [
We use a one-point crossover operator. For our problem, this operator split each parent operation sequence S1 (resp. S2) into two subsequences fS11; S12g (resp. fS21; S22g) according to a cut position k. Then, it combines the subsequences to create to sibling solutions fS11; S22g and fS21; S12g. Our crossover operator could create a child sequence that contains conflict operations. In this case, it will be penalized by the component nvc of the fitness function.
The mutation operator consists in randomly selecting one or two operations in a solution vector and modifying them. Two modifications are used: (1) swapping the two selected operations in the sequence or (2) replacing an operation by a randomly created one.
Solution evaluation. As mentioned in the problem formulation, a solution is evaluated according to three objectives. Thus, for each solution s, we calculate nvc(s), nbOp(s), and disIm(s). These values are used later to establish the dominance relation between solutions.
The validation study was conducted to quantitatively and
qualitatively assess the completeness and correctness of our
co-evolution approach when applied to realistic settings and
to compare its performance with an existing deterministic
approach [
RQ1: To what extend the obtained results are attributable to our approach and not to the fact of exploring a large number of solutions? If a random search, exploring a same number of solutions as our approach, gives same or better results, this means that there is no need to use a metaheuristic search.
RQ2: To what extent can the proposed multi-objective approach co-evolve models to make them comply with a new metamodel version (in terms of correctness and completeness of proposed edit operations)?
research questions, we considered the evolution of UML State
Machine Metamodel from version 1.4 to 2.0 [
2) Evaluation Metrics: To compare our approach with the other alternatives, we use precision and recall measures. For an operation sequence corresponding to a given solution, precision indicates the fraction of correctly edit operations (w.r.t. the baseline sequence) among the set of all operations in the sequence. Recall is the fraction of correctly identified edit operations among the set of all expected operations. Roughly speaking, the precision represents the probability that a detected operation is correct whereas the recall is seen as the probability that an expected operation is detected. Both values range from 0 to 1, with higher values indicating good solutions.
The baseline sequences do not represent unique evolution solutions for the used models. Indeed, more than one alternative can be possible to evolve a given model. Thus, in addition to automatic precision (AC-PR) and recall (AC-RE), we calculated a manual precision (MC). For manual precision, rather than comparing automatically the produced sequence with the expected one, we checked operation by operation if they are correct w.r.t. the evolved model.
3) Statistical Tests: Since the used metaheuristic algorithms
(NSGA-II and GA) are stochastic by nature, different
executions may produce different results for the same model with the
same execution parameters. For this reason, our experimental
study is performed based on 30 independent simulation runs
and the obtained results by the alternative approaches are
compared using the Wilcoxon rank sum test [
4) Parameter Settings: Parameter setting has a significant influence on the performance of a search algorithm. We tried different values to set the execution parameters. For the reported results, we used crossover probability = 0.8, mutation probability = 0.5, population size = 100, number of iteration = 1000. The same parameters were used for the multiand mono-objective algorithms. For the random search, we generated 1000 x 100 solutions and took the one with the best fitness. This ensures that the tree alternatives (multi-objective, mono-objective, and random) explore the same number of solutions to have a fair comparison.
Results for RQ1. We do not dwell long in answering the first research question (RQ1) that involves comparing our approach based on NSGA-II with random search. Figure 3 confirm that using NSGA-II (as well as the GA and the deterministic algorithm) produce results by far better (and statistically significant) than just randomly exploring a comparable number of solutions. NSGA-II has precisions (AC-PR and MC) and recall (AC-RE) more than twice higher than the ones of random search as shown in Figure 3 ( 85% vs 40%).
To formally answer RQ1, we state that there is an empirical evidence that the quality of the co-evolution results obtained are due to our multi-objective approach and not to the number of explored solutions.
Results for RQ2. We evaluated the averages AC-PR, ACRE and MC scores for non-dominated co-evolution solutions proposed by NSGA-II.
For the precision and recall, Figure 4 shows that the produced solutions using NSGA-II are similar to the baseline ones with more than 80% of precision and recall (AC-PR and AC-RE) in general. For four models (SM1, SM2, SM5, and SM8), we obtained more than 90% for the recall. From another perspective, we did not observe a correlation between the size or the number of operations of the models and the precision and recall. For example, we obtained higher precision and recall for SM7 (40 elements and 82 operations) than for SM2 (17 elements and 38 operations). This means that the correctness of the results is not degraded as the size of the models or the size of necessary modifications increase. For the manual precision, the results are even better. Except for SM2 and SM9 all the MCs are higher than 90% with a perfect score for SM8. Here again, the scalability in terms of correctness is valid for MC. Indeed MC increases from 86% (SM2) to 94% (SM10) while the size of the model (resp. operation sequence) goes from 17 to 44 (resp. 38 to 94).
To formally answer RQ2, we state that the multi-objective co-evolution approach allows to migrate models with higher precision and recall and with a limited number of edit operations. This achieved without any explicit knowledge on the specific changes that occurred on the metamodel.
There are several validity threats to the design of this study.
The first threat is related to the parameter tuning of our
multi-objective algorithm. Further experiments are required to
evaluate the impact of the parameters setting on the quality
of the solutions. A second threat is related to our choice
of taking the average of the three objective function in the
mono-objective algorithms. Other forms of combination, e.g.,
weighted average, may give different results. Further
experiments are required to compare our approach with different
settings of the mono-objective algorithm. In this study, we
performed our experiments on a single evolution scenario
(state machine metamodel from v1.4 to v2.0). Future
replications of this study are necessary to confirm our findings, in
particular, with industrial settings. In addition, the comparison
of the performance of NSGA-II to other existing approaches
is limited to the approach of Wimmer et al. [
Several approaches emerged which aim to tackle
metamodel/model co-evolution from different angles using different
techniques (cf. e.g., [
Manual-specification approaches in which the migration
strategy is encoded manually by the modeler using
general purpose programming language (e.g. Java), or
transformation languages (e.g ATL, QVT) [
None of the existing approaches allows the exploration of
different possible co-evolution strategies. On the contrary, only
one specific strategy is either automatically derived or
manually developed from the calculated set of metamodel changes.
The only work we are aware of discussing metamodel/model
co-evolution using some search-based techniques is [
This paper proposes a multi-objective approach for the coevolution of models by finding the best operation sequence of changes applied to the initial model that generate the target model conforming as much as possible to the evolved metamodel. Therefore, a generated revised model is necessary that minimizes the number of inconsistencies (with the new metamodel), the number of operations and the dissimilarity with the initial model. As the search space in terms of all possible sequences of operations is potentially huge and we have three objectives to optimize, we considered in this paper the co-evolution process as a multi-objective optimization problem.
We evaluated our proposal with a metamodel evolution scenario concerning a state machine modeling language. The experiment results indicate clearly that the best generated models have a precision and recall of more than 80% and a manual precision of more than 90%. Furthermore, the results provide strong evidence to support the claim that our proposal outperforms both a mono-objective and deterministic approaches for model co-evolution.
We are working now on larger metamodels and models with larger lists of operations to apply. This is necessary to investigate more deeply the applicability of the approach in practice, but also to study the performance of our approach when dealing with very large models.