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

редактировать
Не путать с алгоритмом Монте-Карло.

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

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

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

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

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

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

СОДЕРЖАНИЕ
  • 1 Обзор
  • 2 История
  • 3 Определения
    • 3.1 Монте-Карло и случайные числа
    • 3.2 Моделирование Монте-Карло в сравнении со сценариями "что, если"
  • 4 Приложения
    • 4.1 Физические науки
    • 4.2 Инженерия
    • 4.3 Изменение климата и радиационное воздействие
    • 4.4 Вычислительная биология
    • 4.5 Компьютерная графика
    • 4.6 Прикладная статистика
    • 4.7 Искусственный интеллект для игр
    • 4.8 Дизайн и визуальные эффекты
    • 4.9 Поиск и спасание
    • 4.10 Финансы и бизнес
    • 4.11 Закон
  • 5 Использование в математике
    • 5.1 Интеграция
    • 5.2 Моделирование и оптимизация
    • 5.3 Обратные задачи
    • 5.4 Философия
  • 6 См. Также
  • 7 ссылки
    • 7.1 Цитаты
    • 7.2 Источники
  • 8 Внешние ссылки
Обзор

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

  1. Определите область возможных входов
  2. Генерация входных данных случайным образом из распределения вероятностей по области
  3. Выполните детерминированное вычисление на входах
  4. Сгруппируйте результаты
Метод Монте-Карло применяется для аппроксимации значения π.

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

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

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

Есть два важных момента:

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

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

История

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

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

В конце 1940-х годов Станислав Улам изобрел современную версию метода Монте-Карло с цепью Маркова, когда работал над проектами ядерного оружия в Национальной лаборатории Лос-Аламоса. Сразу после прорыва Улама Джон фон Нейман осознал его важность. Фон Нейман запрограммировал компьютер ENIAC для выполнения расчетов методом Монте-Карло. В 1946 году физики-ядерщики из Лос-Аламоса исследовали диффузию нейтронов в делящемся материале. Несмотря на наличие большинства необходимых данных, таких как среднее расстояние, которое нейтрон пройдет в веществе до столкновения с атомным ядром, и сколько энергии нейтрон, вероятно, выделит после столкновения, физики из Лос-Аламоса не смогли решить проблема с использованием обычных, детерминированных математических методов. Улам предложил использовать случайные эксперименты. Он так описывает свое вдохновение:

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

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

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

Теория более сложных методов Монте-Карло частиц типа среднего поля, безусловно, началась к середине 1960-х годов с работы Генри П. Маккина-младшего по марковским интерпретациям класса нелинейных параболических уравнений в частных производных, возникающих в механике жидкости. Мы также процитируем более раннюю новаторскую статью Теодора Э. Харриса и Германа Кана, опубликованную в 1951 году, в которой использовались методы Монте-Карло генетического типа среднего поля для оценки энергии прохождения частиц. Методологии Монте-Карло генетического типа среднего поля также используются в качестве эвристических алгоритмов естественного поиска (также известных как метаэвристические ) в эволюционных вычислениях. Истоки этих вычислительных методов среднего поля можно проследить до 1950 и 1954 годов, благодаря работам Алана Тьюринга об обучающих машинах с отбором мутаций по генетическому типу и статьям Нильса Алла Барричелли из Института перспективных исследований в Принстоне, штат Нью-Джерси.

Квантовый Монте - Карло, и более конкретно диффузии методом Монте - Карло методы также могут быть интерпретированы как среднего поля частиц методом Монте - Карло приближении Фейнман - Каца интегралов по траекториям. Истоки методов квантового Монте-Карло часто приписывают Энрико Ферми и Роберту Рихтмайеру, которые в 1948 году разработали интерпретацию цепных нейтронных реакций частицами среднего поля, но первый алгоритм частиц, подобный эвристическому и генетическому (также известный как Resampled или Reconfiguration Monte Carlo методов) для оценки энергий основного состояния квантовых систем (в моделях сокращенных матриц) был разработан Джеком Х. Хетерингтоном в 1984 г. 1955 г. с плодотворной работой Маршалла Н. Розенблут и Арианны В. Розенблут.

