Тема 3. Метод Монте-Карло и имитационное моделирование

1. Понятие метода Монте-Карло

2. Методы получения равномерной случайно последовательности чисел.

Влияние случайных факторов на социально-экономические процессы является серьезной причиной возникновения неопределенности состояния хозяйственных и экономических систем. Для принятия эффективного управленческого решения необходимо как можно полнее учесть влияние неконтролируемых случайных факторов и сделать аргументированный вывод относительно возможных направлений развития системы и оптимальной стратегии управления ею. Такие задачи могут быть решены с помощью метода статистических испытаний (метода Монте-Карло).

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

Зарождение метода Монте-Карло связанно с исследованиями фон Неймана и Улана в конце 40-х годов, когда они ввели термин «метод Монте-Карло» и применили этот метод к решению некоторых задач экранирования ядерных излучений. Этот давно известный математический метод пережил свое второе рождение, когда нашел применение в закрытых работах по ядерной технике в Лос-Аламосе, выполнявшихся под кодовым названием «Монте-Карло».

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

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

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

Для использования метода Монте-Карло необходимы равномерно распределенные случайные числа (РСЧ) в диапазоне [0, 1]. Рассмотрим свойства этих чисел.

Если случайная величина имеет равномерное распределение на отрезке , то ее плотность распределения вероятности имеет вид:

(1.2)

Математическое ожидание и дисперсия случайной величины:

(1.3)

(1.4)

Для случайной величины в диапазоне :

(1.5)

(1.6)

(1.7)

Функция кумулятивного распределения:

(1.8)

Равномерную случайную величину на отрезке [0, 1] обозначим через . Для нее характерно уникальное (присущее лишь данному распределению) свойство: вероятность того, что значения этой случайной величины попадут на некоторый интервал с границами , равняется длине этого интервала:

(1.9)

Это свойство часто используется в методе Монте-Карло как необходимое и достаточное условие того, что некоторая случайная величина имеет распределение (1.5).

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

Принципиальная возможность генерировать последовательные реализации случайной величины  вытекает из такого преобразования:

 = z₁2^-1 + z₂2^-2 +…+ z_i2^-i +…, (1.10)

где z_i ― реализация случайной величины Z, которая приобретает лишь два значения ― 0 и 1 с одинаковой вероятностью 0,5.

Случайная величина , равномерно распределенная на отрезке [0, 1], может иметь бесконечное число реализаций. Тем не менее, при использовании метода Монте-Карло на ЭВМ можно образовать лишь различных случайных чисел (k ― количество двоичных разрядов машинной памяти). Поэтому равномерная случайная последовательность чисел (РСП), используемая при машинных расчетах, фактически является реализацией дискретной случайной величины, распределение которой называется квазиравномерным (от лат. Quasi – почти, будто).

РСП чисел, распределенных на отрезке [0, 1], может быть получена тремя различными методами: физическое, табличное и программное генерирование [6,7].

Физическое устройство или программа ЭВМ, порождающая РСП [0, 1], называется генератором (датчиком) случайных чисел.

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

В настоящее время физическое генерирование РСП [0, 1] базируется на положении, в соответствии с которым при генерировании т-разрядного случайного двоичного числа необходимо получить т реализаций случайной величины Z, приобретающей значения 0 или 1 с одинаковой вероятностью 0,5.

Реализации случайной величины Z можно получить, используя радиоактивное излучение или собственные шумы электронных приборов.

Сущность метода, основанного на радиоактивном излучении, состоит в следующем:

1) выбирается источник радиоактивного излучения с интенсивностью ;

2) в зависимости от значения  выбирается отрезок времени ;

3) с помощью счетчика определяется количество частиц, которые излучает источник за время ;

4) если количество частиц четное, то z_i = 0, иначе z_i = 1.

Для получения т-разрядного случайного двоичного числа достаточно т раз обратиться к счетчику радиоактивных частиц. Аналогично работает и метод, основанный на собственных шумах электроприборов.

Преимущества метода физического генерирования:

1) скорость генерирования чисел очень высока;

2) места в оперативной памяти не занимает;

3) запас чисел не ограничен.

Недостатки метода физического генерирования:

1) нельзя повторить попытки (нет возможности физический датчик зафиксировать на определенном случайном числе);

2) нужна периодическая корректировка датчиков, поскольку их физические свойства со временем изменяются;

3) необходимо иметь специальное устройство к ЭВМ.

