<<
>>

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

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

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

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

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

Использовались и другие подобные генераторы — например, основанные на преобразовании естественного слу­чайного шума при радиоактивном распаде. Все эти генера­торы обладают двумя недостатками:

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

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

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

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

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

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

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

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

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

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

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

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

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

J

б)

a)
і

Рис. 3.3.1. Последовательности ПСЧ: а) Х0 = 2152; б) Х„ = 2153

в)

0,9 •
0,8 -
0,7 -
0,6 -
S 0,5-
if
и 0,4-
В
0,3 -
0,2 -
0,1 ■

О -F—111—'—і—1—'—1—»■ і111—і—'—'—■—'—і—'—111— О 20 40 60 80 100

г)

Рис. 3.3.1.

Последовательности ПСЧ: в) Х0 = 3789; г) Х0 = 3500

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

Мультипликативный метод

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

Х.+1 — аХ (тос! т),

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

Как следует из формулы, для генерации последователь­ности ПСЧ необходимо задать начальное значение (корень) последовательности, множитель и модуль, причем период (длина) последовательности Р зависит от разрядности ЭВМ и выбранного модуля, а статистические свойства — от выб­ранного начального значения и множителя. Таким образом, следует выбирать перечисленные величины так, чтобы по возможности максимизировать длину последовательности и минимизировать корреляцию между генерируемыми ПСЧ. В специальной литературе приводятся рекомендации по выбо­ру значений параметров метода, использование которых обес­печивает (гарантирует) получение определенного количества ПСЧ с требуемыми статистическими свойствами (отметим, что данное замечание можно отнести ко всем конгруэнтным методам). Так, если для машины с двоичной системой счис­ления задать т = 2Ь, а — 8 Т±3-У, где Ь — число двоичных цифр (бит) в машинном слове; Т — любое целое положительное число; V — любое положительное нечетное число, получим последовательность ПСЧ с периодом, рав- т

ным Р = 2 = —. Заметим, что в принципе возможно за

счет другого выбора модуля т увеличить длину последова­тельности до Р = т — 1, частично пожертвовав скоростью вычислений [48]. Кроме того, важно, что получаемые таким образом ПСЧ оказываются нормированными, т. е. распреде­ленными от 0 до 1.

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

Аддитивный метод

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

Х.+1 = а(Х. + Х._1)(тос1 т), где т — целое число.

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

Р = 2ь+1 - 2(Ь - 1).

На рис. 3.3.3 приведены две последовательности ПСЧ, полученные при исходных данных: а) Ъ = 3; Х0 = 1; X, = 3; б) в = 4; Х0 = 5; Х1 = 7. В обоих случаях период последователь­ности ПСЧ равен 12.

Смешанный метод

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

Х.+1 = (аХ. + с)(тос1 т).

Рис. 3.3.2. Последовательности ПСЧ, полученные по мультипликативному методу: а) Ь = 4; б) Ь = 6

б)

О 5 10 15 20 25

I

а) а)

Рис. 3.3.3. Последовательности ПСЧ, полученные по смешанному методу при следующих параметрах: а) Ъ = 3; б) Ъ — 4

За счет выбора параметров генератора можно обеспечить максимальный период последовательности ПСЧ Р = 2Ь.

На рис. 3.3.4 показаны две последовательности ПСЧ, по­лученные при следующих исходных данных: с = 13; а = 9; а) Ь = 3; б) Ъ = 4. В первом случае длина последовательности равна 8, а во втором — 16 ПСЧ.

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

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

<< | >>
Источник: Балдин К. В., Уткин В. Б.. Информационные системы в экономике: Учебник. — 5-е изд. — М.: Издательско-торго- вая корпорация «Дашков и К0», — 395 с.. 2008

Еще по теме 3.3.1. Генерация псевдослучайных чисел:

  1. Формат чисел. Убыток
  2. Закон больших чисел
  3. СПОСОБ СПИСАНИЯ СТОИМОСТИ ПО СУММЕ ЧИСЕЛ ЛЕТ СРОКА ПОЛЕЗНОГО ИСПОЛЬЗОВАНИЯ
  4. Способ списания стоимости по сумме чисел лет срока полезного использования
  5. 79. УРОВНИ ФИБОНАЧЧИ
  6. 79. УРОВНИ ФИБОНАЧЧИ
  7. 79. УРОВНИ ФИБОНАЧЧИ
  8. 7.6. Учет амортизации основных средств
  9. БИБЛИОТЕКА ТОЛЕДО
  10. Типы выборок.
  11. 4.7.1. МОДЕЛИ ОТОБРАЖЕНИЯ ДАННЫХ
  12. 3.2. Эксперимент по методу Монте-Карло
  13. § 3.2. СЛУЧАЙ, КОГДА ПЕРИОД НАЧИСЛЕНИЯ НЕ ЯВЛЯЕТСЯ ЦЕЛЫМ ЧИСЛОМ
  14. Формирование выборки при использовании статистических методов
  15. ОДНОРОДНЫЕ КООРДИНАТЫ точки
  16. Использование маркетинговых каналов
  17. 3.3.2. Моделирование случайных событий
  18. Учебно-методические материалы к теме 2