RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2018, том 25, номер 6, страницы 711–725 (Mi mais658)  

Модели процессов

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

А. А. Каленковаa, Д. А. Колесниковb

a Национальный исследовательский университет «Высшая школа экономики», лаборатория ПОИС, ул. Мясницкая, 20, г. Москва, 101000 Россия
b Национальный исследовательский университет «Высшая школа экономики», факультет компьютерных наук ул. Мясницкая, 20, г. Москва, 101000 Россия

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

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

Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации MK-4188.2018.9
Исследование выполнено при поддержке Гранта Президента РФ для молодых российских ученых — кандидатов наук MK-4188.2018.9.


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

Полный текст: PDF файл (2010 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 004.023
Поступила в редакцию: 01.09.2018
Исправленный вариант: 10.11.2018

Образец цитирования: А. А. Каленкова, Д. А. Колесников, “Применение генетического алгоритма для нахождения редакционного расстояния между моделями процессов”, Модел. и анализ информ. систем, 25:6 (2018), 711–725

Цитирование в формате AMSBIB
\RBibitem{KalKol18}
\by А.~А.~Каленкова, Д.~А.~Колесников
\paper Применение генетического алгоритма для~нахождения редакционного расстояния между~моделями процессов
\jour Модел. и анализ информ. систем
\yr 2018
\vol 25
\issue 6
\pages 711--725
\mathnet{http://mi.mathnet.ru/mais658}
\crossref{https://doi.org/10.18255/1818-1015-711-725}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais658
  • http://mi.mathnet.ru/rus/mais/v25/i6/p711

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:24
    Полный текст:8
    Литература:4

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019