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


 

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

45285. Частотный план сетей UMTS/LTE и его развитие в LTE Advanced. Архитектура сети LTE. Назначение подсистем и узлов. Отличия от сети UMTS. Протоколы интерфейса S1 сети LTE 977 KB
  Для внедрения решений ВКР-07 по системам мобильной связи семейства IMT (LTE) рабочие группы Партнерского проекта 3GPP и ETSI определили в технических спецификациях 17 полос радиочастот для режима FDD и 8 полос для режима TDD (табл. 2.7) 124]. Кроме того, эти диапазоны также входят в число диапазонов, определенных в рекомендациях МСЭ для развития сетей мобильного беспроводного доступа третьего и четвертого поколени2
45286. Эталонная архитектура базовой сети LTE. Функции базовой сети SAE. Взаимодействие сети LTE с другими сетями. Физические, транспортные и логические, каналы сети E-UTRAN вниз и вверх 12.45 MB
  Эталонная архитектура базовой сети LTE. Функции базовой сети SE. Взаимодействие сети LTE с другими сетями. Физические транспортные и логические каналы сети EUTRN вниз и вверх.
45287. Эволюция стандартов и технологий мобильной связи. Концепции технологии 4G и IMS 737.5 KB
  Технология кодового разделения каналов CDM благодаря высокой спектральной эффективности является радикальным решением дальнейшей эволюции сотовых систем связи.51 Эволюция технологий мобильной связи WCDM считается стандартом 3G в эволюционном развития GSM систем. GSM системы поддерживают скорость передачи данных не более 96 кбит с это позволяет предоставлять пользователям услуги голосовой связи и SMS.
45288. Системы мобильной связи стандарта 802.16e. Назначение, характеристики, реалии внедрения. Механизмы безопасности WiMAX 317.9 KB
  Механизмы безопасности WiMX. Мифы: цена оборудования 150200; скорость до 70 Мбит с на полосе 20 МГц; на расстоянии 510 км до 50 км; неограниченное число клиентов; клиентское оборудование будет работать с любым оборудованием WiMX. скорость PreWiMX до 48 Мбит с. Характеристики Мобильный WiMX система б пров.
45289. Три этапа планирования сетей связи. Отличия в планировании сетей GSM, WCDMA и LTE 31.83 KB
  Алгоритм частотнотерриториального планирования сети радиосвязи. Первый этап планирования заключается в подготовке электронной карты местности ЭКЧ содержащей данные описывающие рельеф местности застройку территории лесные и водные массивы и в получении надежных данных в отношении: высоты местности морфоструктруры землепользование распределения населения транспортных потоков и других факторов влияющих на плотность трафика прогноза числа абонентов требований к рабочим характеристикам для обеспечения соответствующего качества...
45290. Концепция системы показателей качества услуг сетей мобильной связи (СМС). Международная стандартизация требований к качеству услуг. Государственная система стандартизации и контроля качества в РФ 222.5 KB
  Концепция системы показателей качества услуг сетей мобильной связи СМС. Конкуренция между операторами связи на национальных и международных телекоммуникационных рынках выдвигает проблему качества услуг связи на одно аз первых мест и следовательно появляется необходимость стандартизировать требования к качеству и методам его измерения. Стандартизация систем управления качеством услуг связи необходима для контроля над качеством технологических процессов их предоставления и согласования возможностей сетей общего пользования принадлежащих...
45291. Критерии и технические показатели, применяемые в международной стандартизации качества. Критерии, параметры, индикаторы, технические и организационные показатели качества работы СМС в системе стандартизации «Связь-качество» 283.27 KB
  Критерии и технические показатели применяемые в международной стандартизации качества. Критерии параметры индикаторы технические и организационные показатели качества работы СМС в системе стандартизации Связькачество. При выборе совокупности показателей качества следует иметь в виду что выбранные услуги важны для конечного пользователя и широко применяюсь большинством сетевых операторов. Отсюда следует что показатели качества должны: оказывать основное влияние на удовлетворение потребностей абонентов в области услуг связи;...
45292. Оценка показателей качества. Методы оценки показателей качества: контрольных вызовов, анализа статистики. Расчет показателей качества: P, R, Q. Модель определения параметров качества услуг. Расчет показателей QoS: NA, SA, ST, SpQ, CCR 224.93 KB
  Оценочные испытания могут проводиться контролирующими органами лабораториями и центрами сертификации а также операторами связи. Оценочные испытания могут проводиться контролирующими органами лабораториями и центрами сертификации а также операторами связи. Контролирующими органами с целью проверки деятельности оператора и повышения качества услуг связи периодически. Проверяется соответствие значений показателей качества нормальному уровню в России устанавливается нормативными документами Министерства информационных технологий и связи РФ.
45293. Объективная оценка показателей качества передачи речи: рейтинговая модель E при планировании; интегральные оценки по отношению сигнал/шум и на основе обобщенного коэффициента 490.5 KB
  Объективная оценка показателей качества передачи речи: рейтинговая модель E при планировании; интегральные оценки по отношению сигнал шум и на основе обобщенного коэффициента. Субъективная оценка показателей качества передачи речи: статистические слушательская и абонентская. Оценка качества передачи речи При оценке качества передачи речевой информации применяются субъективные квазисубъективные либо объективные методы. В последнее время чаще используются объективные методы оценки позволяющие автоматизировать данный процесс сделать его...