close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Раздел 2.
Компьютерное моделирование и
оптимизация в инфокоммуникационных
системах и сетях
Лекция 3. Статистическое моделирование
на ЭВМ
Статистическое моделирование на ЭВМ
Компьютерное моделирование – деятельность по
разработке программных моделей систем, выполнение
этих программ на компьютере и анализ результатов по
исследованию поведения моделей
Области компьютерного моделирования:

имитационное моделирование


GPSS, VisSim, AnyLogic, DyMoLa, Dynast, Multisim,
MBTY, Simulink
статистическое моделирование

метод решения вероятностных и детерминированных
задач, основанный на эффективном использовании
случайных чисел и законов теории вероятностей
Организация статистического моделирования
Последовательность
случайных чисел
Исследуемая модель
Преобразованная
последовательность
случайных величин
(выборка)
Организация статистического моделирования

При имитационном моделировании стохастических
систем имитируются:




случайное событие с заданными вероятностями,
случайные величины с заданными
распределениями,
случайные процессы с заданными характеристиками
(математическое ожидание, дисперсия,
корреляционная функция).
Для имитации случайной величины с заданным
распределением нужно иметь генератор (датчик)
случайных чисел (ДСЧ), генерирующий числа с
заданным законом распределения.
Организация статистического моделирования
Генерирование случайных чисел на ЭВМ с заданным
законом распределения:

Получают последовательность равномерно
распределенных на интервале [0, 1]
псевдослучайных чисел,

Из равномерно распределенной
последовательности получают последовательность
псевдослучайных чисел с заданным законом
распределения в заданном интервале.
Генерирование базового распределения
Типы датчиков случайных чисел

Табличные


Физические


просто таблица случайных чисел
специальное радиоэлектронное устройство,
содержащее источник электронного шума
Программные

числа получают с помощью некоторой рекуррентной
формулы, где каждое следующее значение
образуется из предыдущего предыдущих путем
применения некоторого алгоритма
Генерирование базового распределения
Метод середины квадрата

произвольное число, меньшее 1 возводят в квадрат,

отбрасывают цифры с обоих концов,

оставшуюся часть используют как случайное число.

процесс повторяют.
Пример
x0  0,2601
x02  0,04 2477 21
x1  0,2477
x12  0,061355 29
x2  0,1355
x22  0,018360 25
Генерирование базового распределения
Мультипликативный конгруэнтный метод


расчет по формуле: xi 1  (axi ) mod m,

где mod – операция получения остатка от деления;

a и c – задаваемые целые числа;

x0 – задается в начале расчета алгоритма.
В результате случайное число:
xi
чi 
m
Проверка качества датчика случайных чисел
Основные требования, предъявляемые к ДСЧ:

Равномерность распределения псевдослучайных
чисел.

Независимость чисел.
Проверка равномерности распределения

Дисперсия оценки вероятности события при n
опытах и биномиальной схеме испытаний
P  1  P 
D Pˆ 
n


В действительности оценка может отличаться от
истинного значения на  3

Если оценка входит в интервал:
 
1

ˆ
ˆ
P    3 Pi 
m

то нет основания отвергать гипотезу о равномерности
Проверка независимости чисел

Автокорреляционная функция отражает корреляцию
между элементами последовательности,
расположенными на расстоянии s (s = 0,1,2,...).

Корреляционная функция К(s) идеальной
псевдослучайной последовательности должна


равняться D[r] при s = 0
и нулю при s > 0, где r – случайная величина,
значениями которой являются числа, генерируемые
ДСЧ,
ns
ns
n
1
1
1
Kˆ ( s ) 
ri ri  s  (
ri )(
ri )



n  s i 1
n  s i 1
n  s i  s 1
Моделирование случайных событий

Наступление события А с заданной вероятностью
Р(А) имитируется с помощью ДСЧ

При обращении к ДСЧ выбирается число r и
принимается решение о наступлении (или нет)
события А: if r  " A" then A
if r  " A" then A
Моделирование нескольких
событий

Моделирование дискретных случайных величин

