In this paper we describe a solution for the Class Responsibility Assignment(CRA) case [3] of the 2016 Transformation Tool Contest using the MDEOptimiser 1 [4] tool prototype. While we can solve the problem and explain our solution in this paper, we place substantial focus on the lessons learned from this exercise and how these will inform future development of the tool. The remainder of this paper is structured as follows: We begin with a brief overview of the challenge case in Section 2. Section 3, then, presents our solution to the challenge case, which we evaluate in Section 4 based on the criteria dened with the case. Section 5 discusses lessons learned from this experiment and highlights future research.
The challenge is about a key step in object-oriented software design: assigning responsibilities to classes. Specically, given a set of features (methods and attributes) and their dependencies (data dependencies between methods and attributes and functional dependencies between methods) we are tasked to nd a set of classes with unique names and an allocation of features to these classes that minimises dependencies between classes. 3.1
Solving the search problem Any search problem is composed of 1) a denition of the search space and a corresponding encoding for individual candidate solutions, 2) a means of exploring the search space by moving from existing solution candidates to new ones and 3) a set of objective functions enabling the comparison of candidate solutions along a number of dimensions.
In this section, we describe each of these aspects for our solution using MDEOptimiser.
NamedElement name : String ClassModel
Class
encapsulates isEncapsulatedBy
Feature
Attribute
dataDependency Method functionalDependency MDEOptimiser uses Henshin transformation rules to specify how to derive new candidate solutions from given ones. At this point, the tool only supports mutation-type derivation of new candidate solutions; that is derivations that take a single model and produce a single new model. We call these mutators model evolvers. Figure 2 shows the model evolvers used for the challenge case. When the search is executed, the engine will randomly pick an applicable evolver every time a new candidate solution needs to be derived.
These rules are similar, but not identical to the rules given with the challenge case. In particular, we made the following changes: 1. No names. The rules do not match against or modify the names of any model elements. Ensuring uniqueness of names will be performed as a separate processing step, explained in Sect. 3.2. 2. Additional rules. The challenge case only included two rules (creating a class and assigning a feature). This was sucient for the MOMoT-based [2] implementation, which uses sequences of rule applications to encode candidate solutions. Therefore, they have access to the ‘transformation history’ of any candidate model and can modify past transformation steps to nd optimal solutions. In contrast, MDEOptimiser only keeps
the model resulting from the transformation application. It cannot exchange a past transformation step, so needs additional evolvers to ensure it can fully explore the search space. As a result, we needed to add a rule for moving features from one class to another. We also included a rule for deleting empty classes to enable the search to produce more compact models. 3. Additional negative application conditions. We found that we needed to introduce additional negative application conditions. In particular, it was necessary that rule assignFeature would only match against unassigned features. This is not automatically implied by marking the isEncapsulatedBy edge as create .
Instead, we need to specify an explicit forbid edge to create a negative application condition. 4. No simple class creation. The original createClass rule, which created an empty class turned out to be inecient. By changing it to a rule which creates a class and immediately assigns a previously unassigned feature to it, the search became substantially more ecient. 3.1.3
Objective functions As candidate solutions are encoded as models, objective functions can simply be encoded as model queries for the challenge case. We used the following 3 objective functions: minimise number of unencapsulated features; minimise number of empty classes; maximise CRA (a combination of cohesion and coupling metrics as dened in the challenge case). 3.1.4
Case solution 3.083 -3.79 -23.63381 -66.65545 valid as they may contain unassigned features (we treat feature assignment only as an objective function during the optimisation). From the remaining solutions, we pick the one that has the best CRA value. Finally, we need to ensure all classes in the nal model have unique names. This can be easily achieved by a simple post-processing step as shown in Fig. 4 (Lines 102 . ): we iterate over the list of classes in the models generated and set their names to a unique string by appending a running counter. 3.2
Post-processing 4
4.1
Product criteria In this section, we evaluate our solution against the criteria dened in the challenge case.
Here, we report the results for completeness & correctness, optimality, and performance. As search-based algorithms involve a certain amount of randomness, we have run the transformation 10 times on each input model and report the average time taken as well as the CRA for the best model found across these 10 attempts.
It is worth noting that there can be quite substantial variation in the quality of the models produced. It seems that our optimiser currently gets easily stuck in local optima. Investigating the precise reasons for this remains as future work, but two candidate issues present themselves for initial investigation: 1. Inecient search algorithm. We currently use a very simple search algorithm based on ideas from nondominated sorting. It is very possible that this algorithm is inecient. We are planning to replace this handcoded implementation with standard implementations as, for example, available in the MOEA framework 3. 2. No support for breeding: Breeding (i.e., creating a new candidate solution by intermixing aspects of two good parent solutions) is not yet supported in MDEOptimiser, making it more dicult for the search algorithm to escape from local maxima. Hence, large parts of the search space may never be reached.
Table 1 shows an overview of the results for each of the input models provided. We ran two congurations for each model: First, we ran a search with 100 generations and a population size of 100 models (Conguration I). Second, we ran a search with 1,000 generations and a population size of 50 models (Conguration II). Conguration I uses the same parameters as Fleck’s original solution 4, so we show their CRA values for comparison.
For the less complex models, we could already obtain reasonable results with a smaller number of generations and a smaller population size. For model C, our CRA in Conguration I is better than Fleck’s results. For model A, we are very close to their CRA value. Larger populations or more generations did not improve these values except for model D, for which we obtained a better CRA with Conguration II, but at a substantial time cost. Indeed, it appears from the table that we get worse results for Conguration II for model C and the same CRAs for models A and B. We believe that this is a result of the search getting stuck in local optima, helped by the fact that a smaller population size means more potentially interesting search routes are weeded out earlier. For model E, we were unable to nd any valid models using any of the congurations. In an earlier run (with a 3http://moeaframework.org/ 4https://github.com/martin-fleck/cra-ttc2016/blob/master/MOMoT_solution/TTC2016_CRA_MOMoT.pdf slightly older version of the code base) the tool found a model with a CRA of 0:4556 after 4h 19m 10s 509ms (1,000 generations of 50 models). We have yet to recreate this scenario with the current code base. 4.2
Process criteria The complexity of our solution is comparatively low as MDEOptimiser is a tool dedicated to the expression and execution of search problems. Consequently, the CRA challenge case is a very natural problem for our tool to tackle.
Given that our tool is a very early prototype, there are a number of accidental complexities that make expressing search problems a little more dicult than strictly necessary. In particular, we do not currently support objective functions to be expressed directly as OCL model queries, requiring them to be expressed in Java instead. However, by using Xtend and a number of simple helper functions, we have made the expression of these queries suciently easy to be workable for this case study.
Being completely declarative, our solution is also exible: Adding a new objective function simply requires adding a class implementing the corresponding interface and referencing it from the optimisation specication. Similarly, additional rules for evolving candidate solutions can be added quickly and easily. 5
We have learned a number of lessons from applying MDEOptimiser to the TTC’16 challenge case. These lessons will inuence our future work on MDEOptimiser:
Avoiding local optima. Our current implementation seems to get easily stuck in local optima. We have already discussed in Sect. 4.1 a number of things we will investigate to avoid this.
Additional features required. As a very new tool, MDEOptimiser lacks a number of important features. For example, we currently do not support Henshin rule parameters, which would have enabled us to ensure name uniqueness in one go. Similarly, we do not yet support constraints for the specication of valid solutions. Constraints may have made the search more ecient, in particular for the more complex input models where a large proportion of the nal population consists of invalid models with unassigned features. Systematic development of optimisations. Not having support for rule parameters in the tool, we had to separate the overall transformation into two phases, which could be argued to be a better design. More generally, we need to identify techniques for systematic development of optimisation-based model transformations. Debugging and testing support. Debugging and testing optimisation-based transformations is particularly dicult because they create a very large number of intermediate models and because of their stochastic nature. Current techniques for debugging and testing transformations provide only insucient support for this type of transformation.
Dierences between evolution rules required for dierent search techniques. In solving the challenge case, we had to develop Henshin rules that dier signicantly from the ones presented in the challenge case. Some of these dierences seem to be because our search algorithm works on models directly rather than on transformation chains. It will be important to better understand how dierences in the search algorithm aect the shape of the transformation rules required. [3] Javier Troya Martin Fleck and Manuel Wimmer. The class responsability assignment case. In 9th Transformation Tool Contest (TTC 2016) , 2016.