Физическое генерирование случайных чисел используется в основном там, где очень часто решаются задачи методом Монте-Карло. В последние годы аппаратные генераторы активно применяются в системах защиты информации.

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

Преимущества табличного метода:

1) числа можно получать очень быстро, если таблица записана в оперативную память;

2) можно повторять попытки, что очень важно в случае проведения ответственных экспериментов;

3) обеспечивается однократная проверка качества случайных чисел.

Недостатки табличного метода:

1) таблица занимает много места в оперативной памяти;

2) запас чисел ограничен;

3) необходима внешняя память.

Табличный метод получения РСП [0, 1] применяется в основном для ручных расчетов. В исследованиях на ЭВМ он используется для отладки программ или дублирования особенно ответственных опытов.

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

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

(1.11)

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

Один из первых алгоритмов образования случайных чисел с помощью рекуррентного соотношения – метод серединных квадратов, предложенный в 1946 году фон Нейманом и Метрополисом. В квадрат возводится текущее случайное число и из серединных разрядов результата выделяется следующее случайное число. Этот метод очень легко реализовать, но вырабатываемые генератором числа являются сильно коррелированными. Кроме того, если начальное число четное, то последовательность может вырождаться, т.е. начиная с некоторого значения, следующее будет равно предыдущему. Такое произойдет, если начальным числом серии будет 4500.

Таким же простым является метод произведений. Два следующих друг за другом случайных числа перемножаются, и из серединных разрядов произведения выделяется следующее случайное число.

Теперь почти все стандартные библиотечные программы вычисления последовательности равномерно распределенных случайных чисел основываются на понятии конгруэнтности.

Два целых числа А и В конгруэнтны по модулю т (где т ― целое число), когда существует такое целое число k, что А – В = km, то есть когда разность А – В делится на т без остатка (числа А и В дают одинаковые остатки при делении на абсолютную величину числа m). Это записывается как и читается «А конгруэнтно В по модулю m». Например, , , и т.д.

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

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

, (1.12)

где а и m – положительные целые числа.

Для нахождения следующего случайного числа x_i+1 достаточно:

1) взять последнее случайное число x_i;

2) умножить его на коэффициент а;

3) произведение поделить на модуль m;

4) остаток от деления считать искомым случайным числом x_i+1 (это будет одно из целых чисел 0, 1, 2, 3,..., т – 1.)

Выбор а, т и начального числа x₀ необходимо производить очень осторожно. Если а = 1, то x_i = x₀ для любого i. Когда x₀ = 0, то x_i = 0 для всех i. Очевидно, что любой генератор псевдослучайных чисел может дать лишь конечное множество целых случайных чисел; после этого последовательность будет повторяться.

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

Смешанный конгруэнтный метод отличается от предыдущего наличием определенной константы c:

. (1.13)

Аддитивный конгруэнтный метод базируется на следующем:

. (1.14)

Преимущества программного метода:

1) занимает мало места в оперативной памяти;

2) можно повторить попытки;

3) обеспечивается однократная проверка качества случайных чисел;

4) не нужны внешние устройства.

Недостатки программного метода:

1) относительно небольшая скорость образования случайных чисел;

2) запас чисел ограничен длиной периода.

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

Применение метода Монте-Карло успешно только в случае, когда создаваемые генератором числа являются случайными, равномерно распределенными на отрезке [0, 1] и независимыми. Практически бывает достаточно, чтобы последовательность приблизительно отвечала требованиям идеального генератора, что проверяется с помощью специальных статистических тестов. При этом выполняются две предпосылки.

1. Генератор псевдослучайных чисел считается пригодным, если он выдерживает набор заведомо установленных тестов.

2. Качество случайных чисел проверяется лишь один раз на предварительном этапе построения имитационной модели.

Среди тестов оценки качества случайных чисел есть общеизвестные статистические методы проверки гипотез (проверка соответствия распределений по критериям Пирсона или Колмогорова, выявление корреляционной зависимости между сериями случайных чисел — автокорреляции), а также и специально разработанные для метода Монте-Карло критерии. Количество этих тестов достаточно велико и их описание можно найти в литературе. Как правило, генератор РСП [0, 1] считают возможным использовать лишь в случае, когда он одновременно отвечает всем выбранным тестам (проверка датчика прекращается, как только он не отвечает очередному тесту). Решения о соответствии датчика тому ли другому тесту исследователь часто принимает на интуитивном уровне, опираясь на собственный опыт.