From single-objective to multi-objective reinforcement learning-based model transformation

A common theme in MDO is about projecting the initial state of a problem to a model representation, and subsequently, searching for an alternative model representative of a suitable solution state. One key challenge in tackling complex problems by formulating them as optimization problems is to effectively represent the problem on an appropriate abstraction level [14]. In this respect, MDO offers a remedy by utilizing domain-specific models to capture the problem domain and leveraging a generic encoding to explore the design space through MTs in the solution domain. Thereby, it facilitates the integration of the abstraction power of models and the scalability of exploration techniques such as meta-heuristic search, to name just one prominent example. In order to conduct an appropriate search at a particular state, i.e., model instance, the following prerequisites are essential [1, 14, 15]: (i) a representation for solution candidates, (ii) a method to employ search operators to generate new solutions from existing ones, and (iii) a mechanism for evaluating solution candidates. In essence, this also conveys to employing RL techniques, where we utilize a learning paradigm instead of a search.

Solution representation The initial problem state corresponds to a model instance based on a metamodel which captures the general problem domain. For the solution encoding, candidates can be represented again as model instances (e.g., see [8, 14, 16‐19]), or as sequences of transformation steps (e.g., [2, 3]) producing the solution models when executed on the initial model.

Solution generation New models emerge from introducing structural or attribute changes as a result of the application of MTs. MTs either create a new output model from scratch (out-place) or are executed in-place to modify the existing input model directly [20]. The direct manipulation is frequently performed for refactoring or optimization purposes [21]. In the case of using a model-based encoding, MTs are invoked to mutate a candidate model, whereas when using a rule-based encoding, i.e., transformation sequences, mutation and crossover operators are used to add, delete, or replace transformation rules and exchange subsequences in order to derive new sequences [8].

Solution evaluation The evaluation of solution candidates provides guidance in navigating towards promising areas in the search space. Generally, optimization problems can be formulated in the generic form [22]:Functions \(f_i(\varvec{x})\) are called objective functions, each representing one optimization objective. Multi-objective problems involve two or more objectives, i.e., \(M \ge 2\). The decision variables \(x_i\) and their feasible settings denote the search space \(R^n\). As not all solutions in \(R^n\) may be feasible, additional functions \(h_j(\varvec{x})\) may be introduced to restrict the set of all attainable function values, i.e., the solution space, to the feasible region. In the MDO realm, we also rely on the definition of fitness functions to assess a model’s ability to represent a solution for the problem under consideration [14]. These fitness functions are defined on the metamodel in accordance with the modeled problem domain. The search space corresponds to the design space of the model, which includes all models that can be achieved by applying available MTs. In addition, constraint functions or queries can define properties for a model that indicate infeasibility for the intended application context.

Bild vergrößern

In the evaluation process, the fitness values are calculated for a transformed model and represented as a potential solution in the form of an objective vector. These solutions can then be compared with the concept of Pareto optimality [23]. Furthermore, the solution sets of two different algorithms can be evaluated against each other using measures such as the frequently utilized hypervolume (HV) [24] indicator. The HV calculates the volume of the region in the objective space that is dominated by the Pareto-optimal set of solutions (i.e., the Pareto front) found by an algorithm, relative to a given reference point. This is illustrated for a 2-dimensional problem in Fig. 1. A higher HV of a solution set denotes superior quality of the contained solutions, in the MDO context of the transformed models, concerning the fitness functions.

From an architectural point of view, the constituents of an MDO framework consist of an environment facilitating the generation of metamodels and models, an MT engine and associated language for model manipulation, and algorithms geared towards conducting a search for transformation orchestrations that both optimize the objectives and adhere to designated constraints. Among available tools [1‐4], MOMoT [3], which is explained in more detail in the next subsection, utilizes a rule-based in-place transformation approach and an encoding based on transformations to search for appropriate rule transformation sequences.

Bild vergrößern

Bild vergrößern

MOMoT [3] denotes a framework that integrates the Eclipse Modeling Framework (EMF) [25] together with the Henshin transformation framework [26] with a diverse palette of optimization algorithms, such as evolutionary approaches from the embedded MOEA framework¹ and a set of local searchers. Moreover, we presented an initial study about our efforts to extend the scope for learning techniques [9] which is extended by this work. Fig. 2 shows the input artifacts, the resulting output artifacts, as well as the schema used for conducting the search.

The Problem Instance Model represents the problem to solve in its initial state. Henshin [26] is utilized for its Transformation Rule Language and its transformation engine to define and execute MTs. Objectives and Constraints are provided as OCL queries or Java functions having access to the transformed models. The Exploration Configuration concerns search-related settings such as the algorithm, its parameters, and associated performance metrics for the given problem instance. Throughout the Search-based Exploration, new transformation rule sequences are produced and after application of the rules, the resulting models are subject to an Objective and Constraint Evaluation phase. A set of candidates of transformation sequences remains with the best trade-off solutions from a decision-making point of view. The final output encompasses the Result Models and Rule Orchestrations from the best candidates accompanied by their fitness assessment and search-related Exploration Statistics.

Henshin Henshin [26] includes an engine and language based on the graph-based MT approach [20]. Henshin rules consist of LHS and RHS graphs which describe patterns to match in a model and the changes to apply. During execution, a rule is matched to the graph of a model, and the transformation is carried out successfully only if the resulting graph conforms to the specified changes and application conditions as a matter of formal reasoning. Beyond mere model manipulation, units support a nesting concept and control structures such as loops and conditional branches to manage the control flow.

In the underlying architecture, MOMoT represents solutions as a sequence of transformation units. It thus provides a natural representation for a generic implementation of recombination operators from evolutionary computing [27] but also enables a step-by-step extension of the solution in the sense of a local search. If an error occurs during the execution of the sequence, a repair mechanism handles the error-inducing units to restore feasibility. With the Henshin units used, however, costly repair can be avoided to some extent by using domain-specific constraints.

