Методите „Монте Карло“ (или още експериментите „Монте Карло“) са широк клас от изчислителни алгоритми, които използват повтарянето на случайни извадки за постигане на числов резултат, разчитайки случайността да разкрие по начало детерминизирани явления. Те често се използват във физични и математически задачи и са най-полезни, когато е трудно или невъзможно използването на други математически методи. Методите „Монте Карло“ много често се използват в три отделни класа задачи: оптимизация, числови интеграли и генериране на извадки от разпределението на вероятностите.
При физичните задачи методите „Монте Карло“ са доста полезни за симулация на системи с много свързани степени на свобода, като течности, материали с неподредена структура, структурирани твърди частици и клетъчни структури. Други примери включват създаването на явления с неясен вход в събитията, като изчисляване на рискове в бизнеса. В приложение служи за прогнози за неуспех, превишаване на разходи и други. Тези прогнози често са по-добри от човешката интуиция.
По принцип „Монте Карло“ методите могат да се използват за решаването на всеки проблем от проблематичен характер. По закона за големите числа, за интеграли, описани с очаквана стойност от някаква случайна променлива, резултатът може да се изчисли приблизително, като се вземе емпиричната стойност независимо от зададената променлива. Когато вероятностното разпределение на променливата е параметризирано, математиците често използват сборника „Марков Монте Карло“ (накратко: MCMC). Главната идея е да се създаде модел на Марковска верига на описано съвместно вероятностно разпределение.
В други важни проблеми ние сме заинтересовани в генериране на равенства от редица на вероятностно разпределение, задоволяваща нелинейно уравнение. Тези потоци на вероятностни разпределения може винаги да се интерпретират като разпределения на случайни стадии на Марковски процес, чийто преход на вероятностите зависи от разпределението на текущите случайни стадии.
Въведение Методите „Монте Карло“ варират, но са обикновено следват определен модел: Дефиниране на областта на възможната входяща информация. Генериране на входяща информация на случаен принцип от вероятностно разпределение върху областта. Извършване на детерминистични изчисления на входящата информация. Съвкупност на резултатите.
Например, нека разгледаме ¼ кръг, вписан в единичен квадрат. Като се има предвид, че кръгът и квадратът имат съотношение на повърхнините, което е π/4, стойността на π може да бъде приблизително изчислена с помощта на метод „Монте Карло“: Начертава се квадрат на земята, а след това се вписва окръжност в него. Равномерно се разпръсват няколко обекта с еднакъв размер (зърна от ориз или пясък) над квадрата. Преброяват се обекти във вътрешността на кръга и общия брой на обектите. Съотношението на двата броя е приблизително равно на съотношението между двете области, което е π/4. Резултатът се умножава по 4, за да се изчисли π.
При тази процедура областта на входящата информация е квадратът, който обгръща кръг. Ние генерираме случайна входяща информация от разсейването на зърна над квадрата, след това извършваме изчисления на входящата информация (тест дали тя попада в кръга). И накрая обобщаваме резултатите, за да се получи нашият краен резултат, приблизителната стойност на π.
Има две важни точки за разглеждане тук: Първо, ако зърната не са равномерно разпределени, тогава нашите изчисления ще бъдат лоши. На второ място, трябва да има голям брой входяща информация. Изчисленията обикновено са лоши, ако само няколко зърна са случайно хвърлени в квадрата. Като цяло, изчисленията се подобряват, след като са хвърлени повече зърна.
Ползването на метод „Монте Карло“ изискват големи количества случайни числа. Тяхната употреба ускори развитието на генератори за псевдослучайни числа, които са далеч по-бързи, затова се използват повече от таблиците на случайни числа, които преди това са били използвани за статистическа извадка.
История Преди да бъде разработен методът „Монте Карло“, е използвана статистическа извадка да пресмятане неяснотите в симулациите. „Монте Карло“ симулациите обръщат този подход, намират решение на детерминирани проблеми, използвайки вероятностен аналог.
Ранният вариант на метод „Монте Карло“ може да бъде видян в експеримента „Иглата на Буфон“, където π може да бъде изчислен с хвърляне на игли на под, направен от паралелни и равни по разстояние ленти. През 1930 г. Енрико Ферми първи експериментира с метод „Монте Карло“, докато изучава неутронна дифузия, но не публикува нищо върху него.
Модерната версия на Марковска верига метод „Монте Карло“ е изработена в края на четиридесетте години на XX век от Станислав Улам, докато работи по проекти за ядрени оръжия в националната лаборатория „Лос Аламос“. Веднага след пробива на Улам, Джон фон Нойман разбира неговата важност и програмира електронноизчислителната машина ENIAC да прилага калкулациите на метод „Монте Карло“.
През 1946 г. физици от научната лаборатория „Лос Аламос“ разследват радиационната защита и дистанцията, която неутроните вероятно ще изминат през различни материали. Въпреки че повечето от необходимите данни, като средното разстояние на пътя на неутрона в една материя, преди да се сблъска с атомното ядро, и вероятността да се отдели много енергия от неутрона след сблъсък, физиците от Лос Аламос не успяват да решат проблема, използвайки конвенционални, детерминирани математически методи. Станислав Улам е имал идеята за използване на случайни експерименти.
Запазена в тайна, работата на Улам и Джон фон Нойман изисква кодово име. Колега на фон Нойман и Улам, Николас Метрополис, предлага да използват името Монте Карло, което е казино в Монако, където чичо му взима пари на заем от роднини, за да залага.
Използването на списък от случайни числа било изключително бавно, но фон Нойман измисля начин да се изчислят псевдослучайни числа, използвайки метод на средна квадратична грешка. Въпреки че този метод е доста критикуван, фон Нойман е наясно с това и го оправдава, като казва, че е най-бързият метод на негово разположение.
Методът „Монте Карло“ е централа на симулациите, които са изисквани за проектът „Манхатън“, макар и силно ограничени от изчислителните средства към момента. През петдесетте години на XX век са използвани в Лос Аламос за началото на работата, свързана с развитието на водородната бомба, и се популяризира в областта на физиката, физикохимията и изследване на операции.
Дефиниции Не се стига до консенсус как „Монте Карло“ следва да се определи. Примерно Рипли дефинира най-вероятностно моделиране като стохастично симулиране. Шломо Савиловски прави разграничение между симулация, метод „Монте Карло“ и „Монте Карло“ симулация: симулация е фиктивно изобразяване на реалността, „Монте Карло“ метод е техника, която може да бъде използвана да разрешава математически и статистически проблеми, и „Монте Карло“ симулацията се използва за многократно моделиране и да определя свойствата на някои явления (или поведения). Примери: Симулация: Имаме една псевдослучайна променлива от интервала [0,1] и тя може да бъде използвана да симулира хвърлянето на монета: Ако стойността е по-малка или равна на 0,50, определяме резултата като ези, а ако стойността е по-голяма от 0,50, определяме резултата като тура. Това е симулация, но не и „Монте Карло“ симулация. Метод „Монте Карло“: Изсипвайки пълна с монети кутия на маса, и след това изчислявайки съотношението на монетите, които лежат като ези и тура, е метод „Монте Карло“, който определя поведението на многократното хвърляне на монета, но не е симулация. „Монте Карло“ симулация: Имаме една голяма поредица от псевдослучайни променливи от интервала [0,1] и определяме стойностите им. Ако е по-малка или равна на 0,50 определяме резултата като ези, и ако е по-голяма от 0,50 – като тура, това е „Монте Карло“ симулация на поведението на многократно хвърляне на монета.
„Монте Карло“ и случайни числа „Монте Карло“ симулациите не винаги изискват наистина случайни числа, за да бъдат от полза.
Много от най-използваните техники използват псевдослучайни последователности, правейки ги лесни за тестване и с повтарящи се симулации.
Савиловски изброява характеристиките на „Монте Карло“ симулациите с най-високо качество: Един псевдослучаен генератор на числа има определени характеристики (примерно дългият „период“ преди повторението на последователността) Един псевдослучаен генератор на числа произвежда стойности, които преминават тестове за случайност Правят се достатъчно примери, за да осигурят точни резултати Използвана е техниката на правилното взимане на резултати Алгоритъмът, който е използван, е валиден за това, което се моделира Симулира въпросното явление
„Монте Карло“ симулации срещу „какво ако“ сценарии Има начини за използване на вероятностите, които определено не са „Монте Карло“ симулации – например, детерминираното моделиране използва изчисления на една точка. Всяка неопределена променлива в рамките на модел е определена с „най-доброто предположение“ като приблизителна оценка. Сценариите като най-добър, най-лош или най-вероятен за всяка входна променлива са избрани и резултатите са записани.
Приложения „Монте Карло“ методи са особено полезни за симулиране на явления със значителна несигурност във входната информация и системи с голям брой на обвързаните степени на свобода. Области на приложение включват:
Физика „Монте Карло“ методи са много важни в изчислителната физика, физикохимията и имат разнообразни приложения: от сложни изчисления в квантовата хромодинамика до проектирането на топлинни щитове и аеродинамични форми, както и в моделирането на радиационен транспорт от изчисленията на радиационната дозиметрия. В статистическата физика молекулно моделиране „Монте Карло“ е алтернатива на изчислителната молекулярна динамика, и методи „Монте Карло“ се използват за изчисляване на статистическите полеви теории на прости частици и полимерни системи. Квантовите методи „Монте Карло“ са решение за многотялостни проблеми в квантовите системи. В астрофизиката те се използват по различни начини, като например за моделиране както еволюцията на галактика, така и микровълнова радиационна трансмисия през груба планетарна повърхност. Методите „Монте Карло“ се използват и в модели, които са в основата на съвременното прогнозиране на времето.
Инженерство „Монте Карло“ методите се използват широко в инженерството за анализ на чувствителността и количествен вероятностен анализ в процеса на проектиране. Необходимост възниква от интерактивните, ко-линейните и нелинейните поведения на типичните процесни симулации. Например: В микроелектрониката методите „Монте Карло“ се прилагат, за да се анализират свързаните и несвързани помежду си вариации в аналоговите и цифрови интегрални схеми. В геостатистиката методите „Монте Карло“ са в основата на дизайна на технологичните схеми за обработка на минерали и допринасят за количествен анализ на риска. В телекомуникациите, при планирането на безжична мрежа, проектът трябва да се докаже, при голямо разнообразие от сценарии, които зависят главно от броя на потребителите, техните места и услугите, които те използват. Методите „Монте Карло“ обикновено се използват за генериране на тези потребители. Качеството на мрежата се оценява, ако резултатите не са задоволителни, дизайнът на мрежата преминава през процес на оптимизация. В теорията на надеждността може да се използва „Монте Карло“ симулация за генериране на средното време между сривовете и средното време за ремонт на компонентите.
Компютърна графика Path tracing, понякога наричан „Монте Карло“ рейтрейсинг, изобразява 3D сцена, като произволно проследява възможни пътища на светлината. Многократното пробонабиране на даден пиксел в крайна сметка може да доведе до средната стойност на пробите, която приближава до правилното решение на уравнението на изобразяване, което го прави един от физически най-точните методи за рендиране на 3D графика.
Изкуствен интелект за игри