Применение генетического алгоритма для нахождения редакционного расстояния между моделями процессов

Поиск редакционного расстояния между графовыми моделями (определение схожести графовых моделей) является важной задачей в различных областях компьютерных наук, таких как анализ изображений, машинное обучение, химическая информатика. В последнее время, в связи с развитием методов извлечения и анализа процессов, появилась необходимость в адаптации существующих методов сравнения графовых моделей для анализа моделей процессов (аннотированных графов), извлекаемых из логов событий информационных систем. Методы нахождения минимального редакционного расстояния между графами могут быть использованы для обнаружения шаблонов (подпроцессов), а также для сравнения извлекаемых моделей процессов. Как было показано экспериментально и теоретически обосновано, точные методы нахождения минимального редакционного расстояния между извлекаемыми моделями процессов (и графами в общем случае) имеют большую временную сложность и могут быть применены лишь к небольшим моделям процессов. В этой статье мы оцениваем точность и временные характеристики генетического алгоритма, применяемого для нахождения расстояний между моделями процессов, извлекаемых из логов событий. В частности мы находим расстояния между BPMN (Business Process Model and Notation) моделями, извлекаемыми из логов событий с помощью различных алгоритмов синтеза. В этой работе показано, что представленный генетический алгоритм позволяет в значительной степени уменьшить время вычислений, при этом показывая результаты, близкие к оптимальным (минимальным редакционным расстояниям).

минимальное редакционное расстояние между графами, извлечение и анализ процессов, BPMN (Business Process Model and Notation), генетический алгоритм

1. Van der Aalst W.M.P., Process Mining — Data Science in Action, Second Edition, Springer, 2016.

2. Van der Aalst W. M. P., Weijters T., Maruster L., “Workflow Mining: Discovering Process Models from Event Logs”, IEEE Transactions on Knowledge and Data Engineering, 16:9 (2004), 1128–1142.

3. Leemans S. J. J., Fahland D., van der Aalst W. M. P., “Discovering Block-Structured Process Models from Incomplete Event Logs”, Application and Theory of Petri Nets and Concurrency, Lecture Notes in Computer Science, 8489, Springer, 2014, 91–110.

4. Kalenkova A.A., Ageev A.A., Lomazova I.A., van der Aalst W.M.P., “E-Government Services: Comparing Real and Expected User Behavior”, Business Process Management Workshops, Springer International Publishing, 2018, 484–496.

5. Garey M. R., Johnson D. S., Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1990, ISBN: 0716710455.

6. Ivanov S. Y., Kalenkova A. A., van der Aalst W. M. P., “BPMNDiffViz: A Tool for BPMN Models Comparison”, Proceedings of the BPM Demo Session 2015 Co-located with the 13th International Conference on Business Process Management (BPM 2015) (Innsbruck, Austria, September 2, 2015), 2015, 35–39.

7. Hart P.E, Nilsson N.J, Raphael B., “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 4:2 (1968), 100–107.

8. Business Process Model and Notation (BPMN), Object Management Group, formal/2013-12-09, 2013.

9. Cross A. D. J., Wilson R. C., Hancock E. R., “Inexact Graph Matching Using Genetic Search”, Pattern Recognition, 30:6 (1997), 953 – 970.

10. Riesen K., Fischer A., Bunke H., “Improving Approximate Graph Edit Distance Using Genetic Algorithms”, Structural, Syntactic, and Statistical Pattern Recognition, Springer Berlin Heidelberg, 2014, 63–72.

11. Kalenkova A. A., van der Aalst W. M. P., Lomazova I. A., Rubin V. A., “Process Mining Using BPMN: Relating Event Logs and Process Models”, Software & Systems Modeling, 16:4 (2017), 1019–1048.

12. Levenshtein V. I., “Binary Codes Capable of Correcting Deletions, Insertions and Reversals”, Soviet Physics Doklady, 10 (1966), 707.

13. Гладков Л.А., Курейчик В.В, Курейчик В.М., Генетические алгоритмы, Физматлит, М., 2010, 368 с.;