Application of the theory of petri nets in the development of simulation models of business processes based on the IDEF3 methodology

Full Text

Введение. Постановка задачи

Современные подходы к повышению быстродействия и качества работы эволюционных процедур зачастую связаны с увеличением вычислительных мощностей систем расчета для интеллектуальных моделей синтеза решений, как в генеративной искусственном интеллекте, так и в промышленном или поиску новых структур моделей, позволяющих распределить вычислительные мощности в процессе решения задач. Такого рода задачи в настоящее время решаются на уровне инженерной мысли специалистов в области машинного обучения, без привлечения специализированных кадров, обеспечивающих новизну математической составляющей используемых моделей. В этом случае решение сводится к реализации конструкции контейнеров с последующим обучением или настройке параметров функционирования выбранных для реализации моделей, как правило объединенных в специализированные библиотеки применяемых программных сред разработки, и дополнительной настройкой используемых вычислительных систем в соответствии со структурой применяемых моделей. Еще одно направление, которому уделяется большое внимание в научной среде – это модернизация существующих решений и разработка новых математических моделей, алгоритмов и подходов, которые позволят улучшить быстродействие и качество принимаемых интеллектуальными моделями решений. В данном направлении проводится большое количество исследований, которые совершенствуют математические аппараты, модели, реализуют комбинаций существующих подходов, моделей и методов. Одним из таких подходов является COGAN – подход, синтезирующий наиболее популярных эволюционных алгоритмов – искусственные нейронные сети (ИНС) [1] и генетические алгоритмы (ГА). Примером такого подхода может служить совершенствования процесса обучения искусственных нейронных сетей с использованием генетический алгоритмов и другие варианты использования.

Наиболее важным является решение задачи настройки и адаптации работы генетического алгоритма в задачах, связанных с большими данными, так как время поиска решений в такого рода задачах обычно велико и затухание эволюционной процедуры или нахождение популяции в локальном экстремуме приводит к перезапуску процесса поиска, что негативно сказывается на практике использования данного класса алгоритмов к решению подобного рода задач [6].

Современные исследования предлагают следующие подходы, которые повышают качество применения данной эволюционной процедуры:

• глубокая адаптация генетического алгоритма к решению конкретной задачи в предметной области, связанная с тщательным подбором параметров функционирования основных операторов, без возможности изменения параметров функционирования в процессе синтеза решений [7–9; 12];
• использование дополнительных операторов, позволяющих изменять параметры функционирования операторов, что позволяет оптимизировать параметры работы генетического алгоритма в процессе синтеза решений;
• использованием комбинации из двух и более генетических алгоритмов, разделенных на основную модель поиска и специализированные модели подбора параметров функционирования операторов, что также позволяет оптимизировать параметры функционирования в процессе синтеза решений и т.д.

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

Методы решения рассматриваемой проблемы

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

Таким образом требуется разработать модель искусственной нейронной сети для решения задачи распознавания состояния популяции в генетическом алгоритме и способную оказывать соответствующее влияние на параметры функционирования операторов эволюционной процедуры.

Целевая функция и примеры состояния популяции генетического алгоритма

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

В качестве функции приспособленности использовался подход, базирующийся на расчете расстояния Хэмминга (1) между эталонным выходным вектором Z_out и выходным вектором Z^K_out, полученным в результате работы синтезированной модели при подаче на вход заданного входного вектора.

${\rho }_1\left(x,y\right)=\sum _{w=1}^{W_0}\left|x_w-y_w\right|,$ (1)

Чем меньше ρ₁(Z_out, Z^K_out), тем ближе полученная в результате работы генетического алгоритма модель к требуемому свойству, при ρ₁(Z_out, Z^K_out) = 0 модель обладает заданным свойством.

В рамках данного исследования рассмотрены следующие состояния популяции [10]:

• сходимость (рис. 1, а);
• не вмешиваться в процесс поиска (рис. 1, b)
• наметилось затухание (рис. 2, a);
• затухание (рис. 2, b);
• популяции в локальном экстремуме (рис. 3, a);
• наметилась сходимость (рис. 3, b).

