DCR Event-Reachability via Genetic Algorithms

摘要

In declarative process models, a process is described as a set of rules as opposed to a set of permitted flows. Oftentimes, such rule-based notations are more concise than their flow-based cousins; however, that conciseness comes at a cost: It requires computation to work out which flows are in fact allowed by the rules of the process. In this paper, we present an algorithm to solve the Reachability problem for the declarative Condition Response (DCR) graphs notation: the problem, given a DCR graph and an activity, say "Payout reimbursement", is to find a flow allowed by the graph that ends with the execution of that task. Existing brute-force solutions to this problem are generally unhelpful already at medium-sized graphs. Here we present a genetic algorithm solving Reachability. We evaluate this algorithm on a selection of DCR graphs, both artificial and from industry, and find that the genetic algorithm with one exception outperforms the best known brute-force solution on both whether a path is found and how quickly it is found.