As a motivating and running example for this paper, we consider the static container relocation problem (CRP) [28], also known as block relocation problem [29]. Coming from the logistics domain, container terminals are essential parts of transportation networks with containers being stacked on top of and next to each other in bays while awaiting their retrieval to depart with the intended transportation facility. Naturally, the time to assemble shipment goods affects operation efficiency. Thus, the objective is the efficient retrieval of the containers in the desired order through relocations.

Please note that the CRP may be also natively encoded for RL. However, by following the MDO paradigm, we can represent explicitly the initial problem instances as well as the found solutions for domain experts. In addition, as we will see in the evaluation section (see Section 4), the metamodel, models, transformation rules, and the formulation of the objectives can be reused for different RL approaches as well as other optimization approaches such as genetic algorithms which are available in the MOMoT framework.

Bild vergrößern

Modeling the CRP Formally, the CRP consists of containers \(C=(c_1,c_2,\ldots )\) that are distributed among stacks \(S=(s_1,s_2,\ldots )\) with container indices determining the retrieval order. Naturally, a container can and will only be retrieved if it resides at the top of a stack. A relocation moves a container from the top of one stack to the top of another stack. We consider the unrestricted CRP, which permits relocation from any stack at all stages, an unbounded tier size, i.e., maximum stack height, but posing a fixed width for the stacking area, i.e., no new stacks may be added.

The metamodel in Fig. 4 allows to capture the current container arrangement. A corresponding model instance comprises Stack and Container instances, and holds a reference to the container to be retrieved next. Each stack is located at a position and stores the container currently residing at the top of it, if any. Each container resides on one of the stacks until it has been retrieved and may remain on top of another container. The order of retrievals is implicit, as each container refers to the next required container after its own retrieval. This way, the reference from the root element to the container next in line can be updated with each retrieve operation. We note that alternative designs are conceivable.

The transformation model comprises a single top-level unit (Fig. 3b) which contains two units, Retrieve and Relocate. In each transformation step, one of the two is invoked based on the next required container residing on top of a stack (checked with rule canRetrieveContainer). The retrieve and relocate operator to retrieve and move containers, respectively, in turn consist of several subunits and conditions to keep the transformed model in a consistent state. That includes, for instance, updating the top container of a stack upon retrieval or moving from it. In this respect, the retrieve/move operation is carried out further down within the Retrieve/Relocate unit, e.g., in the rule retrieveLastFromStack, which is depicted in Fig. 3.

Transformation Goal Determining the optimal moves for retrieval has been proven to be NP-hard [30] even without practical considerations affecting efficiency, e.g., each move takes time depending on the distance between involved stacks. We pick up on this in our goal formulation as we seek move sequences to retrieve as many containers as possible and in the right order (RetrievedContainers), while we minimize the number of moves (TransformationLength) along with the total travel distance (TravelDistance) of all moves. The distance calculation for a move is embedded into the MT rules and based on the difference in position of the corresponding source and target stack. These objectives aim to maximize efficiency and are not necessarily conflicting. Nevertheless, it is assumed that the least required moves often do not imply the shortest travel distances. In many cases, taking one or two additional moves between stacks that are closer together can be faster overall.

In sequential decision problems, an agent continually interacts with an environment, which exhibits the current problem state. Fig. 5 depicts this interaction with the intrinsic framework of a Markov Decision Process (MDP) [32]. With each taken action \(A_t\) based on the current state \(S_t\) over time steps \(t=0,1,2,\ldots \), the agent receives the successor state \(S_{t+1}\) and a reward \(R_{t+1}\). The agent ought to learn a behavioral pattern - a policy \(\pi \) - that dictates the optimal action for each state to maximize cumulative rewards. This policy maps states to the most valuable actions, guiding the agent’s decisions and exploration of the environment.

Bild vergrößern

Generally, the agent aims to maximize the cumulative reward \(G_t\) = \(R_{t+1}\) + \(R_{t+2}\) + ...over the (possibly infinite) interaction steps. In episodic tasks, the time horizon for interaction is finite, hence, earlier rewards should be prioritized. Thus, the goal shifts to maximizing the expected discounted return \(G_t\) = \(R_{t+1}\) + \(\gamma R_{t+2}\) + \(\gamma ^2 R_{t+3}\) + ...with the discount rate \(\gamma \in [0, 1]\).

The value function V(s) is defined in Equation 2 as the expectation of future discounted rewards starting from a state s and following a policy \(\pi \) as follows:The value of the terminal state in episodic tasks is always zero.

Value-based methods use the rewards to approximate the value function V(s) through an action-value function Q(s, a) that learns the values of actions in certain states. Accordingly, Q(s, a) in Equation 3 also considers the action a selected to continue from state s following policy \(\pi \).The goal is to find the optimal policy \(\pi ^*\) that maximizes the optimal value function \(V^*\). This corresponds to the sequence of state-action pairs that maximizes \(Q^{\pi }\), i.e., the optimal action-value function \(Q^*\).

Solving the sequential decision problem means determining \(\pi ^*\) based on observed state values \(V^{\pi }\). Using the Bellman equation, \(Q^*(s,a)\) can be approximated by finding the actions that maximize \(Q^{\pi }(s,a)\), which expresses the value function \(V^{\pi }(s)\) for any policy \(\pi \) and state s in terms of the action-value function \(Q^{\pi }(s,a)\):Solving this equation leads to the value function and therefore to \(\pi ^*\). However, in many practical cases, the state space may be unfathomably large, and methods like Q-Learning [33] are employed to approximate the solution. To this effect, Q(s, a) can be approximated using a tabular approach, i.e., learning an explicit mapping from states to action values, or as a parametric policy function \(\pi _{\Theta }\) using function approximation methods. In this study, however, we investigate the former for in-place MTs.

