Optimisation Methods for Model-Driven Engineering ?

Abstract

Recently there has been increased interest in combining the elds of Model-Driven Engineering (MDE) and Search-Based Software Engineering (SBSE). Currently, when solving MDE-SBSE problems, in addition to the problem description, the user is required to manually provide design space exploration (DSE) information, encoded as model transformation rules and an optimisation algorithm. Performance and solution quality strongly depend on the right choice of transformations and optimisation algorithm. The aim of this research is to develop an approach to solving MDE optimisation problems, by removing the need to manually specify model transformations and an optimisation algorithm. The inputs required for the problem description are the metamodel, the initial model if one is available and a set of constraints and tness functions. The remaining components needed for running the optimisation, are inferred from the given problem description. Solving this challenge allows domain experts to model optimisation problems using MDE and nd good solutions without needing extensive knowledge about model transformations, constraint solving or optimisation.

Keywords

• model driven engineering
• domain speci c language
• search based optimisation

-

MDE introduces models as a principal entity to describe complex engineering problems at a higher abstraction level than code [ 1 ]. The model is a representation consistent with a domain speci ed by the parent metamodel. A model is also referred to as an instance of a metamodel. A core MDE concept is model transformations, which enable model creation and alteration while maintaining metamodel consistency of the transformed model.

SBSE is a methodology for describing software engineering problems as optimisation problems [ 2 ]. A search based problem consists of a system to represent solutions, a process to generate new solutions from existing ones and a solution quality evaluation method. ? This research is in the rst year stage.

Recently there has been an increasing amount of interest in combining the elds of MDE and SBSE [ 3,4,5,6 ]. For all of these approaches, the user describes the optimisation problem using MDE and SBSE concepts and the tool returns converging solution models resulting from running the optimisation. In [ 6 ] the authors propose MOMoT, a rule based optimisation tool that o ers a Domain Speci c Language (DSL), implemented as an Eclipse plugin, to enable users to specify optimisation problems in MDE. Viatra-DSE is another tool performing rule based model optimisation [ 7 ]. Both tools in [ 6 ] and [ 7 ] optimise a chain of rule applications to nd the most suitable derivation chain which applied to an initial model results in a good solution model. A tool that runs optimisation directly on models is Crepe [ 3 ]. It has been extended in [ 4 ] to support multiple objectives. The tool uses a generic encoding for the models, as a set of integers, which is then used by genetic algorithms to apply mutations and crossover.

The research question this PhD aims to answer is: Can we simplify the process of running optimisation on models? We aim to contribute solutions to the following challenges in response to this research question: a) manual speci cation of transformation rules to be used as search operators requires knowledge about model transformations, optimisation and how the two elds can be combined; b) manual optimisation algorithm selection suitable for the problem being solved requires advanced knowledge about optimisation methods; c) choosing the most suitable model for the chosen optimisation strategy is not trivial. The proposed solution is to build a tool o ering a DSL that allows users to specify an MDE optimisation problem by supplying only the metamodel, an optional initial model and a set of constraints and tness functions. Using this information, the tool will then determine the best model to start the optimisation from, along with automatically generated transformation rules and a problem suited optimisation algorithm.

The contributions of this research will make the speci cation and solving of MDE optimisation problems more accessible, enabling domain experts to solve them without having knowledge about transformations and optimisation methods. The proposed solution will be evaluated by using the tool to solve industry case studies [ 8,4 ]. This type of evaluation will show if our proposed automated approach is better than the existing user driven alternatives. 2

Background

Search-Based MDE is the idea of combining the concepts of search based optimisation (SBO) and MDE, in order to solve optimisation problems speci ed using MDE [ 9 ]. An SBO problem speci cation requires the following elements: a) a candidate representation method; b) operators to generate new solutions from existing ones, by mutation or breeding; and c) a candidate quality evaluation method commonly referred to as tness functions.

The MDE model and metamodel concepts are an ideal equivalent of the candidate and search space representations from SBO. In MDE, model transformations are the process to change the structure of models while ensuring that their metamodel conformance is maintained. In SBO, transformations can be seen as operators, which are the process to mutate or combine individuals to explore the search space in order to nd better solutions. The SBO search space is the set of all possible candidates that can be solutions to the problem being optimised. The process of generating new candidates using operators and evaluating their suitability is also known as DSE. 3

Problem statement

Existing tools solving MDE-SBSE problems require the users to specify a problem description consisting of a metamodel, model instances, model transformations and an optimisation algorithm. The problem is that in order to use these tools to nd a solution to an optimisation problem, the user is required to know not only the domain of the problem, but also how to specify model transformations to use as search operators and what optimisation algorithm is the most suitable.

The aim of our research is to propose an approach to automatically infer from the problem speci cation consisting of a metamodel and a set of constraints and tness functions, the most suitable starting model for the optimisation process required for the current problem, if this is not already provided by the user, the best operators for e cient design space exploration and the optimisation algorithm. To make this possible, we have identi ed the following challenges that would have to be solved as part of this research: 1. Model evolutions. In order to e ciently explore the search space, it may not be enough to have transformation rules that ensure model consistency, but which also avoid local optima and provide good design space exploration during the search, through mutations and breeding. Automatically generating such transformation rules remains a challenging problem; 2. Optimisation algorithms. Automatically selecting the most suitable optimisation algorithm from a deterministic or stochastic repository of algorithms, using only high-level problem description and no user input is not trivial. Using the right algorithm for a problem can result in considerable performance and quality improvements [ 10 ]; 3. Initial model provision. In some cases an initial model may be available when an existing system needs to be improved or in other cases an initial model may have to be generated automatically. Determining the most suitable model version to use as an input for the selected optimisation algorithm in order to nd the best solutions is a di cult problem. 4

Approach

The plan for this research project is to start by identifying case studies that can be represented as MDE-SBSE problems [ 8,4 ]. The number of case studies will be continuously increased for the duration of the project, to allow us to e ectively validate the proposed solutions.

In Fig. 1 we identify the three steps required to solve the research challenges discussed in Sect. 3. Step 1, consists of using the user given constraints, objectives and the problem metamodel to generate e cient DSE operators. In Step 2, the most suitable search algorithm to solve the prob- Fig. 1: Research steps. lem is automatically identi ed using the generated search operators, the tool input used to generate them and knowledge about algorithm requirements. Step 3, is nding the best model to start the optimisation from. This step consists of determining if there are any transformations that can be applied to the input model before the start of the search process, to better guide the optimisation algorithm towards good solutions by starting from a suitable initial model. For each challenge we will propose an algorithm. This will then be implemented in our MDEOptimiser 1 (MDEO) tool and validated using the identi ed case studies.

The tool is built as an Eclipse plugin and is using the Eclipse Modelling Framework, allowing the user to specify the problem using a Domain Speci c Language (DSL) implemented using XText 2. The optimisation algorithms supported by the tool are implemented using the MOEA framework 3. A high level architecture Fig. 2: Tool architecture. of the tool can be seen in Fig. 2. The grayed box for the initial model denotes that it may be provided by the user only in some cases and therefore, when not available, it would have to be generated automatically using a tool like Cartier [ 11 ].

A high level overview of the expected timeline for completion has been included in Fig. 3. One of the main risks of the proposed research plan, is that 1 https://mde-optimiser.github.io/ 2 https://eclipse.org/Xtext/ 3 http://moeaframework.org/ there may not be a good solution which can be generalized to any MDE optimisation problem. In such a case, because the main aim is to simplify the process of running SBO on MDE, there are two mitigation strategies planned: a) reduce the scope of the research by focusing only on a certain type of problems that can be solved with our approach; b) rather than completely eliminating the requirements for the user to specify model evolutions and an optimisation algorithm, instead require the user to provide a set of helpers that could guide our proposed algorithms to achieve their goals. The occurrence of these risks can be identi ed in the initial stage of solving each of the challenges and mitigated accordingly once identi ed. 5

