Введение

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

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

Применение

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

Расходы на вычисления

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

История

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

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

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

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

Приложения

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

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

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

Инженерная

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Закон

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

Библиотека

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

Другое

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

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

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

Интеграция

Детерминированные алгоритмы численного интегрирования хорошо работают в небольшом числе измерений, но сталкиваются с двумя проблемами, когда функции имеют много переменных. Во-первых, число необходимых вычислений функции быстро возрастает с увеличением числа измерений. Например, если 10 вычислений обеспечивают достаточную точность в одном измерении, то для 100 измерений потребуется 10 в 100-й степени точек – слишком много для вычисления. Это называется "проклятием размерности". Во-вторых, граница многомерной области может быть очень сложной, поэтому может оказаться невозможным свести задачу к повторному интегралу. 100 измерений – это отнюдь не редкость, поскольку во многих физических задачах "измерение" эквивалентно степени свободы. Методы Монте-Карло предоставляют выход из этого экспоненциального роста времени вычислений. Пока рассматриваемая функция достаточно хорошо себя ведет, ее можно оценить, случайным образом выбирая точки в 100-мерном пространстве и вычисляя некоторое среднее значение функции в этих точках. Согласно центральной предельной теореме, этот метод демонстрирует сходимость – то есть, учетверение числа отобранных точек уменьшает ошибку вдвое, независимо от числа измерений. Или, например, алгоритм VEGAS. Схожий подход, метод квази-Монте-Карло, использует последовательности с низкой дисперсией. Эти последовательности лучше "заполняют" область и чаще выбирают наиболее важные точки, поэтому методы квази-Монте-Карло часто могут сходиться к интегралу быстрее. Другой класс методов для выборки точек в объеме – это моделирование случайных блужданий по этому объему (марковские цепи Монте-Карло). К таким методам относятся алгоритм Метрополиса-Хэстингса, выборка Гиббса, алгоритм Ванга и Ландау, а также взаимодействующие методологии типа MCMC, такие как последовательные семплеры Монте-Карло.

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

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

Обратные проблемы

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

Философия

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