36218

Имитация Марковских процессов с непрерывным временем и дискретными состояниями. Планирование машинных экспериментов при имитационном моделировании

Доклад

Математика и математический анализ

Например пусть 1 – время через которое должен произойти переход в состояние Sj1 а 2 – время через которое должен произойти переход в состояние Sj2. Обозначим Т – время в течении которого будем наблюдать имитируемый процесс время прогона. Для тех дуг что i = k0 сформировать с помощью датчика случайных чисел k0 j – время ожидания перехода Sk0 Sj. Определить – время пребывания в состоянии Sk0 через какое время будет реальный переход в новое состояние.

Русский

2013-09-21

91.5 KB

11 чел.

Имитация Марковских процессов с непрерывным временем и дискретными состояниями. Планирование машинных экспериментов при имитационном моделировании

Имитация – это воспроизведение моделируемого процесса на ЭВМ.

Имитация Марковских процессов с непрерывным временем и

дискретными состояниями

В Марковских процессах с непрерывным временем и дискретными состояниями моменты смены состояния являются случайными. Также случайным является выбор каждого нового состояния. Числовыми характеристиками возможных переходов являются интенсивности ij(t). В любом состоянии Sk процесса функционируют одновременно несколько случайных потоков с интенсивностями kj(t), определяющих номер следующего состояния, в которое можно перейти из Sk. Но конкретное новое состояние определяется тем, какое из возможных событий (Sk Sj) произойдет раньше. Например, пусть 1 – время, через которое должен произойти переход в состояние Sj1, а 2 – время, через которое должен произойти переход в состояние Sj2. Если 1 < 2, то произойдет переход в состояние Sj1, в противном случае  – в Sj2. В силу ординарности потоков, не может быть 1 = 2.

Пусть Марковский процесс описан своим графом с известными весами дуг – интенсивностями ij(t). Для простоты будем считать процесс стационарным, т.е.  ij(t) = ij. Обозначим Т – время, в течении которого будем наблюдать имитируемый процесс (время прогона). Предлагается следующий алгоритм имитации.

1. Установить начальный момент времени tтек := 0.

2.  Определить номер начального состояния k0.

3. Просмотреть начальные вершины i = 1,…m дуг графа (i, j ). Для тех дуг, что i = k0, сформировать с помощью датчика случайных чисел k0, j – время ожидания перехода (Sk0 Sj).

4. Определить  – время пребывания в состоянии Sk0 (через какое время будет реальный переход в новое состояние). Найти j0 – номер j, при котором достигается минимум. Соответственно, Sj0– новое состояние.

5. Перейти в Sj0, т.е. положить k0 := j0.

6. Увеличить текущее время tтек := tтек + t(k0).

7. Если tтек < T, идти к 3.

8. Для i = 1, … n  вычислить  – вероятность нахождения процесса в состоянии Si. (Суммарное время t(i) разделить на длительность наблюдения – вероятность равна доле общего времени, приходящегося на нахождение в состоянии Si).

Замечание. В данном алгоритме время ожидания очередного перехода в новое состояние отсчитывается с момента попадания в текущее состояние. Предположим, что Марковский процесс описывает функционирование СМО и пусть в момент времени t1 система находится в состоянии Sk, которое соответствует состоянию обслуживания заявки З1. Пусть – случайная длительность обслуживания, тогда момент t2 окончания обслуживания равен t2 = t1 +. Предположим теперь, что до того, как З1 была полностью обслужена в систему в момент t3 , t1 < t3 < t2 пришла новая заявка З2. Очевидно, в этот момент система перешла в состояние Sk+1. В соответствии с алгоритмом имитации время окончания обслуживания З1 будет отсчитываться с момента последнего перехода – t3, а не с t1. Если же до конца обслуживания в момент t4 < t2 придет еще заявка, то время окончания обслуживания З1 будет отсчитываться с момента t4, и т.д. Получается, что алгоритм не корректен.

На самом деле, если время перехода из одного состояния в другое имеет показательное распределение, т.е. поток смены состояний Марковского процесса является простейшим, то алгоритм корректен. Благодаря свойству 2 простейшего потока распределение длительности ожидания очередного события не зависит от того, сколько времени это событие уже ожидается. Иначе говоря, при генерации времени ожидания конца обслуживания заявки З1 не важно определяем ли мы полное время обслуживания из состояния Sk, или остаток этого времени из состояния Sk+1. В обоих случаях рассчитанные результирующие вероятности будут одинаковы.

Планирование машинных экспериментов при имитационном

моделировании

Задачи и проблемы планирования МЭ

Def.  Машинный эксперимент (МЭ)– прогон имитационной модели исследуемой системы.

