Английский. Технология моделирования случайных факторов

• Название: Технология моделирования случайных факторов
• Анкор: Английский
• Дата: 01.11.2021
• Размер: 237.5 Kb.
• Имя файла: 13.doc
• Тип: Лекция; #260458

Лекция 13

Тема: Технология моделирования случайных факторов

Содержание лекции

1. Генерация псевдослучайных чисел (ПСЧ).

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

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

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

2. Моделирование случайных событий.

2.1. Последовательное моделирование.

2.2. Моделирование после предварительных расчетов.

1. Генерация псевдослучайных чисел (ПСЧ)

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

Как следует из формулы, для генерации последовательности ПСЧ необходимо задать начальное значение (корень) последовательности, множитель и модуль, причем период (длина) последовательности Р зависит от разрядности ЭВМ и выбранного модуля, а статистические свойства – от выбранного начального значения и множителя. Таким образом, следует выбирать перечисленные величины так, чтобы по возможности максимизировать длину последовательности и минимизировать корреляцию между генерируемыми ПСЧ. В специальной литературе приводятся рекомендациипо выбору значений параметров метода, использование которых обеспечивает (гарантирует) получение определенного количества ПСЧ с требуемыми статистическими свойствами. Так, если для машины с двоичной системой счисления задать , , где – число двоичных цифр (бит) в машинном слове; Т – любое целое положительное число; V– любое положительное нечетное число, получим последовательность ПСЧ с периодом, равным . Заметим, что в принципе возможно за счет другого выбора модуля т увеличить длину последовательности до , частично пожертвовав скоростью вычислений. Кроме того, важно, что получаемые таким образом ПСЧ оказываются нормированными, т.е. распределенными от 0 до 1. От выбора корня последовательности ее длина не зависит (при равенстве остальных параметров).

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

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

,

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

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

.

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

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

.

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

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

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

2. Моделирование случайных событий

В теории вероятностей реализацию некоторого комплекса условий называют испытанием. Результат испытания,регистрируемый как факт, называют событием.

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

Моделирование случайного события заключается в " определении ("розыгрыше") факта его наступления.

Для моделирования случайного события А, наступающего в опыте с вероятностью , достаточно одного случайного (псевдослучайного) числаR, равномерно распределенного на интервале [0;1]. В случае попадания ПСЧ R в интервал событие А считают наступившим в данном опыте; в противном случае – не наступившим в данном опыте. На рис. 1 показаны оба исхода: при ПСЧ событие следует считать наступившим; при ПСЧ – событие в данном испытании не наступило. Очевидно, что чем больше вероятность наступления моделируемого события, тем чаще ПСЧ, равномерно распределенные на интервале [0;1], будут попадать в интервал , что и означает факт наступления события в испытании.



Рис. 1. Моделирование случайных событий
Для моделирования одного из полной группы N случайных несовместных событий , ,…, , с вероятностями наступления соответственно, также достаточно одного ПСЧ R.

Напомним, что для таких случайных событий можно записать:

.

Факт наступления одного из событий группы определяют исходя из условия принадлежности ПСЧ R тому или иному интервалу, на который разбивают интервал [0;1]. Так, на рис. 2 для ПСЧ считают, что наступило событие А₂. Если ПСЧ оказалось равным , считают, что наступило событие .




Рис. 2. Моделирование полной группы несовместных событий.
Если группа событий не является полной, вводят дополнительное (фиктивное)событие , вероятность которого определяют по формуле:

.

Далее действуют по уже изложенному алгоритму для полной группы событий с одним изменением: если ПСЧ попадает в последний, -й интервал, считают, что ни одно из N событий, составляющих неполную группу, не наступило.

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

Для того чтобы провести моделирование двух зависимых случайных событий А и В,необходимо задать следующие полные и условные вероятности:

; ; ; .

Заметим, что, если вероятность наступления события В при условии, что событие А не наступило, не задана, ее можно определить по формуле:

.

Существуют два алгоритмамоделирования зависимых событий. Один из них условно можно назвать "последовательным моделированием"; другой – "моделированием после предварительных расчетов".

2.1. Последовательное моделирование

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

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


Рис. 3. Последовательное моделирование зависимых событий.

2.2. Моделирование после предварительных расчетов

Приведенные на рис. 3 четыре исхода моделирования зависимых событий образуют полную группу несовместных событий. На этом основан алгоритм моделирования, предусматривающий предварительный расчетвероятностей каждого из исходов и "розыгрыш" факта наступления одного из них, как для любой группы несовместных событий. Рис. 4 иллюстрирует разбиение интервала [0;1] на четыре отрезка, длины которых соответствуют вероятностям исходов наступления событий.



Рис. 4. Разбиение интервала [0;1] для реализации алгоритма моделирования

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



Рис. 5. Алгоритм моделирования зависимых случайных событий

после предварительных расчетов.