Использование последовательного Монте-Карло для расширенной обработки сигналов и байесовского вывода появилось совсем недавно. В 1993 году Гордон и др. Опубликовали в своей основополагающей работе первое применение алгоритма повторной выборки Монте-Карло для байесовского статистического вывода. Авторы назвали свой алгоритм «бутстрап-фильтром» и продемонстрировали, что по сравнению с другими методами фильтрации их самонастраивающийся алгоритм не требует каких-либо предположений относительно этого пространства состояний или шума системы. Мы также цитируем другую новаторскую статью в этой области Генширо Китагавы о родственном «фильтре Монте-Карло», а также статьи Пьера Дель Мораля и Химилькона Карвалью, Пьера Дель Мораля, Андре Монена и Жерара Салю о фильтрах частиц, опубликованные в середине 1990-х годов.. Фильтры частиц также были разработаны в области обработки сигналов в 1989–1992 гг. П. Дель Мораль, Дж. К. Нойер, Г. Ригал и Г. Салют в LAAS-CNRS в серии закрытых и засекреченных исследовательских отчетов с STCAN (Service Technique des Constructions). et Armes Navales), ИТ-компании DIGILOG и LAAS-CNRS (Лаборатория анализа и архитектуры систем) по проблемам обработки сигналов радара / гидролокатора и GPS. Эти методики последовательного Монте-Карло можно интерпретировать как пробоотборник для приемки-отбраковки, оснащенный взаимодействующим механизмом рециркуляции.

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

В конце 1990-х годов Дэном Крисаном, Джессикой Гейнс и Терри Лайонс, а также Дэном Крисаном, Пьером Дель Моралем и Терри Лайонсом были разработаны методологии частиц ветвящегося типа с различными размерами населения. Дальнейшие разработки в этой области были разработаны в 2000 г. П. Дель Мораль, А. Гионне и Л. Микло.

Определения

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

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

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

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

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

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

Савиловский перечисляет характеристики высококачественного моделирования Монте-Карло:

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

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

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

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

Моделирование Монте-Карло в сравнении со сценариями "что, если"

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

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

Приложения

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

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

Смотрите также: метод Монте-Карло в статистической физике

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

Инженерное дело

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

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

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

Функция плотности вероятности (PDF) ERF из-за общего ПГ, аэрозольного воздействия и общего антропогенного воздействия. ПГ состоит из WMGHG, озона и водяного пара в стратосфере. PDF генерируются на основе неопределенностей, представленных в таблице 8.6. Комбинация отдельных радиочастотных агентов для получения общего принуждения в индустриальную эпоху выполняется с помощью моделирования методом Монте-Карло и основывается на методе, описанном Баучером и Хейвудом (2001). PDF ERF от изменений поверхностного альбедо и комбинированных инверсионных следов и перистых следов, вызванных инверсионным следом, включены в общее антропогенное воздействие, но не показаны в виде отдельного PDF. В настоящее время у нас нет оценок ERF для некоторых механизмов воздействия: озона, землепользования, солнечной энергии и т. Д.

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

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

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

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

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

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

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

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

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

Основная статья: поиск дерева Монте-Карло

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

Метод поиска по дереву Монте-Карло (MCTS) состоит из четырех этапов:

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

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

Поиск по дереву Монте-Карло успешно использовался в таких играх, как Go, Tantrix, Battleship, Havannah и Arimaa.

См. Также: Computer Go

Дизайн и визуальные эффекты

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

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

Береговая охрана США использует методы Монте - Карло в рамках его компьютерного моделирования программного обеспечения SAROPS для расчета вероятных местоположения судов во время поисково-спасательных операций. Каждое моделирование может генерировать до десяти тысяч точек данных, которые случайным образом распределяются на основе предоставленных переменных. Затем на основе экстраполяции этих данных генерируются шаблоны поиска для оптимизации вероятности сдерживания (POC) и вероятности обнаружения (POD), которые вместе будут равны общей вероятности успеха (POS). В конечном итоге это служит практическим применением распределения вероятностей, чтобы обеспечить самый быстрый и наиболее целесообразный метод спасения, спасая как жизни, так и ресурсы.

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

См. Также: методы Монте-Карло в финансах, методы квази-Монте-Карло в финансах, методы Монте-Карло для ценообразования опционов, стохастическое моделирование (страхование) и стохастическая модель активов.

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

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

Закон

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

Использование в математике

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

Интеграция

Основная статья: интеграция Монте-Карло Интеграция Монте-Карло работает путем сравнения случайных точек со значением функции. Ошибки уменьшаются в раз 1 / N {\ displaystyle \ scriptstyle 1 / {\ sqrt {N}}}

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

Методы Монте-Карло позволяют избежать этого экспоненциального увеличения времени вычислений. Пока рассматриваемая функция ведет себя достаточно хорошо, ее можно оценить путем случайного выбора точек в 100-мерном пространстве и взятия некоторого среднего значения значений функции в этих точках. Согласно центральной предельной теореме, этот метод отображает сходимость, т. Е. Учетверение количества точек выборки вдвое уменьшает ошибку, независимо от количества измерений. 1 / N {\ displaystyle \ scriptstyle 1 / {\ sqrt {N}}}

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

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

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

Моделирование и оптимизация

Основная статья: Стохастическая оптимизация

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

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

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

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

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

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

Философия

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

Смотрите также
использованная литература

Цитаты

Источники

внешние ссылки
  • СМИ, связанные с методом Монте-Карло на Викискладе?
Последняя правка сделана 2023-03-19 06:00:41
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте