Резюме (1137086), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Действительно, модель,16которая не может воспроизвести поведение анализируемой системы, приносит мало пользы. Поэтому и в данной работе соответствие рассматриваетсякак главный критерий. Сформулируем теперь условия исправления моделидо идеального соответствия.Определение (Исправление сети потоков работ до идеального соответствия). Пусть ∈ ℬ(* ) — журнал событий, для которого ⊆ ,а N ∈ N — сеть потоков работ такая, что fitness(, N ) < 1. ПустьN ′ = ModularRepair (, N ) — это модульная схема исправления. Будем говорить, что схема ModularRepair (L, N ) исправляет до идеального соответствия, если fitness(, N ′ ) = 1.Модульный подход исправления гарантирует, что исправленная модель будет идеально соответствовать журналу событий, если в блоке исправления используется идеальный алгоритм синтеза 5 , а в блоке декомпозицииприменяется алгоритм валидной декомпозиции.

По определению идеальныйалгоритм синтеза для любого журнала событий синтезирует идеально емусоответствующую модель процесса. Алгоритм декомпозиции называется валидным, если с его помощью можно успешно декомпозировать на фрагменты и модель, и её разметку, а также имеется известный способ композиции,позволяющий однозначным образом собрать из этих фрагментов исходнуюмодель.Теорема (Условия исправления до идеального соответствия). Модульнаясхема исправления ModularRepair (L, N ) обеспечивает идеальное соответствие, если1. split — это функция валидной декомпозиции;2.

repair — это идеальный алгоритм синтеза, то есть для любого журнала событий он синтезирует идеально соответствующую ему сетьПетри;3. compose — это функция слияния переходов, которая объединяет всепереходы с одинаковыми пометками.Доказательство этой теоремы приводится во второй части диссертации.Затем описывается алгоритм, полученный в результате использованияконкретных алгоритмов в качестве процедурных аргументов обобщённой модульной схемы.5Такие алгоритмы всегда синтезируют модели с идеальным соответствием.17Зададим значения процедурных параметров модульной схемы исправления следующим образом:∙ в качестве функции оценки eval ∈ (ℬ(* ) × N ) → [0; 1] используем алгоритм проверки соответствия, использующий выравнивания [22],∙ в качестве функции исправления repair ∈ ℬ(* ) × N ) → N используем индуктивный алгоритм синтеза [23] или алгоритм синтеза набазе решения задачи целочисленного линейного программирования [24],∙ в качестве функции декомпозиции split ∈ N → (N ) используем алгоритм максимальной декомпозиции,∙ в качестве функции композиции compose ∈ (N ) → N используемалгоритм слияния переходов с одинаковыми пометками.Такой выбор процедурных аргументов даёт алгоритм декомпозированного исправления.

В данной части показывается, что этот алгоритм удовлетворяет первому, второму и третьему условиям исправления до идеальногосоответствия.Для получения максимальной декомпозиции сети Петри в данной работе предлагается собственный алгоритм, который также описывается в части 2.SN5hSN2hsourceSN3t8SN1aat1t1c1bbt2t2c2cSN4ct3t3ddt4t4t8c3eet5t5c4fSN6ft6t6ggt7t7sinkРисунок 5: Максимальная декомпозиция модели, показанной на рисунке 3На рисунке 5 демонстрируется максимальная декомпозиция моделипроцесса, показанной на рисунке 3.

Сеть декомпозирована на шесть фрагментов: 1 , 2 , 3 , 4 , 5 и 6 . Все переходы исходной модели видимыи имеют уникальные пометки. Поэтому переходы 1 (a), 2 (b), 3 (c), 4 (d),5 (e), 6 (f), 7 (g) и 8 (h) являются граничными узлами. Внутренними являются позиции , 1 , 2 , 2 , 3 , 4 , а также . Нетрудно заметить, чтоначальная разметка тоже была разбита тривиальным образом.

Единственный маркер вместе с позицией помещается в суб-сети 1 . Ясно, что18представленные фрагменты могут быть композированы в сеть потоков работ,которая показана на рисунке 3. Для этого надо выполнить слияние переходовс одинаковыми пометками.Назовём этот метод наивной техникой модульного исправления. Нарисунке 6 показывается результат наивного исправления модели, изображённой на рисунке 3, для случая, когда журнал событий состоит всего из двухтрасс: ⟨, , , , ⟩ и ⟨, , , , ⟩.hft8asourcet1cbt2c1s3t3ec3ττts1s2t6t5c4gsinkt7ts2dt4Рисунок 6: Модель процесса, показанная на рисунке 3, исправленная с помощьюнаивного методаРезультаты применения наивного метода могут быть улучшены, таккак этот метод имеет тенденцию к построению неточных моделей.

Дело в том,что данная процедура довольно существенным образом увеличивает количество возможных вариантов исполнения модели. Во второй части диссертациисодержится подробное обсуждение причин данного снижения точности. Дляустранения данного недостатка наивного метода в диссертации предлагаетсяусовершенствованный алгоритм исправления.Его ключевая идея состоит в том, чтобы увеличить каждый из фрагментов, требующих замены, таким образом, чтобы процедура исправления незатрагивала граничные переходы увеличенных фрагментов.

