Генерация равномерно-распределенных случайных чисел. Оценка их качества на тестах (по книге).

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

На практике наиболее часто применяют следующие 4 метода генерации случайных чисел:

1.Метод квадратов:

При возведении в квадрат n-разрядного числа в общем случае максимально в произведении будет 2n разряда. В качестве i-го случайного числа берется n средних разрядов предыдущего случайного числа.

2.Метод произведений:

Бреется n средних разрядов произведения двух предыдущих чисел.

3.Конгруэнтный метод:

.º – сравнимо по модулю. l и m – целые положительные числа. Для получения очередного случайного числа предыдущее умножается на l и затем делится на m, а остаток от деления берется в качестве i-го случайного числа.

4.Смешанный конгруэнтный метод – улучшает качество случайных чисел и отличается от предыдущего добавлением к произведению целого положительного числа m.

Генераторы псевдослучайных чисел современных ЭВМ как правило строятся на основании смешанного конгруэнтного метода. Качество случайных чисел, в том числе длина периода, которая является существенным показателем качества, во многом зависит от выбранных значений l,m,m.

Проверка качества равномерно распределенных случайных чисел

Для проверки качества равномерно распределённых случайных чисел используют три вида тестов: на равномерность, случайность, периодичность.

Проверка равномерности

Наиболее часто используют два теста: частот и разрядов. Оценку производят по критерию согласия c² (КС Пирсона).

Тест частот

Функция распределения равномерно распределенных случайных чисел в диапазоне от 0 до 1 представлена на рис.14.1, а функция плотности на рис.14.2.

Функция плотности равномерного закона определяется зависимостью:

при 0£ х£ 1. Для оценки равномерности по тестам частот весь диапазон существования распределения от 0 до 1 разбивают на L интервалов одинаковой длины и подсчитывают попадание случайной величины в каждый из них.

Вычисляется критерий согласия c², с количеством степеней свободы R.

По вычисленным значениям c² и R по статистическим таблицам находим коэффициент доверия гипотезе о равномерности по КС Пирсона, который должен попасть в 10% интервал 0,1£Р_р£0,9. В противном случае гипотеза отвергается.

Тест разрядов

Для равномерного закона вероятность появления любого символа в любом разряде числа одинакова. Для десятичных чисел она равна 0,1; для двоичных – 0,5. Для проведения тестирования подсчитывается количество каждых символов в каждом разряде числа, то есть их частоты. И аналогично предыдущему вычисляется критерий c² и количество степеней свободы R. А далее проверяем попадание коэффициента доверия гипотезе в 10%-ный доверительный интервал. При отрицательном результате гипотеза отвергается.

Тест оценки случайности

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

Коэффициент линейной автокорреляции меняется от -1 до +1. Приведем формулу для вычисления критического значения коэффициента автокорреляции:

где n – количество пар случайных чисел;

t_крит – критическое значение критерия Стьюдента, взятое по статистическим таблицам для рекомендуемого уровня значимости a=0,05 для количества степеней свободы n-2; r_крит – критическое значение коэффициента линейной автокорреляции и если вычисленное значение не меньше критического, то связь между переменными считается существенной. Если же вычисленное значение по абсолютной величине не меньше 0,8

, то такая автокорреляционная связь считается близкой к линейной.

 

Для моделирования требуется использовать генераторы случайных чисел, для которых коэффициент автокорреляции не превышает r_крит, а еще лучше не превышает 0,2 по абсолютной величине.

Тест периодичности

Тест периодичности заключается в вычислении длины периода и длины отрезка апериодичности. Период – это количество повторяющихся чисел, а отрезок апериодичности – это такая последовательность случайных чисел, в которой нет ни одной пары одинаковых чисел, но следующее число за отрезком апериодичности имеет в нем «свою» пару. Для корректного проведения имитационного моделирования и получения достоверных результатов требуется использовать случайные числа только на отрезке апериодичности, потому что любое повторение случайных чисел искажает получаемые результаты. Для вычисления длины периода используется следующий метод: генератор случайных чисел по интуиции выводится за пределы отрезка апериодичности, то есть на совокупность случайных чисел, в которой имеются периоды. Затем запоминается очередное случайное число, а каждое последующее число сравнивается с числом, которое запомнили. Количество случайных чисел до совпадения случайного числа с числом, которое запомнили, будет являться длиной периода.

