Метод Монте-Карло: алгоритм и применение — Gamblipedia

Вероятностный алгоритм решения задач

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

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

Обзор

Название происходит от казино Монте-Карло в Монако, где основной разработчик метода, математик Станислав Улам (Stanisław Ulam), вдохновился привычками своего дяди к азартным играм. Методы Монте-Карло широко используются в различных областях науки, техники и математики: физике, химии, биологии, статистике, искусственном интеллекте, финансах и криптографии. Они также применяются в социальных науках — социологии, психологии и политологии. Методы Монте-Карло признаны одной из самых важных и влиятельных идей XX века, благодаря которым произошли многие научные и технологические прорывы.

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

• Определить область возможных входных данных
• Сгенерировать входные данные случайно из распределения вероятностей над этой областью
• Выполнить детерминированное вычисление выходных данных
• Агрегировать результаты

Например, рассмотрим квадрант, вписанный в единичный квадрат. Поскольку отношение их площадей равно π/4, значение π можно приблизить методом Монте-Карло:

• Нарисовать квадрат и вписать в него квадрант
• Равномерно разбросать заданное количество точек по квадрату
• Подсчитать количество точек внутри квадранта (на расстоянии менее 1 от начала координат)
• Отношение количества точек внутри к общему количеству точек приблизительно равно π/4. Умножить результат на 4, чтобы получить приближение π

В этой процедуре область входных данных — это квадрат, описанный вокруг квадранта. Случайные входные данные можно генерировать, разбрасывая зёрна по квадрату, а затем проверяя каждую точку. Агрегирование результатов даёт приближение π. Здесь важны два момента:

• Если точки распределены неравномерно, приближение будет неточным
• Приближение улучшается по мере добавления большего количества случайных точек

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

Применение

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

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

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

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

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

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

Простой метод Монте-Карло

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

Типичный алгоритм для получения m:

«`

s = 0

для i = 1 до n:

запустить симуляцию i раз, получить результат r

s = s + r

m = s / n

«`

Примеры

Предположим, нужно узнать, сколько раз в среднем нужно бросить три восьмигранных кубика, чтобы сумма была не менее T. Известно, что математическое ожидание существует, броски независимы и случайны. Поэтому применим простой метод Монте-Карло:

«`

s = 0

для i = 1 до n:

бросать три кубика до достижения или превышения T; r = количество бросков

s = s + r

m = s / n

«`

При достаточно большом n значение m будет в пределах ε от μ для любого ε > 0.

Определение достаточно большого n

Общая формула

Пусть ε = |μ — m| > 0. Выбрать желаемый уровень доверия — процент вероятности того, что по завершении алгоритма Монте-Карло значение m действительно находится в пределах ε от μ. Пусть z — z-оценка, соответствующая этому уровню доверия.

Пусть s² — оценённая дисперсия, иногда называемая «выборочной» дисперсией; это дисперсия результатов, полученных из относительно небольшого количества k «пробных» симуляций. Выбрать k; исследователи отмечают, что даже при размерах выборки на порядок меньше требуемого расчёт этого числа остаётся довольно стабильным. Следующий алгоритм вычисляет s² за один проход, минимизируя вероятность накопления численных ошибок:

«`

s = 0

запустить симуляцию в первый раз, получить результат r

m = r

для i = 2 до k:

запустить симуляцию i раз, получить результат r

δ = r — m

m = m + (1/i)δ

s = s + ((i — 1)/i)δ²

s = s / (k — 1)

«`

По завершении алгоритма m_k — это среднее k результатов.

Значение n достаточно велико, когда:

n ≥ s²z² / ε²

Если n ≤ k, то m_k = m; было выполнено достаточно пробных симуляций, чтобы гарантировать, что m_k находится в пределах ε от μ. Если n > k, то можно запустить n симуляций «с нуля» или, поскольку k симуляций уже выполнено, просто запустить ещё n — k симуляций и добавить их результаты к результатам пробных симуляций.

Формулы для результатов симуляций с границами

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

Выбрать значение ε, равное удвоенной максимально допустимой разнице между μ и m. Пусть 0 < δ < 100 — желаемый уровень доверия, выраженный в процентах. Пусть каждый результат симуляции r₁, r₂, ..., r_n удовлетворяет условию a ≤ r_i ≤ b для конечных a и b. Чтобы иметь уверенность не менее δ в том, что |μ - m| < ε/2, используйте значение n такое, что:

n ≥ 2(b — a)² ln(2 / (1 — (δ/100))) / ε²

