Метод Монте-Карло

916
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
  • Название: Метод Монте–Карло (Method Monte-Karlo — MMK);
  • Применение: Разыгрывание многократных случайных событий;
  • Сложность: Средняя;
  • Входные данные: Набор случайных чисел (нормально распределенных);
  • Результат: Вероятность возникновения, приблизительная оценка результата.

Пример из жизни:

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

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

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

Остается понять как получить этот, по сути, аналитический результат? Можно составить сложную систему дифференциальных уравнений и попробовать рассчитать решение. Но это очень сложно, тем более, когда ничего не известно или мало данных о самом процессе. Есть другой способ отказаться от этих сложных вычислений и просто провести многократные наблюдения. Но как проводить наблюдения? и какое количество необходимо? На эти вопросы поможет ответить довольно популярный метод — разыгрывания многократных случайных событий, названный в честь известного города, Монте-Карло. Как видно, данный класс задач может охватывать большую предметную область: от решения математических задач (вычисления интегралов или площади сложной фигуры) до прикладных (имитация различных сложных процессов или явлений). Последние могут применяться: в экономике (моделирование инфляции, объема сбыта, налогов и т.д.), физике (имитация ядерных реакций, сложных процессов и т.д.), математике (вычисление интегралов, дифференциальных уравнений, оптимизации, аппроксимации и т.д.) и др.

Годом рождения метода Монте-Карло считается 1949 год, когда в свет выходит статья Метрополиса и Улама «Метод Монте-Карло». Название метода происходит от названия коммуны в княжестве Монако, широко известного своими многочисленными казино, поскольку именно рулетка является одним из самых широко известных генераторов случайных чисел. Станислав Улам пишет в своей автобиографии «Приключения математика», что название было предложено Николасом Метрополисом в честь его дяди, который был азартным игроком.

Постановка задачи:

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

Лингвистическое описание алгоритма:

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

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

Шаг 1. Определяются области применения случайных величин в рамках задачи;

Шаг 2. Разыгрывается случайная величина и используется в расчетах задачи;

Шаг 3. Многократное повторение расчетов задачи и сохранение «успешных» результатов;

Шаг 4. Оценка полученного решения.

Алгоритм Бюффона использует ММК для определения числа Пи = 3.1214… с помощью разыгрывания случайной величины бросанием иголки в определенную область. Так  ММК раскрывает не очевидные на первый взгляд вещи. Например, из группы 30 человек с вероятностью свыше 70% дни рождения совпадут как минимум у двоих человек.

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

Реализация:

Вычисление площади сложной фигуры:

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

внешнее множество

 

 

+

внутреннее множество

 

 

=

 

Представим, что на внешнее множество кидаются в точки (координаты) точки. Соответственно, некоторые из этих точек попадут и во внутреннее множество. По теории вероятностей  — вероятность попадания во внутреннюю область = n (точки попали в область)/N (общее количество точек).

Площадь внутренней области/Площадь внешней области ≈ Число точек во внутренней области/Число всех точек ≈ n/N или

Площадь внутренней области ≈ Число точек во внутренней области * Площадь внешней области / Число всех точек

Причем, как правило, число всех точек известно заранее — это ширина и высота в пикселях т.е. = ширина * высоту (в пикселях), а число точек во внутренней области можно определить следующим образом:

Таким образом, чем больше число точек будет разыграно в процессе выполнения алгоритма, тем точнее будет результат.

Моделирование ситуации:

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

Давайте представим, что у Вашего близкого человека день рождения (юбилей) и опоздать просто нельзя! Таким образом, можно с высокой вероятностью оценить время в пути, а значит предсказать прибытие вовремя. Известно, что дорога занимает 5 условных отрезков в пути [AB (поездка с работы до остановки)->BC (путь от остановки до магазина)->CD (время от посещения магазина до покупки товара в нем)->DE (время пути от выхода из магазина до остановки)->EF (поездка от остановки до дома, где ждет друг)]. Представим путь:

