В данной статье мы не будем углубляться в математику, а постараемся дать общее представление о методе Монте-Карло.
Суть метода заключается в следующем: для целевой случайной величины генерируется набор случайных значений, а затем на его основе рассчитываются требуемые значения.
Метод Монте-Карло имеет множество различных приложений. Он применяется в следующих областях: в промышленности для моделирования изменчивости производственных процессов; в физике, химии и биологии для моделирования разнообразных явлений; в области игр для моделирования искусственного интеллекта, например, в китайской игре го; в области финансов для оценки производных финансовых инструментов и опционов. По сути, метод Монте-Карло используется везде.
Современный вариант метода сформировался в рамках Манхэттенского проекта, где он применялся для моделирования расстояний, которые могут пройти нейтроны в различных материалах. Идея моделирования на основе генерации набора случайных значений существовала уже в течение некоторого времени, но особое развитие получила при создании атомной бомбы, распространившись затем во многих других областях знаний.
Большим преимуществом метода Монте-Карло является то, что он позволяет учесть в модели элемент случайности и сложность реального мира. Кроме того, метод является робастным по отношению к изменению различных параметров, таких как распределение случайной величины. В его основе лежит закон больших чисел.
Одним из типичных примеров использования метода Монте-Карло являются задачи, в которых необходимо найти математическое ожидание некоторой случайной величины. Для этого нужно сгенерировать набор случайных значений данной величины и найти среднее. Случайная величина обычно характеризуется определенным распределением вероятностей.
Вычисление числа Пи
С помощью метода Монте-Карло можно вычислить число Пи. Код на R для данного примера находится здесь.
Вписав круг в квадрат (диаметр круга равен стороне квадрата), можно выразить отношение площади круга к площади квадрата следующим образом:
Если мы сможем вычислить это отношение, значит, мы сможем получить значение числа Пи.
Заполним квадрат точками со случайными координатами. Рассчитаем отношение количества точек, попавших в круг, к общему количеству точек. Умножим результат на 4, чтобы получить значение числа Пи.
Чем больше количество точек, тем ближе полученное значение к истинному значению числа Пи.
Этот простой пример демонстрирует метод Монте-Карло в действии.
Моделирование транспортных потоков
Рассмотрим более полезный пример. Мы можем смоделировать транспортный поток с помощью модели Нагеля-Шрекенберга (Nagel-Schreckenberg model). В рамках этой модели трасса состоит из ячеек, задана максимально допустимая скорость и определенное количество автотранспортных средств (АТС). На каждом шаге состояние всех АТС обновляется в соответствии со следующими правилами:
- Скорость данного АТС v увеличивается на единицу, если она меньше максимально допустимой скорости.
- Найдем расстояние d между данным АТС и впереди идущим АТС. Если скорость данного АТС больше либо равна расстоянию d, она уменьшается до величины d-1.
- С помощью метода Монте-Карло добавим элемент случайности. С вероятностью p скорость данного АТС уменьшается на единицу.
- Данное АТС перемещается вперед на v единиц.
Эта модель достаточно проста, но при этом очень эффективна. В данной модели не учитываются ДТП или плохое вождение. Ее назначением является моделирование спонтанных изменений в характере транспортных потоков. Существуют и более сложные модели, но многие из них основаны на модели Нагеля-Шрекенберга.
Код для моделирования находится здесь, а для визуализации на языке Processing – здесь.
Проблемы в рамках метода Монте-Карло
Основной проблемой является генерация независимых случайных величин. Это не такая простая задача, как может показаться на первый взгляд. В примерах кода мы просто вызывали встроенные функции R или Python для генерации случайных чисел, но этот процесс может быть намного более сложным. При необходимости вы можете обратиться к научным источникам по данной теме.
По этой ссылке вы можете найти информацию о том, как в R осуществляется генерация случайных чисел с равномерным распределением (uniform distribution).
Другая проблема состоит в том, как обеспечить сходимость ошибки. Обратите внимание на то, что в примере вычисления числа Пи ошибка перестала уменьшаться. В большинстве приложений метода Монте-Карло для решения этой проблемы используются очень большие выборки.
Метод Монте-Карло – очень интересная тема для изучения. Надеюсь, данная статья сделает этот метод еще более популярным за пределами сферы физики и финансов.
По материалам: Analyticbridge
Метод монте-карло используется как один из примеров тестовых задач проверки рабостопосбности кластера Apache Hadoop