A prevalent approach to multi-objective optimization is to derive a combined objective reflecting the user preferences [43]. The preferences are expressed as a weight vector to scale the observed objective values, which are then aggregated with a scalarization function. The resulting value can then be treated as a single objective. In the simplest form, the function is a linear combination \(\sum _{o=1}^{m} w_i*f_i(x)\).

Similarly, for multi-objective RL, a weight vector can be specified to scale rewards in \(\varvec{r}(s,a)\) as they are linked to more or less important objectives [6]. Combining rewards from several utility functions for estimating action values was first studied in [44]. In the present approach, a separate action value function \(Q_i(s, a)\) is approximated for each objective i using the values observed from the reward vector. Meanwhile, the scalarized value is computed with function SQ(s, a), which is used for the action selection and updates of \(Q_i(s,a)\):Alternative to the linear function, the Chebyshev metric [45] (see Appendix A.1) can be used to calculate SQ(s, a). In addition to weight scaling, a current estimate of the utopian point is factored into selection, which has shown to yield a performance increase [39].

Aggregation to a single value is generally simple and computationally efficient, making it also appropriate for evaluating the fitness of models in the context of transformation problems. For each fitness function used to evaluate the model, a value function \(Q_i(s,a)\) is initialized and updated. During selection, their values are summed for a given transformation in a given model state (\(Q_i(s,a)\)) after each is scaled by the according weight. However, the scalarization approach might not be appropriate if the weight specification is difficult or objectives cannot be reasonably projected to a single metric, especially if the fitness values have different orders of magnitude.

This algorithm adheres to a compromise that guarantees the optimal selection of an action for at least one of the objectives [40]. Similar to the weighted sum approach, each objective is associated with an agent approximating a dedicated action-value function. Instead of aggregating the criteria aiming for a reasonable trade-off, W-learning selects one objective to prioritize at each step. Accordingly, the expected outcomes for an action in the current state are compared between agents, i.e., from the perspective of each criterion. This comparison can be seen as engaging in a negotiation for the next executed transformation (see Appendix A.2 for more details on the negotiation procedure).

For an intuitive illustration, consider our running example, dedicating an agent to the retrieved containers (\(A_{RC}\)) and the travel distance (\(A_{TD}\)), respectively. An initial proposal from \(A_{RC}\) for a transformation \(t_a\) could move a container to enable retrieval of underlying containers. However, to the detriment of \(A_{TD}\), the relocation involves a long traveling distance (expressed by a weight \(W_{TD}\)). Hence \(A_{TD}\) can suggest a transformation \(t_b\) for an alternate move operation with a shorter distance. Yet, with \(t_b\) further retrieval is hampered (as is quantified by \(W_{RC}\)), which exceeds the disadvantage of \(t_a\) for the assessment of \(A_{TD}\), i.e., \(W_{RC} > W_{TD}\), again enabling \(A_{RC}\) to intervene for a new counter-proposal. The finally executed transformation is ultimately decided by the agent to whom the counterpart cannot assert a greater disadvantage for its objective for not following its suggestion.

For practical considerations, W-learning constitutes an unbiased approach concerning explicit objective prioritization, and the memory requirements are comparably marginal. In this respect, there is no preference setting, but a trade-off of all optimization criteria for the learned policy is inherent to the continual change of decision-making power. Notably, an action-value function \(Q_i(a,s)\) is still learned for each criterion although a single policy is learned as all agents collectively decide which transformation they all execute. Despite the weights being continuously calculated in the negotiation procedure described, they do not have to be learned or stored but are obtained ad-hoc from \(Q_i(a,s)\).

Whereas the scalarization approach and W-learning attune to a trade-off in criteria for the learned policy, either by weighting objectives or implicitly, PQL [41] accommodates objective vectors instead of action-value functions. With the latter, the update rule for Q(s, a) in Equation 6 is based on the immediate reward and expected future reward. Here, however, for each state-action pair an average vector \(\overline{{\mathcal {R}}}(s,a)\) is maintained whereas the future reward corresponds to a (Pareto) vector set \(ND_t(s,a)\). After each step, the sole agent adds the observed immediate reward \(\varvec{r}\) to \(\overline{{\mathcal {R}}}(s,a)\) and updates \(ND_t(s,a)\) with the vectors resulting from adding the immediate reward and the expected future rewards from the successor state, \(\hat{Q}_{set}(s',a')\). For details on the update rules as well as the usable action selection mechanisms, please refer to Appendix A.3.

Reward decomposition in PQL allows for the preservation of individual goal contributions and therefore leads to a variety of solutions for different preference scenarios. Since only the non-dominated set is retained during updates, any action that is later reconsidered is part of a non-dominated strategy. In MDO terms, this ensures that each time the agent reuses a transformation, it is one of a transformation sequence that produces a model that is optimal for at least one of the criteria. This potentially allows learning several optimal policies along the entire Pareto front. Nevertheless, it does not guarantee optimal or even better solutions for MDO problems with large design spaces due to limited exploration. Implementation-wise, the algorithm requires more memory to store vector sets instead of scalar values.

Our selection includes several cases frequently used for the evaluation of MDO approaches, for whose representation the respective domain models are available, and objective formulations for evaluating a model’s fitness have already been devised. These include refactoring tasks, design model optimizations, as well as a common workflow from the logistics domain. An overview is provided in Table 2. The artifacts used in each case study are available in our public project [10].

Each of the case studies comprises multiple instances of varying complexity, the results of which we consider collectively in order to gain insights with regard to the research objective. The problem domains are described in terms of the model abstractions, the transformation rules used to define the search space, and the objective functions for measuring the degree of optimality.