Для определения длины отрезка апериодичности берется два одинаковых генератора. После того, как первый из них выработает количество чисел равное длине периода, запускается второй генератор, и пары вырабатываемых ими чисел сравниваются между собой до тех пор, пока сравнение не даст положительный результат. После этого подсчитывается количество чисел, выработанных первым генератором. Это и есть длина отрезка апериодичности, и чем качественнее генератор, тем больше длина его отрезка апериодичности.

 

 

Планирование имитационных экспериментов. Концепция «черного ящика»

Планирование экспериментов

Цель планирования экспериментов – получение результатов с требуемой достоверностью при наименьших затратах. Планирование подразделяется на стратегическое и тактическое.

Стратегическое планирование

Для стратегического планирования будем использовать концепцию «черного ящика», суть которого – абстрагирование от физической сущности процессов, происходящих в моделируемой системе и выдаче заключений о ее функционировании только на основании входных и выходных переменных. Входные, независимые переменные называются факторами. Выходные – откликами, их величина зависит от значений факторов и параметров ОИ. Структурная схема чёрного ящика представлена на рис.15.1.

Х1

ОИ

Y1

Х2 Y2

Факторы.. Отклики.

Х_М.. Y_К

x_m

При использовании концепции чёрного ящика должны выполняться следующие условия.
1.Рандомизация – случайность. Только при наличии случайности возможно корректное использование математического аппарата теории вероятностей и статистики.

2.Одновременное изменение всех факторов. Обеспечивает уменьшение стандартной ошибки при проведении экспериментов.

3.Последовательность планирования. Проведение экспериментов подразделяется на ряд последовательных этапов и планировние каждого последующего этапа производится с учётом результатов, полученных на предыдущих этапах.

4. Кодирование. Не обязательно. Кодирование значительно упрощает расчёты и делает анализ результатов более наглядным, что весьма существенно при «ручной» обработке результатов. При применении ЭВМ кодирование также представляет некоторые преимущества в анализе результатов.

К факторам предъявляют следующие требования.

1. Легкая управляемость, что позволяет сравнительно несложно повторять проводимые эксперименты.

2. Факторы не должны являться функциями каких-то аргументов.

3. Факторы должны быть хотя бы линейно независимыми между собой, что позволяет упростить математическую модель, не вводя в неё произведения факторов между собой.

4. Любое сочетание факторов в стратегических планах не должно выводить объект из допустимого режима функционирования.

 

9.План ДФЭ (дробных факторных экспериментов).

В некоторых случаях, если факторы независимы друг от друга, можно значительно уменьшить количество проводимых экспериметов, применяя план дробных факторных экспериментов (ДФЭ). В ДФЭ факторы разделяются на основные и дополнительные. Для основных факторов составляется план ПФЭ, а дополнительные меняются по законам изменения произведений основных факторов. Таким образом, например, если в эксперименте используется семь факторов, то по плану ПФЭ нам понадобилось бы провести 128 экспериментов. Если же они независимы друг от друга, то выделив из них три основных фактора и составив для них план ПФЭ мы сможем ограничиться всего 9 экспериментами с учётом центральной точки. Планы ДФЭ сохраняют все вышеназванные достоинства планов ПФЭ

10. РЦКП (ротатабельный центральный композиционный план).

РЦКП обеспечивает незначимую величину ошибки в точках, равноотстоящих от центра проведения экспериментов, поэтому они широко применяются в динамических методах поиска экстремальных значений. Расстояние звёздной точки от центра осей координат и количество проводимых экспериментов в центральной точке вычисляются по формулам:

Составим матрицу планирования РЦКП для двух факторов:

 

 

Композиционные планы ОЦКП и РЦКП имеют существенный недостаток, который начинает сказываться с увеличением количества факторов в проводимых экспериментах, чем больше факторов, тем больше расстояние звёздных точек от центра осей координат, которое всё больше и больше удаляется от заданных границ диапазонов изменения факторов, что является нежелательным.

 

11.Д–оптимальные планыВ D – оптимальных планах значения факторов не выходят за установленные границы диапазонов их изменения. Кроме того они обладают ещё одним существенным достоинством, обеспечивая минимальную ошибку во всём принятом диапазоне изменения факторов. На практике наиболее часто применяются планы Коно и планы Кифера.

Планы Коно Для многофакторных экспериментов в геометрической интерпретации диапазон изменения факторов представляется многомерным кубом, который далее будем называть просто куб. Для двух факторов этот куб вырождается в квадрат. Эксперименты по плану Коно проводятся в вершинах куба, серединах рёбер и центре куба. Характерной особенностью D – оптимальных планов является разница в количестве проводимых экспериментов для точек плана различного вида. Удельные веса видов точек для двухфакторных экспериментов в планах Коно приняты следующие.