Current status

The research has been started by working on the model evolutions challenge. While working on this step, we have found promising results by proposing an automated way of generating transformation rules from a metamodel and a set of additional multiplicity constraints. The algorithm is based on the SERGe rule generation meta-tool [ 12 ], and it improves the transformation rules generated by SERGe, by adding a set of re nements to enable the model search to avoid getting stuck in local optima and ensuring a better search space exploration.

Our approach has been tested using the Class Responsibility Assignment (CRA) case study proposed as a challenge at TTC 16 [ 8 ]. The CRA scores found by the automatically generated rules have been close to, or in some cases better than, the scores obtained with the manually de ned rules. A detailed overview of our results for this implementation can be found in [ 13 ]. We are now working on generalising the approach and validating it with more case studies. 6

Related work

In [ 12 ] the authors introduce an automated way for generating consistency preserving edit operations (CPERs) from a metamodel. The rules are generated so that they can generate a valid model upon multiple applications. Another approach to generating transformation rules is proposed in [ 14 ]. The author presents a framework to generate DSE exploration rules using a genetic algorithm which is used to run a set of higher-order transformations on a training model. The obtained rules can then be used to transform models conforming to the same metamodel as the training model. This approach is one possible solution to the identi ed evolutions generator challenge, however, we aim to generate transformation rules using a deterministic algorithm, eliminating the performance overhead of a genetic algorithm.

In [ 15 ] the author introduces the model transformations by example (MTBE) approach to generating model transformation rules using an iterative, semiautomated method of generating model transformation rules from a set of example mappings between the source and the target models of the transformations, provided by the user at the start of the process. At each iteration, the user can re ne the generated rules by validating them with more test models. Using this approach, the quality of the generated rules depends on the intuition of the user and also on increased availability of test models. In [ 16 ] the authors propose the Model Transformation as Optimisation by Examples (MOTOE) approach to transform a source model into a target model using particle swarm optimisation (PSO) [ 17 ] and without specifying transformation rules.

Kessentini et al. propose an approach to generating transformation rules as an optimisation problem in [ 18 ]. The solution starts by randomly generating transformation rules, which are used to nd target models. The solution uses PSO to nd the best rules that generate good quality target models and once these rules are identi ed a local heuristic is used for further improvement.

In [ 19 ], the author identi es some of the current approaches to automatically selecting an algorithm to solve an optimisation problem. The survey also highlights the need for more contributions to this eld as the problem of algorithm selection is non-trivial. 7

Conclusions

This research will contribute to the eld by proposing an automated way to solve complex MDE optimisation problems by only requiring the user to input the problem metamodel, an optional initial model, and a set of constraints and tness functions. The solution will automatically determine: a) the most suitable model to start the optimisation from, b) the most e cient transformation rules to use for exploring the search space and c) the appropriate optimisation algorithm to nd the best solution.

The contributions made by this project will consist of proposed algorithmic approaches to solve each of the challenges identi ed and a tool implemented as an Eclipse plugin. The proposed approaches will be validated by using the tool to solve industry case studies and compare the obtained results with results obtained by manual attempts at solving the same case studies.

References

