Дискретно-стохастические модели (Р-схемы)

2. Непрерывно-стохастические модели (Q-схемы)

В практике моделирования объектов часто приходится решать задачи, связанные с формализованным описанием и анализом причинно-следственных связей в сложных системах, где одновременно параллельно протекает несколько процессов. Самым распространенным в настоящее время формализмом, описывающим структуру и взаимодействие параллельных систем и процессов, являются сети Петри (англ. Petri Nets), предложенные К. Петри.

Теория сетей Петри развивается в нескольких направлениях:

3. различные приложения (параллельное программирование, дискретные динамические системы и т. д.).

Формально сеть Петри (N-схема) задается четверкой вида

где В — конечное множество символов, называемых позициями

D — конечное множество символов, называемых переходами,

;

I — входная функция (прямая функция инцидентности)

;

О — выходная функция (обратная функция инцидентности),

Таким образом, входная функция I отображает переход d_j в множество входных позиций

, а выходная функция О отображает переход d_j в множество выходных позиций

. Для каждого перехода

можно определить множество входных позиций перехода I(d_j) и выходных позиций перехода О(d_j) как

Аналогично, для каждого перехода

вводятся определения множества входных переходов позиции I(b_i) и множества выходных переходов позиции O(b_i):

Графически N -схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов (рис. 1).

Как видно из этого рисунка, граф N-схемы имеет два типа узлов: позиции и переходы, изображаемые 0 и 1 соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой.

Приведенное представление N-схемы может использоваться только для отражения статики моделируемой системы (взаимосвязи событий и условий), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки (разметки)

Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин-позиций соответствующего числа точек (когда количество точек велико, ставят цифры).

Маркированная (размеченная) N-схема может быть описана в виде пятерки

и является совокупностью сети Петри и маркировки М.

Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как

. Смена разметок происходит в результате срабатывания одного из переходов

сети. Необходимым условием срабатывания перехода d_j является

, где

, - разметка позиции b_i. Переход d_j для которого выполняется указанное условие, определяется как находящийся в состоянии готовности к срабатыванию или как возбужденный переход.

Срабатывание перехода изменяет разметку сети М(b) = (М(b₁), М(b₂),..., M(b_n))² на разметку М¢(b) по следующему правилу:

т. е. переход d_j изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций.

Рис. 2. Пример функционирования размеченной N-схемы

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

Типовые N-схемы на основе обычных размеченных сетей Петри пригодны для описания в моделируемой системе S событий произвольной длительности. В этом случае модель, построенная с использованием таких N-схем, отражает только порядок наступления событий в исследуемой системе S. Для отражения временных параметров процесса функционирования моделируемой системы S на базе N-схем используется расширение аппарата сетей Петри: временные сети, E -сети.

5. основные требования, предъявляемые к модели

6. Концептуальные модели систем и их формализация

7. Алгоритмизация моделей систем и их машинная реализация

8. Получение и интерпретация результатов моделирования систем

2. Непрерывно-стохастические модели (Q-схемы)

Дискретно-стохастические модели (Р-схемы)

при дискретно-стохастическом подходе к формализации процесса функционирования системы S подход остается аналогичный рассмотренному конечному автомату, то влияние фактора стохастичности можно проследить разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах.

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

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

множество G, элементами которого являются всевозможные пары

, где х_i и z_s —-элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции j и y, то с их помощью осуществляются отображения

, то говорят, что

определяет автомат детерминированного типа.

Введем в рассмотрение более общую математическую схему. Пусть Ф — множество всевозможных пар вида

, где y_j — элемент выходного подмножества Y. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида:

При этом

, где b_kj — вероятности перехода автомата в состояние z_k и появления на выходе сигнала y_j если он был в состоянии z_s и на его вход в этот момент времени поступил сигнал x_i. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов

называется вероятностным автоматом (Р - автоматом).

Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, что можно представить соответственно в виде:

При этом

где z_k и q_k — вероятности перехода Р-автомата в состояние z_k и появления выходного сигнала у_k при условии, что Р-автомат находился в состоянии z_s и на его вход поступил входной сигнал х_i.

Если для всех k и j имеет место соотношение

, то такой Р-автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.

определение выходного сигнала Р-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы. Другими словами, пусть каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:

Здесь

, где s_i — вероятность появления выходного сигнала y_i при условии, что Р-автомат находился в состоянии z_k.

для всех k и i имеет место соотношение

, то такой Р-автомат называется вероятностным автоматом Мура.

Понятие Р-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом, задаваемым

. Частным случаем Р-автомата, задаваемого как

являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал Р-автомата определяется детерминированно, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.

Y-детерминированный Р-автомат задаётся таблицей переходов и таблицей выходов. Первую из этих таблиц можно представить в виде квадратной матрицы размерности К´К, которую будем называть матрицей переходных вероятностей или просто матрицей переходов Р-автомата. В общем случае такая матрица переходов имеет вид

Для описания У-детерминированного Р-автомата необходимо задать начальное распределение вероятностей вида

Здесь d_k — вероятность того, что в начале работы Р-автомат находится в состоянии k. При этом

У-детерминированный Р-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги — возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода р_ij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями рис 1.

Р-автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е.

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

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: