Humboldt-Universität zu Berlin - Faculty of Mathematics and Natural Sciences - Search-Based Model Engineering Workshop 2018

Home-Bild-neu.jpg

Programme Overview

The workshop will follow a three-step agenda:

  • In the first part, there will be an opportunity for participants to give a short (20 minute plus 10 minutes for discussion) presentation on their research background, potential contributions to as well as questions of interest for or needs for expertise in such joint research. Junior participants (post-docs and PhD students), will have the choice of presenting a poster or giving a talk.
  • The next phase will start with a presentation of potential opportunities for funding collaborative work, followed by matchmaking and brainstorming of concrete ideas for future collaborative work.
  • Finally, we will aim to produce at least two sketches of potential future projects, including a one-page overview of the idea and key steps for post-workshop work towards a proposal.

 

Schedule

Day 1 (August 7th)
  • 11:30 - 12:00: Arrival - Tea/Coffee and Biscuits
  • 12:00 - 01:30: Session 1 (Introduction)        
    • Steffen Zschaler: Introduction
    • Steffen Zschaler: Search-Based Model Engineering with MDEOptimiser
    • Timo Kehrer: Where Search-Based Model Engineering Meets Model Management and Evolution
  • 02:00 - 03:45: Session 2 (Applications and Domain-Specific Optimisation Problems)      
    • Maike Basmer: In search of the optimal configuration: comparing model transformation rules by use of a generic matching engine                
    • Yannic Noller: Differential Program Analysis with Fuzzing and Symbolic Execution           
    • Michael Hintermüller: Generalised Nash Equilibrium Problems With Partial Differential Equations
  • 03:45 - 04:00: Break - Tea/Coffee and Biscuits
  • 04:00 - 05:30: Session 3 (Optimization Approaches)
    • Ciaran McCreesh: Modelling and Optimisation with Graphs
    • Daniel Varro: Design space exploration for graph model generation         
  • 06:30: Joint Dinner

    Royal India Covent Garden
    3 Endell Street, London WC2H 9EL

 

Day 2 (August 8th)
  • 09:00 - 09:15: Arrival - Morning Cofee Breakfast                
  • 09:15 - 11:15: Session 1 (Search Heuristics and its Specification)               
    • Stefan John: Rule-based Crossover Operators for Model-driven Optimization        
    • Daniel Strüber: Generating Efficient Mutation Operators for Search-Based Model Engineering        
    • Alexandru Burdusel: Automatic Generation of Atomic Consistency Preserving Search Operators for Search-Based Model Engineering        
  • 11:15 - 11:30: Break - Tea/Coffee and Biscuits                
  • 11:30 - 01:00: Session 2               
    • Simon Miles: Agent-Based Modelling of Normative Change in Active Travel        
    • Thomas Vogel: Fitness Landscape Analysis to improve Search Heuristics in Software Engineering  
  • 01:00 - 02:00: Lunch                
  • 02:00 - 03:45: Session 3 (Invited Talks)
    • Eleanor Salt: Funding opportunities through the King’s partnership and through EU and Germany
    • Michael Ward: Research Support
  • 03:45 - 04:00: Break - Tea/Coffee and Biscuits                
  • 04:00 - 05:30: Session 4:
    • Matchmaking and brainstorming of concrete ideas for future collaborative work
 
Day 3 (August 9th)
  • 09:00 - 09:15: Arrival - Morning Cofee Breakfast
  • 09:15 - 10:45: Breakout Groups: Elaboration of concrete ideas for future collaborative work
  • 10:45 - 11:00: Break - Tea/Coffee and Biscuits
  • 11:00 - 12:00: Get Together: Collection of ideas, future planning

 

Talks

Speaker

Title

Abstract

Ciaran McCreesh

Modelling and Optimisation with Graphs

In constraint programming, we describe problems in terms of a set of variables, each of which has a (typically finite) domain of values, together with a set of constraints that forbid certain combinations of variable-value assignments. The objective is to find a value for each variable, such that all the constraints are satisfied (or to find the best such assignment, subject to some scoring function). I'll give a very quick overview of constraint solving technology, followed by an introduction to high level modelling languages that are used to make the technology accessible to non-experts. Finally, I'll discuss my current research, which is on extending both the high- and low-level technologies to make it easier to model and solve constraint problems that involve graphs.

Yannic Noller

Differential Program Analysis with Fuzzing and Symbolic Execution

Differential program analysis means to identify the behavioral divergences between two program versions for the same input (i.e. regression testing), but also to identify divergent behavior for different inputs for the same program (e.g., worst-case complexity and side- channel analysis). Most of the existent approaches for both subproblems try to solve it with single techniques which suffer from its weaknesses like scalability issues or imprecision. In order to tackle these problems and to provide scalable solutions for real-world applications, we are performing research on how to combine search- based techniques with semantics-based techniques, namely fuzzing and symbolic execution.

Stefan John

Rule-based Crossover Operators for Model- driven Optimization

In search-based model-driven engineering (SBMDE), search-based optimization techniques are applied in a model-driven environment. One of many emerging application areas in that field is model-driven optimization (MDO), which focuses on models to express and solve optimization problems. Algorithm- wise, meta-heuristics relying on the evolutionary concepts of mutation and crossover, implemented as model transformations, have caught the most attention. While meta-models are commonly used to define the problem at hand, two different approaches have been proposed to encode solutions. In the direct encoding approach, models are used as solutions and changed directly by applying evolutionary operators. In the transformation sequence approach, in contrast, sequences of model transformations are optimized and evaluated by applying them to a common initial model.