Точно предсказать время в пути не представляется возможным из-за различных обстоятельств (ожидание общественного транспорта, очередь при покупке подарка, пробки и т.д.). Поэтому можно просто заложить риски на тех участках дороги, где это необходимо. Например, примерная оценка времени в пути: от работы до остановки рядом с магазином занимает 10 минут. Но это «идеальное» время — без ожидания общественного транспорта, в то же время известно (по опыту), что максимальное время ожидания составляет примерно 20 мин. Таким образом,  можно просто заложить этот риск с помощью генерации случайных чисел из этого интервала — [0;20]. Соответственно, проигрывая много-много раз эти риски можно получить усредненный случай, который и будет конечным результатом.

Если существует ситуация при которой можно даже прибыть в место назначения раньше, то необходимо и это учитывать. Например, разыгрывание вероятности прибытия в пункт назначения на 10 минут раньше или позже можно представить в виде [-10;10].  Добавлять неопределенность необходимо только к тем участкам пути на которых существуют риски.

После того как риски были учтены наступает момент многократной «прогонки» ситуаций. Результатом будет количество успешные исходов разыгранных событий. Для нормализации этого результата к заданной точности — количество успешных исходов делится на количество всех попыток. На основе этого получается результат в виде вероятности успешного исхода.          

Программная разработка:

Шаг 1. Определяем области применения случайных величин в рамках задачи. Формируем оценку времени без рисков $track. И закладываем риски $delta.

Напишем класс ModelingTrip, который будет воспроизводить имитационные расчеты согласно ММК. Определим свойства, которые понадобятся для дальнейшей работы.

Определим конструктор класса, который принимает время начала и завершения пути. Так же «идеальное» время в минутах и заложенные риски.

Шаг 2. Разыграем случайную величину и используется ее в расчетах задачи. Учитываем риски при рассчете общего времени в пути в минутах. Происходит добавление к участкам пути, где заложены риски случайно сгенерированого значения из интервала. И возврат значения, если не превышает заданного время прибытия.

Шаг 3. Многократное повторение расчетов задачи и сохранение «успешных» результатов. Формируем цикл в рамках которого производим многократное повторение ситуации с разными значениями рисков. Таким образом, если рассчитанное время не превыжает время пребытия (т.е. успеваем), то увеличивает счетчик ($inTime) на единицу. После окончания цикла получаем вероятность успешных исходов собтия (приезд вовремя на ДР).

Шаг 4. Оценка полученного решения. В методе run реализована оценка решения — $this->result[0] = $inTime/$this->countExperiences;

Теперь посмотрим работу данного класса — произведем оценку времени прибытия на день рождения к 18-35.

Результат будет примерно такой:
Вы будите на ДР через: 73 минут ( вероятность события 67 %)
Вероятность прибытия не внушает доверия, здесь вариантов решения задачи много:

  • Оптимизировать маршрут следования — сократить временные интервалы на определенных участках маршрута;
  • Смоделировать другое время и оценить вероятность прибытия;
  • Изменить условия рассчета — изменить риски. Tем самым предложить другой способ решения задачи — взять такси, заказать товар через Интернет и т.д.

Давайте смоделируем другое время прибытия, например заложим не 18:35, а 18:37 и посмотрим какая вероятность прибытия будет теперь.

Обратите внимание — добавили всего 2 минуты, а вероятность уже внушает доверие. Теперь можно смело сказать, что «я буду через: плюс минус две минуты» или чтобы не обижать друга ускорить шаг или даже пробежаться  до подъезда дома.

Выводы:

  • ММК — позволяет получить приближенные решения с приемлемой точностью там, где прямое вычисление слишком сложно или требует большого количества времени;
  • Применяется для широкого спектра задач в различных областях: от экономики до вычислительной математики;
  • Данный метод используется во многих других алгоритмах, например, метод отжига;
  • Простота метода делает его привлекательным для использования во многих сложных задачах, где присутствует случайная составляющая.

Что еще почитать:

Поделиться

Отправить ответ

avatar
wpDiscuz