Please note that the selected case studies are all endogenous, i.e., transformations within the same modeling language, and horizontal, i.e., staying on the same abstraction level [51]. While other types of transformations may be also formulated as MDO problems in MOMoT, we leave the evaluation of RL for such transformations (exogenous and vertical ones) as subject to future work.

Container Relocation Problem (CRP) We refer to Section 2.1.3 for a general description. As objective functions, in the multi-objective evaluation, we use (1) the Container-Index and (2) the travel distances between stacks over all moves. In the single-objective evaluation, we omit the travel distance and only consider the Container-Index as a combined measure factoring in the retrieved containers and a metric for the amount of blocked containers, called blocking factor. The global blocking factor (\(BF_{G} \in [0, 1]\)) quantifies the containers having one or more containers of lower priority stacked above them. For a container \(c_i\) (with i implying the container index) we denote the blocking degree (BD) in Equation 9 as the number of containers above it having a larger index on the same stack \(s_i\) (with i implying the stack index). The BD is normalized using the triangular number \(T_n = \frac{n*(n+1)}{2}\), which gives the number of possible blockages on a stack with \(n+1\) containers. Factors are summed up over the stacks and divided by the number of overall containers |C|. Finally, the retrieved units and \(BF_{G}\) are combined in the combined objective in Equation 10.The four model instances range between three stacks and eight containers to ten stacks and forty containers.

Stack load balancing (SLB) Already used in the context of MDO in [3, 52], this case study concerns the distribution of items in a system of stacks. The StackModel (cf. Fig. 8) consists of multiple stacks (Stack) that are connected in a circular way with each stack having two neighbors, left and right, and a load assigned.

Bild vergrößern

Using two rules, shiftRight and shiftLeft (defined analogously), stacks can shift load to their neighbors. Feasibility of the shift operation depends on available units on the providing stack and is guaranteed by a precondition. Changes are defined by rule parameters specifying the sending and receiving stack, and the amount of shifted items.

The transformation goal is to shift load accordingly to balance the load distribution. That is, to minimize the standard deviation over the loads of all stacks.

With increasing shifting possibilities, the state space increases exponentially with each additional stack, which complicates the steps to reach an equal distribution. We use problem instances with 5, 10, 25, or 50 stacks.

Class Responsibility Assignment (CRA) The CRA problem stems from the quality assurance domain of object-oriented systems [53] and has been extensively used in the Transformation Tool Contest as a particular transformation case [54]. Given a set of methods and attributes, it aims for an assignment to classes that well separates their concerns. This is of interest to raise the quality of software models and consequently the generated code. As defined in Fig. 9, the ClassModel consists of classes (Class) which hold a set of features (Feature). A feature is either a Method with functional (functionalDependency) or data dependencies (dataDependency), or an Attribute.

Bild vergrößern

Models are evaluated using CohesionRatio and CouplingRatio as common metrics to measure separation of concerns [54]. The former indicates the concentration of dependencies in the same classes and should be maximum. The latter counts dependencies between features of different classes and should be minimal to indicate an extensive separation of independent system aspects. The formulations used consider the method-attribute and method-method combinations formable within/between classes. Specifically, for two classes \(c_i\) and \(c_j\), the total sum of dependencies across all feature combinations is counted. For CohesionRatio, combinations are considered for class pairs where \(c_i = c_j\), meaning feature combinations within the same classes are reflected, and whose dependencies should be maximized as a result. For CouplingRatio, combinations are considered for class pairs where \(c_i \ne c_j\), meaning the dependencies between features of different classes are counted, which should therefore be minimized. The same schema is applied for counting dependencies between methods. For the single-objective variant the two metrics are combined to a single measure, CRA-Index, defined as their difference CohesionRatio - CouplingRatio [54].

Bild vergrößern

In our study, we use five design models from the Transformation Tool Contest in 2016². As pointed out in [54], the number of possible arrangements such that every feature is assigned to a class is given by the Bell number \(B_{n+1} = \sum _{k=0}^{n} {n\atopwithdelims ()k} B_k\). The n-th number in this sequence, \(B_n\), denotes the number of possibilities to distribute n elements into disjoint subsets. In the smallest instance considered, this means 21147 possible result models for 9 features. The next instance with 18 features exhibits 682076806159 possibilities already.

Refactoring This study is considering the class diagram restructuring case from the Transformation Tool Contest [55], and thus, aims at improvements of an object-oriented design model by abstracting classes that share common data features to accomplish a less redundant structure. It involves identification of duplicate attributes in classes that could alternatively be accessed from a common object on a higher level, and derive new classes that share features of related entities. As illustrated in Fig. 10, a model consists of entities (Entity) and properties (Property) with inheritance relationships depicted as Generalization. That is, an entity A inherits properties of another entity B if A has a generalization relationship to a Generalization G and B is the target entity of G (general). In addition, properties have a type (Type).

The refinement transformations are defined with three rules: First, createRootClass introduces a new entity C with a property a previously declared in two subclasses that henceforth inherit this property from C. Second, the rule extractSuperClass adds an intermediate level to the inheritance hierarchy. More precisely, a new entity C becomes the superclass of classes that share a common property a and previously derived from a class S. Entity C then declares a and inherits from S, exposing a to entities that individually declared a before this change. Third, for classes sharing a common superclass S and declaring an attribute a, pullUpAttribute removes a from these classes and re-declares it in S.

The aim is to achieve the lowest possible redundancy for elements used in the design model. To this extent, the objective function used minimizes the total sum of entities and properties.

We consider two different problem instances. For the model denoted as Ref-1, attributes need to be moved over multiple inheritance layers to the top of the hierarchy, for Ref-2, several of the mentioned activities need to be performed to optimize the model.

For the applicability question (RQ1) we focus on potential obstacles one may encounter when using RL for in-place MTs, but also necessary preliminary steps and limitations in the application. More practically, we show the feasibility by instrumenting implementations of the algorithms described in Section 4 next to the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [56]. The capability of NSGA-II has been demonstrated extensively in the MOMoT environment [3], which is the same we leverage in this work.

For the performance evaluation (RQ2) we consider the models that result from the transformation sequences produced by algorithms, henceforth referenced as solution or approximation sets. Having at least one case-specific objective in place and as we also consider the length of MT sequences, each solution has in any of our cases an objective vector in n-dimensional space. Specifically, due to considering the transformation length as an additional general objective, \(n=2\) for cases with a single quality objective (here referred to as single-objective) and \(n > 2\) for cases with multiple quality objectives (here referred to as multi-objective).

Considering these different settings, we use the HV indicator for a direct comparison of solution sets. The same is recommended by the authors of [23] when dealing with fewer than 10 objectives. As the reference set, we use the combined non-dominated front as is deemed common practice [23]. Furthermore, we are interested in the total optimization capability where there is only one quality objective in place, hence determining the best objective fitness value (BOV) after each algorithm run. The BOV corresponds to the best value observable in the produced solution set for the object of interest, which is for each case designated in bold in Table 2. Finally, we measure the execution times of the individual algorithms to obtain an estimate of the overhead of the RL techniques. This is seen in contrast to GAs, which have a diverse potential for parallelizing computations.

Due to the stochastic elements present in both meta-heuristic algorithms and our RL implementations, resulting solutions vary across multiple executions. To ascertain the significance of performance differences, we collect results over 30 independent experiment runs for each instance of each case study and conduct pairwise tests for all case studies, evaluating the effect size and testing for significance of the differences in performance. Regarding effect size, we analyze Vargha and Delaney’s \(\hat{A}_{12}\) statistic [57], which is suitable for non-normally distributed data samples [58], as we find them in our experiments. To this end, we calculate the pooled statistic on a case-study basis, averaging over the results for the instances of each case study. The statistic indicates a small (.5-.56), medium (.57-.64), large (.65-.71), or very large (.72-1) difference in favor of the algorithm in the column. In addition, statistical significance is determined applying the Mann-Whitney U test [59] as a non-parametric test, using a significance level \(\alpha = 0.05\). The null hypothesis states performance equality whereas the alternative hypothesis states that there is a significant difference in performance.

The algorithms require an appropriate configuration before they can be executed for each case study.

Each experiment is run 30 times, where each algorithm terminates after a predefined number of function evaluations (FEs): Up to 40,000 for SLB, 80,000 for the CRA problem, 20,000 for the CRP, and 1,000 for the Refactoring case. As performance indicators, we use the mean HV, runtime, and the best overall solutions per algorithm.

We use the NSGA-II that is implemented in MOMoT as a baseline for comparison against the learning-based algorithms, and for configuration adhere to the settings reported in previous case studies [3]: population size of 100; deterministic tournament selection (\(n=2\)); one-point crossover (\(p=1.0\)); two mutation operators to remove (\(p=0.1\)) and replace (\(p=0.05\)) a rule in the transformation sequence.

For RL algorithms we use a discount \(\gamma \)=0.9 to optimize towards shorter transformation sequences. We set \(\epsilon \)=1.0 for an exploration-heavy phase at the start and gradually decrease \(\epsilon \) to shift towards exploitation of transformations with increasing FEs until \(\epsilon \)=0.05. Our studies test the approaches from Section 4, in particular, Q-learning (\(Q\)), the Chebyshev scalarization function (\(Q_{Chebyshev}\)), Negotiated W-learning (\(Q_{W}\)), and PQL using the HV indicator (\(PQ\)-\(HV\)) and Pareto set evaluation (\(PQ\)-\(PO\)) mechanism, respectively. We enable the enhanced exploration strategy (Section 4.4) for instances of large combinatorial problems, therefore marking those instances with a superscript plus (“⁺”) following the algorithm name.

The search space is also determined by the sequence length (i.e., transformation steps) a solution comprises. It is also an essential parameter for the NSGA-II. We choose the maximum transformation length (\(TL_{max}\)) per case and complexity such that the optimal output model can be found if known, and otherwise set it to a length that enables far-reaching improvements.

Software Using Java 14.0.2 and Eclipse version 4.28.0, we limit memory usage to 20GB with initial heap size set to 1GB. Due to building on the toolset integrated in the MOMoT framework [3], the Eclipse Modeling Framework (v2.25) and Henshin SDK (v1.6.0) are required.

The extension for RL algorithms has been implemented to adhere to the interfaces of the MOEA framework, in particular the "AbstractAlgorithm" class, to enable the same usage pattern as with the GA encoding utilized for MDO. The algorithms and environment utilities were implemented as Java classes without a dedicated RL framework. To this end, we provide a unified interface for the following interaction pattern: execute a transformation rule (i.e., the action), receive the objective fitness value(s) of the model (i.e., the reward), and the transformed model (i.e., the successor state) as output. In doing so, we aim for comprehensibility and to facilitate further adaptation efforts, e.g., to implement new RL algorithms for MDO based on our framework.

Our tool extension, including all case study setups and used artifacts such as models and transformation rules, is available online [10].

In addition to the transformation length, the results involve a single domain-specific objective. Empirical results are reported in Tables 3 and 4.

