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

Как уже отмечалось, имитационное моделирование экономи­ческих систем, как правило, предполагает необходимость учета различных случайных факторов: событий, величин, векторов (си­стем случайных величин), процессов. В основе всех методов и при­емов моделирования названных случайных факторов лежит ис­пользование случайных чисел, равномерно распределенных на интервале [0;1].

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

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

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

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

259

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

Программные генераторы ПСЧ должны удовлетворять следу­ющим требованиям:

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

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

 

• последовательность ПСЧ должна быть воспроизводима; . генератор должен быть быстродействующим;

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

Метод срединных квадратов. Первой расчетной процедурой генерации ПСЧ, получившей достаточно широкое распростране­ние, можно считать метод срединных квадратов, предложенный Д. фон Нейманом и Н. Метрополисом в 1946 г. Сущность метода заключается в последовательном нахождении квадрата некоторо­го m-значного числа, выделении из него т средних цифр, образу­ющих новое число, которое и принимается за очередное в после­довательности ПСЧ, возведении этого числа в квадрат, выделе­нии из квадрата т средних цифр и далее до получения последова­тельности требуемой длины. Как следует из описания процедуры метода, он весьма прост в вычислительном отношении и, следо­вательно, легко реализуем программно. Однако ему присущ очень серьезный недостаток — обусловленность статистических свойств генерируемой последовательности выбором ее корня (начального значения), причем эта обусловленность не является «регулярной», т. е. трудно определить заранее, можно ли использовать получен­ные данным методом ПСЧ при проведении исследований. Это обстоятельство иллюстрируется рис. 20.1, на котором представле­ны результаты генерации последовательности из ста ПСЧ при следующих исходных данных: число знаков т = 4; корни после­довательности Х₀ = 2 152; Х₀ = 2 153; ^₀ = 3 789; Х₀ = 3 500.

Из анализа рисунка видно, что при Х₀ = 2 152 уже с 78-го члена последовательности все ПСЧ принимают нулевые значения; при Х₀ = 2 153, начиная с 36-го значения, последовательность пере­стает быть случайной; при Х₀ - 3 789 первые 100 членов последо­вательности можно использовать в качестве ПСЧ (дальнейшее по­ведение последовательности ПСЧ требует дополнительных иссле-

260

 

 

KJ

ел

a — корень последовательности Х_й = 2 152;

Рис. 20.1. Последовательности ПСЧ:

б — корень последовательности Х₀ = 2 153; в г — корень последовательности Х₀ = 3 500

корень последовательности Х_й = 3 789;

дований); при Х₀ = 3 500 (2 500; 4 500 и т.д.) нулевые значения принимают все ПСЧ. Иными словами, метод срединных квадра­тов не позволяет по начальному значению оценить качество по­следовательности ПСЧ, в частности ее период.

Наибольшее распространение сегодня получили так называ­емые конгруэнтные методы генерации ПСЧ, предложенные в 1946 г. американским математиком Д.Лемером: мультипликатив­ный, аддитивный и смешанный.

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

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

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

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

где Ъ — число двоичных цифр (бит) в машинном слове; Т — лю­бое целое положительное число; V — любое положительное не­четное число.

Заметим, что, в принципе, возможно за счет другого выбора модуля m увеличить длину последовательности до р = m - 1, час­тично пожертвовав скоростью вычислений. Кроме того, важно,

262

Получим последовательность ПСЧ с периодом, равным

 

Рис. 20.2. Последовательности ПСЧ, полученные по мультипликативному методу: а — число двоичных цифр в машинном слове b = 4; б — число двоичных цифр в машинном слове b = 6

257

 

 

 

Рис. 20.3. Последовательности ПСЧ, полученные по аддитивному методу при следующих параметрах:

а — при Ъ = 3; X = 1-;.-X, = 3; б — при 6 = 3; Х₀ = 5; Jf, = 7

что получаемые таким образом ПСЧ оказываются нормирован­ными, т. е. распределенными от нуля до единицы.

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

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

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

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

На рис. 20.3 приведены две последовательности ПСЧ, полу­ченные при исходных данных: Ь = 3, Х₀= I, Х_{ = 3 а Х₀ = 5, Х_{ = 7. В обоих случаях период последовательности равен 12 ПСЧ.

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

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

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

264

Рис. 20.4. Последовательности ПСЧ, полученные по смешанному методу при следующих параметрах:

а — при 6 = 3; б — при 6 = 4

повышенных требованиях к точности имитации реального про­цесса (объекта).

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

⇐ Предыдущая38394041424344454647Следующая ⇒

Поделиться: