Geodesic
Application of genetic algorithms for finding edit distance between process models
Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 6, pp. 711-725

Voir la notice de l'article provenant de la source Math-Net.Ru

Finding graph-edit distance (graph similarity) is an important task in many computer science areas, such as image analysis, machine learning, chemicalinformatics. Recently, with the development of process mining techniques, it became important to adapt and apply existing graph analysis methods to examine process models (annotated graphs) discovered from event data. In particular, finding graph-edit distance techniques can be used to reveal patterns (subprocesses), compare discovered process models. As it was shown experimentally and theoretically justified, exact methods for finding graph-edit distances between discovered process models (and graphs in general) are computationally expensive and can be applied to small models only. In this paper, we present and assess accuracy and performance characteristics of an inexact genetic algorithm applied to find distances between process models discovered from event logs. In particular, we find distances between BPMN (Business Process Model and Notation) models discovered from event logs by using different process discovery algorithms. We show that the genetic algorithm allows us to dramatically reduce the time of comparison and produces results which are close to the optimal solutions (minimal graph edit distances calculated by the exact search algorithm).
Keywords: minimal graph edit distance, process mining, BPMN (Business Process Model and Notation), genetic algorithm. 
@article{MAIS_2018_25_6_a7,
     author = {A. A. Kalenkova and D. A. Kolesnikov},
     title = {Application of genetic algorithms for finding edit distance between process models},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {711--725},
     publisher = {mathdoc},
     volume = {25},
     number = {6},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/}
}
TY  - JOUR
AU  - A. A. Kalenkova
AU  - D. A. Kolesnikov
TI  - Application of genetic algorithms for finding edit distance between process models
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2018
SP  - 711
EP  - 725
VL  - 25
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/
LA  - ru
ID  - MAIS_2018_25_6_a7
ER  - 
%0 Journal Article
%A A. A. Kalenkova
%A D. A. Kolesnikov
%T Application of genetic algorithms for finding edit distance between process models
%J Modelirovanie i analiz informacionnyh sistem
%D 2018
%P 711-725
%V 25
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/
%G ru
%F MAIS_2018_25_6_a7
A. A. Kalenkova; D. A. Kolesnikov. Application of genetic algorithms for finding edit distance between process models. Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 6, pp. 711-725. http://geodesic.mathdoc.fr/item/MAIS_2018_25_6_a7/