Application of a Genetic Algorithm for Finding Edit Distances between Process Models

Abstract

Finding graph edit distances (determining the similarity of graph models) is an important task in various areas of computer science, such as image analysis, machine learning, and chemoinformatics. In recent years, due to the development of process mining techniques, it has become necessary to adapt the existing graph matching methods to be applied to the analysis of process models (annotated graphs) discovered from event logs of information systems. In particular, methods for finding the minimum graph edit distance can be used to reveal patterns (subprocesses) and to compare discovered process models. As was shown experimentally and theoretically substantiated, exact methods for finding the minimum edit distance between the discovered process models (and graphs in the general case) have a great time complexity and can be applied only to small-sized process models. In this paper, we estimate the accuracy and time performance characteristics of a genetic algorithm applied to find distances between process models discovered from the event logs. In particular, we find distances between BPMN (Business Process Model and Notation) models discovered from the event logs by using different synthesis algorithms. It is shown that the genetic algorithm proposed in the paper allows us to significantly reduce the computation time and produces results close to the optimal solutions (the minimum edit distances).