Рис. 1. Примеры сходимости генетического алгоритма (a) и невмешательства в процесс поиска решений (b)

Fig. 1. Examples of convergence of a genetic algorithm (a) and of non-interference in the process of finding solutions (b)

Выбор класса и разработка модели искусственных нейронных сетей для решения задачи

Выбор класса моделей искусственных нейронных сетей

В качестве основных моделей искусственных нейронных сетей, способных реализовать данный подход рассматривались ИНС с памятью, а именно RNN и LSTM. Применение данного класса сетей обусловлено тем, что в указанных примерах состояния популяции генетического алгоритма не предусмотрено отображение хронологии работы генетического алгоритма, что может существенно повлиять на решение поставленной задачи с применением данного инструментального средства. При этом целесообразно рассмотреть, как модели с памятью, так и модели с долгой краткосрочной памятью [2].

Модель искусственной нейронной сети

Модели искусственных нейронных сетей имели следующую структуру (рис. 4):

• содержит такое же количество входов, как и количество особей популяции;
• внутренний слой RNN или LSTM;
• количество выходов соответствует количеству состояний популяции генетического алгоритма.

Рис. 2. Примеры наличия предпосылок затухания в процессе поиска решений (a) и затухания в процессе поиска решений (b)

Fig. 2. Examples of the presence of prerequisites for attenuation in the process of finding solutions (a) and of fading in the process of finding solutions (b)

Для обучения моделей искусственной нейронной сети использовалась выборка из 18 000 вариантов состояния генетического алгоритма по 3000 состояний на каждую из выделенных групп. Количество особей популяции в каждой выборке – 250, что соответствовало количеству входов у моделей искусственной нейронной сети [5].

В предложенных моделях использовалось три внутренних слоя следующей размерности:

• 1 слой – 32 нейрона;
• 2 слой – 64 нейрона;
• 3 слой – 128 нейронов.

В качестве активации предложено использование ReLU. Для валидации использовалась выборка размерностью 15% от обучающей [3].

В целом оба подхода показали достаточно высокий результат в отношении распознавания состояния популяции генетического алгоритма. Но стоит отметить, что несмотря на более высокую облученность RNN, модель LSTM сохраняла устойчивость к переобучению.

В рамках обучения сравнение эффективность моделей ИНС для решения задачи распознавания состояния популяции генетического алгоритма будем использовать две метрики [4]:

• средней F1-score;
• Accuracy.

Рис. 3. Примеры нахождения популяции в локальном экстремуме (a) и предпосылок начала сходимости в процессе поиска (b)

Fig. 3. Examples of finding a population in a local extremum (a) and of the prerequisites for the onset of convergence in the process of finding solutions (b)

Такой подход позволит определить наиболее подходящую модель ИНС для решения поставленной задачи определения состояния популяции генетического алгоритма.

Рис. 4. Структура искусственной нейронной сети

Fig. 4. Structure of an artificial neural network

Результаты обучения

В ходе выполнения вычислительных экспериментов наиболее эффективной показала себя искусственная нейронная сеть RNN по соотношению с классом LSTM (табл. 1).

Таблица 1. Результаты обучения искусственной нейронной сети по распознаванию состояния популяции в генетическом алгоритме [Results of training an artificial neural network for recognizing the state of a population in a genetic algorithm]

Управление генетическим алгоритмом с помощью искусственной нейронной сети на основе математического аппарата теории сетей Петри

Задача управление генетическим алгоритмом непосредственно в процессе поиска решений с применением эволюционного подхода на основе искусственных нейронных сетей не решается только классификацией состояния популяции, а требует адаптации и интеграции полученной модели ИНС к генетическому алгоритму.

В предшествующих исследованиях прилагалось применение вложенных сетей Петри для адаптации генетического алгоритма к решению задачи структурно-параметрического синтеза больших дискретных систем с заданным поведением [13]. Именно с данной моделью ГА требуется провести интеграцию полученных моделей ИНС.