Дискретная случайная величина задается перечнем
случайных величин и их вероятностями

Каждый раз при обращении к ДСЧ выбирается то
значение случайной величины, в чью область попало
случайное число
Механизм моделирования случайной величины с
произвольным законом распределения
Порядок определения СВ X:
 Выбирается r (с помощью ДСЧ).
 Определяется F( x ) = r.
 Рассчитывается x = F-1 ( r )
Моделирование экспоненциального
распределения

Функция распределения
F ( x)  1  e  x
1  e  x  r

Выражение для определения искомой величины:
x
ln 1  r 
x

ln(r )

Моделирование нормального распределения

Эмпирические формулы:

1
x  
3   3
20n
1 n

ri

n i 1

x  
41
13440  n 2  5  10 3  15


центральная предельная теорема теории вероятностей:
 сумма случайных величин имеет распределение
асимптотически стремящееся к нормальному, если все СВ
имеют конечные математические ожидания и дисперсии и ни
одна из величин по своему значению резко не отличается от
остальных
 СВ с нормальным законом можно получить путем
суммирования величин r (для практических задач можно
ограничиться 12-ю слагаемыми)
Приближенные методы моделирования
непрерывных случайных величин
Метод численного интегрирования

Для определения x требуется решить уравнение
F ( x)   ax f x dx  r
Последовательность действий:

С помощью ДСЧ выбирается r.

Интегрируется f(x) до тех пор, пока интеграл не
превзойдет r.

То значение x, при котором F(x)  r и есть искомое
значение x.
Приближенные методы моделирования
непрерывных случайных величин
Интервальный метод
 заключается в разбиении области значений х на
непересекающиеся интервалы.
ai 1  ai
r   i 
x  ai 
 i 1   i
Лекция 4. Организация компьютерного
моделирования и оптимизации
инфокоммуникационных систем и сетей
Моделирование марковских цепей с дискретным
временем переходов

Для марковских цепей переходы осуществляются в
соответствии с заданными вероятностями

Переход в новое состояние связывается с
попаданием СВ r в интервал: если r попал в
интервал “j", то переход на шаге (t + 1) произойдет в
состояние j. В этом случае переходы будут
происходить с частотами, в пределе совпадающими
с вероятностями
Моделирование марковских процессов с
непрерывным временем переходов

Как по интенсивностям разыграть состояние, в
которое произойдет переход?

При разрешении поставленного вопроса возникает
необходимость решения двух задач:


определение времени перехода –
t
ln( r )
i
определение состояния, в которое переходит
система из текущего состояния (i -е состояние).
Моделирование марковских процессов с
непрерывным временем переходов

Определение состояния, в которое переходит
система из текущего состояния (i -е состояние):


диапазон ДСЧ (0…1) разбивается на отрезки,
пропорциональные вероятности перехода в другое
состояние
выбрать r и тем самым определить, в какое
состояние перейдет система
Моделирование систем массового обслуживания

Для решения задачи статистического
моделирования функционирования СМО должны
быть заданы следующие исходные данные:




описание СМО (тип, параметры, критерии
эффективности работы системы);
параметры закона распределения периодичности
поступлений требований в систему;
параметры закона распределения времени
пребывания требования в очереди (для СМО с
ожиданием);
параметры закона распределения времени
обслуживания требований в системе.
Моделирование систем массового обслуживания

Время функционирования системы разделяется на
достаточно большое количество подинтервалов

единиц времени, в течение которых не может
возникнуть более одной заявки или завершиться
выполнение более одной заявки
Моделирование систем массового обслуживания

Для каждого такого подинтервала:




последовательно моделируется факт появления
новой заявки (да/нет).
проверяется наличие свободного канала (закончено
ли обслуживание какой-то заявки) и загрузка его
заявкой из очереди,
проверяется наличие мест в очереди с последующим
выводом (принять в очередь/отказать в
обслуживании) и т.д.
Фиксируется число отказов, время ожидания заявок в
очереди и в системе вообще, число заявок в очереди
в каждый момент и другие значения.
1/--страниц
Пожаловаться на содержимое документа