HV In the five-stack case, the RL algorithms turn out superior, albeit \(Q\) only to a marginal extent, and show higher consistency (\(\sigma = .015\) and \(\sigma = .009\)). For higher-stacked models, \(Q^+\) increasingly outperforms NSGA-II as it covers a much broader region in the objective space although NSGA-II claims some parts in the midsection for SLB-25 (Fig. 11a–c). This manifests for the larger models (SLB-25 and SLB-50) even when accounting for variations between runs. In this regard, \(Q^+\) also shows the most consistent performance. Meanwhile, \(Q\) falls off with increasing model size and accounting for deviations clearly below NSGA-II from SLB-25 onwards.

BOV The optimal distribution for the simplest case demands three steps, which all algorithms manage to find. For SLB-10, \(Q^+\) finds the solution for the most even load distribution with standard deviations over loads of .4. Moreover, facing increasing complexity with increasing stacks (SLB-25 and SLB-50), \(Q^+\) surpasses the GA in balancing the loads.

Bild vergrößern

Runtime NSGA-II is the fastest algorithm for smaller model sizes and the therefore defined maximum length for rule sequences. This advantage against the learning algorithms vanishes with more rules per individual in NSGA-II with longer mean execution times than \(Q^+\) for SLB-25 and SLB-50 with \(TL_{max}\) of 50 and 100, respectively.

Effect size and significance Results show superiority of \(Q^+\) for all instances with large or very large differences in the pairwise comparisons, whereas NSGA-II still vastly outperforms our basic Q-learning adoption, named \(Q\). Further, all comparisons show a significant difference, except for NSGA-II and \(Q\) on the SLB-5 model (\(p = .053\)).

HV Talking nominally, \(Q\) determines widespread trade-offs for the required moves and resulting emerging container retrieval, and thus, appears more effective than \(Q^+\) and NSGA-II. A look at the non-dominated solutions for each algorithm in Fig. 12a–c reveals dense regions from the learners for short transformation sequences, but also to a great extent for long sequences, particularly ones from \(Q\). Consequently, the GA only marginally reaches the space outlined by the combined non-dominated set, which reasons for the low performance on the mid-sized model. Despite the high coverage for \(Q^+\) and \(Q\), solutions determined for the later steps in the sequence are inferior to NSGA-II, which takes the lead on the BOV. The enhanced exploration subject to \(Q^+\) appears to be non-beneficial for this task. Although the \(Container-Index\) factors in the inaccessibility of containers yet to be retrieved, the greedy approach seems to neglect crucial steps for their retrieval later on.

Bild vergrößern

BOV Although showing higher coverage in the objective space, BOV (\(14.94 < 16.92\)) indicates that \(Q\) lacks further exploration of its options later in the episodes with most progress occurring on the first 20-40 steps. The greedy approach in this task turns out not as suitable as the classic variant.

Runtime Considering all instances together, NSGA-II positions between Q-Learning with and without a local search in terms of runtime. \(Q^+\) shifts towards exploitation faster than Q, and thus, finishes a lot earlier. The GA spends time during initialization of initial solutions and later for lengthy repair operations which are expected to occur frequently due to infeasible relocation sequences from recombination.

Effect size and significance \(Q\) yields a large performance difference over both \(Q^+\) and NSGA-II, which also holds for \(Q^+\) in contrast to NSGA-II. Only for the simplest instance, CRP-3S8, the advantage of \(Q\) is insignificant (\(Q\) vs. NSGA-II, \(p=.212\))

HV   Throughout all instances, \(Q^+\) provides the best trade-offs in assignments and model quality. With increasing features, the separation of dependencies works better by extensive exploration with \(Q^+\), which consistently outperforms \(Q\). Furthermore, the Pareto front approximation in Fig. 13a–c is for NSGA-II centered around transformations with medium length, but does not reach the extreme points. Additionally, \(\sigma \) shows the performance of \(Q^+\) as more consistent. \(Q\) yields better approximations for smaller models (CRA-9 and CRA-18), but loses against NSGA-II for the larger ones.

Bild vergrößern

BOV   Considering CRA-9, the optimal model is found universally. With increasing complexity, \(Q^+\) yields better solutions as shown by the BOV here embodying the CRA-Index. Performance of \(Q\) deteriorates with increasing features. In contrast, the NSGA-II finds better assignments although these are clearly not at the level of ones from \(Q^+\).

Runtime As observed before, the GA operates fast for short solution vectors but its runtime grows with increasing model size and more extensive MT sequences. The \(Q\) on average takes roughly two times as long as NSGA-II to instrument the reassignment steps for the CRA-9 instance. It is noteworthy that, in contrast to the genetic operators in the GA, the execution of \(Q^+\) and \(Q\) is independent of the sequence length of the transformation chains and therefore becomes faster than the GA for increasing model size and thus transformation length.

Effect size and significance Result differences are large to \(Q^+\), favoring it over the other algorithms, whereas no difference can be established between \(Q\) and NSGA-II. All tests prove significance, where \(Q\) outperforms NSGA-II on smaller-sized models (\(p < .000\) for CRA-9 and CRA-18, respectively), and vice versa, NSGA-II is preferable on larger instances (\(p < .000\) for CRA-35 and CRA-80, respectively)

HV Both learning algorithms very well learn to instrument the refactoring operators in the right order. In fact, all solutions along the Pareto front are found by all algorithms (Fig. 14a and b). This is even with reducing the FEs per execution to 1,000. While \(Q^+\) takes the edge in average performance and turns out more robust concerning solution set quality (\(\sigma = .0\) and \(\sigma = .003\)), NSGA-II shows slightly less effectiveness and higher deviations between runs.

Bild vergrößern

Runtime As before, the GA is faster than the learning algorithms with \(Q\) taking the longest. In the case of several different refactoring steps, the enhanced exploration in \(Q^+\) leads to much more increased execution times than random selection in \(Q\). This originates from the problem nature in connection with the three employed MT rules for refactoring. Thereby, often only a small number of specific changes can be carried out on the current model in terms of matching rule applications. However, the local search always searches for a certain number of rule applications including all rules, which often leads to unsuccessful and therefore lengthy matching attempts for a rule application on the model in the transformation engine.

