stringtranslate.com

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

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

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

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

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

Обзор

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

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

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

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

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

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

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

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

Приложение

Методы Монте-Карло часто используются при решении физических и математических задач и наиболее полезны, когда использовать другие подходы затруднительно или невозможно. Методы Монте-Карло в основном используются в трех классах задач: [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] В прикладной статистике методы Монте-Карло могут использоваться как минимум для четырех целей:

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

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

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

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

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

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

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

Поиск по дереву Монте-Карло успешно использовался для таких игр, как 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]

Смотрите также

Рекомендации

Цитаты

  1. ^ Калос и Уитлок 2008.
  2. ^ Крозе, ДП; Бреретон, Т.; Таймре, Т.; Ботев, З.И. (2014). «Почему метод Монте-Карло так важен сегодня». ПРОВОДА Вычисление Стат . 6 (6): 386–392. дои : 10.1002/wics.1314. S2CID  18521840.
  3. ^ Хаббард, Дуглас; Самуэльсон, Дуглас А. (октябрь 2009 г.). «Моделирование без измерений». OR/MS Сегодня : 28–33.
  4. ^ Метрополис, Николас; Розенблут, Арианна В.; Розенблут, Маршалл Н.; Теллер, Огаста Х.; Теллер, Эдвард (1 июня 1953 г.). «Уравнение расчета состояния с помощью быстрых вычислительных машин». Журнал химической физики . 21 (6): 1087–1092. Бибкод : 1953ЖЧФ..21.1087М. дои : 10.1063/1.1699114. ISSN  0021-9606. ОСТИ  4390578. S2CID  1046577.
  5. ↑ Гастингс, WK (1 апреля 1970 г.). «Методы выборки Монте-Карло с использованием цепей Маркова и их приложения». Биометрика . 57 (1): 97–109. Бибкод :1970Бимка..57...97H. дои : 10.1093/biomet/57.1.97. ISSN  0006-3444. S2CID  21204149.
  6. ^ Лю, Цзюнь С.; Лян, Слава; Вонг, Вин Хунг (1 марта 2000 г.). «Метод множественных попыток и локальная оптимизация выборки в мегаполисе». Журнал Американской статистической ассоциации . 95 (449): 121–134. дои : 10.1080/01621459.2000.10473908. ISSN  0162-1459. S2CID  123468109.
  7. ^ Сполл, JC (2003). «Оценка с помощью цепи Маркова Монте-Карло». Журнал IEEE Control Systems . 23 (2): 34–45. дои : 10.1109/MCS.2003.1188770.
  8. ^ Хилл, Стейси Д.; Сполл, Джеймс К. (2019). «Стационарность и сходимость алгоритма Метрополиса-Гастингса: взгляд на теоретические аспекты». Журнал IEEE Control Systems . 39 : 56–67. дои : 10.1109/MCS.2018.2876959. S2CID  58672766.
  9. ^ аб Колокольцов, Василий (2010). Нелинейные марковские процессы . Издательство Кембриджского университета . п. 375.
  10. ^ abc Дель Мораль, Пьер (2013). Моделирование среднего поля для интегрирования Монте-Карло. Чепмен и Холл/ CRC Press . п. 626. Монографии по статистике и прикладной теории вероятности.
  11. ^ Дель Мораль, П.; Дусе, А.; Ясра, А. (2006). «Последовательные пробоотборники Монте-Карло». Журнал Королевского статистического общества, серия B. 68 (3): 411–436. arXiv : cond-mat/0212648 . дои : 10.1111/j.1467-9868.2006.00553.x. S2CID  12074789.
  12. ^ Шонквилер, RW; Мендивил, Ф. (2009). Исследования по методам Монте-Карло . Спрингер.
  13. ^ Атанасова, Э.; Гуров Т.; Караиванова А.; Ивановская, С.; Дурчова, М.; Димитров, Д. (2016). «О подходах к распараллеливанию архитектуры Intel MIC». Материалы конференции AIP . 1773 (1): 070001. Бибкод : 2016AIPC.1773g0001A. дои : 10.1063/1.4964983.
  14. ^ Кунья-младший, А.; Насер, Р.; Сампайо, Р.; Лопес, Х.; Брейтман, К. (2014). «Количественная оценка неопределенности с помощью метода Монте-Карло в условиях облачных вычислений». Компьютерная физика. Коммуникации . 185 (5): 1355–1363. arXiv : 2105.09512 . Бибкод : 2014CoPhC.185.1355C. дои :10.1016/j.cpc.2014.01.006. S2CID  32376269.
  15. ^ Вэй, Дж.; Круис, FE (2013). «Распараллеленный метод Монте-Карло на основе графического процессора для коагуляции частиц с использованием стратегии принятия-отклонения». Химико-техническая наука . 104 : 451–459. Бибкод :2013ЧЭнС.104..451В. doi :10.1016/j.ces.2013.08.008.
  16. ^ Лин, Ю.; Ван, Ф.; Лю, Б. (2018). «Генератор случайных чисел для крупномасштабного параллельного моделирования Монте-Карло на FPGA». Журнал вычислительной физики . 360 : 93–103. Бибкод : 2018JCoPh.360...93L. дои : 10.1016/j.jcp.2018.01.029.
  17. ^ abc Метрополис 1987.
  18. ^ Экхардт 1987.
  19. ^ аб Маждраков, Бенов и Валканов 2018, с. 250.
  20. ^ Хей, Томас; Пристли, Марк; Веревка, Криспин (2014). «Лос-Аламос делает ставку на ENIAC: ядерное моделирование Монте-Карло, 1947–1948». IEEE Анналы истории вычислений . 36 (3): 42–63. дои : 10.1109/MAHC.2014.40. S2CID  17470931.
  21. ^ Маккин, Генри П. (1967). «Распространение хаоса для класса нелинейных параболических уравнений». Серия лекций по дифференциальным уравнениям, Католический университет . 7 : 41–57.
  22. ^ Маккин, Генри П. (1966). «Класс марковских процессов, связанных с нелинейными параболическими уравнениями». Учеб. Натл. акад. наук. США . 56 (6): 1907–1911. Бибкод : 1966ПНАС...56.1907М. дои : 10.1073/pnas.56.6.1907 . ПМК 220210 . ПМИД  16591437. 
  23. ^ Герман, Кан; Теодор, Харрис Э. (1951). «Оценка пропускания частиц методом случайной выборки» (PDF) . Натл. Бур. Стоять. Прил. Математика. Сер . 12 :27–30.
  24. ^ Тьюринг, Алан М. (1950). «Вычислительная техника и интеллект». Разум . ЛИКС (238): 433–460. дои : 10.1093/mind/LIX.236.433.
  25. ^ Барричелли, Нильс Аалл (1954). «Числовые примеры процесса эволюции». Методы : 45–68.
  26. ^ Барричелли, Нильс Аалл (1957). «Процессы симбиогенной эволюции, реализуемые искусственными методами». Методы : 143–182.
  27. ^ ab Дель Мораль, Пьер (2004). Формулы Фейнмана–Каца. Генеалогические аппроксимации и взаимодействующие частицы. Вероятность и ее приложения. Спрингер. п. 575. ИСБН 9780387202686. Серия: Вероятность и приложения
  28. ^ аб Дель Мораль, П.; Микло, Л. (2000). «Аппроксимации ветвящихся и взаимодействующих систем частиц формул Фейнмана – Каца с применением к нелинейной фильтрации». Семинар вероятностей XXXIV. Конспект лекций по математике. Том. 1729. Берлин: Шпрингер. стр. 1–145. дои : 10.1007/BFb0103798. ISBN 978-3-540-67314-9. МР  1768060.
  29. ^ Дель Мораль, Пьер; Микло, Лоран (2000). «Аппроксимация системы частиц Морана формул Фейнмана – Каца». Случайные процессы и их приложения . 86 (2): 193–216. дои : 10.1016/S0304-4149(99)00094-0 .
  30. ^ Дель Мораль, Пьер (2003). «Частичные аппроксимации показателей Ляпунова, связанные с операторами Шредингера и полугруппами Фейнмана – Каца». ESAIM Вероятность и статистика . 7 : 171–208. дои : 10.1051/ps:2003001 .
  31. ^ Ассараф, Роланд; Каффарель, Мишель; Хелиф, Анатоль (2000). «Диффузионные методы Монте-Карло с фиксированным количеством пешеходов» (PDF) . Физ. Преподобный Е. 61 (4): 4566–4575. Бибкод : 2000PhRvE..61.4566A. doi : 10.1103/physreve.61.4566. PMID  11088257. Архивировано из оригинала (PDF) 7 ноября 2014 г.
  32. ^ Каффарель, Мишель; Сеперли, Дэвид; Калос, Мальвин (1993). «Комментарий к расчету интегральных путей Фейнмана – Каца энергий основного состояния атомов». Физ. Преподобный Летт . 71 (13): 2159. Бибкод : 1993PhRvL..71.2159C. doi : 10.1103/physrevlett.71.2159. ПМИД  10054598.
  33. ^ аб Хетерингтон, Джек Х. (1984). «Наблюдения за статистической итерацией матриц». Физ. Преподобный А. 30 (2713): 2713–2719. Бибкод : 1984PhRvA..30.2713H. doi : 10.1103/PhysRevA.30.2713.
  34. ^ Ферми, Энрике; Рихтмайер, Роберт Д. (1948). «Примечание о проведении переписи населения в расчетах Монте-Карло» (PDF) . ЛАМ . 805 (А). Рассекреченный отчет Лос-Аламосского архива
  35. ^ аб Розенблут, Маршалл Н.; Розенблут, Арианна В. (1955). «Расчеты Монте-Карло среднего удлинения макромолекулярных цепей». Дж. Хим. Физ . 23 (2): 356–359. Бибкод : 1955JChPh..23..356R. дои : 10.1063/1.1741967 . S2CID  89611599.
  36. ^ Гордон, Нью-Джерси; Салмонд, диджей; Смит, AFM (апрель 1993 г.). «Новый подход к оценке нелинейного/негауссовского байесовского состояния». Труды IEE F-радар и обработка сигналов . 140 (2): 107–113. дои : 10.1049/ip-f-2.1993.0015. ISSN  0956-375X. S2CID  12644877.
  37. ^ Китагава, Г. (1996). «Фильтр Монте-Карло и сглаживатель для негауссовских нелинейных моделей в пространстве состояний». Журнал вычислительной и графической статистики . 5 (1): 1–25. дои : 10.2307/1390750. JSTOR  1390750.
  38. ^ ab Дель Мораль, Пьер (1996). «Нелинейная фильтрация: решение взаимодействующих частиц» (PDF) . Марковские процессы и связанные с ними области . 2 (4): 555–580. Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 11 июня 2015 г.
  39. ^ Карвалью, Химилькон; Дель Мораль, Пьер; Монен, Андре; Салют, Жерар (июль 1997 г.). «Оптимальная нелинейная фильтрация при интеграции GPS/INS» (PDF) . Транзакции IEEE по аэрокосмическим и электронным системам . 33 (3): 835–850. Бибкод : 1997ITAES..33..835C. дои : 10.1109/7.599254. S2CID  27966240. Архивировано из оригинала (PDF) 10 ноября 2022 года . Проверено 11 июня 2015 г.
  40. ^ П. Дель Мораль, Г. Ригал и Г. Салют. «Оценка и нелинейное оптимальное управление: единая основа для решений частиц». LAAS-CNRS, Тулуза, отчет об исследовании №. 91137, контракт DRET-DIGILOG-LAAS/CNRS, апрель (1991 г.).
  41. ^ П. Дель Мораль, Г. Ригал и Г. Салют. «Нелинейные и негауссовы фильтры частиц, применяемые для перемещения инерциальной платформы». LAAS-CNRS, Тулуза, отчет об исследовании №. 92207, STCAN/DIGILOG-LAAS/CNRS Конвенция STCAN №. А.91.77.013, (94с.) сентябрь (1991).
  42. ^ П. Дель Мораль, Г. Ригал и Г. Салют. «Оценка и нелинейное оптимальное управление: Разрешение частиц при фильтрации и оценке: Экспериментальные результаты». Конвенция DRET №. 89.34.553.00.470.75.01, Отчет об исследовании № 2 (54 стр.), январь (1992 г.).
  43. ^ П. Дель Мораль, Г. Ригал и Г. Салют. «Оценка и нелинейное оптимальное управление: разрешение частиц при фильтрации и оценке: теоретические результаты». Конвенция DRET №. 89.34.553.00.470.75.01, Отчет об исследовании № 3 (123 стр.), октябрь (1992 г.).
  44. ^ П. Дель Мораль, Ж.-Ч. Нойер, Г. Ригаль и Г. Салют. «Фильтры частиц при обработке радиолокационных сигналов: обнаружение, оценка и распознавание воздушных целей». LAAS-CNRS, Тулуза, отчет об исследовании №. 92495, декабрь (1992 г.).
  45. ^ П. Дель Мораль, Г. Ригал и Г. Салют. «Оценка и нелинейное оптимальное управление: разрешение частиц при фильтрации и оценке». Исследования по теме: Фильтрация, оптимальное управление и оценка максимального правдоподобия. Конвенция DRET №. 89.34.553.00.470.75.01. Отчет об исследовании № 4 (210 стр.), январь (1993 г.).
  46. ^ Дель Мораль, Пьер (1998). «Измерительные процессы и взаимодействующие системы частиц. Применение к задачам нелинейной фильтрации». Анналы прикладной вероятности (Publications du Laboratoire de Statistique et Probabilités, 96-15 (1996) изд.). 8 (2): 438–495. CiteSeerX 10.1.1.55.5257 . дои : 10.1214/aoap/1028903535. 
  47. ^ Крисан, Дэн; Гейнс, Джессика; Лайонс, Терри (1998). «Сходимость метода ветвящихся частиц к решению Закая». SIAM Journal по прикладной математике . 58 (5): 1568–1590. дои : 10.1137/s0036139996307371. S2CID  39982562.
  48. ^ Крисан, Дэн; Лайонс, Терри (1997). «Нелинейная фильтрация и измерительные процессы». Теория вероятностей и смежные области . 109 (2): 217–244. дои : 10.1007/s004400050131 . S2CID  119809371.
  49. ^ Крисан, Дэн; Лайонс, Терри (1999). «Частичная аппроксимация решения уравнения Кушнера – Стратоновича». Теория вероятностей и смежные области . 115 (4): 549–578. дои : 10.1007/s004400050249 . S2CID  117725141.
  50. ^ Крисан, Дэн; Дель Мораль, Пьер; Лайонс, Терри (1999). «Дискретная фильтрация с использованием ветвящихся и взаимодействующих систем частиц» (PDF) . Марковские процессы и связанные с ними области . 5 (3): 293–318.
  51. ^ Дель Мораль, Пьер; Гионне, Алиса (1999). «Об устойчивости мерозначных процессов с приложениями к фильтрации». ЧР акад. наук. Париж . 39 (1): 429–434.
  52. ^ Дель Мораль, Пьер; Гионне, Алиса (2001). «Об устойчивости взаимодействующих процессов с приложениями к фильтрующим и генетическим алгоритмам». Анналы Института Анри Пуанкаре . 37 (2): 155–194. Бибкод : 2001AIHPB..37..155D. дои : 10.1016/s0246-0203(00)01064-5.
  53. ^ Рипли 1987
  54. ^ аб Савиловский 2003
  55. ^ Калос и Уитлок, 2008 г.
  56. ^ Шоджаифард, Миннесота; Халхали, А.; Ярмохаммадисатри, Садег (2017). «Эффективный метод анализа чувствительности модифицированной геометрии подвески Макферсона на основе коэффициента корреляции Пирсона». Динамика систем автомобиля . 55 (6): 827–852. Бибкод : 2017VSD....55..827S. дои : 10.1080/00423114.2017.1283046. S2CID  114260173.
  57. ^ Давенпорт 1992
  58. ↑ Маршрут, Мэтью (10 августа 2017 г.). «Синтез популяции ультрахолодных карликов с радиовспышкой». Астрофизический журнал . 845 (1): 66. arXiv : 1707.02212 . Бибкод : 2017ApJ...845...66R. дои : 10.3847/1538-4357/aa7ede . S2CID  118895524.
  59. ^ Восе 2008, с. 13.
  60. ^ Восе 2008, с. 16.
  61. ^ Цзя, Сюнь; Цигенхейн, Питер; Цзян, Стив Б. (2014). «Высокопроизводительные вычисления на базе графических процессоров для лучевой терапии». Физика в медицине и биологии . 59 (4): Р151–Р182. Бибкод : 2014PMB....59R.151J. дои : 10.1088/0031-9155/59/4/R151. ПМК 4003902 . ПМИД  24486639. 
  62. ^ Хилл, Р.; Хили, Б.; Холлоуэй, Л.; Кунчич, З.; Туэйтс, Д.; Бэлдок, К. (март 2014 г.). «Достижения в области киловольтной рентгеновской дозиметрии». Физика в медицине и биологии . 59 (6): Р183–Р231. Бибкод : 2014PMB....59R.183H. дои : 10.1088/0031-9155/59/6/R183. PMID  24584183. S2CID  18082594.
  63. ^ Роджерс, DWO (2006). «Пятьдесят лет моделирования Монте-Карло для медицинской физики». Физика в медицине и биологии . 51 (13): Р287–Р301. Бибкод : 2006PMB....51R.287R. дои : 10.1088/0031-9155/51/13/R17. PMID  16790908. S2CID  12066026.
  64. ^ Берле 2009
  65. ^ Мёллер, В.; Экстайн, В. (1 марта 1984 г.). «Tridyn — код моделирования TRIM, включающий динамические изменения композиции». Ядерные приборы и методы в физических исследованиях. Раздел B: Взаимодействие пучков с материалами и атомами . 2 (1): 814–818. Бибкод : 1984NIMPB...2..814M. дои : 10.1016/0168-583X(84)90321-5.
  66. ^ МакГилливрей и Додд, 1982 г.
  67. ^ Золотой 1979 г.
  68. ^ Г. А. Берд, Динамика молекулярного газа, Кларендон, Оксфорд (1976)
  69. ^ Дитрих, С.; Бойд, И. (1996). «Скалярно-оптимизированная параллельная реализация метода DSMC». Журнал вычислительной физики . 126 (2): 328–42. Бибкод : 1996JCoPh.126..328D. дои : 10.1006/jcph.1996.0141 .
  70. ^ Чен, Шан-Ин; Сюй, Го-Чин; Фань, Цзя-Мин (15 марта 2021 г.). «Усовершенствование обобщенного метода конечных разностей для стохастического моделирования подземных течений». Журнал вычислительной физики . 429 : 110002. Бибкод : 2021JCoPh.42910002C. doi :10.1016/J.JCP.2020.110002. S2CID  228828681.
  71. ^ Изменение климата, 2013. Основы физических наук (PDF) . Издательство Кембриджского университета . 2013. с. 697. ИСБН 978-1-107-66182-0. Проверено 6 июля 2023 г.
  72. ^ Охеда и др. 2009.
  73. ^ Милик и Сколник 1993.
  74. ^ Кэсси; Смит (2014). «Имитация уверенности в индексе Эллисона-Глейзера». Журнал городской экономики . 81 : 93. doi :10.1016/j.jue.2014.02.005.
  75. ^ Савиловский и Фахум, 2003 г.
  76. ^ Сполл, Джеймс К. (2005). «Расчет Монте-Карло информационной матрицы Фишера в нестандартных настройках». Журнал вычислительной и графической статистики . 14 (4): 889–909. CiteSeerX 10.1.1.142.738 . дои : 10.1198/106186005X78800. S2CID  16090098. 
  77. ^ Дас, Сонджой; Сполл, Джеймс К.; Ганем, Роджер (2010). «Эффективное вычисление информационной матрицы Фишера по методу Монте-Карло с использованием априорной информации». Вычислительная статистика и анализ данных . 54 (2): 272–289. дои : 10.1016/j.csda.2009.09.018.
  78. ^ Шасло, Гийом; Баккес, Сандер; Сита, Иштван; Спронк, Питер. «Поиск в дереве Монте-Карло: новая основа для игрового ИИ» (PDF) . Sander.landofsand.com . Проверено 28 октября 2017 г.
  79. ^ "Поиск по дереву Монте-Карло - О" . Архивировано из оригинала 29 ноября 2015 года . Проверено 15 мая 2013 г.
  80. ^ Шасло, Гийом MJ -B; Винандс, Марк Х.М.; Ван Ден Херик, Х. Яап (2008). «Параллельный поиск в дереве Монте-Карло». Компьютеры и игры . Конспекты лекций по информатике. Том. 5131. стр. 60–71. CiteSeerX 10.1.1.159.4373 . дои : 10.1007/978-3-540-87608-3_6. ISBN  978-3-540-87607-6.
  81. ^ Брунс, Пит. Поиск по дереву Монте-Карло в игре Tantrix: Итоговый отчет Cosc490 (PDF) (Отчет).
  82. ^ Сильвер, Дэвид; Венесс, Джоэл. «Планирование Монте-Карло в больших POMDP» (PDF) . 0.cs.ucl.ac.uk. _ Архивировано из оригинала (PDF) 18 июля 2016 года . Проверено 28 октября 2017 г.
  83. ^ Лоренц, Ричард Дж. (2011). «Улучшение поиска по деревьям Монте-Карло в Гаване». Компьютеры и игры . Конспекты лекций по информатике. Том. 6515. стр. 105–115. Бибкод : 2011LNCS.6515..105L. дои : 10.1007/978-3-642-17928-0_10. ISBN 978-3-642-17927-3.
  84. ^ Якль, Томас. «Проблема Аримаа - сравнительное исследование методов MCTS и альфа-бета» (PDF) . Arimaa.com . Проверено 28 октября 2017 г.
  85. ^ Сирмай-Калос 2008.
  86. ^ «Как береговая охрана использует аналитику для поиска пропавших в море» . Информация о кубиках . 3 января 2014 г.
  87. ^ Стоун, Лоуренс Д.; Крацке, Томас М.; Фрост, Джон Р. «Моделирование поиска и оптимизация в системе оптимального планирования поисково-спасательных операций Береговой охраны США (SAROPS)» (PDF) . Ifremer.fr . Проверено 28 октября 2017 г.
  88. ^ Кармона, Рене; Дель Мораль, Пьер; Ху, Пэн; Уджан, Надя (2012). «Введение в методы частиц с финансовыми приложениями». В Кармоне, Рене А.; Мораль, Пьер Дель; Ху, Пэн; и другие. (ред.). Спрингерские труды по математике. Том. 12. Шпрингер Берлин Гейдельберг. стр. 3–49. CiteSeerX 10.1.1.359.7957 . дои : 10.1007/978-3-642-25746-9_1. ISBN  978-3-642-25745-2. {{cite book}}: |journal=игнорируется ( помощь ) ; Отсутствует или пусто |title=( помощь )
  89. ^ Кармона, Рене; Дель Мораль, Пьер; Ху, Пэн; Уджан, Надя (2012). Численные методы в финансах. Спрингерские труды по математике. Том. 12. дои : 10.1007/978-3-642-25746-9. ISBN 978-3-642-25745-2.
  90. ^ Крозе, ДП; Таймре, Т.; Ботев, З.И. (2011). Справочник по методам Монте-Карло . Джон Уайли и сыновья.
  91. ^ Аренас, Дэниел Дж.; Летт, Ланэр А.; Клюсариц, Хизер; Тейтельман, Энн М. (2017). «Подход к моделированию Монте-Карло для оценки воздействия на здоровье и экономики вмешательств, проводимых в студенческой клинике». ПЛОС ОДИН . 12 (12): e0189718. Бибкод : 2017PLoSO..1289718A. дои : 10.1371/journal.pone.0189718 . ПМЦ 5746244 . ПМИД  29284026. 
  92. ^ Элварт, Лиз; Эмерсон, Нина; Эндерс, Кристина; Фумия, Дэни; Мерфи, Кевин (декабрь 2006 г.). «Расширение доступа к запретительным ордерам для жертв домашнего насилия с низкими доходами: анализ затрат и выгод предлагаемой программы грантов против домашнего насилия» (PDF) . Адвокатура штата Висконсин . Архивировано из оригинала (PDF) 6 ноября 2018 года . Проверено 12 декабря 2016 г.
  93. ↑ Дахлан, Хади Акбар (29 октября 2021 г.). «Perbandingan Penerbitan dan Harga Buku Mengikut Genre di Malaysia dan Jepun Menggunakan Data Akses Terbuka dan Simulasi Monte Carlo» (PDF) . Каджян Малайзия . 39 (2): 179–202. дои : 10.21315/км2021.39.2.8. S2CID  240435973.
  94. ^ ab Press et al. 1996 год
  95. ^ МЕЗЕЙ, М (31 декабря 1986 г.). «Адаптивная зонтичная выборка: самосогласованное определение небольцмановской систематической ошибки». Журнал вычислительной физики . 68 (1): 237–248. Бибкод : 1987JCoPh..68..237M. дои : 10.1016/0021-9991(87)90054-4.
  96. ^ Бартельс, Кристиан; Карплюс, Мартин (31 декабря 1997 г.). «Распределения вероятностей для сложных систем: адаптивная зонтичная выборка потенциальной энергии». Журнал физической химии Б. 102 (5): 865–880. дои : 10.1021/jp972280j.
  97. ^ Дель Мораль, Пьер; Дусе, Арно; Ясра, Аджай (2006). «Последовательные пробоотборники Монте-Карло». Журнал Королевского статистического общества, серия B. 68 (3): 411–436. arXiv : cond-mat/0212648 . дои : 10.1111/j.1467-9868.2006.00553.x. S2CID  12074789.
  98. ^ Сполл, Дж. К. (2003), Введение в стохастический поиск и оптимизацию: оценка, моделирование и контроль , Уайли, Хобокен, Нью-Джерси. http://www.jhuapl.edu/ISSO
  99. ^ Мозегорд и Тарантола, 1995 г.
  100. ^ Тарантола 2005 г.
  101. ^ Маккракен, Д.Д., (1955) Метод Монте-Карло, Scientific American, 192 (5), стр. 90-97.
  102. ^ Элишакофф И., (2003) Заметки по философии метода Монте-Карло, Международная прикладная механика, 39 (7), стр. 753-762.
  103. ^ Грюне-Янофф, Т., и Вейрих, П. (2010). Философия и эпистемология симуляции: обзор, Simulation & Gaming, 41 (1), стр. 20–50.

Источники

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