1. Вершины куба - =0.148.

2. Середины ребер - =0.078.

3. Центр куба - =0.096.

Расположение точек стратегического плана на квадрате и кубе представлено на рис.15.3.

 

Рис.15.3. Геометрическая интерпретация двухфакторного плана на квадрате и

трёхфакторного – на кубе

 

Планы Кифера

Эксперименты по плану Кифера проводятся в вершинах куба, серединах рёбер и центрах граней. Для двухфакторных экспериментов по плану Кифера приняты следующие удельные веса.

1. Вершины куба - =0.1458.

2. Середины рёбер - =0.08015.

3. Центры граней - =0.0962.

Расположение точек плана для двухфакторных экспериментов представлено на рис.15.4; для трёхфакторных на рис.15.5.

план Кифера, которые позволяют построить математическую зависимость вида:

Отметим что для того, чтобы не потерять корректность D – оптимальных планов, чтобы количество реализаций в каждом варианте было целым числом, общее количество проводимых экспериментов для планов Коно требуется брать точно кратным 1000 а для планов Кифера – кратным 10000.

 

12.Тактическое планирование имитационных эксперементов

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

При выводе формулы для вычисления количества реализаций в эксперименте проведена замена вероятности попадания нормально распределённой случайной величины от минус бесконечности до левой границы доверительного интервала, ввиду симметричности нормального закона, на вероятность попадания от правой границы доверительного интервала до плюс бесконечности, то есть на величину .

Вероятность попадания случайной величины в доверительный интервал вычисляется при следующих преобразованиях:
Вероятность попадания случайной величины в доверительный интервал вычисляется при следующих преобразованиях:

требуется задаться доверительной вероятностью β.

Рекомендуемое значение: β=0,95. По статистическим таблицам находим . Задаёмся половиной ширины доверительного интервала Принимаем Если условия центральной предельной теоремы теории вероятностей не выполняются, например, если сравнительно невелико количество случайных чисел, или они выработаны при недостаточно общих условиях, например, от весьма различающихся законов или параметров других законов, то применяют неравенство Чебышева:

Вероятность β в (15.13) показывает, что разность случайной величины Х и ее математического ожидания по абсолютной величине меньше, или равно сколь угодно малому положительному числу ε, не меньше, чем величина

Возьмем вместо переменной Х оценку математического ожидания , тогда неравенство (15.13) запишется в виде: .

Преобразуя получим формулу для вычисления количества реализаций случайной величины для получения результатов с заданной достоверностью.

Если по результатам моделирования с заданной достоверностью требуется оценить вероятность какого-либо события, то считают, что с вероятностью р событие наступает и равно 1, и с вероятностью (1-р) событие, равное 0, не наступает, тогда

Тогда по центральной предельной теореме:

по неравенству Чебышева:

Полученные формулы позволяют вычислять требуемое количество реализаций случайного процесса в моделируемых вариантах систем при тактическом планировании.

13.Основные свойства языка GPSS W.
Язык GPSS W расшифровывается как General Purpose Simulation System World – Всемирная общая целевая моделирующая система.

В GPSS W имеется два специализированных языка.

· Язык высокого уровня, предназначенный для описания объектов моделирования, это операторы GPSS W

· Язык низкого уровня – это PLUS-операторы, ориентированные на вычисления и управление экспериментом.

В качестве операторов имитационной модели можно одновременно использовать операторы GPSS W и PLUS-операторы.

Операторы GPSS W подразделяются на блоки и команды. Блоки – это операторы, которые исполняют возложенные на них функции при входе в них движущихся объектов, называемых транзактами. Команды предназначены для определения параметров некоторых объектов модели и управления процессом моделирования. Операторы GPSS W состоят из 53 блоков и 25 команд. Состояние объектов модели в процессе моделирования отображается 35 системными числовыми атрибутами (СЧА). К СЧА можно обращаться из любых операторов GPSS W. Операторы GPSS W имеют единый формат записи, состоящий из следующих полей:

1. Поля метки, в котором указывается либо имя объекта, либо натуральная метка для организации перехода транзакта.

2. Поля операции, в которое записывается либо тип объекта, либо вид выполняемой операции.

3. Поля операндов, в которое записываются параметры объекта. В некоторых операторах записывается вычисляемое математическое выражение. В зависимости от типа оператора, изменяется количество операндов и их назначение.

Любая запись после поля операндов, сделанная с пробелом не менее, чем в одну позицию считается комментарием. Кроме того, комментарий можно записать с новой строки после символа