=Paper=
{{Paper
|id=Vol-1758/paper7
|storemode=property
|title=Class Responsiblity Assignment Case: a Viatra-DSE Solution
|pdfUrl=https://ceur-ws.org/Vol-1758/paper7.pdf
|volume=Vol-1758
|authors=András Szabolcs Nagy,Gábor Szárnyas
|dblpUrl=https://dblp.org/rec/conf/staf/NagyS16
}}
==Class Responsiblity Assignment Case: a Viatra-DSE Solution==
https://ceur-ws.org/Vol-1758/paper7.pdf
Class Responsibility Assignment Case:
a Viatra-DSE Solution∗
András Szabolcs Nagy Gábor Szárnyas
nagya@mit.bme.hu szarnyas@mit.bme.hu
Budapest University of Technology and Economics
Department of Measurement and Information Systems
MTA-BME Lendület Research Group on Cyber-Physical Systems
Abstract
This paper presents a solution for the Class Responsibility Assign-
ment Case of the 2016 Transformation Tool Contest. The task is
to assign features (methods and attributes with dependencies to each
other) to classes and optimize a software metric called CRA-Index.
The solution utilizes the rule-based design space exploration frame-
work Viatra-DSE with the Non-dominated Sorting Genetic Algo-
rithm (NSGA-II) and it extends the framework with a domain-specific
state encoder to identify similar solutions and to obtain better perfor-
mance. Furthermore, it also uses a domain-specific mutation operator
and a slightly modified version of the provided transformation rule.
1 Introduction
Automated model transformations are a key factor in modern model-driven system engineering. Model trans-
formations allow the users to query, derive and manipulate large industrial models, including models based on
existing systems, e.g., source code models created with reverse engineering techniques. Since such transforma-
tions are frequently integrated with modeling environments, they need to feature both high performance and a
concise programming interface to support software engineers.
Design space exploration (DSE) aims to explore different design candidates with respect to well-formedness
constraints and objectives to aid system engineers in finding the best design or to dynamically reconfigure a
system at runtime. While DSE has a long history (20–30 years) [8], especially for embedded systems, it has been
adapted to model-driven system engineering only in recent years (discussed as related work in [1]).
Viatra [2, 5] aims to provide the tooling support needed for these challenges by 1) an expressive model query
language, 2) a carefully designed API for transformations and 3) a design space exploration tool easily integrated
to the model-driven design process.
This paper presents a solution using Viatra for the TTC 2016 Class Responsibility Assignment Case [7] (see
Section A.1) which can be formalized as a DSE problem. The source code of the solution is available as an
open-source project.1 Additionally, there is a SHARE image available with the source code and scripts to run
the solution on the provided input models.2
∗This work was partially supported by the MTA-BME Lendület Research Group on Cyber-Physical Systems.
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Garcia-Dominguez, F. Krikava and L. Rose (eds.): Proceedings of the 9th Transformation Tool Contest, Vienna, Austria,
08-07-2016, published at http://ceur-ws.org
1 https://github.com/FTSRG/ttc16-cra-viatra-dse
2 http://is.ieis.tue.nl/staff/pvgorp/share/?page=ConfigureNewSession&vdi=ArchLinux64_TTC-Arch-CRA-VIATRA.vdi
1
2 Background of the Solution
Viatra-DSE is a rule-based DSE framework [1, 9], which can explore different design candidates satisfying
multiple criteria with respect to multiple objectives using graph transformation rules.
2.1 Approach of Rule-Based DSE
Figure 1 gives an overviews the most important con- Initial model
Design space Trajectory
cepts of this approach. A rule-based DSE problem exploration
consists of the following parameters: Rules Initial Sequence
Sequenceof
Sequence of
of
model rule
ruleapplications
rule applications
applications
• an initial model M0 , Constraints
Rule
• a set of transformation rules R that defines how application
Objectives
the initial model (and the current model) can be
manipulated, Exploration strategy
• a set of well-formedness constraints C and
Goal model state
• a set of objectives O to optimize (minimize or
maximize).
Figure 1: Overview of the rule-based DSE approach.
A solution for such a problem is a sequence of trans-
formation rule applications (also called trajectory), which transforms the initial model M0 to a model Ms , which
satisfies all the well-formedness constraints in C. This solution is expected to be optimal (high-quality) with
respect to objectives O.
The key strengths of this approach are that 1) models are attributed typed graphs and rules are graph
transformation rules, which allows tight integration with model-driven system design, 2) the solution (i.e., the
trajectory) also describes how to reach the found model from the initial state, which is important in certain
problems, (e.g., runtime reconfiguration of a system needs to answer how to reach the candidate configuration)
and 3) objectives can be derived from the model directly using even black box tools and from the trajectory as
well.
To solve such a problem, a solver has to traverse a state space (also called design space) with an exploration
strategy. This state space has an initial state representing the initial model and further states can be reached by
applying the transformation rules. The state space can be infinitely large (e.g., a rule can make elements without
an upper bound) and it can contain cycles (e.g., a rule can delete elements that an other rule just created). In
Appendix A, Figure 4 shows a partial design space of a small CRA problem, where there are three methods and
a single attribute.
2.2 VIATRA
Viatra is an open-source Eclipse project written in Java and Xtend [6] and it builds upon the Eclipse Modeling
Framework [4]. The Viatra project provides the following main features:
• A declarative language for writing queries over models, which are evaluated incrementally upon model
changes (formerly known as EMF-IncQuery).
• An internal domain-specific language over the Xtend [6] language to specify both batch and event-driven,
reactive transformations.
• A complex event-processing engine over EMF models to specify reactions upon detecting complex sequences
of events.
• A rule-based design space exploration framework to explore design candidates with transformation rules
where the design candidates must satisfy multiple criteria (presented in Section 2.3).
• A model obfuscator to remove sensitive information from a confidential model, e.g., for creating bug reports.
2.3 VIATRA-DSE
Viatra-DSE provides an easy way to specify a rule-based DSE problem and to extend it with domain-specific
needs. The condition (left hand side) of the transformation rules can be specified by the Viatra Query language
and the operation (right hand side) by simple Java code. Both constraints and objectives can be specified
either by the Viatra Query language or by any custom Java code. Furthermore, it supports the calculation
of objectives both on the actual model and on the trajectory as well (e.g., executing certain rules has a cost).
2
Viatra-DSE has several built-in strategies such as depth-first search, breadth-first search for systematic full
exploration of the design space, fixed-priority search which uses priorities assigned to rules, and has metaheuristic
strategies such as hill climbing and evolutionary algorithms, including Non-dominated Sorting Genetic Algorithm
(NSGA-II) [3] and Pareto Envelope-based Selection Algorithm (PESA) [10]. Custom, domain-specific strategies
can be integrated as well.
To recognize similar model states it uses a state encoding technique, which encodes model states into a
textual representation. While these state codes can be easily compared to each other, the efficiency of the
encoding process has a great impact on the exploration time. Additionally, rule applications are also encoded
into a textual representation called activation codes. This allows to store a trajectory by its activation codes
and to re-execute it later on an arbitrary model. Viatra-DSE has a built-in generic state coder, which works
out-of-the-box for most use cases, but it can be exchanged with a custom, domain-specific state coder, which
can improve the performance of the exploration.
The framework is also capable of parallel exploration – at the time of writing the depth-first search, breadth-
first search and the evolutionary exploration algorithms exploit this feature.
3 Implementation
In this section, we provide a detailed description of how we instantiated the task as a rule-based DSE problem.
3.1 Transformation Rules
Our solution uses the two transformation rules provided by the case, namely the createClass and assignFeature
rules, however we enhanced the createClass rule with the following two modifications:
1. A class can be created only if there are no empty classes in the current model. This allows to prune the
search space without losing any solutions.
2. Newly created classes are given a name CX, where X is a number depending on how many classes were
created on the actual trajectory. This ensures that the classes have a unique name.
3.2 Well-Formedness Constraints
While the modified createClass rule ensures the unique name of the classes, we used Viatra Query to capture
the other two constraints (see Section A.3).
3.3 Objectives
We use two objective functions: one that calculates the CRA-Index of a class diagram and one that measures
the violations of well-formedness constraints. The CRA-Index is calculated in the provided way, except we
use Viatra Query to calculate MAI and MMI incrementally upon model change. The other fitness function
measures the number of unassigned features and it shall be minimized. This helps the exploration to reach a
solution more easily.
These two objectives create a multi-objective optimization problem, which makes comparing solutions non-
trivial. In this solution, we use the domination function [3] to compare solution candidates: a solution candidate
s1 dominates an other solution candidate s2 if there is an objective function oi that oi (s1 ) > oi (s2 ) and for
any other objective oj ̸= oi : oj (s1 ) ≥ oj (s2 ). This approach will find a well-formed solution and an ill-formed
solution candidate equal (in the sense of quality) if the ill-formed solution candidate has a higher CRA-Index.
3.4 Exploration with NSGA-II
For the exploration strategy, we used the NSGA-II genetic algorithm [3] crafted for multi-objective optimization
problems. This algorithm maintains a population, i.e., a set of solution candidates (trajectories), and modifies
them with genetic operators (mutations and crossovers) to derive new solution candidates. In an iteration, it
combines the previous population and a newly created population and selects the best solution candidates to
produce the next generation. The adaption of this algorithm as a rule-based DSE strategy can be found in [1].
We configured the NSGA-II strategy in the following way:
• The first population is generated by a breadth-first search algorithm selecting a trajectory into the population
with a given probability and with a minimal length of 2. A population consists of 40 individuals.
• The following genetic operators are used, where mutations are used 80% of the time:
3
1. A mutation that adds a random rule application to the end of a trajectory.
2. A mutation that changes a random rule application in the trajectory to an other rule application.
3. Cut and splice crossover, which exchanges the tails of two trajectories creating two child trajectories.
4. Swap rule application crossover, which exchanges one activation code in the parent trajectories.
5. A custom domain-specific mutation operator that removes all createClass rule applications, where the
created class remained unused. This helps the algorithm to find a well-formed solution.
• The stop condition consists of two sub-conditions that have to be fulfilled at the same time: 1) in the current
population there is at least one solution that survived 100 iterations (i.e., the exploration cannot create a
better solution) and 2) there is a well-formed solution in the current population.
As trajectories are encoded by a sequence of activation codes, for example a swap rule application crossover is
executed by 1) randomly choosing the rule applications (activation codes) to swap, 2) creating the first child by
executing the new trajectory, omitting rule applications that are infeasible, 3) backtracking to the initial model
and 4) creating the second child as in step 2.
3.5 State Encoding
The solution uses a custom domain-specific state coder as the built-in state coder failed to recognize similar
solutions. For example, if there are two methods M 1 and M 2 that are assigned to two different classes C1 and
C2, then the built-in state coder creates a state code C1(M 1), C2(M 2) or C1(M 2), C2(M 1) depending on the
trajectory, which are eventually representing the same solution (also the actual state code is much longer and
redundant). Using this state coder, NSGA-II can store duplications in the population, which decreases efficiency.
Thus, we created a domain-specific state coder that encodes model states leaving out the identifiers of the classes,
encoding only the grouping of the features: (M 1), (M 2). This state coder also has better performance reducing
the exploration time.
3.6 An Alternative Solution
We also experimented with an other approach, where first we created a class for each feature in the initial model
using the VIATRA Model Transformation API. Then we ran the exploration with a single rule that merges two
classes. While, this approach could generate good solutions with positive CRA-Index with approximately in the
same time, the presented solution produces better results.
4 Evaluation
4.1 Setup
As NSGA-II is a metaheuristic algorithm, it cannot provide a consistent solution for each run and runtime may
vary because of the adaptive stop condition. Thus, we run the exploration 30 times for each input model and
consider the median of the found fitness values and the median of runtime as result. This allows us to easily
compare our results to other contestants’ work.
The benchmarks were conducted on a 64-bit Windows 10 PC with a 2.50 GHz Intel i5-2450M CPU and 8 GB
of RAM using Oracle JDK 8, 256 MB maximum heap size and four threads to exploit the four logical cores.
4.2 Results
Optimality: Figure 2 shows a box plot for the CRA-Index of the generated solution models for each input model.
The smallest input model is solved pretty consistently, with a CRA-Index of 3. While for input model B, most of
the runs returns a solution with a CRA-Index around 3.75, for the more complex input models the result varies
greatly. However, the found solution models always have a positive CRA-Index disregarding a few outliers.
Performance: Figure 3 shows exploration times of the different runs in seconds on a logarithmic scale. The
median values are marked with red. The runtime of the exploration varies greatly, especially on the largest input
model E. While it could find a solution in about 4 minutes, in the worst case it needed one and a half hour.
An interesting property of the input model C is that while it has twice as many features and thrice as many
dependencies than input model B, the exploration time is just slightly longer.
Table 1 presents our aggregated results for each input model as stated in Section 4.1. We also included the
metric of the best solutions our approach could find, to show that if there is no limit for execution time it can
produce even better solutions.
4
Values of the CRA-Index Execution times of the design space exploration
8
Execution time [s]
6 1000
CRA-Index
4
100
2
0 10
-2
A B C D E A B C D E
Input model Input model
Figure 2: CRA-Index values by input model. Figure 3: Execution times by input model with the me-
dian values marked with red.
A B C D E
CRA-Index (best) 3 4 3.002 5.08 8.0811
CRA-Index (median) 3 3.75 1.9992 2.8531 5.0188
Time (median) 00:04.729 00:13.891 00:17.707 01:19.136 09:14.769
Table 1: Optimality and performance results of 30 runs.
5 Summary
This paper presented a complete solution for the Class Responsibility Assignment case of the 2016 Transformation
Tool Contest. The approach of rule-based DSE and the Viatra-DSE framework proved to be efficient for
modeling the problem and sufficient for solving the case. The solution could be improved by gaining a deeper
understanding of the CRA-Index metric and by adding a supplementary heuristic to the exploration.
References
[1] H. Abdeen, D. Varró, H. A. Sahraoui, A. S. Nagy, C. Debreceni, Á. Hegedüs, and Á. Horváth. Multi-
objective optimization in rule-based design space exploration. In ACM/IEEE Inter. Conf. on Autom. Soft.
Eng., pages 289–300, 2014.
[2] G. Bergmann, I. Dávid, Á. Hegedüs, Á. Horváth, I. Ráth, Z. Ujhelyi, and D. Varró. VIATRA 3: A reactive
model transformation platform. In 8th International Conference on Model Transformations. Springer, 2015.
[3] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm:
NSGA-II. IEEE Trans. Evolutionary Computation, 6(2):182–197, 2002.
[4] Eclipse.org. Eclipse Modelling Framework (EMF). https://www.eclipse.org/emf/.
[5] Eclipse.org. VIATRA Project. https://www.eclipse.org/viatra/.
[6] Eclipse.org. Xtend – Modernized Java. https://www.eclipse.org/xtend/.
[7] M. Fleck, J. Troya, and M. Wimmer. The class responsibility assignment case. In 9th Transformation Tool
Contest (TTC 2016), 2016.
[8] M. Gries. Methods for evaluating and covering the design space during early design development. Integration,
38(2):131–183, 2004.
[9] Á. Hegedüs, Á. Horváth, and D. Varró. A model-driven framework for guided design space exploration.
Autom. Softw. Eng., 22(3):399–436, 2015.
[10] J. D. Knowles, R. A. Watson, and D. Corne. Reducing local optima in single-objective problems by multi-
objectivization. In Evolutionary Multi-Criterion Optimization, First International Conference, pages 269–
283, 2001.
5
A Appendix
A.1 Case Description in a Nutshell
The problem to solve is a simplified version of the class responsibility assignment (CRA) problem. As an input
model, a set of attributes and methods are given with dependencies between them, in particular, methods can
use certain attributes and other methods. The task is to assign all these features to classes with the goal of
optimizing a software metric called CRA-Index. The CRA-Index is an objective function to maximize and it
combines the cohesion ratio (inner dependencies of a class divided by the cardinality of the features) and coupling
ratio (dependencies between two classes divided by the cardinality of the features) of the class diagram.
Contestants are given five models with increasing complexity to solve and they are to produce the corre-
sponding high-quality models by using model transformation tools. The resulting models also have to satisfy
the following constraints: 1) all features have to be assigned, 2) classes must have a unique name and 3) empty
classes are not allowed.
The full description can be found in [7].
A.2 Design Space
Recurring states
M1 M2 M1 M2 are reachable through
multiple trajectories
M3 A1 M3 A1 C1
M1 M2
M3 A1 C1
M1 M2 M1 M2 M1 M2 C2
M3 A1 C1 M3 A1 C1 M3 A1 C1
M1 M2 C2
M3 A1 C1
A solution state
A solution trajectory
C2 M1 M2
Activation of createClass rule ... C1
Activation of assignFeature rule C3 M3 A1
Figure 4: A part of the DSE state space and a solution trajectory.
A.3 Well-Formedness Constraints Captured by Viatra Query
1 pattern allFeatureEncapsulated() { 13 pattern notEncapsulatedFeature(f : Feature) {
2 neg find notEncapsulatedFeature(_); 14 neg find encapsulated(_, f);
3 } 15 }
4 16
5 pattern noEmptyClass() { 17 pattern emptyClass(c : Class) {
6 neg find emptyClass(_); 18 neg find encapsulated(c, _);
7 } 19 }
8 20
9 21 pattern encapsulated(c : Class, f : Feature) {
10 22 Class.encapsulates(c, f);
11 23 }
12 24
Well-formedness constraints Helper patterns
6