In this paper we describe a solution for the Transformation Tool Contest 2016 (TTC'16) Class Responsibility Assignment (CRA) case study using Sigma, a family of Scala internal Domain-Specific Languages (DSLs) that provide an expressive and efficient API for model consistency checking and model transformations. Since the Class Responsibility Assignment problem is a search-based problem, we base our solution on multi-objective genetic algorithms. Concretely, we use NSGA-III and SPEA2 to minimize the coupling between classes' structural features and to maximize their cohesion.
In this paper we describe our solution for the TTC’16 Class Responsibility Assignment (CRA) case study [FTW16] using Sigma [KCF14]. The goal of this case study is to find high-quality class diagrams from existing responsibility dependency graphs (RDG). The RDGs only contain a set of methods and attributes with functional and data relationships among them. The CRA problem is essentially about deciding where the different responsibilities in the form of class structural features (i.e. operations and attributes) belong and how objects should interact by using those operations [BBL10]. Since the design space of all possible class diagrams grows exponentially with the size of the RDG model [FTW16] (i.e. the number of structural features), the problem is hard to solve. However, a possible approximation could be found using search-based optimization techniques [CLV07]. Concretely, the use of multi-objective genetic algorithms seems to provide an efficient solution for the CRA problem as demonstrated by Bowman et al. [BBL10].
In this paper, we therefore present a solution to the CRA problem using Sigma and multiobjective genetic algorithms. We use Sigma to transform the input RDG diagram into a searchbased problem which is then solved by a genetic algorithm. In the implementation we use NSGA-III and SPEA2 algorithms from the MOEA framework1. The MOEA Framework is a free and open source Java library for developing and experimenting with multi-objective evolutionary algorithms (MOEAs) and other general-purpose multi-objective optimization algorithms [Had16].
Sigma is a family of Scala2 internal DSLs for model manipulation tasks such as model validation, model to model (M2M), and model to text (M2T) transformations. Scala is a statically typed production-ready General-Purpose Language (GPL) that supports both object-oriented and functional styles of programming. It uses type inference to combine static type safety with a “look and feel” close to dynamically typed languages.
Sigma DSLs are embedded in Scala as a library allowing one to manipulate models using high-level constructs similar to the ones found in the external model manipulation DSLs. The intent is to provide an approach that developers can use to implement many of the practical model manipulations within a familiar environment, with a reduced learning overhead as well as improved usability and performance. The solution is based on the Eclipse Modeling Framework (EMF) [SBPM08], which is a popular meta-modeling framework widely used in both academia and industry, and which is directly supported by Sigma.
In this particular TTC’16 case study, the main problem is in solving an optimization problem rather than a transformation problem. Sigma is therefore only used for straightforward transformation of input RDG models into optimization problems and problems’ solutions back into class diagrams.
The complete source code is available on Github3. In the Appendices A and B we provide steps how to install it locally as well as how to run it on the SHARE environment.
The core of this case study is to transform a RDG model into a high-quality class diagram (cf. Figure 1).
NamedElement name: EString
Legend instances to be added in output ClassModel classes
Class 0..* 0..1 isEncapsulatedBy 1..* encapsulates features
Feature 0..* functionalDependency
0..* Method dataDependency 0..*
Attribute cwiehsic).h Tsihmeptlwyosmubettrraiccstscathnebceofuuprltihnegr fcroommbBicnn+o1eh=dekX=ns0ii✓nonk◆noB.nkeT,shiengclaesqeusatluitdyymaeuttrhi(co1)rcsalplerodvCidRe Aa-Isnedteoxf, utility functions that can compute all these Bm0=e1trics from a class digram instance and therefore we do not need to cCoonnsidcereinrg nthe fiorsutBrelslneulmvbeerss,whbicyharetshhoewnirbelopw r(cef. cseiqsueencedAe00fi01n10i2tinitohenOEsI.S online database for integer
sequences), we can see that the number of partition possibilities grows exponentially and is already quite high for a low The outline of thneumbseroolf ufetatuiroesn.Foprerxoamppleo, saneidnstanicnewthehreiysou pneaed ptoeasrsigins15afesaturfeostlolaon wunksn:own amount of classes
already yields 1382958545 different possibilities. 1http://www.moeaf51119,70r21849,a19253m82,22e53,5,13w317852o2,,9r455728k45,84.26509,83o11,06r841875g07617,/4542111,444075,,082621781165447783,6814914857093472,536,,846247017856528700006,5148525915,3055889437324,7624,72624045403577,, 2http://scala-la4n45g95.88o692r94g805289, 4638590332229999353, 49631246523618756274, . . . 3https://github.Incoordemr /to fsoilvekthoe vcansei,aksd/estcritbecd 1in 6th-encexrtsaec-tiosn, isegvemralatechniques may be applied by the contestants.
2 Case Description In this case study we propose a simplified version of the CRA problem. Contestants are given a set of methods and attributes as well as dependencies between them. Such a structure is also referred to as responsibilities dependency graph (RDG). Based on the RDG, the goal is to generate a high-quality class diagram (CD) model. The purpose is therefore to create a RDG2CD model transformation, where the RDG must evolve into a CD, categorized as an endogenous model transformation [MVG06], since both the input and output models conform to the same metamodel.
Figure 1 depicts the common metamodel that is used to represent both, the RDG and the output CD. The RDG is the subset of the metamodel containing only the features a2nd their dependencies, and is represented in black, while the additional class and relationships needed to produce a CD are represented in green. The concepts depicted in the metamodel are summarized as follows: Class Classes represent classes as known from object-oriented programming and modeling languages. A class hereby encapsulates certain functionality aspects in terms of methods, which in turn use data stored in attributes of instances of the same or other classes. In this sense, classes serve as a container object for behavioral features (methods) and data features (attributes).
2http://oeis.org/A000110 1. Load the input RDG model from a given XMI file. 2. Transform the RDG model into MOEA problem instance. 3. Run the MOEA solver using either NSGA-III or SPEA2 algorithms. 4. From the possible solutions (which are part of a Pareto optimal front cf. below), select the one with the highest CRA-Index. 5. Transform the selected solution into class digram.
6. Save the resulting class diagram into XMI file.
An optimization problem defines a search space, or the set of possible solutions together with one or more objective functions. In our case the search space spans are all the valid class diagrams that can represent a given RDG model. The ob jectives are: (1) to minimize coupling, and (2) to maximize cohesion.
The functions that compute coupling and cohesion ratios from a class diagram are part of the case study description. What remains is to find the way how to represent the RDG model as a vector of variables that can be used in a evolutionary algorithm to find a solution. We use a simple integer vector where the index corresponds to the feature index in the input RDG model and the value corresponds to the index of a class in the resulting class diagram. The range of each vector element is between 0 and the number of features 1 (since we use 0-based indexing). In the worst case, (i.e. one feature per class), this actually equals to the number of features. For example, a vector (3; 5; : : :) represents a solution in which first feature belongs to fourth class, second feature to sixth class, and so on and so forth. Figure 2 shows a further example of this representation on the example input/output model pair from the case description [FTW16]. rdg : ClassModel name = "inputRDG"
MyShop
[0Ca]rt [1] I[t2em] [8] acidatdre0Itm.tTseo.mt8(a)l()0..8qpnuraaminecte0i.ty.8 ... 0..8 (b) incphuetckoRutD(G) traintsefmToortmala(t)ion to problem vector
print() features items : Attribute name = "items" name : Attribute name = "name" price : Attribute name = "price" qtyr d:g A:t tCrliabsustMeodel namen a=me "=q u"ainntpiuttyR"DG" (a) [5] [6] (b) (c)
MAIc i, ci
MMIc i, ci [7] CohesionRatio
MAIc i, cj [8] CMoMuIpclini, gcRj(aat)io ∑ CohesionRatio ∑ CouplingRatio items : Attribute
CRA‐Index name = "items" [0]C[a1rt][2][3]It[em4][5][6][7][8] 0 3 0 0 1 5 1 0 1 1 1 1 0 1.1(6c6)7 a so0l.8u3t3i3on vector 1 [1] MyS1hop Item 0.4444 [00] 0Cart items 0 2addItem() cartTotal() 0.44c4h4eckout() 1.5556 name price quantity itemTotal() print()
addItem : Method name = "addItem" (b) (a) an input RDG model (d) sol(uct)ion transformatCiaortn to a Ictelmass diagram iFnigcuornec3re:tEexsaymntpalxe, i(ncp)umt/eoausntupacrumaeters tmf=Too or"dtcaoeallur ptt:paT uioMrttewmatlhiot"ohddeqlu. ality charancnataemmreie s =t:i c "sAn:ta(tmare)i"ibnuptuet model in abMstAraIccti,scyintax, (b) output3model 5 Optimality With optimality the quality of Ftheigcourrrecetly2g:enEeraxteadmmodpellseisoevfaltuahteed, Si.eo.M,ltMhueIctCii,RociAn-Index of the1output 0
model. The higher the CchReAck-oInutd e:x Mtheethboedtter the qualitpyroicfet h:e Aotuttrpiubtumteodel. Here, tChoeheresivoineRwaetrios need to1r.1an6k67the 0.8333
The atsdoolvtuhtaeiownnostriasnt gr(epeloastsioiobnlfeto)nsttahohmeleui otis=toh ne"crrahsneeodcplku1otr0iuoetrne"ssfeeprnrsottvoiadthetediboaennsdt ngsaoiimvlesue tti=ho ten"mh.prTapiocotseiun"ptsiptoonrtcathasicsnarlaenbbkeitnMewgAe,Iewecneai,1cpsjaroinlvdyid1e0,tmhwehaCerRpeAp11-rIeenfddeerxs to M0OEA decision variables.of oAurlrseofe,renecaecsohlutifoenaipntrtihnet e:v aMleutahtioodn asplrweadasyheset abnqdetay p:r oAgtrtarmibtuhtaet catlcoula(teesnthcMeaMCpIRcAsi, -ucIjnldaext efodra bgiyve1)n cslaossme c0lass. Therefore, ure will assigned the seconddiagvraaml.idation ncaomen =s "tprrainitn"t all featurneamse =p "rqouavntiidtye"d in theCoiunplipnguRattiomodel0.4m444ust be 0encapsulated by a classC,omwplielxlitybWeitahlcwomapylesxitysawetimsefiaseudre thwe ietffhortos unetedaedntoypraovdidde isteairochncaaplabliolitgieis∑cfCo.orhgeosioodnRsoatliuotions as well as 2 itemTotal : Method to evaluate the solutions based on the given metrics. For instance, this involves to evalu∑aCteouhpolwingmRuatciho effort has bee0n.4444 Concreintveeslteyd,toinaugtmhenet thMenapmOreo v=Ei d"eAidtermufTlreosta,adml"eveelwopoorrckhe,strwatieon hspaecvifiecactiornesasutcehdas paroCvPRidAi‐nInogdaebnx lexeplimcit ccolnatrsolsfl,o1wc.5a55l6led CRAProblem. r The integfoer rthevruelcest,oimrplemeuntsseearch algorithms as transformdateiocniss,oirotonimvpalermieant transformations to dediceasted encodingisntegers) and bounds is d to define the bles, their typ (i.e.
used for performing the search and back. Here, again, the reviewers need to rank the solutions in relation to the other (i.e. 0 : : :sonluutiomnsbpreovriFdoiegdufarenfd3e:gaEivtxeaumthrpeelmesipnopiuntt/1souo)tnp.uat Tsmcaohldeeeblpentawiruewe mnith1bqauenadrli1ty0o,cfhwahrdaecreetec1riisrsteiifceosr:sn(ato) vitnhapeurwtimoarosbdte(llpeionsssaibbcsltoer)arcstrosleuystnitopanxo,(nb)doustputtomotdhele number and 10 refers tointhceonbcersettesoslyuntitoanx., (c) mmeaosudreesflo.r oTutphutemondeul.mber of objectives is always two, the first one for of features in the input RDG coupliFnlegxibailnityd FtlehxiebilsOiteypctmimoeansluidtryesoWhniotwheoefpaotsiymraitlcitioyshtoheemqsouidaoilfitnyy .tohfeTthgeihvceeonrrsmeocltuleytitognhentoeordastuepdipnmorsotdtaeadlsdnitsitoeinvaalt/uoiatntheedgr, qi.nuea.e,litwthye mCseRotArlic-uIsntdieoxonf the output besides coupling, cmohoedseiol.nTahned htihgeheCrRthAe-ICnRdeAx-.InFdoerx thies bcertiteritah,ereqvuiaelwityerosfnteheedotuotpeust imoadteelt.heHerfefo,rttheit rteavkieswetors need toinranskttahences looks integrate new objectsiovleusti(osnuschinarsefilaxtinogn thoethneumotbher osoflcultaiossnessptrooavigdievdenanvdalguiev)eatnhdemgipvoeitnhtes ponroavisdceadlesboelut wtioeenns p1oaindts10, where 1 refers on a scale between 1toatnhde 1w0o,rwsth(eproes1sibrelefe)rssotlouttihoen wanodrs1t0(preofsesrisblteo)tshoelubteisotns,oil.uet.,iotnh.e Tsolsuutipopnorwt htheirsertahnekminogs,tweeffpor otviside the CRA-Index needed, and 10 referosf toutrhreefbeersetnscoelusotilounti,oin.ei.,ntthheeienvteagluration scparneabdesdhoeneteaqnudicakplyr.ogram that calculates the CRA-Index for a given class diagram.
Performance The performance evaluation consists of the measured execution time, i.e., the time it takes the provided solution to genCeroamtepalehxigtyh-qWuiatlhitycoomupt pleuxtitmyowdelmfoerasaurgeivtehne einffpourt3smnoedeedle.dPtoleapsreovnidoetestehaartchrecaadpinabgiltihtieesinfpourtgmoooddeslolutions as well as and writing the outptoutevmaoludaetleitshneostocluotniosnidsebreadsetdoobnethpeargtiovfenthmiseptreicrfso.rFmoarnicnestaenvacelu, athtiiosni.nvFoolrveJsavtoa-ebvaasleudatseohluotwionmsu, ch effort has been we suggest using Javinav’sesitnetdertnoaalutgimmeenmtethaseuprreomveidnetsd, riu.ele.,st,hdeevmeelothpoodrcjhaevstara.tlioannsgpe.cSifiycsattieonms.snuacnhoasTpirmoevi(d)in,gwahnicehxplicit control flow is also used by the AfopratchheerCuloems, mimopnlseLmaenngt’sse4aSrcthoaplgWoaritthcmhscalasstsra.nAsflloprmeraftoiormnsa,nocretovaimlupelsemmuenstt btreangsivfoernmeaxtaiocntstotothdeedicated encodings millisecond, e.g., 03u:se0d2f.o4r2pe6rfmoremani ninggth3emseinaurctehsa,n2dsebcaockn.dsHaenred, 4a2g6aimn,itlhlieserceovniedwseorrsinneteodtatlo1ra8n2k4t2h6e smoliulltiisoencsonindsre.lation to the other solutions provided and give them points on a scale between 1 and 10, where 1 refers to the worst (possible) solution All criteria, except the caonmdp1le0xrietyfearsndtoflthexeibeilsit ysoolufttihoen.solution, are evaluated separately on all provided input models.
4https://commonFsl.eaxpibaiclhitey.oFrlgex/pibrioliptyerm/ceoamsumroenssh-olwangea/sy it is to modify the given solution to support additional/other quality metrics besides coupling, cohesion and the CRA-Index. For this criteria, reviewers need to estimate the effort it takes to integrate new objectives (such as fixing the number of classes to a given value) and give the provided solutions points on a scale between 1 and 10, where 1 refers to the worst (possible) solution, i.e., the solution where the most effort is needed, and 10 refers to the best solution, i.e., the integration can be done quickly. override def newSolution() = { val s = new Solution(numVars, numObjs) (0 until numVars) foreach (x => s.setVariable(x, newInt(0, numVars - 1))) s // return the new instance
Next to providing a method to instantiate new instances of solutions for the problem, we need to also define the evaluation of a solution to compute the objectives. This involves two steps: (1) transforming the solution into a class diagram (2) using the provide calculateCoupling and calculateCohesion utility functions to compute the metrics. In code this is implemented as: override def evaluate(s: Solution) = { val m = solutionToClassModel(initModel, s) // transformation s.setObjective(0,calculateCoupling(m)) // minimize coupling s.setObjective(1,-calculateCohesion(m)) // maximize cohesion } The negation of the cohesion ratio is due to the fact that MOEA only works on minimization problems and thus we need to negate the objective value to convert from maximization into minimization. The following is the code that does the transformation. This is the main code that uses Sigma. def solutionToClassModel(initModel: ClassModel, s: Solution) = { val m = initModel.sCopy // create a new model as a copy of the input one val v = EncodingUtils.getInt(solution) // get problem vector (v: Array[Int]) // create new classes val classes = (0 to v.max) map (x => Class(name = s"Class $x")) } } // assignment v.zipWithIndex.foreach {
case (cIdx, fIdx) => m.features(fIdx).isEncapsulatedBy = classes(cIdx) // add non-empty classes m.classes ++= classes filter (x => !x.getEncapsulates.isEmpty) m
Finally, we define a new type, Solver, which is a function RDG ! ClassDiagram. The solver is responsible (1) to find the Pareto optimal front of all possible solutions (subject to solver configuration), and (2) to select the solution from that set which has the highest CRA-Index. The non-dominated, Pareto optimal front refers to optimal solutions whose corresponding vectors are non-dominated by any other solution vector [BBL10] and it can be found by MOEA Executor. For example using the NSGA-III algorithm, we find the non-dominated vector as: new Executor().withProblemClass(classOf[CRAProblem], initModel) .withAlgorithm("NSGAIII") .withProperty("populationSize", 64) .withMaxEvaluations(10000) .run() The individual solutions in this vector are first converted to the class model using the function solutionToClassModel. Then we use the given calculateCRA function to find the highest CRA. To have a better chance to find a good solution, we run each algorithm 10 times (this starts the algorithm from 10 different random seeds). The properties of each algorithm are defined based on the suggestion by Bowman et al. [BBL10]. 3
In this section we provide an evaluation of our solution following the categories given by the case study description. We leave the complexity and flexibility characteristics to be evaluated by reviewers. All the presented results are based on the NSGA-III algorithm which in all runs performed better than SPEA2. More results are provided on the github page. Completeness & Correctness. The solution always converts a valid input RDG into a class model. The three constraints that were imposed by the solution description are solved as follows: — Every class must have a unique name. The new classes are created in a loop that iterates over a number range. Part of the class name is the iteration variable and thus it must be always unique. — All features provided in the input model must be encapsulated by a class. This has been already explained in the previous section. This is a property of the problem mapping we have chosen. — There cannot be any empty classes. We explicitly filter out empty classes. Optimality and Performance. The following table shows the cohesion and coupling rations, the resulting CRA-Index as well as the completion time from the SHARE environment4:
A B C D E F [BBL10] Carlos Coello Coello, Gary B Lamont, and David A Van Veldhuizen. Evolutionary algorithms for solving multi-objective problems. Springer, 2007.
Martin Fleck, Javier Troya, and Manuel Wimmer. The Class Responsibility Assignment Case. In Transformation Tool Contest 2016, Vienna, 2016.
David Hadka. MOEA Framework - A Free and Open Source Java Framework for Multiobjective Optimization. Version 2.10, 2016.
F. Krikava, P. Collet, and R. France. SIGMA: Scala Internal Domain-Specific Languages for Model Manipulations. In Proceedings of 17th International Conference on Model-Driven Engineering Languages and Systems, volume 8767, 2014. [SBPM08] Dave Steinberg, Frank Budinsky, Marcelo Paternostro, and Ed Merks. EMF: Eclipse
Modeling Framework (2nd Edition). Addison-Wesley Professional, 2008.
4These are the initial results submitted for the competition. Improved result obtained after a better use of parallelism and better crossover and mutation ratios are available at https://github.com/fikovnik/ ttc16-cra-sigma The only requirements for running the solution is to have git and sbt5 tools installed. To reproduce the benchmark simply execute these steps in a command line:
On the share environment we provide ready to be run solution. Simply log into the SHARE VM remoteArchLinux64-TTC16_SIGMA with ttcuser/ttcuser as user name/password and run the following: $ cd ttc16-cra-sigma $ ./run.sh