1. Atkinson , C. , Kuhne , T. : Model-driven development: a metamodeling foundation . IEEE software 20(5) ( 2003 ) 36 { 41

2. Harman , M. , Jones , B.F. : Search-based software engineering . Information and Software Technology 43 ( 14 ) ( 2001 ) 833 { 839

3. Williams , J.R.: A novel representation for search-based model-driven engineering . PhD thesis , University of York, UK ( 2013 )

4. Efstathiou , D. , Williams , J.R. , Zschaler , S. : Crepe complete: Multi-objective optimisation for your models . In: Proc. 1st Int'l Workshop on Combining Modelling with Search- and Example-Based Approaches (CMSEBA'14) . ( 2014 )

5. Abdeen , H. , Varro , D. , Sahraoui , H. , Nagy , A.S. , Debreceni , C. , Hegedus, A. , Horvath , A. : Multi-objective optimization in rule-based design space exploration . In Crnkovic, I., Chechik , M. , Grunbacher, P., eds. : Proc. 29th ACM/IEEE Int'l Conf . Automated Software Engineering (ASE'14) , ACM ( 2014 ) 289 { 300

6. Fleck , M. , Troya , J. , Wimmer , M. : Marrying search-based optimization and model transformation technology . Proceedings of the First North American Search Based Software Engineering Symposium ( 2015 ) 1 { 16

7. Hegedus, A. , Horvath , A. , Rath , I. , Varro , D. : A model-driven framework for guided design space exploration . In: Proc 26th IEEE/ACM Int'l Conf . Automated Software Engineering (ASE'11) . (November 2011 ) 173 { 182

8. Fleck , M. , Troya , J. , Wimmer , M.: The Class Responsibility Assignment Case . In: Proceedings of the 9th Transformation Tool Contest @STAF. Volume 1758 of CEUR Workshop Proceedings . ( 2016 ) 1{ 8

9. Burton , F.R. , Poulding , S. : Complementing metaheuristic search with higher abstraction techniques . In: Proceedings of the 1st International Workshop on Combining Modelling and Search-Based Software Engineering , IEEE Press ( 2013 ) 45 { 48

10. Rice , J.R.: The algorithm selection problem . Advances in computers 15 ( 1976 ) 65 { 118

11. Sen , S. , Baudry , B. , Mottu , J.M. : Automatic model generation strategies for model transformation testing . In: International Conference on Theory and Practice of Model Transformations , Springer ( 2009 ) 148 { 164

12. Kehrer , T. , Taentzer , G. , Rindt , M. , Kelter , U. : Automatically deriving the speci - cation of model editing operations from meta-models . In: International Conference on Theory and Practice of Model Transformations , Springer ( 2016 ) 173 { 188

13. Burdusel , A. , Zschaler , S.: Automatic generation of evolution rules for modeldriven optimisation . In: 8th International Workshop on Graph Computation Models (GCM'17) . (2017) accepted .

14. Struber, D.: Generating e cient mutation operators for search-based model-driven engineering . In: International Conference on Theory and Practice of Model Transformations (ICMT) . (2017) accepted .

15. Varro , D. : Model transformation by example . In: Proc. Model Driven Engineering Languages and Systems (MODELS 2006 ). Volume 4199 of LNCS ., Springer ( 2006 ) 410 { 424

16. Kessentini , M. , Sahraoui , H. , Boukadoum , M. : Model transformation as an optimization problem . In Czarnecki, K. , Ober , I. , Bruel , J.M. , Uhl , A. , Volter, M., eds.: Model Driven Engineering Languages and Systems: 11th International Conference, MoDELS 2008 , Toulouse, France, September 28 - October 3 , 2008 . Proceedings, Berlin, Heidelberg, Springer Berlin Heidelberg ( 2008 ) 159 { 173

17. Eberchart , R. , Kennedy , J.: Particle swarm optimization . In: IEEE International Conference on Neural Networks, Perth , Australia. ( 1995 )

18. Kessentini , M. , Wimmer , M. , Sahraoui , H. , Boukadoum , M. : Generating transformation rules from examples for behavioral models . In: Proceedings of the Second International Workshop on Behaviour Modelling: Foundation and Applications , ACM ( 2010 ) 2

19. Kottho , L. : Algorithm selection for combinatorial search problems: A survey . AI Magazine 35 ( 3 ) ( 2014 ) 48 { 60