Для разработки единой модели структурно-параметрического синтеза имитационных моделей бизнес-процессов следует разработать подход для моделирования искусственных нейронных сетей с использованием математического аппарата теории сетей Петри, получившего широкое распространение при решении различного класса задач [15; 16; 18; 19]. Тогда процесс управления может быть реализован с применением специализированных переходов, совмещенных с позициями управления, позволяющими выполнять активацию переходов, моделирующих работу операторов генетического алгоритма в соответствии с требуемыми настройками (рис. 5).

В соответствии с представленным фрагментом представленной сети Петри управление может быть представлено следующим образом:

• переходы T₀, T₁ и T₂ моделируют работу операторов генетического алгоритмы в соответствии с требуемыми параметрами функционирования;
• позиция P₃ – моделирует наличие популяции в генетическом алгоритме;
• позиция P₄ – моделирует сохранение популяции после работы оператора генетического алгоритма;
• позиции P₀, P₁ и P₂ – являются позициями управления, в которые помещаются метки, активизирующие требуемый переход (Т₁, Т₂ или Т₃);
• позиции Р₅, Р₆ и Р₇ служат для приема сигнала управления от искусственной нейронной сети;
• переходы Т₃, Т₄ и Т₅ передают управление в позиции Р₀, Р₁ и Р₂, активация данных переходов возможна только после сброса предшествующих настроек работы операторов генетического алгоритма;
• позиция Р₈ используется для управления запуском перенастройки работы операторов генетического алгоритма;
• переходы Т₆, Т₇ и Т₈ активируются для сброса предшествующих настроек работы операторов генетического алгоритма.

Рис. 5. Пример работы соединения ИНС и операторов генетического алгоритма

Fig. 5. An example of the operation of the connection of ANN and genetic algorithm operators

В соответствии с предложенной моделью управление процессом поиска решений в ГА будет реализовываться следующим образом.

1. На вход ИНС подается состояние популяции (значение функции приспособленности каждой особи популяции).
2. Обученная ИНС принимает решение об изменении параметров работы ГА.
3. В позицию контроля (обозначенную на рис. 5 Р₈) передается сигнал управления, т.е. метка, которая сообщает модели, что требуется выполнить изменения в параметрах работы операторов ГА.
4. ИНС передает решение о подключении параметра функционирования оператора генетического алгоритма путем размещения метки в специализированных позициях (представлены на рис. 5 Р₅, Р₆ и Р₇).
5. В начале активируется один из следующих переходов Т₆, Т₇ или Т₈, это требуется для сброса настроек работы операторов генетического алгоритма путем очищения позиций Р₀, Р₁ или Р₂ и непосредственно самой позиции Р₈.
6. Далее срабатывает один из следующих переходов Т₃, Т₄ или Т₅ в зависимости от размещения меток от результата, принятого решений ИНС в одной из позиций Р₅, Р₆ или Р₇, также отметим, что для того, чтоб предложенная модель оставалась «правильной» сетью Петри (т.е. в один промежуток времени существует только один переход, который может сработать), а также для того, чтобы модель работала корректно, условие срабатывания представленных переходов отсутствие метки в позиции Р₈, которое моделируется ингибиторными дугами.
7. После размещения метки в одной из позиций Р₀, Р₁ или Р₂ популяция, моделируемая меткой, из позиции Р₃ активирует соответствующий переход Т₀, Т₁ или Т₂, где данные переходы моделируют работу оператора генетического алгоритма в соответствии с требуемыми параметрами (например, Т₀ – одноточечное скрещивание, Т₁ – двухточечное скрещивание, а Т₃ – многоточечное скрещивание).
8. В предложенной модели для обеспечения обработки более чем одного поколения используется обратная связь, возвращающая метку управления в исходную позицию Р₀, Р₁ или Р₂, при этом обработанная оператором генетического алгоритма популяция перемещается в позицию Р₄.