Effect size and significance RL algorithms here show medium to very large differences to NSGA-II regarding performance with \(Q^+\) taking the edge overall. Significance is evident in all pairwise comparisons except for NSGA-II and \(Q\) on instance Ref-2 (\(p=.115\)).

In addition to the transformation length, the results involve more than one domain-specific objective. Empirical results are reported in Tables 5 and 6.

HV  For the smaller models (CRA-9 and (CRA-18), \(PQ\)-\(PO\) and \(Q_{Chebyshev}\) yield the best set approximations, respectively, yet do only marginally differ considering variations and the other learning-based algorithms. As seen earlier, RL approximations are highly concentrated for shorter transformation sequences, as can also be observed in Fig. 15. The GA outperforms all multi-objective RL variants on the larger models but is subject to higher variance. However, the RL variants visibly deteriorate as the search space grows further with increasing model size.

Runtime The runtime turns out similar to what we observed for single-objective RL and NSGA-II. Larger models, for which we permit longer MT sequences, lead to increased runtimes for the GA but not to the same extent for the RL algorithms. Thus, the difference in execution time of RL against NSGA-II diminishes the more feature assignments a solution may contain.

Effect size and significance No notable performance differences are observable with the aggregated statistic, however, some are significant when comparing instance by instance. NSGA-II is outperformed on small instances (\(p < .000\) for CRA-9 and CRA-18, respectively, against all RL algorithms) but excels for larger ones (\(p < .000\) for CRA-35 and CRA-80, respectively, against all RL algorithms). \(Q_{Chebyshev}\) appears superior to all other RL algorithms for CRA-35 (\(p < .008 \)) but yields no significant advantage for CRA-80 (\(p > .344\)).

HV For the smallest instance, all learning-based algorithms find all solutions of the Pareto frontier consistently, which remarkably is only not the case for the GA (\(\sigma = .012\)). For the mid-sized model, the RL algorithms perform equally well considering deviations whereas trade-offs found by NSGA-II are inferior by a margin. This originates from the RL algorithms naturally engaging with a solution of each size continually. Hence we can observe these solutions close to the origin in Fig. 16, whereas the GA is not represented in this region. Given the variation observed in the largest model, no algorithm has a visible advantage in this task. Similarly, no differences in performance between the RL algorithms can be detected when the variations in all three cases are taken into account.

Runtime  NSGA-II executes substantially faster, taking roughly between a third and a half of the time compared to the RL algorithms dependent on the model size. This advantage decreases for larger instances along with larger MT sequences, whereas RL approaches are very close in this respect.

Bild vergrößern

Bild vergrößern

Effect size and significance  All RL algorithms demonstrate a very large difference as indicated by the test statistic, favoring them over NSGA-II. Differences between RL algorithms range from medium to very large differences with no clear winner. Notably, NSGA-II still performs significantly better on instance CRP-3S8 against \(PQ\)-\(HV\) (\(p = .008\)), however, is outperformed on instances CRP-5S20 and CRP-10S40 (\(p < .000\), against all RL algorithms.

The results from various case studies, which we conducted with an available prototype that we extended for a palette of RL algorithms, advocate for the feasibility of RL for in-place MTs. The motivation to aim for high-scoring outcomes resulting from interaction in a limited time horizon aligns well with in-place MTs, where we look for models that express high problem-specific fitness with a preferably small number of changes. The implemented algorithms offer general applicability but, as became evident from our case studies, face limits when the search space is too large for sufficient exploration. A critical factor emerges in our tabular methods as all carried-out MTs will be stored, which imposes a storage condition. Naturally, this also holds true for the multi-objective implementations. The rule applications are kept in memory at runtime to recognize previously carried out MTs and reconstruct transformed models at any given time.

An alternative strategy for retaining MTs encoded in a table-like structure involves acquiring and retaining information from past transformations by learning a parametric function. Consequently, storing explicit transformations becomes obsolete as the function is henceforth consulted for decision-making on the basis of the current (encoded) model. However, adjusting the parameters of this function requires a processable encoding for both the model and the rule applications.

For single-objective RL, the resulting models express fitness values for a similar or better approximation of the Pareto front in most cases, provided that an extensive exploration phase is granted. Measured by HV and BOV, our \(Q^+\) variant mostly finds the highest quality models. The plain Q-Learning approach (\(Q\)) exhibits limitations as the search space grows with increasing model sizes and longer transformation sequences are permitted with greater \(TL_{max}\). A significant factor in executing a randomly applicable rule in \(Q\) is that it can influence the subsequent options in the current learning episode. Indeed, executing a suboptimal MT at the beginning of an episode may enter a region in the solution space that is detrimental to the further development of the chain. In the best case, this can be compensated or reversed in subsequently selected MTs. At worst, the negative effect propagates into subsequent decisions, impeding the transition to better regions until the reset to the initial state is carried out at the end of the misguided sequence. On the other hand, \(Q\) suits whenever the consideration of all options is crucial to recognize dependencies inherent to the domain. The CRP demonstrates this in that important steps move one container to make another accessible, yet the primary reward is issued upon the following retrieval. Therefore, evaluating all possible moves in a greedy search is ineffective. It is important to note that the CRA problem is unaffected by the particular ordering. That is, whether a feature is assigned to a class sooner or later in the MT chain does not affect the output model. In such scenarios, where the search space is enormous and the resulting model is invariant to the order in the sequence, the greedy search demonstrates good performance as it fast-tracks the agent towards good regions early in an episode. Meanwhile, the random movement with \(Q\) leads to comparatively slow improvements in such fitness landscapes, as becomes evident in particular in Fig. 11b and c, but also Fig. 13b and c. Therein, non-dominated solutions of \(Q\) deviate further from the approximation set of \(Q^+\) with increasing sequence length and solutions are far from achieving the same quality overall.

Adopting multi-objective formulations for the CRP and CRA gives ambivalent results. The set quality measured by HV draws a similar picture for the CRP as when employing the combined metric where the best results are on average produced by the multi-objective learners. Nevertheless, the inspection of the non-dominated solutions produced by NSGA-II in Fig. 15 indicates convergence to optimal values, that is the “Container” dimension in this case. For feature assignment in the CRA, likewise, the GA finds many of the extreme points which appear off-limits for RL algorithms here. This is not congruent with single-objective RL results where \(Q^+\) clearly surpasses NSGA-II, which at this point indicates substantially higher potential for the single-objective formulation of the greedy approach. Ultimately, some problems seem to be more susceptible to rigorous exploration as is realized in GAs or also \(Q^+\). This is the case where there is a large design space for the model and few restrictions regarding the applicability of the transformation rules, such as the assignment of features to classes in the CRA example. Some problems, however, require a more fine-grained procedure. This becomes evident with the CRP for the aforementioned interdependencies relevant to solving the task, hence, each subsequent step must be carefully determined and a greedy search is counterproductive if the optimal solution includes steps that appear suboptimal in the short term. In such cases, conventional Q-learning (\(Q\)) can be used more effectively.

The incremental approach in all our implementations leads to longer execution times due to continuous interchange with the transformation engine for the next step. Thereby, in each iteration the engine is tasked to suggest feasible rule applications for the current model state. GAs, in contrast, consult the engine mostly once to generate the initial population and thereafter, only for computing mutations and repair operations. For recombination, the engine is not concerned. As a result, NSGA-II outruns RL competitors in almost all cases. Nevertheless, this gap in computation time decreases substantially as models increase in size for the more complex cases. The reason lies in the evaluation of solutions during initialization and mutation, which is less efficient than generating neighbors using the Henshin engine. Eventually, each newly generated transformation sequence must be executed to produce the solution model for its evaluation in the genetic algorithm, whereas with the RL approaches only one rule application is ever added. This is further taken advantage of when generating several individual application steps at once when running \(Q^+\).

Compared solutions emerged from learning episodes using a fixed transformation sequence length (\(TL_{max}\)) as termination criterion before resetting the environment to the initial model. This was to establish equal terms when comparing performances between RL algorithms and NSGA-II, which is naturally bound to a fixed size for solutions. Practically, there is no such requirement for a constant termination criterion. In fact, a dedicated strategy could leave it to the agent to determine valuable chain lengths and further explore models after transformations deemed particularly profitable. For instance, one could define a quality-based criterion to stop further model evaluation if a certain amount of recent transformations showed no improvements. Such a strategy may avoid the problematic scenario where one action hampers the progress for the whole remaining episode.

Construct validity questions the legitimacy of the chosen experiment setup in contrast to the stated research objective. In this regard, we evaluated the optimization capability with the BOV obtained with each algorithm and used the well-established HV indicator to assess trade-offs within produced solution sets. Admittedly, we only compared the final models produced in each case and, therefore, are not able to pinpoint the superiority observed in some of the results from learned agents. Indeed, we demonstrated the effect of an enhanced exploration phase with the proposed \(Q^+\). Nevertheless, a thorough analysis of the execution phases in which algorithms show most of their progress may justify a study on its own. The NSGA-II represents a well-established GA that was demonstrated to perform best of all tested algorithms in most cases within the MOMoT approach [3], hence why we considered it an appropriate baseline for our experiments. Moreover, the episode length for the RL algorithms has been fixed at the maximum transformation length, thus ensuring comparability to the transformation solutions found by the GA. However, it should be noted that other criteria could prove more conducive to performance.

Internal validity can be threatened by our case study selection, the choices for variables in the experimental setup, and stochastic elements in algorithms. We have demonstrated RL algorithms to tackle four problem formulations that are not amenable to exhaustive methods due to large or even infinite search spaces. The formulations contain either two or three objectives, where minimizing the transformation length is implicitly considered in RL algorithms. To compare the solution sets, we used HV, which is considered the most important indicator for comprehensive quality evaluation for studies like ours [23]. Our configurations ensure a balance between exploration and exploitation in terms of a common \(\epsilon \)-greedy strategy for RL algorithms. Furthermore, we allowed all tested algorithms the same number of FEs for each execution, although other quality-oriented termination criteria could have been beneficial for the learning agent, e.g., by conducting premature resets in poorly evolving episodes. Reproducibility is threatened as the Henshin Engine is set to propose applicable rules in a non-deterministic way⁴. That is, the engine randomly returns one rule considering all applicable rules for a model. This is essential for us to be able to generate a population of random rule sequences during initialization in the GA implementation, and further to enable exploration in RL algorithms. However, due to the low variance in our experiments with 30 repetitions, we do not consider it an issue.

The RL algorithms are integrated in the MOMoT framework which uses Henshin as MT language. The latter supports constructs in the transformation that include non-determinism whereas none are present in the case studies discussed in the present work. However, the implemented RL algorithms are generally feasible for application in stochastic environments. The agents in RL obtain and store a new state through exchange with the environment that receives applicable rules from the engine as a response to a transformable model. Therefore, environment and RL algorithms would need to be adapted to accommodate other model representations and MT languages. Moreover, the solution representation of MOMoT builds on the APIs of the MOEA framework. Although we used several cases of varying complexity levels, further experiments are required to identify strengths and weaknesses before adding RL to MDE toolboxes.