Using genetic algorithms to mine process models : representation, operators and results

This paper presents a new process representation, a fitness measure and the genetic operators used in a genetic algorithm to mine process models, and shows that genetic algorithms can be used to discover Petri net models from event logs.

Abstract

The topic of process mining has attracted the attention of both researchers and tool vendors in the Business Process Management (BPM) space. The goal of process mining is to discover process models from event logs, i.e., events logged by some information system are used to extract information about activities and their causal relations. Several algorithms have been proposed for process mining. Many of these algorithms cannot deal with concurrency. Other typical problems are the presence of duplicate activities, hidden activities, non-free-choice constructs, etc. In addition, real-life logs contain noise (e.g., exceptions or incorrectly logged events) and are typically incomplete (i.e., the event logs contain only a fragment of all possible behaviors). To tackle these problems we propose a completely new approach based on genetic algorithms. In this paper, we present a new process representation, a fitness measure and the genetic operators used in a genetic algorithm to mine process models. Our focus is on the use of the genetic algorithm for mining noisy event logs. Additionally, in the appendix we elaborate on the relation between Petri nets and this representation and show that genetic algorithms can be used to discover Petri net models from event logs.