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 и находят более точную оценку .


 

А также другие работы, которые могут Вас заинтересовать

14240. Календарные песни 33 KB
  Третья лекция. Тема: Календарные песни завершение темы Покос. Совпадал с Петровым днем. Первый покос разгар лета. Мужчины косили женщины сгребали сено и формировали стога. Покосные песни – лирические; их содержание: женщины жалуются на свою судьбу а мужчины на
14241. Северный календарь 25.5 KB
  Лекция пятая. Тема: Северный календарь. Северный календарь сильно ослаблен по сравнению с Западным; это от того что на Севере практически нет земледелия. На Пинеге имеется особый жанр бородные песни. Колядки. Виноградье краснозелено мое этот припев характ
14242. Песенная традиция донских казаков 25 KB
  Лекция восьмая. Тема: Песенная традиция донских казаков. Для песенного фольклора донских казаков так же как и в южнорусской культуре очень характерны такие формы бытования как плясовой хоровод свадебная игра календарные празднества насыщенные плясовыми напе
14243. Песенная традиция кубанских, уральских, оренбургских, астраханских казаков; казаков «некрасовцев» 27 KB
  Лекция девятая. Тема: Песенная традиция кубанских уральских оренбургских астраханских казаков; казаков некрасовцев. В искусстве кубанских казаков заметно проступают некоторые общие местные черты что проявляется и в особенностях песенного репертуара наличие
14244. Южно-русская музыкальная традиция 30 KB
  Лекция десятая и одиннадцатая. Тема: южнорусская музыкальная традиция. Южнорусская народная музыкальная культура представляет собой самобытнейший пласт отечественной культуры это особая песенная традиция вобравшая в себя черты иных регионов но создавшая уни...
14245. Уральские и Сибирские песенные традиции 28.5 KB
  Лекция двенадцатая. Тема: Уральские и Сибирские песенные традиции. Урал. Освоение Урала шло с Севера. Наиболее ярко уральская северная традиция проявляется в свадебном обряде. Песни данной традиции основаны на тоническом стихе. На синем было на море песн...
14246. Русские народные музыкальные инструменты 49.5 KB
  Лекция тринадцатая. Тема: русские народные музыкальные инструменты. Музыка в понимании современного крестьянства это инструментальная игра. Музыка скрипач побелорусски. Инструментальная игра мужское дело. После войны женщины тоже стали музицировать и эт
14247. Песни алтайских казаков 28 KB
  Лекция четырнадцатая. Тема: песни алтайских казаков. Алтайские казаки – это особая этническая группа длительное время имевшая специальные военные задачи по охране южных рубежей сибирских российских владений. Это отразилось на поэтическом содержании песен отра
14248. Композитор и фольклор 33.5 KB
  Лекция шестнадцатая. Тема: Композитор и фольклор. В конце 19 века Эдисон изобрел фонограф. Фонографы работали по следующему принципу: по вращающемуся звуконосителю перемещалась игларезец полученные при помощи мебранымикрофона механические колебания механичес...