Цель МЭ – получение информации о системе для анализа ее характеристик, либо для поиска оптимального варианта ее структуры или значений параметров. Задача планирования МЭ – получение достаточного количества информации о системе при ограниченных вычислительных ресурсах.

При планировании МЭ следует учитывать ряд их особенностей, отличающих МЭ от натурных экспериментов, т.е. экспериментов над реальными объектами. Сюда относятся:

1) простота повторений условий эксперимента, а также варьирования его условий;

2) возможность управления МЭ, включая его прерывание и возобновление в любой момент;

3) возможность обеспечения большого числа реализаций МЭ.

Планирование МЭ призвано решить определенные проблемы их проведения.

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

2) Обеспечение точности и достоверности результатов моделирования. Статистическое моделирование в принципе не может дать точного значения исследуемой характеристики Е системы, а дает лишь какую-то ее оценку . Точность этой оценки в значительной мере зависит от количества N реализаций (прогонов) модели – чем больше N, тем выше точность. Однако число реализаций не может быть бесконечно большим, т.к. любая вычислительная система, на которой реализуются МЭ, имеет ограниченный ресурс. Поэтому при планировании МЭ, в частности, при определении значения N, необходимо искать разумный компромисс между требуемой точностью решения и ресурсами вычислительной системы, реализующей имитацию.

В качестве показателя точности модели используются:

- величина  – достоверность найденной оценки , она должна быть близка к 1;

- величина  – дисперсия найденной оценки , она должна быть достаточно мала.

Обе эти величины зависят от N, поэтому значение N подбирают из заданного условия, которому удовлетворяет величина достоверности или дисперсии оценки . Методы определения значения N и оценки точности модели рассмотрим далее.

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

1) Теорема Бернулли. Если проводится N независимых испытаний, в каждом из которых случайное событие А происходит с вероятностью р, то относительная частота появления событии А при N   сходится по вероятности к р. То есть , где m(A) – число наступлений события А.

2) Центральная предельная теорема. Если  – независимые, одинаково распределенные случайные величины с математическим ожиданием а и дисперсией 2, то распределение суммы  при N   неограниченно приближается к нормальному распределению с матожиданием Na и дисперсией N2:

= Ф() – Ф(),

где Ф(х) – функция Лапласа (функция нормального распределения, интеграл вероятности).

3) Теорема Муавра-Лапласа. Если проводится N независимых испытаний, в каждом из которых случайное событие А происходит с вероятностью р, то распределение величины m(A) при N   неограниченно приближается к нормальному распределению с матожиданием Np и дисперсией Np(1–p). То есть

= Ф() – Ф().            (4.5)

Пример использования предельных теорем. Пусть цель МЭ – получение оценки  вероятности наступления случайного события А. Согласно теореме Бернулли, оценкой является величина , т.к. она может при больших N быть сколь угодно близкой к истинному значению р. В качестве меры точности данной оценки примем достоверность, а именно, потребуем, чтобы выполнялось условие = Q , т.е. чтобы вероятность малого различия между р и  (не более заданного ) была равна заданному числу Q. Или в соответствие с принятым выражением ,

= Q.                                             (4.6)

Для оценки данной вероятности воспользуемся теоремой Муавра-Лапласа. При достаточно большом N можно положить в (4.5)

=

= .

Для выполнения требуемого условия (4.6) положим . Отсюда в силу (4.5) и (4.6) имеем уравнение

Q = ,

из которого надо найти N.

Обозначим  – двухсторонняя Q-квантиль нормального распределения. Тогда получим формулу

.                                                (4.7)

Пояснение. По определению функция распределения F(t) случайной величины равна вероятности P( < t). Иными словами, зная t, можно по F(t) найти вероятность события ( < t). Квантиль же позволяет по известной вероятности найти значение t. Двухсторонняя Q-квантиль позволяет найти такое t, при котором вероятность события || < t равна заданному числу Q, т.е. найти корень уравнения  Р(|| < t) = Q.

Значение tQ можно найти либо по специальным таблицам, либо воспользовавшись qnorm – функцией MathCad, а именно, .

Недостаток полученной формулы (4.7) в том, что в ней фигурирует неизвестная величина р. Чтобы избежать этого на практике место р используют ее грубую оценку , где N1 << N. Таким образом, при определении необходимого количества МЭ надо проделать следующие шаги:

1) провести предварительные МЭ с числом повторений N11000, фиксируя в них наступление события А и подсчитывая m(A);

2)  вычислить р1;

3) подставить р1 в (7) вместо р и вычислить N.

После этого проводят основную серию МЭ с числом повторений N и находят более точную оценку .