Например, если δ = 99%, то n ≥ 2(b — a)² ln(2 / 0.01) / ε² ≈ 10.6(b — a)² / ε².

Вычислительные затраты

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

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

История

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

Ранний вариант метода Монте-Карло был разработан для решения задачи Бюффона об игле, в которой π можно оценить, бросая иглы на пол, сделанный из параллельных равноудалённых полос. В 1930-х годах Энрико Ферми (Enrico Fermi) впервые экспериментировал с методом Монте-Карло при изучении диффузии нейтронов, но не опубликовал эту работу.

В конце 1940-х годов Станислав Улам изобрёл современную версию метода цепей Маркова Монте-Карло, работая над проектами ядерного оружия в Лос-Аламосской национальной лаборатории. В 1946 году физики ядерного оружия в Лос-Аламосе исследовали диффузию нейтронов в ядре ядерного оружия.

Несмотря на наличие большей части необходимых данных, таких как среднее расстояние, которое нейтрон проходит в веществе перед столкновением с атомным ядром, и количество энергии, которое нейтрон, вероятно, отдаст после столкновения, физики Лос-Аламоса не смогли решить задачу, используя традиционные детерминированные математические методы. Улам предложил использовать случайные эксперименты. Вот как он описывает своё вдохновение:

«Первые мысли и попытки, которые я предпринял, были подсказаны вопросом, который пришёл мне в голову в 1946 году, когда я выздоравливал от болезни и играл в пасьянс. Вопрос был: какова вероятность того, что пасьянс «Канфилд», разложенный из 52 карт, выйдет успешно? После того как я потратил много времени, пытаясь оценить это с помощью чистых комбинаторных расчётов, я подумал, не будет ли более практичным методом, чем «абстрактное мышление», просто разложить его, скажем, сто раз и просто наблюдать и подсчитать количество успешных раскладов. Это уже было возможно представить с началом новой эры быстрых компьютеров, и я сразу же подумал о задачах диффузии нейтронов и других вопросах математической физики, и в более общем смысле о том, как преобразовать процессы, описываемые определёнными дифференциальными уравнениями, в эквивалентную форму, интерпретируемую как последовательность случайных операций. Позже я описал эту идею Джону фон Нейману, и мы начали планировать фактические расчёты».

Поскольку работа была засекречена, фон Нейман и Улам нуждались в кодовом названии. Коллега фон Неймана и Улама Николас Метрополис (Nicholas Metropolis) предложил использовать название Монте-Карло, которое относится к казино Монте-Карло в Монако, где дядя Улама занимал деньги у родственников для азартных игр.

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

В 1950-х годах методы Монте-Карло использовались в Лос-Аламосе для разработки водородной бомбы и получили распространение в физике, физической химии и исследовании операций. Корпорация RAND и ВВС США были двумя основными организациями, ответственными за финансирование и распространение информации о методах Монте-Карло в этот период, и методы начали находить широкое применение в различных областях.

Теория более сложных методов частиц Монте-Карло типа среднего поля, несомненно, началась в середине 1960-х годов с работы Генри П. Маккина-младшего (Henry P. McKean Jr.) по интерпретациям Маркова класса нелинейных параболических дифференциальных уравнений в частных производных, возникающих в механике жидкости. Более ранняя пионерская статья Теодора Э. Харриса (Theodore E. Harris) и Германа Кана (Herman Kahn), опубликованная в 1951 году, использовала методы Монте-Карло генетического типа среднего поля для оценки энергий передачи частиц.

Методы Монте-Карло генетического типа среднего поля также используются как эвристические алгоритмы естественного поиска (метаэвристики) в эволюционных вычислениях. Истоки этих методов среднего поля можно проследить до 1950 и 1954 годов с работой Алана Тьюринга (Alan Turing) по машинам обучения генетического типа с мутацией-селекцией и статьями Нильса Ола Барричелли (Nils Aall Barricelli) в Институте перспективных исследований в Принстоне, Нью-Джерси.

Квантовый метод Монте-Карло, и более конкретно методы диффузионного Монте-Карло, также можно интерпретировать как приближение методом частиц среднего поля интегралов по путям Фейнмана-Каца. Истоки квантовых методов Монте-Карло часто приписывают Энрико Ферми и Роберту Рихтмайеру (Robert Richtmyer), которые разработали в 1948 году интерпретацию частиц среднего поля цепных реакций нейтронов, но первый эвристический алгоритм генетического типа частиц (методы переэвристического или переконфигурационного Монте-Карло) для оценки энергий основного состояния квантовых систем принадлежит Джеку Х. Хезерингтону (Jack H. Hetherington) в 1984 году. В молекулярной химии использование методов частиц генетического типа (стратегии обрезки и обогащения) можно проследить до 1955 года с основополагающей работой Маршалла Н. Розенблюта (Marshall N. Rosenbluth) и Арианны В. Розенблюта (Arianna W. Rosenbluth).