Таким образом обеспечивается связь между моделью генетического алгоритма и моделью искусственной нейронной сети класса RNN для решения задачи структурно-параметрического синтеза моделей больших дискретных систем с заданным поведением.

Выводы

В ходе выполнения научного исследования, направленного на определение класса искусственной нейронной сети, способной классифицировать состояние популяции генетического алгоритма был проведен ряд вычислительных экспериментов, которые показали, что наиболее подходящим классом для решения данной задачи является класс нейронных сетей с памятью, а точнее класс RNN. Данный класс ИНС позволяет классифицировать состояние популяции с более чем 95% случаев, что является хорошим показателем и позволит влиять на состояние популяции в генетическом алгоритме.

Решение задачи структурно-параметрического синтеза моделей больших дискретных систем с помощью объединенного подхода на основе искусственных нейронных сетей и генетического алгоритма предлагается выполнять в рамках одного математического аппарата – теории сетей Петри. В данной работе предложена модель объединения двух эволюционных процедур с использованием управляющих сигналов. Данный подход выполнен с использованием классических инструментариев теории сетей Петри с дополнением ингибиторных дуг, что позволяет реализовать «правильные» модели сетей Петри, что является важным при разработке больших моделей с применением данного инструмента.

Заключение

Комбинация двух эволюционных алгоритмов, которая рассматривается в COGAN подходе является перспективным направлением, объединение данных алгоритмов одним математическим аппаратом позволяет упростить работу моделей и повысить быстродействие путем применения распределенных вычислений не только с использованием облачных сервисов, специализированных GRID систем, но и использовать вычисления на основе технологии GPGPU, на основе которого строятся высокопроизводительные системы. Применение сетей Петри позволяет упростить реализацию многопоточности вычислений, так как уменьшает количество разветвлений, которые являются «узким» местом при использовании специализированных графических вычислителей, и сводит вычислительный процесс к работе с матрицами, что хорошо распараллеливается на множество вычислителей графических карт и вычисляется ими с большой скоростью. Кроме этого, следует отметить, что количество расширений в теории сетей Петри позволяет выполнить моделирование не только дискретных, но и непрерывных процессов, что также является актуальным. Существуют различные подходы к моделированию ИНС с применением сетей Петри, например, в работе [11] приведено использование информационных сетей Петри к решению задачи моделирования искусственной нейронной сети Элмана, а в работе [17; 20] предложен подход, который моделирует веса персептрона с использованием специализированных весов меток. В рамках дальнейшего исследования целесообразно рассмотреть разные классы сетей Петри, и определить какой класс позволит оптимизировать время работы и обучения моделей на основе данного математического аппарата.

Использование искусственных нейронных сетей с памятью для классификации состояния популяции генетического алгоритма в процессе работы является перспективным направление, так как позволит адаптироваться ГА к процессу поиска без остановки эволюционной процедуры и будет проводить тонкую настройку работы операторов, что повысит не только качество находимых решений, но и увеличит вероятность сходимости, и уменьшит время поиска.

About the authors

David А. Petrosov

Author for correspondence.
Email: dapetrosov@fa.ru
ORCID iD: 0000-0002-8214-052X
SPIN-code: 2574-6798

Cand. Sci. (Eng.), Associate Professor, Head, Department of Information Technologies

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Fig. 1. Examples of convergence of a genetic algorithm (a) and of non-interference in the process of finding solutions (b)

Download (719KB)

Indexing metadata

3. Fig. 2. Examples of the presence of prerequisites for attenuation in the process of finding solutions (a) and of fading in the process of finding solutions (b)

Download (457KB)

Indexing metadata

4. Fig. 3. Examples of finding a population in a local extremum (a) and of the prerequisites for the onset of convergence in the process of finding solutions (b)

Download (750KB)

Indexing metadata

5. Fig. 4. Structure of an artificial neural network

Download (250KB)

Indexing metadata

6. Fig. 5. An example of the operation of the connection of ANN and genetic algorithm operators

Download (606KB)

Indexing metadata