Методы Монте-Карло , или эксперименты Монте-Карло , представляют собой широкий класс вычислительных алгоритмов , которые полагаются на повторяющуюся случайную выборку для получения численных результатов. Основная концепция заключается в использовании случайности для решения проблем, которые в принципе могут быть детерминированными . Название происходит от казино Монте-Карло в Монако, где главный разработчик метода, физик Станислав Улам, был вдохновлен азартными играми своего дяди.
Методы Монте-Карло в основном используются в трех различных классах задач: оптимизация, численное интегрирование и генерация результатов на основе распределения вероятностей. Их также можно использовать для моделирования явлений со значительной неопределенностью входных данных, например, для расчета риска отказа атомной электростанции. Методы Монте-Карло часто реализуются с использованием компьютерного моделирования и могут обеспечить приблизительные решения проблем, которые иначе трудноразрешимы или слишком сложны для математического анализа.
Методы Монте-Карло широко используются в различных областях науки, техники и математики, таких как физика, химия, биология, статистика, искусственный интеллект, финансы и криптография. Они также применялись к социальным наукам, таким как социология, психология и политология. Методы Монте-Карло были признаны одной из самых важных и влиятельных идей 20-го века и позволили совершить множество научных и технологических прорывов.
Методы Монте-Карло также имеют некоторые ограничения и проблемы, такие как компромисс между точностью и вычислительными затратами, проклятие размерности, надежность генераторов случайных чисел, а также проверка и подтверждение результатов.
Методы Монте-Карло различаются, но, как правило, следуют определенной схеме:
Например, рассмотрим квадрант (круговой сектор) , вписанный в единичный квадрат . Учитывая, что соотношение их площадейπ/4, значение π можно аппроксимировать методом Монте-Карло: [1]
В этой процедуре областью входных данных является квадрат, описывающий квадрант. Можно генерировать случайные входные данные, разбрасывая зерна по квадрату, а затем выполнять вычисления для каждого входного сигнала (проверять, попадает ли он в пределы квадранта). Агрегирование результатов дает наш окончательный результат — аппроксимацию π .
Есть два важных соображения:
Использование методов Монте-Карло требует большого количества случайных чисел, и их использование значительно выиграло от генераторов псевдослучайных чисел , которые гораздо быстрее использовать, чем таблицы случайных чисел, которые ранее использовались для статистической выборки.
Методы Монте-Карло часто используются при решении физических и математических задач и наиболее полезны, когда использовать другие подходы затруднительно или невозможно. Методы Монте-Карло в основном используются в трех классах задач: [2] оптимизация , численное интегрирование и генерация результатов из распределения вероятностей .
В задачах, связанных с физикой, методы Монте-Карло полезны для моделирования систем со многими связанными степенями свободы , таких как жидкости, неупорядоченные материалы, сильно связанные твердые тела и ячеистые структуры (см. клеточную модель Поттса , системы взаимодействующих частиц , процессы Маккина-Власова , кинетические модели газов ).
Другие примеры включают моделирование явлений со значительной неопределенностью входных данных, таких как расчет риска в бизнесе и, в математике, оценка многомерных определенных интегралов со сложными граничными условиями . Применительно к проблемам системного проектирования (космос, разведка нефти , проектирование самолетов и т. д.) прогнозирование сбоев, превышений затрат и сроков на основе Монте-Карло обычно лучше, чем человеческая интуиция или альтернативные «мягкие» методы. [3]
В принципе, методы Монте-Карло можно использовать для решения любой задачи, имеющей вероятностную интерпретацию. По закону больших чисел интегралы, описываемые ожидаемым значением некоторой случайной величины, могут быть аппроксимированы путем взятия эмпирического среднего значения ( так называемого «выборочного среднего») независимых выборок переменной. Когда распределение вероятностей переменной параметризовано, математики часто используют пробоотборник цепи Маркова Монте-Карло (MCMC). [4] [5] [6] Основная идея заключается в разработке разумной модели цепи Маркова с предписанным стационарным распределением вероятностей . То есть в пределе выборки, генерируемые методом MCMC, будут выборками из желаемого (целевого) распределения. [7] [8] По эргодической теореме стационарное распределение аппроксимируется эмпирическими мерами случайных состояний пробоотборника MCMC.
В других задачах целью является создание выборок из последовательности вероятностных распределений, удовлетворяющих нелинейному уравнению эволюции. Эти потоки распределений вероятностей всегда можно интерпретировать как распределения случайных состояний марковского процесса , вероятности перехода которого зависят от распределений текущих случайных состояний (см. Процессы Маккина–Власова , уравнение нелинейной фильтрации ). [9] [10] В других случаях нам дан поток вероятностных распределений с возрастающим уровнем сложности выборки (модели пространств путей с увеличивающимся временным горизонтом, меры Больцмана-Гиббса, связанные с уменьшением температурных параметров, и многие другие). Эти модели также можно рассматривать как эволюцию закона случайных состояний нелинейной цепи Маркова. [10] [11] Естественный способ моделировать эти сложные нелинейные марковские процессы — это выборка нескольких копий процесса, заменяя в уравнении эволюции неизвестные распределения случайных состояний выборочными эмпирическими показателями . В отличие от традиционных методологий Монте-Карло и MCMC, эти методы частиц среднего поля полагаются на последовательные взаимодействующие образцы. Терминологическое среднее поле отражает тот факт, что каждый из образцов ( т. е. частицы, индивидуумы, ходоки, агенты, существа или фенотипы) взаимодействует с эмпирическими показателями процесса. Когда размер системы стремится к бесконечности, эти случайные эмпирические меры сходятся к детерминированному распределению случайных состояний нелинейной цепи Маркова, так что статистическое взаимодействие между частицами исчезает.
Несмотря на концептуальную и алгоритмическую простоту, вычислительные затраты, связанные с моделированием Монте-Карло, могут быть ошеломляюще высокими. В общем, метод требует большого количества образцов для получения хорошего приближения, что может потребовать сколь угодно большого общего времени выполнения, если время обработки одного образца велико. [12] Хотя это серьезное ограничение в очень сложных задачах, поразительно параллельная природа алгоритма позволяет снизить эти большие затраты (возможно, до осуществимого уровня) за счет стратегий параллельных вычислений на локальных процессорах, кластерах, облачных вычислениях, графических процессорах, ПЛИС и т. д. [13] [14] [15] [16]
До того, как был разработан метод Монте-Карло, при моделировании проверялась ранее понятная детерминированная проблема, а для оценки неопределенностей моделирования использовалась статистическая выборка. Моделирование Монте-Карло переворачивает этот подход, решая детерминированные проблемы с использованием вероятностной метаэвристики (см. Моделирование отжига ).
Ранний вариант метода Монте-Карло был разработан для решения проблемы иглы Бюффона , в которой π можно оценить, роняя иглы на пол, сделанный из параллельных равноудаленных полосок. В 1930-х годах Энрико Ферми впервые экспериментировал с методом Монте-Карло при изучении диффузии нейтронов, но не опубликовал эту работу. [17]
В конце 1940-х годов Станислав Улам изобрел современную версию метода Монте-Карло с цепью Маркова, когда работал над проектами ядерного оружия в Лос-Аламосской национальной лаборатории . В 1946 году физики-ядерщики в Лос-Аламосе исследовали диффузию нейтронов в ядре ядерного оружия. [17] Несмотря на наличие большинства необходимых данных, таких как среднее расстояние, которое нейтрон пройдет в веществе до того, как он столкнется с атомным ядром, и сколько энергии, вероятно, выделит нейтрон после столкновения, физики из Лос-Аламоса неспособен решить проблему, используя традиционные детерминированные математические методы. Улам предложил использовать случайные эксперименты. Он рассказывает о своем вдохновении следующим образом:
Первые мысли и попытки применить [метод Монте-Карло] были вызваны вопросом, который пришел мне в голову в 1946 году, когда я выздоравливал от болезни и раскладывал пасьянсы. Вопрос заключался в том, каковы шансы, что пасьянс Кэнфилд, расложенный из 52 карт, сложится удачно? Потратив много времени, пытаясь оценить их с помощью чистых комбинаторных вычислений, я задался вопросом, не может ли быть более практичным методом, чем «абстрактное мышление», состоять в том, чтобы разложить все, скажем, сто раз, а затем просто наблюдать и подсчитывать количество успешных игр. Это уже можно было представить с началом новой эры быстрых компьютеров, и я сразу же подумал о проблемах диффузии нейтронов и других вопросах математической физики, а в более общем плане о том, как преобразовать процессы, описываемые некоторыми дифференциальными уравнениями, в эквивалентную интерпретируемую форму. как последовательность случайных операций. Позже [в 1946 году] я описал эту идею Джону фон Нейману , и мы начали планировать реальные расчеты. [18]
Будучи секретной, работа фон Неймана и Улама требовала кодового названия. [19] Коллега фон Неймана и Улама Николас Метрополис предложил использовать название « Монте-Карло» , которое относится к казино Монте-Карло в Монако , где дядя Улама занимал деньги у родственников, чтобы играть в азартные игры. [17] Методы Монте-Карло играли центральную роль в моделировании , необходимом для Манхэттенского проекта , хотя и были сильно ограничены вычислительными инструментами того времени. Фон Нейман, Николас Метрополис и другие запрограммировали компьютер ENIAC для выполнения первых полностью автоматизированных расчетов Монте-Карло ядра ядерного оружия деления весной 1948 года. [20] В 1950-х годах методы Монте-Карло использовались в Лос-Аламосе для разработки водородной бомбы и стал популяризирован в области физики , физической химии и исследования операций . Корпорация Рэнд и ВВС США были двумя основными организациями, ответственными за финансирование и распространение информации о методах Монте-Карло в то время, и они начали находить широкое применение во многих различных областях.
Теория более сложных методов Монте-Карло для частиц типа среднего поля, безусловно, началась в середине 1960-х годов, с работы Генри П. Маккина-младшего по марковским интерпретациям класса нелинейных параболических уравнений в частных производных, возникающих в механике жидкостей. [21] [22] Мы также цитируем более раннюю новаторскую статью Теодора Э. Харриса и Германа Кана, опубликованную в 1951 году, в которой используются методы Монте-Карло генетического типа среднего поля для оценки энергии передачи частиц. [23] Методологии Монте-Карло генетического типа среднего поля также используются в качестве эвристических алгоритмов естественного поиска (также известных как метаэвристические ) в эволюционных вычислениях. Истоки этих вычислительных методов среднего поля можно проследить до 1950 и 1954 годов, когда были написаны работы Алана Тьюринга об обучающих машинах с мутационным отбором генетического типа [24] и статьи Нильса Аалла Барричелли из Института перспективных исследований в Принстоне, штат Нью-Йорк. Джерси . [25] [26]
Квантовые методы Монте-Карло и, более конкретно, диффузионные методы Монте-Карло также можно интерпретировать как приближение Монте-Карло частиц среднего поля для интегралов по траекториям Фейнмана – Каца . [27] [28] [29] [30] [31] [32] [33] Истоки квантовых методов Монте-Карло часто приписывают Энрико Ферми и Роберту Рихтмайеру , которые в 1948 году разработали интерпретацию нейтронно-частичной теории среднего поля. цепные реакции, [34] , но первый алгоритм частиц эвристического и генетического типа (также известный как методы Монте-Карло с повторной выборкой или реконфигурацией) для оценки энергий основного состояния квантовых систем (в моделях с уменьшенной матрицей) принадлежит Джеку Х. Хетерингтону в 1984 году [ 34]. 33] В молекулярной химии использование методологий генетических эвристических частиц (также известных как стратегии обрезки и обогащения) можно проследить до 1955 года, когда появилась основополагающая работа Маршалла Н. Розенблута и Арианны В. Розенблут . [35]
Использование последовательного Монте-Карло в расширенной обработке сигналов и байесовском выводе появилось совсем недавно. В 1993 году Гордон и др. опубликовали в своей плодотворной работе [36] первое применение алгоритма повторной выборки Монте-Карло в байесовском статистическом выводе. Авторы назвали свой алгоритм «бутстрап-фильтром» и продемонстрировали, что по сравнению с другими методами фильтрации их бутстрап-алгоритм не требует каких-либо предположений об этом пространстве состояний или шуме системы. Мы также цитируем еще одну новаторскую статью в этой области Генширо Китагавы о родственном «фильтре Монте-Карло» [37] и статьи Пьера Дель Мораля [38] и Химилькона Карвальо, Пьера Дель Мораля, Андре Монина и Жерара Салюта [39] по сажевым фильтрам, опубликованные в середине 1990-х годов. Фильтры частиц также были разработаны для обработки сигналов в 1989–1992 годах П. Дель Моралем, Дж. К. Нойером, Г. Ригалом и Г. Салютом в LAAS-CNRS в серии ограниченных и секретных исследовательских отчетов с STCAN (Service Technique des Constructions). et Armes Navales), ИТ-компания DIGILOG и LAAS-CNRS (Лаборатория анализа и архитектуры систем) по проблемам обработки радиолокационных/гидролокационных сигналов и сигналов GPS. [40] [41] [42] [43] [44] [45] Эти последовательные методологии Монте-Карло можно интерпретировать как пробоотборник принятия-отбраковки, оснащенный взаимодействующим механизмом рециркуляции.
С 1950 по 1996 год все публикации по методологиям последовательного Монте-Карло, включая методы обрезки и повторной выборки Монте-Карло, введенные в вычислительную физику и молекулярную химию, представляли естественные и эвристические алгоритмы, применяемые в различных ситуациях, без единого доказательства их непротиворечивости или обсуждение систематической ошибки оценок, а также алгоритмов, основанных на генеалогических и родовых деревьях. Математические основы и первый строгий анализ этих алгоритмов частиц были написаны Пьером Дель Моралем в 1996 году. [38] [46]
Методологии частиц разветвленного типа с различными размерами популяции были также разработаны в конце 1990-х годов Дэном Крисаном, Джессикой Гейнс и Терри Лайонсом, [47] [48] [49] и Дэном Крисаном, Пьером Дель Моралем и Терри Лайонсом. [50] Дальнейшие разработки в этой области были описаны в 1999–2001 годах П. Дель Моралем, А. Гионне и Л. Микло. [28] [51] [52]
Нет единого мнения о том, как следует определять Монте-Карло . Например, Рипли [53] определяет большую часть вероятностного моделирования как стохастическое моделирование , при этом метод Монте-Карло используется для интегрирования Монте-Карло и статистических тестов Монте-Карло. Савиловский [54] различает моделирование , метод Монте-Карло и моделирование Монте-Карло: моделирование — это фиктивное представление реальности, метод Монте-Карло — это метод, который можно использовать для решения математической или статистической задачи, а метод Монте-Карло — это метод, который можно использовать для решения математической или статистической задачи. Моделирование Монте-Карло использует повторную выборку для получения статистических свойств некоторого явления (или поведения). Примеры:
Калос и Уитлок [55] отмечают, что такие различия не всегда легко поддерживать. Например, излучение атомов — естественный стохастический процесс. Его можно смоделировать напрямую, или его среднее поведение можно описать стохастическими уравнениями, которые сами могут быть решены с использованием методов Монте-Карло. «Действительно, один и тот же компьютерный код можно рассматривать одновременно как «естественную симуляцию» или как решение уравнений путем естественной выборки».
Сходимость моделирования Монте-Карло можно проверить с помощью статистики Гельмана-Рубина .
Основная идея этого метода заключается в том, что результаты рассчитываются на основе повторной случайной выборки и статистического анализа. Моделирование Монте-Карло представляет собой, по сути, случайные эксперименты, в том случае, если результаты этих экспериментов недостаточно известны. Моделирование Монте-Карло обычно характеризуется множеством неизвестных параметров, многие из которых трудно получить экспериментально. [56] Методы моделирования Монте-Карло не всегда требуют действительно случайных чисел , чтобы быть полезными (хотя для некоторых приложений, таких как проверка на простоту , непредсказуемость жизненно важна). [57] Многие из наиболее полезных методов используют детерминированные псевдослучайные последовательности, что упрощает тестирование и повторный запуск моделирования. Единственное качество, которое обычно необходимо для хорошего моделирования, — это чтобы псевдослучайная последовательность казалась «достаточно случайной» в определенном смысле.
Что это означает, зависит от приложения, но обычно они должны пройти серию статистических тестов. Проверка того, что числа распределены равномерно или следуют другому желаемому распределению, когда рассматривается достаточно большое количество элементов последовательности, является одним из самых простых и распространенных. Слабые корреляции между последовательными выборками также часто желательны/необходимы.
Савиловский перечисляет характеристики высококачественного моделирования Монте-Карло: [54]
Алгоритмы выборки псевдослучайных чисел используются для преобразования равномерно распределенных псевдослучайных чисел в числа, которые распределяются в соответствии с заданным распределением вероятностей .
Последовательности с низким расхождением часто используются вместо случайной выборки из пространства, поскольку они обеспечивают равномерное покрытие и обычно имеют более быстрый порядок сходимости, чем моделирование Монте-Карло с использованием случайных или псевдослучайных последовательностей. Методы, основанные на их использовании, называются методами квази-Монте-Карло .
Пытаясь оценить влияние качества случайных чисел на результаты моделирования Монте-Карло, исследователи-астрофизики протестировали криптографически безопасные псевдослучайные числа, генерируемые с помощью набора инструкций Intel RDRAND , по сравнению с числами, полученными с помощью таких алгоритмов, как Mersenne Twister , в симуляциях Монте-Карло. радиовспышки от коричневых карликов . RDRAND — это генератор псевдослучайных чисел, наиболее близкий к истинному генератору случайных чисел. [ нужна ссылка ] Никакой статистически значимой разницы не было обнаружено между моделями, созданными с помощью типичных генераторов псевдослучайных чисел, и RDRAND для испытаний, состоящих из генерации 10 7 случайных чисел. [58]
Существуют способы использования вероятностей, которые определенно не являются симуляциями Монте-Карло – например, детерминированное моделирование с использованием одноточечных оценок. Каждой неопределенной переменной в модели присваивается оценка «наилучшего предположения». Для каждой входной переменной выбираются сценарии (например, наилучший, наихудший или наиболее вероятный случай) и записываются результаты. [59]
Напротив, моделирование Монте-Карло выбирает распределение вероятностей для каждой переменной, чтобы получить сотни или тысячи возможных результатов. Результаты анализируются для определения вероятностей различных исходов. [60] Например, сравнение модели построения стоимости в электронной таблице, выполненной с использованием традиционных сценариев «что если», а затем повторное сравнение с моделированием Монте-Карло и треугольными распределениями вероятностей, показывает, что анализ Монте-Карло имеет более узкий диапазон, чем « Что, если» анализ. [ нужен пример ] Это связано с тем, что анализ «что, если» придает равный вес всем сценариям (см. количественную оценку неопределенности в корпоративных финансах ), в то время как метод Монте-Карло вряд ли производит выборку в регионах с очень низкой вероятностью. Образцы в таких регионах называются «редкими событиями».
Методы Монте-Карло особенно полезны для моделирования явлений со значительной неопределенностью входных данных и систем со многими связанными степенями свободы. Области применения включают в себя:
Методы Монте-Карло очень важны в вычислительной физике , физической химии и смежных прикладных областях и имеют разнообразные применения: от сложных расчетов квантовой хромодинамики до проектирования тепловых экранов и аэродинамических форм, а также при моделировании переноса радиации для расчетов дозиметрии радиации. [61] [62] [63] В статистической физике молекулярное моделирование Монте-Карло является альтернативой вычислительной молекулярной динамике , а методы Монте-Карло используются для расчета статистических теорий поля простых частиц и полимерных систем. [35] [64] Квантовые методы Монте-Карло решают проблему многих тел для квантовых систем. [9] [10] [27] В радиационном материаловедении приближение бинарных столкновений для моделирования ионной имплантации обычно основано на методе Монте-Карло для выбора следующего сталкивающегося атома. [65] В экспериментальной физике элементарных частиц методы Монте-Карло используются для проектирования детекторов , понимания их поведения и сравнения экспериментальных данных с теорией. В астрофизике они используются столь разнообразно, что моделируют как эволюцию галактик [66] , так и передачу микроволнового излучения через шероховатую поверхность планеты. [67] Методы Монте-Карло также используются в ансамблевых моделях , которые составляют основу современного прогнозирования погоды .
Методы Монте-Карло широко используются в технике для анализа чувствительности и количественного вероятностного анализа при проектировании технологических процессов . Необходимость возникает из-за интерактивного, коллинеарного и нелинейного поведения моделирования типичных процессов. Например,
Межправительственная группа экспертов по изменению климата опирается на методы Монте-Карло при анализе функции плотности вероятности радиационного воздействия . [71]
Методы Монте-Карло используются в различных областях вычислительной биологии , например, для байесовского вывода в филогении или для изучения биологических систем, таких как геномы, белки [72] или мембраны. [73] Системы могут изучаться в общих рамках или в рамках ab initio в зависимости от желаемой точности. Компьютерное моделирование позволяет нам контролировать локальное окружение конкретной молекулы , чтобы увидеть, происходит ли, например, какая-то химическая реакция . В тех случаях, когда проведение физического эксперимента невозможно, можно провести мысленные эксперименты (например: разрыв связей, введение примесей в определенные места, изменение локальной/глобальной структуры или введение внешних полей).
Трассировка пути , иногда называемая трассировкой лучей Монте-Карло, визуализирует трехмерную сцену путем случайного отслеживания образцов возможных путей света. Повторная выборка любого данного пикселя в конечном итоге приведет к тому, что среднее значение выборок сойдётся к правильному решению уравнения рендеринга , что делает его одним из наиболее физически точных существующих методов рендеринга 3D-графики.
Стандарты для экспериментов Монте-Карло в статистике были установлены Савиловским. [74] В прикладной статистике методы Монте-Карло могут использоваться как минимум для четырех целей:
Методы Монте-Карло также представляют собой компромисс между методами приблизительной рандомизации и перестановочными тестами. Приблизительный тест рандомизации основан на определенном подмножестве всех перестановок (что влечет за собой потенциально огромную работу по проверке того, какие именно перестановки рассматривались). Подход Монте-Карло основан на заданном количестве случайно выбранных перестановок (заменяя небольшую потерю точности, если перестановка рисуется дважды или чаще, на эффективность отсутствия необходимости отслеживать, какие перестановки уже были выбраны).
Методы Монте-Карло были развиты в метод, называемый поиском по дереву Монте-Карло , который полезен для поиска лучшего хода в игре. Возможные ходы организованы в виде дерева поиска , и для оценки долгосрочного потенциала каждого хода используется множество случайных симуляций. Симулятор черного ящика представляет действия противника. [78]
Метод поиска по дереву Монте-Карло (MCTS) состоит из четырех этапов: [79]
Конечный эффект в ходе многих смоделированных игр заключается в том, что значение узла, представляющего ход, будет увеличиваться или уменьшаться, что, как мы надеемся, соответствует тому, представляет ли этот узел хороший ход или нет.
Поиск по дереву Монте-Карло успешно использовался для таких игр, как Go , [80] Tantrix , [81] Battleship , [82] Havannah , [83] и Arimaa . [84]
Методы Монте-Карло также эффективны при решении связанных интегрально-дифференциальных уравнений полей излучения и переноса энергии, и поэтому эти методы использовались в вычислениях глобального освещения , которые создают фотореалистичные изображения виртуальных 3D-моделей, с приложениями в видеоиграх , архитектуре , дизайне . , компьютерные фильмы и кинематографические спецэффекты. [85]
Береговая охрана США использует методы Монте-Карло в своей программе компьютерного моделирования SAROPS для расчета вероятного местоположения судов во время поисково-спасательных операций. Каждое моделирование может генерировать до десяти тысяч точек данных, которые случайным образом распределяются на основе предоставленных переменных. [86] Затем на основе экстраполяции этих данных генерируются шаблоны поиска для оптимизации вероятности сдерживания (POC) и вероятности обнаружения (POD), которые вместе будут равняться общей вероятности успеха (POS). В конечном итоге это служит практическому применению распределения вероятностей , чтобы обеспечить самый быстрый и наиболее целесообразный метод спасения, спасающий как жизни, так и ресурсы. [87]
Моделирование Монте-Карло обычно используется для оценки риска и неопределенности, которые могут повлиять на результат различных вариантов решения. Моделирование Монте-Карло позволяет аналитику бизнес-рисков учитывать общие эффекты неопределенности в таких переменных, как объем продаж, цены на товары и рабочую силу, процентные ставки и обменные курсы, а также влияние отдельных событий риска, таких как расторжение контракта или изменение налоговое законодательство.
Методы Монте-Карло в финансах часто используются для оценки инвестиций в проекты на уровне бизнес-подразделения или корпорации, а также для других финансовых оценок. Их можно использовать для моделирования графиков проектов , где симуляции объединяют оценки для наихудшего, наилучшего и наиболее вероятного сценария продолжительности каждой задачи, чтобы определить результаты для всего проекта.[1] Методы Монте-Карло также используются при ценообразовании опционов, анализе риска дефолта. [88] [89] [90] Кроме того, их можно использовать для оценки финансовых последствий медицинских вмешательств. [91]
Метод Монте-Карло использовался для оценки потенциальной ценности предлагаемой программы, призванной помочь женщинам-истцам в Висконсине добиться успеха в подаче заявлений о запретительном судебном приказе о преследовании и домашнем насилии . Было предложено помочь женщинам добиться успеха в их петициях, предоставив им более широкую защиту, тем самым потенциально снизив риск изнасилования и физического нападения . Однако в игре было много переменных, которые невозможно было точно оценить, включая эффективность запретительных приказов, степень успеха петиционеров как с защитой, так и без нее, и многие другие. В ходе исследования были проведены испытания, в которых эти переменные варьировались, чтобы получить общую оценку уровня успеха предлагаемой программы в целом. [92]
Метод Монте-Карло также использовался для моделирования количества книжных публикаций в зависимости от жанра книги в Малайзии. В моделировании Монте-Карло использовались ранее опубликованные данные о публикациях National Book и цены книг в зависимости от жанра книги на местном рынке. Результаты Монте-Карло были использованы для определения того, какой книжный жанр нравится малазийцам, а также для сравнения книжных изданий в Малайзии и Японии . [93]
Нассим Николас Талеб пишет о генераторах Монте-Карло в своей книге 2001 года «Одураченные случайностью » как о реальном примере обратного теста Тьюринга : человека можно объявить неразумным, если его письмо нельзя отличить от сгенерированного.
В общем, методы Монте-Карло используются в математике для решения различных задач путем генерации подходящих случайных чисел (см. также Генерация случайных чисел ) и наблюдения за той частью чисел, которая подчиняется некоторому свойству или свойствам. Метод полезен для получения численного решения задач, слишком сложных для аналитического решения. Наиболее распространенным применением метода Монте-Карло является интегрирование Монте-Карло.
Детерминированные алгоритмы численного интегрирования хорошо работают в небольшом количестве измерений, но сталкиваются с двумя проблемами, когда функции имеют много переменных. Во-первых, количество необходимых оценок функций быстро увеличивается с увеличением числа измерений. Например, если 10 оценок обеспечивают достаточную точность по одному измерению, то для 100 измерений потребуется 10100 баллов — слишком много, чтобы их можно было вычислить. Это называется проклятием размерности . Во-вторых, граница многомерной области может быть очень сложной, поэтому свести задачу к повторному интегралу может оказаться невозможным . [94] 100 измерений ни в коем случае не являются чем-то необычным, поскольку во многих физических задачах «размерность» эквивалентна степени свободы .
Методы Монте-Карло позволяют избежать этого экспоненциального увеличения времени вычислений. Пока рассматриваемая функция ведет себя достаточно хорошо , ее можно оценить, случайным образом выбрав точки в 100-мерном пространстве и взяв некое среднее значение функции в этих точках. Согласно центральной предельной теореме , этот метод демонстрирует сходимость, то есть увеличение в четыре раза количества точек выборки уменьшает ошибку вдвое, независимо от количества измерений. [94]
Усовершенствованный метод, известный как выборка по важности в статистике, включает в себя выборку точек случайным образом, но чаще, когда подынтегральное выражение велико. Чтобы сделать это точно, нужно уже знать интеграл, но можно аппроксимировать интеграл интегралом от аналогичной функции или использовать адаптивные процедуры, такие как стратифицированная выборка , рекурсивная стратифицированная выборка , адаптивная зонтичная выборка [95] [96] или Алгоритм ВЕГАС .
Подобный подход, метод квази-Монте-Карло , использует последовательности с низким расхождением . Эти последовательности лучше «заполняют» область и чаще выбирают наиболее важные точки, поэтому методы квази-Монте-Карло часто могут быстрее сходиться к интегралу.
Другой класс методов выборки точек в объёме — моделирование случайных блужданий по нему ( цепь Маркова Монте-Карло ). К таким методам относятся алгоритм Метрополиса-Гастингса , выборка Гиббса , алгоритм Ванга и Ландау , а также методологии MCMC взаимодействующего типа, такие как последовательные пробоотборники Монте-Карло . [97]
Еще одним мощным и очень популярным применением случайных чисел в численном моделировании является численная оптимизация . Проблема состоит в том, чтобы минимизировать (или максимизировать) функции некоторого вектора, который часто имеет много измерений. Многие задачи можно сформулировать таким образом: например, компьютерную шахматную программу можно рассматривать как попытку найти набор, скажем, из 10 ходов, который в конце дает наилучшую оценочную функцию. В задаче о коммивояжере цель состоит в том, чтобы минимизировать пройденное расстояние. Существуют также приложения для инженерного проектирования, такие как междисциплинарная оптимизация проектирования . Он применялся с квазиодномерными моделями для решения проблем динамики частиц путем эффективного исследования большого конфигурационного пространства. Ссылка [98] представляет собой всесторонний обзор многих вопросов, связанных с моделированием и оптимизацией.
Задача коммивояжера — это так называемая традиционная задача оптимизации. То есть все факты (расстояния между каждой точкой назначения), необходимые для определения оптимального пути следования, известны с уверенностью, и цель состоит в том, чтобы просмотреть возможные варианты путешествия и найти тот, который имеет наименьшее общее расстояние. Однако давайте предположим, что вместо минимизации общего расстояния, пройденного для посещения каждого желаемого пункта назначения, мы хотим минимизировать общее время, необходимое для достижения каждого пункта назначения. Это выходит за рамки обычной оптимизации, поскольку время в пути по своей сути неопределенно (пробки, время суток и т. д.). В результате, чтобы определить наш оптимальный путь, мы хотели бы использовать моделирование – оптимизацию, чтобы сначала понять диапазон потенциального времени, которое может потребоваться, чтобы перейти от одной точки к другой (представленной в данном случае распределением вероятностей, а не конкретным расстоянием). а затем оптимизировать наши решения о поездках, чтобы определить лучший путь, по которому следует следовать, принимая во внимание эту неопределенность.
Вероятностная постановка обратных задач приводит к определению распределения вероятностей в модельном пространстве. Это распределение вероятностей объединяет априорную информацию с новой информацией, полученной путем измерения некоторых наблюдаемых параметров (данных). Поскольку в общем случае теория, связывающая данные с параметрами модели, является нелинейной, апостериорную вероятность в пространстве модели может быть нелегко описать (она может быть мультимодальной, некоторые моменты могут быть не определены и т. д.).
При анализе обратной задачи получения модели максимального правдоподобия обычно недостаточно, поскольку мы обычно также хотим иметь информацию о разрешающей способности данных. В общем случае у нас может быть много параметров модели, и проверка интересующих предельных плотностей вероятности может оказаться непрактичной или даже бесполезной. Но можно псевдослучайно сгенерировать большую коллекцию моделей в соответствии с апостериорным распределением вероятностей , а также проанализировать и отобразить модели таким образом, чтобы информация об относительной вероятности свойств модели передавалась зрителю. Этого можно добиться с помощью эффективного метода Монте-Карло даже в тех случаях, когда явная формула для априорного распределения недоступна.
Самый известный метод выборки по важности, алгоритм Метрополиса, можно обобщить, и это дает метод, который позволяет анализировать (возможно, сильно нелинейные) обратные задачи со сложной априорной информацией и данными с произвольным распределением шума. [99] [100]
Популярное изложение метода Монте-Карло провел Маккракен. [101] Общая философия метода обсуждалась Элишаковым [102] и Грюне-Яновым и Вейрихом. [103]
Монографии по статистике и прикладной теории вероятности.
Серия: Вероятность и приложения
Рассекреченный отчет Лос-Аламосского архива
{{cite book}}
: |journal=
игнорируется ( помощь ) ; Отсутствует или пусто |title=
( помощь ){{cite book}}
: CS1 maint: date and year (link)