Использование последовательного метода Монте-Карло в продвинутой обработке сигналов и байесовском выводе более недавнее. В 1993 году Гордон и др. опубликовали в своей основополагающей работе первое применение алгоритма переэвристического Монте-Карло в байесовском статистическом выводе. Авторы назвали свой алгоритм «фильтром начальной загрузки» и продемонстрировали, что в отличие от других методов фильтрации их алгоритм не требует никаких предположений о пространстве состояний или шуме системы. Другая пионерская статья в этой области принадлежит Генширо Китагаве (Genshiro Kitagawa) о связанном «фильтре Монте-Карло» и статьям Пьера Дель Морала (Pierre Del Moral) и Химилькона Карвалью (Himilcon Carvalho), Пьера Дель Морала, Андре Монина (André Monin) и Жерара Салю (Gérard Salut) о фильтрах частиц, опубликованным в середине 1990-х годов. Фильтры частиц также были разработаны в обработке сигналов в 1989–1992 годах П. Дель Моралем, Дж. К. Нойером, Г. Ригалем и Г. Салютом в LAAS-CNRS в серии ограниченных и засекреченных исследовательских отчётов с STCAN, IT-компанией DIGILOG и LAAS-CNRS по проблемам обработки сигналов радара/сонара и GPS. Эти методы последовательного Монте-Карло можно интерпретировать как сэмплер принятия-отклонения, оснащённый механизмом интерактивной переработки.

С 1950 по 1996 год все публикации по методологиям последовательного Монте-Карло, включая методы обрезки и переэвристического Монте-Карло, введённые в вычислительной физике и молекулярной химии, представляли естественные и эвристические алгоритмы, применённые к различным ситуациям без единого доказательства их согласованности или обсуждения смещения оценок и алгоритмов, основанных на генеалогических и предковых деревьях. Математические основы и первый строгий анализ этих алгоритмов частиц были написаны Пьером Дель Моралем в 1996 году.

Методологии частиц ветвящегося типа с переменными размерами популяций также были разработаны в конце 1990-х годов Дэном Крисаном (Dan Crisan), Джессикой Гейнс (Jessica Gaines) и Терри Лайонсом (Terry Lyons), а также Дэном Крисаном, Пьером Дель Моралем и Терри Лайонсом. Дальнейшие разработки в этой области были описаны в 1999–2001 годах П. Дель Моралем, А. Гионне (A. Guionnet) и Л. Микло (L. Miclo).

Определения

Нет единого мнения о том, как следует определять метод Монте-Карло. Например, Рипли определяет большинство вероятностного моделирования как стохастическую симуляцию, оставляя метод Монте-Карло для интегрирования Монте-Карло и статистических тестов Монте-Карло. Сэвилоуски различает симуляцию, метод Монте-Карло и симуляцию Монте-Карло: симуляция — это вымышленное представление реальности, метод Монте-Карло — это техника, которая может быть использована для решения математической или статистической задачи. Симуляция Монте-Карло использует повторную выборку для получения статистических свойств некоторого явления. Вот несколько примеров:

• Симуляция: Рисование одного псевдослучайного равномерного числа из интервала [0, 1] можно использовать для симуляции подбрасывания монеты: если значение ≤ 0,50, результат — орёл, если > 0,50 — решка. Это симуляция, но не симуляция Монте-Карло.
• Метод Монте-Карло: Высыпание коробки монет на стол и подсчёт отношения монет, упавших орлом к решке, — это метод Монте-Карло определения поведения повторных подбрасываний монеты, но это не симуляция.
• Симуляция Монте-Карло: Рисование большого количества псевдослучайных равномерных чисел из интервала [0, 1] одновременно или в разные моменты времени и присвоение значений ≤ 0,50 как орлов и > 0,50 как решек — это симуляция Монте-Карло поведения повторных подбрасываний монеты.

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

Метод Монте-Карло и случайные числа

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

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

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

• Генератор (псевдослучайных) чисел имеет определённые характеристики (например, длинный «период» перед повторением последовательности)
• Генератор (псевдослучайных) чисел производит значения, которые проходят тесты на случайность
• Достаточно выборок для обеспечения точных результатов
• Используется правильная техника выборки
• Используемый алгоритм действителен для моделируемого явления
• Он симулирует рассматриваемое явление

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

В попытке оценить влияние качества случайных чисел на результаты симуляции Монте-Карло астрофизические исследователи тестировали криптографически защищённые псевдослучайные числа, генерируемые набором инструкций Intel RDRAND, в сравнении с числами, полученными из алгоритмов, таких как Mersenne Twister, в симуляциях Монте-Карло радиовспышек от коричневых карликов. Статистически значимой разницы между моделями, созданными с использованием типичных генераторов псевдослучайных чисел и RDRAND для испытаний, состоящих из генерации 10 случайных чисел, не было обнаружено.

Симуляция Монте-Карло в сравнении со сценариями «что если»

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

В отличие от этого, симуляции Монте-Карло выбирают из распределения вероятностей для каждой переменной, чтобы получить сотни или тысячи возможных результатов. Результаты анализируются для получения вероятностей различных исходов. Например, сравнение модели построения стоимости электронной таблицы, выполненной с использованием традиционных сценариев «что если», а затем повторное сравнение с симуляцией Монте-Карло и треугольными распределениями вероятностей показывает, что анализ Монте-Карло имеет более узкий диапазон, чем анализ «что если». Это потому, что анализ «что если» придаёт равный вес всем сценариям, в то время как метод Монте-Карло редко выбирает в регионах с очень низкой вероятностью. Выборки в таких регионах называются «редкими событиями».

Приложения

Методы Монте-Карло особенно полезны для симуляции явлений с существенной неопределённостью входных данных и систем с множеством связанных степеней свободы. Области применения включают:

Физические науки

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

Статистическая физика

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

Радиационная материаловедение

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

Инженерия

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

• В микроэлектронной инженерии методы Монте-Карло применяются для анализа коррелированных и некоррелированных вариаций в аналоговых и цифровых интегральных схемах.
• В геостатистике и геометаллургии методы Монте-Карло лежат в основе проектирования схем переработки полезных ископаемых и способствуют количественному анализу рисков.
• В гидродинамике, особенно в динамике разреженного газа, где уравнение Больцмана решается для потоков жидкости с конечным числом Кнудсена, используется метод прямого моделирования Монте-Карло в сочетании с высокоэффективными вычислительными алгоритмами.
• В автономной робототехнике локализация Монте-Карло может определить положение робота. Часто применяется к стохастическим фильтрам, таким как фильтр Калмана или фильтр частиц, которые составляют основу алгоритма SLAM (одновременная локализация и картирование).
• В телекоммуникациях при планировании беспроводной сети проект должен быть доказан для работы в широком диапазоне сценариев, которые в основном зависят от количества пользователей, их местоположения и услуг, которые они хотят использовать. Методы Монте-Карло обычно используются для генерации этих пользователей и их состояний. Затем оценивается производительность сети, и если результаты неудовлетворительны, проект сети проходит процесс оптимизации.
• В инженерии надёжности симуляция Монте-Карло используется для вычисления системного отклика с учётом компонентного отклика.
• В обработке сигналов и байесовском выводе фильтры частиц и методы последовательного Монте-Карло — это класс методов частиц среднего поля для выборки и вычисления апостериорного распределения сигнального процесса с учётом некоторых зашумленных и частичных наблюдений, используя взаимодействующие эмпирические меры.

Изменение климата и радиационное воздействие

Межправительственная группа экспертов по изменению климата полагается на методы Монте-Карло при анализе функции плотности вероятности радиационного воздействия.

Вычислительная биология

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

Системы можно изучать в грубозернистой или ab initio схемах в зависимости от желаемой точности. Компьютерные симуляции позволяют отслеживать локальное окружение конкретной молекулы, чтобы увидеть, происходит ли какая-либо химическая реакция. В случаях, когда невозможно провести физический эксперимент, можно провести мысленные эксперименты, например разрыв связей, введение примесей в определённые места, изменение локальной/глобальной структуры или введение внешних полей.

Компьютерная графика

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

Прикладная статистика

Стандарты для экспериментов Монте-Карло в статистике установлены Сэвилоуски. В прикладной статистике методы Монте-Карло могут использоваться по крайней мере для четырёх целей:

• Для сравнения конкурирующих статистик на малых выборках в реалистичных условиях данных. Хотя свойства ошибки типа I и мощности статистики можно вычислить для данных, полученных из классических теоретических распределений (например, нормальное распределение, распределение Коши) при асимптотических условиях (то есть бесконечный размер выборки и бесконечно малый эффект лечения), реальные данные часто не имеют таких распределений.
• Для предоставления реализаций тестов гипотез, которые более эффективны, чем точные тесты, такие как тесты перестановок (которые часто невозможно вычислить), при этом будучи более точными, чем критические значения для асимптотических распределений.
• Для предоставления случайной выборки из апостериорного распределения в байесовском выводе. Эта выборка затем приблизительно и суммирует все существенные особенности апостериорного распределения.
• Для предоставления эффективных случайных оценок матрицы Гессиана функции отрицательного логарифма правдоподобия, которые могут быть усреднены для формирования оценки информационной матрицы Фишера.

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

Искусственный интеллект для игр

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

• Начиная с корневого узла дерева, выбирать оптимальные дочерние узлы до достижения листового узла.
• Развернуть листовой узел и выбрать один из его дочерних узлов.
• Сыграть симулированную игру, начиная с этого узла.
• Использовать результаты этой симулированной игры для обновления узла и его предков.

Чистый эффект в ходе множества симулированных игр заключается в том, что значение узла, представляющего ход, будет расти или падать, надеюсь, соответствуя тому, является ли этот узел хорошим ходом. Поиск дерева Монте-Карло успешно использовался для игры в такие игры, как го, Tantrix, Battleship, Havannah и Arimaa.

Дизайн и визуализация

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

Поиск и спасение

Береговая охрана США использует методы Монте-Карло в своём компьютерном программном обеспечении для моделирования SAROPS для расчёта вероятных местоположений судов во время операций поиска и спасения. Каждая симуляция может генерировать до десяти тысяч точек данных, которые случайно распределены на основе предоставленных переменных.

Затем на основе экстраполяции этих данных генерируются схемы поиска для оптимизации вероятности локализации (POC) и вероятности обнаружения (POD), которые вместе равны общей вероятности успеха (POS). В конечном итоге это служит практическим применением распределения вероятностей для обеспечения самого быстрого и эффективного метода спасения, спасая как жизни, так и ресурсы.

Финансы и бизнес

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

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

Право

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

Библиотечное дело

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

Прочее

Нассим Николас Талеб пишет о генераторах Монте-Карло в своей книге 2001 года «Одураченные случайностью» как о реальном примере обратного теста Тьюринга: человека можно объявить неразумным, если его письмо невозможно отличить от сгенерированного.

Математические приложения

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

Интегрирование

Детерминированные алгоритмы численного интегрирования хорошо работают в небольшом количестве измерений, но сталкиваются с двумя проблемами, когда функции имеют много переменных. Во-первых, количество вычислений функции, необходимых для быстрого увеличения с количеством измерений. Например, если 10 вычислений обеспечивают адекватную точность в одном измерении, то для 100 измерений требуется 10¹⁰⁰ точек — слишком много для вычисления. Это называется проклятием размерности. Во-вторых, граница многомерной области может быть очень сложной, поэтому может быть невозможно свести задачу к повторному интегралу. 100 измерений — это отнюдь не необычно, так как во многих физических задачах «измерение» эквивалентно степени свободы.

Методы Монте-Карло предоставляют выход из этого экспоненциального увеличения времени вычисления. Пока функция в вопросе ведёт себя достаточно хорошо, её можно оценить, случайно выбирая точки в 100-мерном пространстве и беря некоторый вид среднего значений функции в этих точках. По центральной предельной теореме этот метод показывает сходимость 1/√N — то есть увеличение в четыре раза количества выбранных точек уменьшает ошибку вдвое, независимо от количества измерений.

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

Похожий подход, метод квази-Монте-Карло, использует последовательности с низкой дискрепантностью. Эти последовательности «заполняют» область лучше и выбирают наиболее важные точки чаще, поэтому методы квази-Монте-Карло часто могут быстрее сходиться к интегралу. Другой класс методов для выборки точек в объёме — это симуляция случайных блужданий над ним (цепь Маркова Монте-Карло). Такие методы включают алгоритм Метрополиса-Гастингса, выборку Гиббса, алгоритм Ванга и Ландау, и методы MCMC взаимодействующего типа, такие как сэмплеры последовательного Монте-Карло.

Симуляция и оптимизация

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

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

Обратные задачи

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

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

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

Философия

Популярное изложение метода Монте-Карло было проведено МакКракеном. Общая философия метода обсуждалась Элишаковым и Грюне-Яноффом и Вейричем.