Полная версия

Главная arrow Информатика arrow ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ СИСТЕМ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Моделирование равномерно распределенной случайной величины

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

Определение 3.1. Непрерывная случайная величина у имеет равномерное распределение в интервале (а; Ь), если ее плотность вероятности Дх) определяется так (рис. 3.9):

Плотность вероятности равномерного распределения

Рис. 3.9. Плотность вероятности равномерного распределения

Значения характеристик равномерного распределения:

ЛЛГ л а + Ь

  • • математическое ожидание М{у) = ;
  • (Ь - а)2
  • • дисперсия D(у) = ———.

При моделировании часто используются случайные числа из интервала (0; 1). Непрерывная случайная величина у равномерно распределена в интервале (0; 1), если:

В этом случае М(у) = i, D(у) =

Случайное число х, из интервала (0; 1) легко преобразуется в случайное число х[ для интервала (а; Ь):

Применительно к двоичным дробям случайное число из интервала (0; 1) представляет собой бесконечную дробь:

Очевидно, что реализовать такую дробь в компьютере невозможно, так как разрядная сетка компьютера ограничена. В компьютере можно формировать дискретные последовательности случайных чисел, которые не могут отличаться друг от друга на величину меньше 2~п (п — число разрядов в сетке компьютера), т.е. непрерывного, «теоретического» распределения на компьютерах получить нельзя. Если эти числа равновероятны, то такое распределение случайных чисел называют квазиравномерным.

Заметим, что непрерывные случайные величины существуют только в теории. На практике все случайные величины дискретны и шаг дискретности равен наименьшей единице измерения.

Случайная величина имеющая квазиравномерное распределение в интервале (0; 1), принимает значения

с вероятностями р, = 0,5".

Можно показать, что случайная величина Е, имеет характеристики

Современные компьютеры имеют разрядность не менее 32. Следовательно, М(?) = М(у) и дисперсии тоже практически совпадают.

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

  • 1) аппаратный (физический);
  • 2) алгоритмический (программный).

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

Преимущества такого способа:

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

Однако, такой датчик (генератор) случайных чисел имеет существенные недостатки, которые в настоящее время исключили его из инженерной практики:

  • • трудность настройки;
  • • необходимость периодической проверки формируемой последовательности на соответствие закону распределения;
  • • обеспечение стабильности условий работы устройства — питания, влажности, температуры, и входящих в него приборов, так как в результате старения материалов стабильность показаний приборов нарушается;
  • • при необходимости невозможно повторить эксперимент при одной и той же последовательности случайных чисел.

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

Достоинства способа:

  • • в настоящее время предлагается достаточно датчиков, генерирующих случайные числа, проверенных практикой и, следовательно, не нуждающихся в особых проверках;
  • • можно многократно воспроизвести одну и ту же последовательность;
  • • в памяти компьютера хранится только программа датчика (генератора), занимающая, как правило, малый объем;
  • • алгоритмический датчик может быть реализован и аппаратно, за счет чего существенно сокращается время формирования случайного числа и в целом время моделирования.

Недостатки:

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

В настоящее время практически везде применяются алгоритмические датчики случайных чисел. Создание высокопроизводительных компьютеров существенно снижает роль первого недостатка (затраты машинного времени). Второй недостаток устраняется использованием в одной модели нескольких датчиков случайных чисел (ДСЧ).

Алгоритмические датчики не обеспечивают получение теоретически «чистой» случайности чисел, так как их формирование идет по формулам. Вследствие этого рано или поздно последовательность случайных чисел станет повторяться или выродится. Последнее означает, что начиная с некоторого элемента последовательности все последующие числа будут равны нулю.

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

  • статистическими свойствами случайных чисел, определяемыми путем их проверки специальными тестами;
  • периодичностью, т.е. повторяемостью через определенные промежутки времени.

Качество алгоритмического датчика оценивается тем, насколько полно он удовлетворяет следующим требованиям:

  • • закон распределения формируемых чисел должен быть равномерным (квазиравномерным);
  • • числа должны быть статистически независимыми;
  • • числа в последовательности не должны повторяться;
  • • формирование чисел должно занимать минимальное машинное время и минимальный объем памяти.

В дальнейшем алгоритмический ДСЧ, выдающий детерминированную, псевдослучайную последовательность квазиравномерно распределенных случайных чисел, будем называть датчиком равномерно распределенных случайных чисел и обозначать у ~ Rav(0; 1).

Для формирования равномерно распределенных случайных чисел в интервале (0; 1) могут использоваться следующие методы:

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

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

  • • подбирается начальное целое число, например четырехразрядное число 2152;
  • • вычисляется квадрат: 21522 = 04631104;
  • • выделяется четыре средних разряда, которые рассматриваются как дробная часть первого случайного числа 0,6311;
  • • вычисляется квадрат 63112 = 39828721;
  • • выделяется четыре средних разряда, которые рассматриваются как дробная часть второго случайного числа 0,8287;
  • • вычисляется квадрат 82872 = 68674369;
  • • выделяется третье случайное число 0,6743 и т.д.

Очевидно, что максимальная длина периода генератора, т.е. максимальное количество неповторяющихся случайных чисел, определяется количеством разрядов в дробной части. В нашем примере максимально возможная длина периода равна 9999 (от 0,0001 до 0,9999). Однако в действительности длина периода меньше максимально возможной и зависит от исходного целого числа. Неудачно выбранное значение исходного числа может привести к двум неприятностям: маленькой длине периода или даже к вырождению генератора, когда значения случайной величины начинают повторяться.

Метод произведений аналогичен методу квадратов. Отличие состоит в том, что перемножаются два п-разрядных целых числа, одно из которых, называемое ядром или множителем, не меняется, а второе, называемое множимым, формируется из п последних (правых) разрядов полученного 2п-разрядного числа — произведения ядра и множимого. Естественно, что вначале, как и в методе квадратов, необходимо грамотно выбрать исходные значения ядра и множителя.

В настоящее время очень широкое распространение в практике моделирования получили конгруэнтные методы формирования псевдослучайной последовательности.

Два целых числа а и b называются конгруэнтными (сравнимыми) по модулю М, где М — целое число, если разность (а - b) делится на М без остатка, а числа а и b дают одинаковые остатки от деления на М.

Например, конгруэнтными являются 2568 и 148 (по модулю 10), 1746 и 511 (по модулю 5), 6493 и 2221 (по модулю 2) и т.д.

Конгруэнтные методы описываются в виде рекуррентного соотношения следующего вида:

где Xt, X, ц, М — неотрицательные целые числа; Х0 — произвольное неотрицательное нечетное число; X — множитель; р — аддитивная константа; М — модуль.

Каждое новое значение Xi+1 псевдослучайной последовательности представляет собой целочисленный остаток от деления на модуль М суммы произведения предыдущего значения Xt на множитель X и аддитивной константы ц. Далее псевдослучайное число xi+1 в интервале (0; 1) получается путем деления целочисленного значения Xi+l на модуль М: xl+l =Xj+1/M.

Описанный метод генерирования псевдослучайных чисел получил название смешанного конгруэнтного метода.

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

где Х0 — произвольное нечетное число, неотрицательное; X = 8t ± 3, t — любое целое положительное число; М — значение модуля. Для реализации на компьютере удобно брать М = рч, где р — основание системы счисления (2 или 10); q — число разрядов в случайном числе.

В этом случае взятие числа по модулю сводится к выделению q младших разрядов произведения АХ,.

Алгоритм мультипликативного конгруэнтного метода следующий.

  • 1. Выбрать Х0, например Х0 = 234 567.
  • 2. Вычислить коэффициент X. Пусть t = 1, тогда Х = 8-1-3 = 5.
  • 3. Выбрать модуль М. Пусть система счисления десятичная (р = 10), разрядность случайных чисел q = 6. Тогда М = 106.
  • 4. Вычислить произведение АХ0:

5. Найти остаток от деления по модулю М:

6. Найти число Xj последовательности случайных чисел из интервала (0; 1):

7. Присвоить Х0 г и перейти к п. 4.

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

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

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

Проверка на периодичность требует обязательного определения длины периода. Чем больше длина периода, тем генератор более качественный.

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

  • • математическое ожидание М(у) « 0,5;
  • • дисперсия D(y) = 0,0833;
  • • среднее квадратическое отклонение а ~ 0,2887.

Частотный тест позволяет выявить, сколько чисел попало в интервал (М(у) - а; М(у) + а), т.е. (0,5 - 0,2887; 0,5 + 0,2887), или в конечном итоге (0,2113; 0,7887). Так как 0,7887 - 0,2113 = 0,5774, заключаем, что в хорошем генераторе в этот интервал должно попадать около 57,7% из всех выпавших случайных чисел.

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

Тест проверки частот предполагает разбиение диапазона распределения на несколько интервалов и подсчет количества (частот или вероятностей) попаданий случайных чисел в выделенные интервалы.

Тест проверки пар заключается в подсчете количества единиц для каждого разряда всей совокупности выработанных генератором двоичных случайных чисел. Число единиц во всех разрядах должно составлять примерно 50% от количества выработанных генератором чисел.

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

Тест проверки серий заключается в подсчете количества различных длин последовательностей одинаковых значений (1 или 0).

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>