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

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

Аппроксимация нормального распределения методом Монте-Карло

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

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

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

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

Обзор

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

1. Определите область возможных входных данных
2. Генерируйте входные данные случайным образом из распределения вероятностей по области
3. Выполните детерминированное вычисление выходных данных
4. Обобщить результаты

Метод Монте-Карло, примененный для аппроксимации значения π

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

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

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

Есть два важных соображения:

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

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

Приложение

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

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

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

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

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

затраты

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

История

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

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

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

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

Будучи секретной, работа фон Неймана и Улама требовала кодового названия. Коллега фон Неймана и Улама Николас Метрополис предложил использовать название «Монте-Карло» , которое относится к казино Монте-Карло в Монако, где дядя Улама занимал деньги у родственников, чтобы играть в азартные игры. Методы Монте-Карло играли центральную роль в моделировании, необходимом для Манхэттенского проекта , хотя и были сильно ограничены вычислительными инструментами того времени. Фон Нейман, Николас Метрополис и другие запрограммировали компьютер ENIAC для выполнения первых полностью автоматизированных расчетов Монте-Карло ядра ядерного оружия весной 1948 года. В 1950-е годы методы Монте-Карло были использованы в Лос-Аламосе при разработке водородной бомбы и стали популяризироваться в области физики , физической химии и исследования операций . Корпорация Рэнд и ВВС США были двумя основными организациями, ответственными за финансирование и распространение информации о методах Монте-Карло в то время, и они начали находить широкое применение во многих различных областях.

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

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

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

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

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

Определения

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

Вот примеры:

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

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

Сходимость моделирования Монте-Карло можно проверить с помощью статистики Гельмана-Рубина .

и

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

климата и

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

биология

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск по дереву Монте-Карло успешно использовался для таких игр, как го , Тантрикс , Линкор , Гаванна , и Аримаа .

См. также: Компьютер Go

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

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

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

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

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

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

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

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

Закон

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

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

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

Другое

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

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

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

Интеграция

Основная статья: Интеграция Монте-Карло

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

Ошибки уменьшаются в раз $\scriptstyle 1/{\sqrt {N}}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

Философия

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

См. также

• Вспомогательное поле Монте-Карло
• Биологический метод Монте-Карло
• Прямое моделирование Монте-Карло
• Динамический метод Монте-Карло
• Эргодичность
• Генетические алгоритмы
• Кинетический Монте-Карло
• Список программного обеспечения для молекулярного моделирования Монте-Карло
• Методы частиц среднего поля
• Метод Монте-Карло для транспорта фотонов
• Методы Монте-Карло для электронного транспорта
• Код переноса N-частиц Монте-Карло
• метод Морриса
• Многоуровневый метод Монте-Карло
• Метод квази-Монте-Карло
• Последовательность Соболя
• Обучение временной разнице

Ссылки

Источники

