Общие принципы генерации случайных величин

Тема 4. Генерация случайных чисел

Имитационное моделирование требует использования большого количества случайных величин. Например, в моделях систем массового обслуживания требуется получение случайного интервала времени между поступлениями заявок, а также случайное время их обслуживания. Кроме того, случайные числа могут быть нужны для определения маршрута движения транзакта (блок TRANSFER в режиме статистической передачи), розыгрыша объема покупки или спроса на товар в моделях управления запасами, и т.д. Моделирование этих случайных величин может быть выполнено на основе наблюдений за реальной системой. Результаты наблюдений могут быть использованы в модели либо непосредственно (т.е. в “сыром виде”), либо через генераторы случайных чисел, воспроизводящие их статистические аналоги.

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

a) не гарантируется типичность данных;

b) длительность моделируемого процесса ограничена длительностью реального;

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

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

1) Физическим или программным методом формируется случайное число U_i, равномерно распределенное на интервале [0,1).

2) Выполняется программный переход от U_i к случайному числу X_i, имеющему требуемое распределение.

Равномерно распределенное на [0,1) случайное число представляется в компьютере в виде n – разрядной последовательности нулей и единиц, причем в каждом разряде нуль или единица должны наблюдаться с вероятностью 0,5.

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

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

Числа, выдаваемые программными генераторами, называются “псевдослучайными”. В работе Лемера (1951г) формулируется идея использования псевдослучайных чисел следующим образом: ”последовательность псевдослучайных чисел можно считать случайной, если ее каждый элемент непредсказуем для непосвященных и она удовлетворяет ряду традиционных статистических тестов”.

В n - разрядной сетке компьютера количество различных двоичных чисел равно 2ⁿ, т.е. ограничено. Поэтому последовательность генерируемых псевдослучайных чисел рано или поздно начнет повторяться. Количество чисел, генерируемых до начала повторения последовательности, называется периодом генератора L. В лучшем случае период генератора L=2ⁿ. Тогда говорят, что генератор имеет полный период. Однако для многих генераторов период гораздо меньше, чем 2ⁿ, и может зависеть от начального значения генератора.

Хороший программный генератор случайных чисел должен обладать следующими свойствами:

1. Получаемые числа должны быть равномерно распределены в интервале [0,1) и не должны иметь корреляции друг с другом. Данное свойство проверяется различными методами: например, исследуется равномерность заполнения r - мерного единичного гиперкуба точками (U₁,U₂,…,U_r),(U_r+1,U_r+2,…,U_2r),…Существуют и другие тесты проверки равномерности и отсутствия корреляции.

2. Генератор должен обладать быстродействием и не требовать больших затрат памяти (удобство использования на практике).

3. В генераторе должен быть предусмотрен простой способ получения отдельных потоков случайных чисел, т.е. независимых последовательностей чисел. Каждый поток можно выделить для конкретного источника случайности при моделировании. Например, один поток – для интервала прихода транзактов, а другой поток – для интервалов обслуживания. Либо один поток – для интервалов прихода транзактов одного типа, а второй – для транзактов другого типа. В этом случае обеспечивается сравнимость результатов моделирования.

4. Генератор должен иметь достаточно большую длину периода.

Дата добавления: 2014-01-07