Генерация псевдослучайных чисел

Как уже отмечалось ранее, имитационное моделирование ЭИС, как правило, предполагает необходимость учета различных случайных факторов — событий, величин, векторов (систем случайных величин), процессов.

В основе всех методов и приемов моделирования названных случайных факторов лежит использование случайных чисел, равномерно распределенных на интервале [0; 1].

До появления ЭВМ в качестве генераторов случайных чисел применяли механические устройства — колесо рулетки, специальные игральные кости и устройства, которые перемешивали фишки с номерами, вытаскиваемые вручную по одной.

По мере роста объемов применения случайных чисел для ускорения их моделирования стали обращаться к помощи электронных устройств. Самым известным из таких устройств был электронный импульсный генератор, управляемый источником шума, разработанный широко известной фирмой RAND Corporation. Фирмой в 1955 г. была выпущены книга, содержащая миллион случайных чисел, сформированных этим генератором, а также случайные числа в записи на магнитной ленте. Использовались и другие подобные генераторы — например, основанные на преобразовании естественного случайного шума при радиоактивном распаде. Все эти генераторы обладают двумя недостатками:

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

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

В принципе можно заранее ввести полученные таким образом случайные числа в память машины и обращаться к ним по мере необходимости, что сопряжено с понятными негативными обстоятельствами — большим (причем неоправданным) расходом ресурсов ЭВМ и затратой времени на обмен данными между долгосрочной и оперативной памятью (особенно существенно для «больших» имитационных моделей).

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

· ПСЧ должны быть равномерно распределены на интервале [0; 1] и независимы, т.е. случайные последовательности должны быть некоррелированы;

· цикл генератора должен иметь возможно большую длину;

· последовательность ПСЧ должна быть воспроизводима;

· генератор должен быть быстродействующим;

· генератор должен занимать малый объем памяти.

Первой расчетной процедурой генерации ПСЧ, получившей достаточно широкое распространение, можно считать метод срединных квадратов, предложенный Дж.фон Нейманом и Ф.Метрополисом в 1946 г. Сущность метода заключается в последовательном нахождении квадрата некоторого m-значного числа; выделении из него т средних цифр, образующих новое число, которое и принимается за очередное в последовательности ПСЧ; возведении этого числа в квадрат; выделении из квадрата т средних цифр и далее до получения последовательности требуемой длины. Как следует из описания процедуры метода, он весьма прост в вычислительном отношении и, следовательно, легко реализуем программно. Однако ему присущ очень серьезный недостаток — обусловленность статистических свойств генерируемой последовательности выбором ее корня (начального значения), причем эта обусловленность не является «регулярной», т.е. трудно определить заранее, можно ли использовать полученные данным методом ПСЧ при проведении исследований. Это обстоятельство иллюстрируется рис. 10.1, на котором представлены результаты генерации последовательности из ста ПСЧ при следующих исходных данных: число знаков т = 4; корни последовательности Х₀ = 2152; Х₀ = 2153; Х₀ = 3789; X₀ = 3500.

Из анализа рисунка видно, что при Х₀ = 2152 уже с 78-го члена последовательности все ПСЧ принимают нулевые значения; при Х₀= 2153, начиная с 36-го значения, последовательность перестает быть случайной; при Х₀ = 3789 первые 100 членов последовательности можно использовать в качестве ПСЧ (дальнейшее поведение последовательности ПСЧ требует дополнительных исследований); при Х₀ = 3500 (2500; 4500 и т.д.) нулевые значения принимают все ПСЧ. Иными словами, метод срединных квадратов не позволяет по начальному значению оценить качество последовательности ПСЧ, в частности ее период.

Мультипликативный метод. Основная формула мультипликативного генератора для расчета значения очередного ПСЧ по значению предыдущего имеет вид

где а, т — неотрицательные целые числа (их называют множитель и модуль).

Как следует из формулы, для генерации последовательности ПСЧ необходимо задать начальное значение (корень) последовательности, множитель и модуль, причем период (длина) последовательности Р зависит от разрядности ЭВМ и выбранного модуля, а статистические свойства — от выбранного начального значения и множителя. Таким образом, следует выбирать перечисленные величины так, чтобы по возможности максимизировать длину последовательности и минимизировать корреляцию между генерируемыми ПСЧ. В специальной литературе приводятся рекомендации по выбору значений параметров метода, использование которых обеспечивает (гарантирует) получение определенного количества ПСЧ с требуемыми статистическими свойствами (отметим, что данное замечание можно отнести ко всем конгруэнтным методам). Так, если для машины с двоичной системой счисления задать m = 2^b, a = 8T±3V, где b — число двоичных цифр (бит) в машинном слове; Т — любое целое положительное число; V — любое положительное нечетное число, получим последовательность ПСЧ с периодом, равным р = 2^{b - 2} = m/4. Заметим, что в принципе возможно за счет другого выбора модуля т увеличить длину последовательности до Р = т - 1, частично пожертвовав скоростью вычислений [48]. Кроме того, важно, что получаемые таким образом ПСЧ оказываются нормированными, т.е. распределенными от 0 до 1.

На рис. 10.2 приведены последовательности ПСЧ, полученные по мультипликативному методу со следующими параметрами: X₀ = 15; T = 3; V = 1; b = 4 и b = 6(столь малые значения b объясняются стремлением проиллюстрировать работоспособность рекомендованных формул). Очевидно, что в первом случае длина последовательности до повторений равна 4, а во втором — 16 ПСЧ. Легко показать, что от выбора корня последовательности ее длина не зависит (при равенстве остальных параметров).

Аддитивный метод. Основная формула для генерации ПСЧ по аддитивному методу имеет вид

где т — целое число.

Очевидно, что для инициализации генератора, построенного по этому методу, необходимо, помимо модуля т, задать два исходных члена последовательности. При Х₀ = 0; Х₁ = 1 последовательность превращается в ряд Фибоначчи. Рекомендации по выбору модуля совпадают с предыдущим случаем; длину последовательности можно оценить по приближенной формуле

На рис. 10.3 приведены две последовательности ПСЧ, полученные при исходных данных: b = 3; Х₀ = 1; Х₁ = 3 и b = 4; Х₀= 5; Х₁ = 7. В обоих случаях период ПСЧ равен 12.

Смешанный метод.Данный метод несколько расширяет возможности мультипликативного генератора за счет введения так называемого коэффициента сдвига с. Формула метода имеет вид

За счет выбора параметров генератора можно обеспечить максимальный период последовательности ПСЧ р = 2^b. На рис. 10.4 показаны две последовательности ПСЧ, полученные при следующих исходных данных: Х₀ = 7; с = 13; а = 9; b = 3 и b = 4. В первом случае длина последовательности равна 8, а во втором — 16 ПСЧ.

Разработано множество модификаций перечисленных конгруэнтных методов, обладающих определенными преимуществами при решении конкретных практических задач, а также рекомендаций по выбору того или иного метода [48]. Для весьма широкого круга задач вполне удовлетворительными оказываются типовые генераторы ПСЧ, разработанные, как правило, на основе смешанного метода и входящие в состав стандартного общего программного обеспечения большинства ЭВМ. Специальным образом генерацию ПСЧ организуют либо для особо масштабных имитационных исследований, либо при повышенных требованиях к точности имитации реального процесса (объекта).

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