• Андерсон, Герберт Л. (1986). «Метрополис, Монте-Карло и МАНИАК» (PDF) . Лос-Аламосская наука . 14 : 96–108.
• Бенов, Добриян М. (2016). «Манхэттенский проект, первый электронный компьютер и метод Монте-Карло». Методы Монте-Карло и их приложения . 22 (1): 73–79. дои : 10.1515/mcma-2016-0102 . S2CID   30198383 .
• Берле, Стефан А. (2009). «Многомасштабное моделирование полимерных материалов с использованием теоретико-полевых методологий: обзор последних разработок». Журнал математической химии . 46 (2): 363–426. дои : 10.1007/s10910-008-9467-3 . S2CID   117867762 .
• Берг, Бернд А. (2004). Моделирование Монте-Карло марковской цепью и их статистический анализ (с использованием веб-кода на языке Фортран) . Хакенсак, Нью-Джерси: World Scientific. ISBN  978-981-238-935-0 .
• Биндер, Курт (1995). Метод Монте-Карло в физике конденсированного состояния . Нью-Йорк: Спрингер. ISBN  978-0-387-54369-7 .
• Кафлиш, RE (1998). Методы Монте-Карло и квази-Монте-Карло . Акта Нумерика. Том 7. Издательство Кембриджского университета. стр. 1–49.
• Давенпорт, Дж. Х. (1992). «Возвращение к тестированию примитивности». Материалы международного симпозиума по символьным и алгебраическим вычислениям - ISSAC '92 . стр. 123–129. CiteSeerX   10.1.1.43.9296 . дои : 10.1145/143242.143290 . ISBN  978-0-89791-489-5 . S2CID   17322272 .
• Дусе, Арно; Фрейтас, Нандо де; Гордон, Нил (2001). Последовательные методы Монте-Карло на практике . Нью-Йорк: Спрингер. ISBN  978-0-387-95146-1 .
• Экхардт, Роджер (1987). «Стэн Улам, Джон фон Нейман и метод Монте-Карло» (PDF) . Лос-Аламосская наука (15): 131–137.
• Фишман, Г.С. (1995). Монте-Карло: концепции, алгоритмы и приложения . Нью-Йорк: Спрингер. ISBN  978-0-387-94527-9 .
• К. Форастеро, Л. Самора, Д. Гирадо и А. Лаллена (2010). «Инструмент Монте-Карло для моделирования программ скрининга рака молочной железы». Физ. Мед. Биол . 55 (17): 5213–5229. Бибкод : 2010PMB....55.5213F . дои : 10.1088/0031-9155/55/17/021 . ПМИД   20714045 . S2CID   30021759 .
• Голден, Лесли М. (1979). «Влияние шероховатости поверхности на передачу микроволнового излучения через поверхность планеты». Икар . 38 (3): 451–455. Бибкод : 1979Icar...38..451G . дои : 10.1016/0019-1035(79)90199-4 .
• Гулд, Харви; Тобочник, Ян (1988). Введение в методы компьютерного моделирования. Часть 2. Приложения к физическим системам . Чтение: Аддисон-Уэсли. ISBN  978-0-201-16504-3 .
• Гринстед, Чарльз; Снелл, Дж. Лори (1997). Введение в вероятность . Американское математическое общество . стр. 10–11 .
• Хаммерсли, Дж. М.; Хэндскомб, округ Колумбия (1975). Методы Монте-Карло . Лондон: Метуэн. ISBN  978-0-416-52340-9 .
• Хартманн, АК (2009). Практическое руководство по компьютерному моделированию . Всемирная научная. ISBN  978-981-283-415-7 . Архивировано из оригинала 11 февраля 2009 года.
• Хаббард, Дуглас (2007). Как измерить что угодно: определение ценности нематериальных активов в бизнесе . Джон Уайли и сыновья . п. 46 . ISBN  9780470110126 .
• Хаббард, Дуглас (2009). Провал управления рисками: почему он не работает и как это исправить . Джон Уайли и сыновья .
• Канеман, Д.; Тверский, А. (1982). Суждение в условиях неопределенности: эвристика и предубеждения . Издательство Кембриджского университета.
• Калос, Малвин Х.; Уитлок, Паула А. (2008). Методы Монте-Карло . Вайли-ВЧ . ISBN  978-3-527-40760-6 .
• Крозе, ДП; Таймре, Т.; Ботев, З.И. (2011). Справочник по методам Монте-Карло . Нью-Йорк: Джон Уайли и сыновья . п. 772. ИСБН  978-0-470-17793-8 .
• МакГилливрей, ХТ; Додд, Р.Дж. (1982). «Моделирование галактических систем Монте-Карло». Астрофизика и космическая наука . 86 (2): 419–435. дои : 10.1007/BF00683346 . S2CID   189849365 .
• Маккеун, П. Кевин (1997). Стохастическое моделирование в физике . Нью-Йорк: Спрингер. ISBN  978-981-3083-26-4 .
• Метрополис, Н. (1987). «Начало метода Монте-Карло» (PDF) . Los Alamos Science (специальный выпуск 1987 г., посвященный Станиславу Уламу): 125–130.
• Метрополис, Северная Каролина ; Розенблут, Арианна В.; Розенблут, Маршалл Н.; Теллер, Огаста Х.; Теллер, Эдвард (1953). «Уравнение вычислений состояний на быстрых вычислительных машинах» . Журнал химической физики . 21 (6): 1087. Бибкод : 1953ЖЧФ..21.1087М . дои : 10.1063/1.1699114 . ОСТИ   4390578 . S2CID   1046577 .
• Метрополис, Северная Каролина ; Улам, С. (1949). «Метод Монте-Карло». Журнал Американской статистической ассоциации . 44 (247): 335–341. дои : 10.1080/01621459.1949.10483310 . JSTOR   2280232 . ПМИД   18139350 .
• Милик, М.; Сколник, Дж. (январь 1993 г.). «Вставка пептидных цепей в липидные мембраны: внерешеточная динамическая модель Монте-Карло». Белки . 15 (1): 10–25. дои : 10.1002/прот.340150104 . ПМИД   8451235 . S2CID   7450512 .
• Мозегор, Клаус; Тарантола, Альберт (1995). «Выборка решений обратных задач методом Монте-Карло» (PDF) . Дж. Геофиз. Рез . 100 (Б7): 12431–12447. Бибкод : 1995JGR...10012431M . дои : 10.1029/94JB03097 . Архивировано из оригинала (PDF) 10 марта 2021 г. Проверено 1 ноября 2017 г.
• Охеда, П.; Гарсия, М.; Лондоно, А.; Чен, штат Нью-Йорк (февраль 2009 г.). «Моделирование белков в клетках методом Монте-Карло: влияние заключения на стабильность промежуточных состояний» . Биофиз. Дж . 96 (3): 1076–1082. Бибкод : 2009BpJ....96.1076O . дои : 10.1529/biophysj.107.125369 . ПМЦ   2716574 . ПМИД   18849410 .
• Инт Панис, Л.; Де Нокер, Л.; Де Влигер, И.; Торфс, Р. (2001). «Тенденции и неопределенность в отношении воздействия загрязнения воздуха и внешних издержек от движения легковых автомобилей в Бельгии». Международный журнал автомобильного дизайна . 27 (1–4): 183–194. дои : 10.1504/IJVD.2001.001963 .
• Инт Панис, Л.; Рабл, А.; Де Нокер, Л.; Торфс, Р. (2002). Штурм, П. (ред.). «Дизель или бензин? Сравнение окружающей среды, затрудненное неопределенностью». Институт связи двигателей внутреннего сгорания и термодинамики . Выпуск 81 Том 1. Технологический университет Граца, Австрия: 48–54.
• Пресс, Уильям Х.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. (1996) [1986]. Численные рецепты на Фортране 77: Искусство научных вычислений . Числовые рецепты Фортрана. Том. 1 (2-е изд.). Издательство Кембриджского университета . ISBN  978-0-521-43064-7 .
• Рипли, Б.Д. (1987). Стохастическое моделирование . Уайли и сыновья .
• Роберт, К.; Казелла, Г. (2004). Статистические методы Монте-Карло (2-е изд.). Нью-Йорк: Спрингер. ISBN  978-0-387-21239-5 .
• Рубинштейн, Р.Ю.; Крозе, Д.П. (2007). Моделирование и метод Монте-Карло (2-е изд.). Нью-Йорк: Джон Уайли и сыновья. ISBN  978-0-470-17793-8 .
• Саввидес, Саввакис К. (1994). «Анализ рисков при оценке инвестиций» (PDF) . Журнал оценки проектов . 9 (1). дои : 10.2139/ssrn.265905 . S2CID   2809643 .
• Савиловский, Шломо С.; Фахум, Гейл К. (2003). Статистика с помощью моделирования Монте-Карло с помощью Фортрана . Рочестер-Хиллз, Мичиган: JMASM. ISBN  978-0-9740236-0-1 .
• Савиловский, Шломо С. (2003). «Думаешь, у тебя есть мелочи?» . Журнал современных прикладных статистических методов . 2 (1): 218–225. дои : 10.22237/jmasm/1051748460 .
• Сильвер, Дэвид; Венесс, Джоэл (2010). «Планирование Монте-Карло в больших POMDP» (PDF) . В Лафферти, Дж.; Уильямс, CKI; Шоу-Тейлор, Дж.; Земель, РС; Кулотта, А. (ред.). Достижения в области нейронных систем обработки информации 23 . Нейронные системы обработки информации 2010. Фонд нейронных систем обработки информации. Архивировано из оригинала (PDF) 25 мая 2012 года . Проверено 15 марта 2011 г.
• Ширмай-Калос, Ласло (2008). Методы Монте-Карло в глобальном освещении — фотореалистичный рендеринг с рандомизацией . ВДМ Верлаг Др. Мюллера eK ISBN  978-3-8364-7919-6 .
• Тарантола, Альберт (2005). Теория обратной задачи . Филадельфия: Общество промышленной и прикладной математики. ISBN  978-0-89871-572-9 .
• Восе, Дэвид (2008). Анализ рисков, Количественное руководство (3-е изд.). Джон Уайли и сыновья . ISBN  9780470512845 .
• Маждраков, Методи; Бенов, Добриян; Валканов, Николай (2018). Метод Монте-Карло. Инженерные приложения . Академическое издательство АКМО. ISBN  978-619-90684-3-4 .

Внешние ссылки

• СМИ, связанные с методом Монте-Карло, на Викискладе?