На рисунке 7 показано, каким образом работает эта процедура увеличения. В данном случаек фрагменту 3 присоединяются соседние фрагменты 2 и 4 .Определим увеличение (N ) для фрагмента N как суб-сеть, получаемую путём присоединения к N всех его соседей, то есть (N ) = N ∪{︀}︀ (N ). Здесь (N ) = N | N ∈ ∧ ∩ ̸= ∅ , а , ∈ {1, 2, .

. . , }.Процедура увеличения фрагментов применяется в случаях, когда декомпозиция модели содержит более одного фрагмента с несоответствиями.Она определяется следующим образом.{︀}︀Определение (Процедура увеличения суб-сетей). Пусть = N 1 , . . . ,N n— это декомпозиция сети потоков работ , а = ∪ , где — это19W(SN3) SN5hSN2hsourceSN3t8SN1aat1t1c1bbt2t2c2cSN4ct3t3ddt4t4t8c3W(SN3)cSN1sourceaat1t1t3bc1t2c2dc3t4eet5t5c4fSN6ft6t6ggt7t7sinkSN5hht8t8eet5t5c4fSN6ft6t6ggt7t7sinkРисунок 7: Суб-сеть увеличивается за счёт присоединения соседних фрагментовмножество фрагментов сети с несоответствиями, тогда как — этомножество остальных фрагментов. Очевидно, что ∩ = ∅.

Процедураувеличения суб-сетей состоит из следующих шагов:1. Каждый фрагмент из увеличивается за счёт присоединения его со⋃︀седей: ∀N ∈ : = (N ), = (N ); здесь = —⋃︀ это множество всех увеличенных фрагментов, а = — множество всех фрагментов, которые были затронуты процедурой, где = 1, 2, .

. . , ; заметим, что фрагменты могут иметь общих соседей;2. Все фрагменты, затронутые процедурой, удаляются из исходной декомпозиции = ∖ ;3. Увеличенные фрагменты включаются в новую декомпозицию: N = ∪ .В данной диссертации показано, что процедура увеличения суб-сетейсохраняет валидность декомпозиции, а потому может быть включена в модульную схему исправления.

Этот факт сформулирован в виде следующейтеоремы из части 2.Теорема (Увеличение суб-сетей сохраняет валидность декомпозиции).{︀}︀Пусть N = N 1 , . . . ,N n ∈ (N ) — это валидная декомпозиция сети . Пусть N — это декомпозиция после увеличения суб-сетей, во время которого два фрагмента были объединены, то есть ∃, такие, что{︀}︀{︀}︀1 ≤ < ≤ и N = ∪ ∪ N ∖ , . Тогда N — это такжевалидная декомпозиция, то есть N ∈ (N ).20Доказательство данной теоремы содержится во второй части диссертации.Назовём продвинутый алгоритм, использующий процедуру увеличения суб-сетей, усовершенствованным модульным алгоритмом исправления.Модели, исправленные с его применением (см. рисунок 8), обычно более точны, когда исправляются локальные несоответствия журналу событий.dbt4as-startτt1c1ts1t2c3c2c5c8τττts2ts3ts4c4eτt5ts5c6csourcec7s-endft3t6hc9t8gsinkt7Рисунок 8: Модель процесса, исправленная с помощью усовершенствованного алгоритмаЛокальными несоответствиями будем называть такие, которые могутбыть исправлены путём изменения отношений потока в рамках одного фрагмента модели.

Для исправления нелокального несоответствия в действительности требуется «перенести» переход из одного фрагмента в другой, чтоневозможно сделать с применением методов исправления локальных несоответствий. В таких случаях наивный и усовершенствованный алгоритмыисправления справятся с получением модели, способной воспроизвести всетрассы журнала событий, но точность исправленной модели будет снижена.Два типа несоответствий графически показаны на рисунке 9.Local:...at1bp1...t2et20dp20...t21<...,a,b,,d,e,...>d...Non-local:...at1bp1...t2et20p20t21<...,a,d,bРисунок 9: Два типа несоответствий21,e,...>В данной части предлагается жадный метод исправления, также базирующийся на модульном подходе.

Этот метод может удачно исправлятьмодель и в тех случаях, когда имеют место нелокальные несоответствия.На вход данного алгоритма, как и ранее, подаются две составляющие:сеть потоков работ , требующая исправления, а также журнал событий, содержащий запись поведения системы.

Алгоритм декомпозирует модельс помощью алгоритма максимальной декомпозиции. Затем выбирается субсеть с наихудшим уровнем соответствия суб-журналу событий. Послеэтого запускается итеративная процедура. На каждом её шаге выбранная субсеть увеличивается, то есть объединяется со своими соседями = ( ),а затем этот увеличенный фрагмент заменяется моделью, синтезированнойс помощью алгоритма автоматического синтеза, переданного в процедурныйпараметр discover (L A(Nb ) ).

Затем все фрагменты композируются в промежуточную сеть ′ . Алгоритм повторяет итерации до тех пор, пока промежуточная сеть ′ не окажется идеально соответствующей нормативному журналусобытий . Когда это условие выполняется, алгоритм заканчивает работу.Модель ′ — это исправленная сеть Петри.EventLogInputInitialWorkflow netDecompositionProjectionSelectionSub-netsConformingSub-netsSub-logsNon-conformingSub-netsEvaluationSub-logs forNon-conformingSub-netsAll Sub-nets, Some Non-conformingEnlargementAll Sub-nets,ConformingConforming Sub-netsEnlargedSub-netsRepairCorrectedSub-netsCompositionEvaluationEvaluationResultOutputCorrectedWorkflow netРисунок 10: Схема исправления модели процесса для нелокального случая22Схема алгоритма изображена на рисунке 10. Светло-синим цветом выделена ключевая модификация модульной схемы исправления, которая лежит в основе жадного алгоритма.Пример работы жадного алгоритма исправления показан на рисунке 11.

Характеристики

Список файлов диссертации