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


https://doi.org/10.18255/1818-1015-2018-6-711-725

Полный текст:


Аннотация

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

Об авторах

Анна Алексеевна Каленкова
Национальный исследовательский университет «Высшая школа экономики»
Россия

ст. науч. сотр., лаборатория ПОИС

ул. Мясницкая, 20, г. Москва, 101000



Данил Александрович Колесников
Национальный исследовательский университет «Высшая школа экономики»
Россия

студент, факультет компьютерных наук

ул. Мясницкая, 20, г. Москва, 101000



Список литературы

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 с.;


Дополнительные файлы

Для цитирования: Каленкова А.А., Колесников Д.А. Применение генетического алгоритма для нахождения редакционного расстояния между моделями процессов. Моделирование и анализ информационных систем. 2018;25(6):711-725. https://doi.org/10.18255/1818-1015-2018-6-711-725

For citation: Kalenkova A.A., Kolesnikov D.A. Application of Genetic Algorithms for Finding Edit Distance between Process Models. Modeling and Analysis of Information Systems. 2018;25(6):711-725. (In Russ.) https://doi.org/10.18255/1818-1015-2018-6-711-725

Просмотров: 148

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)