For the latter approach, known crossover techniques for sequential encodings can be easily adapted and applied. Directly working on models, however, new rule-based approaches for crossover operators have to be investigated. To that end, “What are the building blocks of a model?”, “How can structural features of a model be exchanged in a performant and consistency preserving way?”, and “Can we generalize model crossover?” are among the questions of interest.

Daniel Strüber

Generating Efficient Mutation Operators for Search-Based Model Engineering

Search-based model engineering combines the abstraction power of models with the versatility of meta-heuristic search algorithms. While current approaches in this area use genetic algorithms with fixed mutation operators to explore the solution space, the efficiency of these operators may heavily depend on the problem at hand. In this work, we propose FitnessStudio, a technique for generating efficient problem-tailored mutation operators automatically based on a two-tier framework. The lower tier is a regular meta-heuristic search whose mutation operator is constrained by an upper-tier search using a higher- order model transformation. We implemented this framework using the Henshin transformation language and evaluated it in a benchmark case, where the generated mutation operators enabled an improvement to the state of the art in terms of result quality, without sacrificing

performance.

Steffen Zschaler

Search-Based Model Engineering with MDEOptimiser

Finding models that optimise a set of objective functions is a non-trivial task. It often requires encoding the search space in a mathematical format and using complicated tools to implement a suitable search strategy. In this talk, I will present MDEOptimiser, a model-driven tool that implements evolutionary search on top of domain-specific modelling languages. As a result, a natural encoding of an optimisation problem can be used and a standard search algorithm can be easily deployed on top of this.

Daniel Varro

Design space exploration for graph model generation

In this talk, I will provide an overview on how design space exploration (DSE) techniques and tools can be used as a core component of a model generator framework which derives graph models that are simultaneously consistent and diverse graph models without mapping them to back-end logic solvers. I will discuss key challenges as how to encode partial graphs as abstract states, how to continuously evaluate consistency constraints over them and (3) how different traditional SAT-solving techniques can be implemented as DSE exploration strategies.

Timo Kehrer

Where Search-Based Model Engineering Meets Model Management and Evolution

In this talk, I will give an overview of promising research synergies arising from integrating techniques from the field of Model Management and Evolution with Search-Based Model Engineering. Examples of this include but are not limited to the adoption of model merging for the sake of breeding new candidate solutions, the incorporation of model repair for automatically resolving inconsistencies in candidate solutions, and, on the meta-tool level, the usage of high-order transformation rule generation and inference for the sake of (semi-)automatically synthesizing mutation operators. The goal is to provide the necessary background information for fostering discussions on how to exploit these techniques while meeting the specific requirements in the field of Search-Based Model Engineering.

Thomas Vogel

Fitness Landscape Analysis to improve Search Heuristics in Software Engineering

Many software engineering tasks such as release planning, architecture and design optimization, automatic program repair, test suite generation, and test case prioritization can be formulated as optimization problems and automatically solved with search heuristics/algorithms. However, for most of these problems the characteristics of the search space and fitness landscape are usually not known, which leads to algorithm selection and configuration on a trail-and-error basis. Furthermore, search spaces can be diverse and may vary from problem instance to problem instance, which exacerbates the problem of algorithm selection and configuration. We envision that a better understanding of the different search problems will lead to better algorithm selection and parameter tuning, either at design-time or at runtime, and eventually to improvements of the state-of-the-art algorithms. In this talk, I will particularly focus on the fitness landscape analysis and improvements of search-based test suite generation for Android apps.

Simon Miles Agent-Based Modelling of Normative Change in Active Travel Agent-based modelling is a form of simulation that can be used to explore social phenomena. It is a bottom-up simulation approach, in which individuals act and interact and results of interest emerge from the complex system. In the MOTIVATE project, our model's domain focus is on people making daily decisions on modes of transport for commuting. The model is intended to investigate the effects of different interventions by local government aiming to increase healthier travel, in particular through changing what people consider normal. In this talk, I will explain how we think about specifying an agent-based model as a piece of software, and how domain knowledge translates into the MOTIVATE model specifically.
Michael Hintermüller Generalised Nash Equilibrium Problems With Partial Differential Equations A class of noncooperative Nash equilibrium problems is presented, in which the feasible set of each player is perturbed by the decisions of their competitors via a convex constraint. In addition, for every vector of decisions, a common “state” variable is given by the solution of an affine linear equation. The resulting problem is therefore a generalized Nash equilibrium problem (GNEP). The existence of an equilibrium for this problem is briefly addressed, and first-order optimality conditions are derived under a constraint qualification. An approximation scheme is proposed, which involves the solution of a parameter-dependent sequence of standard Nash equilibrium problems. An associated path-following strategy based on the Nikaido–Isoda function is then proposed. Function space-based numerics for parabolic GNEPs and a spot-market model are developed.
Maike Basmer In search of the optimal configuration: comparing model transformation rules by use of a generic matching engine The need to compare model transformation rules arises in various applications, e.g., in collaborative modelling or when testing tools that operate on such transformation rules. However, conventional diff tools such as EMF Compare struggle with their graph-like structure. As an alternative, we intend to configure a generic model matching system that employs similarity-based matching along with other matching strategies. Now the question is: how can we optimize the configuration of the matching engine - from choosing comparison functions to setting similarity thresholds - in order to achieve useful results?