Метод „Монте Карло“

Методите „Монте Карло“ (или още експериментите „Монте Карло“) са широк клас от изчислителни алгоритми, които използват повтарянето на случайни извадки за постигане на числов резултат, разчитайки случайността да разкрие по начало детерминизирани явления. Те често се използват във физични и математически задачи и са най-полезни, когато е трудно или невъзможно използването на други математически методи. Методите „Монте Карло“ много често се използват в три отделни класа задачи: оптимизация, числови интеграли и генериране на извадки от разпределението на вероятностите.

При физичните задачи методите „Монте Карло“ са доста полезни за симулация на системи с много свързани степени на свобода, като течности, материали с неподредена структура, структурирани твърди частици и клетъчни структури. Други примери включват създаването на явления с неясен вход в събитията, като изчисляване на рискове в бизнеса. В приложение служи за прогнози за неуспех, превишаване на разходи и други. Тези прогнози често са по-добри от човешката интуиция.

По принцип „Монте Карло“ методите могат да се използват за решаването на всеки проблем от проблематичен характер. По закона за големите числа, за интеграли, описани с очаквана стойност от някаква случайна променлива, резултатът може да се изчисли приблизително, като се вземе емпиричната стойност независимо от зададената променлива. Когато вероятностното разпределение на променливата е параметризирано, математиците често използват сборника „Марков Монте Карло“ (накратко: MCMC). Главната идея е да се създаде модел на Марковска верига на описано съвместно вероятностно разпределение.

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

Въведение

Методите „Монте Карло“ варират, но са обикновено следват определен модел:

1. Дефиниране на областта на възможната входяща информация.

   

   Метод „Монте Карло“ се прилага за приблизително определяне на стойността на π. След поставянето 30 000 произволни точки, прогнозата за π е в рамките на 0,07% от действителната стойност

2. Генериране на входяща информация на случаен принцип от вероятностно разпределение върху областта.
3. Извършване на детерминистични изчисления на входящата информация.
4. Съвкупност на резултатите.

Например, нека разгледаме ¼ кръг, вписан в единичен квадрат. Като се има предвид, че кръгът и квадратът имат съотношение на повърхнините, което е π/4, стойността на π може да бъде приблизително изчислена с помощта на метод „Монте Карло“:

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

При тази процедура областта на входящата информация е квадратът, който обгръща кръг. Ние генерираме случайна входяща информация от разсейването на зърна над квадрата, след това извършваме изчисления на входящата информация (тест дали тя попада в кръга). И накрая обобщаваме резултатите, за да се получи нашият краен резултат, приблизителната стойност на π.

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

Ползването на метод „Монте Карло“ изискват големи количества случайни числа. Тяхната употреба ускори развитието на генератори за псевдослучайни числа, които са далеч по-бързи, затова се използват повече от таблиците на случайни числа, които преди това са били използвани за статистическа извадка.

История

Преди да бъде разработен методът „Монте Карло“, е използвана статистическа извадка да пресмятане неяснотите в симулациите. „Монте Карло“ симулациите обръщат този подход, намират решение на детерминирани проблеми, използвайки вероятностен аналог.

Ранният вариант на метод „Монте Карло“ може да бъде видян в експеримента „Иглата на Буфон“, където π може да бъде изчислен с хвърляне на игли на под, направен от паралелни и равни по разстояние ленти. През 1930 г. Енрико Ферми първи експериментира с метод „Монте Карло“, докато изучава неутронна дифузия, но не публикува нищо върху него.

Модерната версия на Марковска верига метод „Монте Карло“ е изработена в края на четиридесетте години на XX век от Станислав Улам, докато работи по проекти за ядрени оръжия в националната лаборатория „Лос Аламос“. Веднага след пробива на Улам, Джон фон Нойман разбира неговата важност и програмира електронноизчислителната машина ENIAC да прилага калкулациите на метод „Монте Карло“.

През 1946 г. физици от научната лаборатория „Лос Аламос“ разследват радиационната защита и дистанцията, която неутроните вероятно ще изминат през различни материали. Въпреки че повечето от необходимите данни, като средното разстояние на пътя на неутрона в една материя, преди да се сблъска с атомното ядро, и вероятността да се отдели много енергия от неутрона след сблъсък, физиците от Лос Аламос не успяват да решат проблема, използвайки конвенционални, детерминирани математически методи. Станислав Улам е имал идеята за използване на случайни експерименти.

Запазена в тайна, работата на Улам и Джон фон Нойман изисква кодово име. Колега на фон Нойман и Улам, Николас Метрополис, предлага да използват името Монте Карло, което е казино в Монако, където чичо му взима пари на заем от роднини, за да залага.

Използването на списък от случайни числа било изключително бавно, но фон Нойман измисля начин да се изчислят псевдослучайни числа, използвайки метод на средна квадратична грешка. Въпреки че този метод е доста критикуван, фон Нойман е наясно с това и го оправдава, като казва, че е най-бързият метод на негово разположение.

Методът „Монте Карло“ е централа на симулациите, които са изисквани за проектът „Манхатън“, макар и силно ограничени от изчислителните средства към момента. През петдесетте години на XX век са използвани в Лос Аламос за началото на работата, свързана с развитието на водородната бомба, и се популяризира в областта на физиката, физикохимията и изследване на операции.

Дефиниции

Не се стига до консенсус как „Монте Карло“ следва да се определи. Примерно Рипли дефинира най-вероятностно моделиране като стохастично симулиране. Шломо Савиловски прави разграничение между симулация, метод „Монте Карло“ и „Монте Карло“ симулация: симулация е фиктивно изобразяване на реалността, „Монте Карло“ метод е техника, която може да бъде използвана да разрешава математически и статистически проблеми, и „Монте Карло“ симулацията се използва за многократно моделиране и да определя свойствата на някои явления (или поведения). Примери:

• Симулация: Имаме една псевдослучайна променлива от интервала [0,1] и тя може да бъде използвана да симулира хвърлянето на монета: Ако стойността е по-малка или равна на 0,50, определяме резултата като ези, а ако стойността е по-голяма от 0,50, определяме резултата като тура. Това е симулация, но не и „Монте Карло“ симулация.
• Метод „Монте Карло“: Изсипвайки пълна с монети кутия на маса, и след това изчислявайки съотношението на монетите, които лежат като ези и тура, е метод „Монте Карло“, който определя поведението на многократното хвърляне на монета, но не е симулация.
• „Монте Карло“ симулация: Имаме една голяма поредица от псевдослучайни променливи от интервала [0,1] и определяме стойностите им. Ако е по-малка или равна на 0,50 определяме резултата като ези, и ако е по-голяма от 0,50 – като тура, това е „Монте Карло“ симулация на поведението на многократно хвърляне на монета.

„Монте Карло“ и случайни числа

„Монте Карло“ симулациите не винаги изискват наистина случайни числа, за да бъдат от полза.

Много от най-използваните техники използват псевдослучайни последователности, правейки ги лесни за тестване и с повтарящи се симулации.

Савиловски изброява характеристиките на „Монте Карло“ симулациите с най-високо качество:

• Един псевдослучаен генератор на числа има определени характеристики (примерно дългият „период“ преди повторението на последователността)
• Един псевдослучаен генератор на числа произвежда стойности, които преминават тестове за случайност
• Правят се достатъчно примери, за да осигурят точни резултати
• Използвана е техниката на правилното взимане на резултати
• Алгоритъмът, който е използван, е валиден за това, което се моделира
• Симулира въпросното явление

„Монте Карло“ симулации срещу „какво ако“ сценарии

Има начини за използване на вероятностите, които определено не са „Монте Карло“ симулации – например, детерминираното моделиране използва изчисления на една точка. Всяка неопределена променлива в рамките на модел е определена с „най-доброто предположение“ като приблизителна оценка. Сценариите като най-добър, най-лош или най-вероятен за всяка входна променлива са избрани и резултатите са записани.

Приложения

„Монте Карло“ методи са особено полезни за симулиране на явления със значителна несигурност във входната информация и системи с голям брой на обвързаните степени на свобода. Области на приложение включват:

Физика

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

Инженерство

„Монте Карло“ методите се използват широко в инженерството за анализ на чувствителността и количествен вероятностен анализ в процеса на проектиране. Необходимост възниква от интерактивните, ко-линейните и нелинейните поведения на типичните процесни симулации. Например:

• В микроелектрониката методите „Монте Карло“ се прилагат, за да се анализират свързаните и несвързани помежду си вариации в аналоговите и цифрови интегрални схеми.
• В геостатистиката методите „Монте Карло“ са в основата на дизайна на технологичните схеми за обработка на минерали и допринасят за количествен анализ на риска.
• В телекомуникациите, при планирането на безжична мрежа, проектът трябва да се докаже, при голямо разнообразие от сценарии, които зависят главно от броя на потребителите, техните места и услугите, които те използват. Методите „Монте Карло“ обикновено се използват за генериране на тези потребители. Качеството на мрежата се оценява, ако резултатите не са задоволителни, дизайнът на мрежата преминава през процес на оптимизация.
• В теорията на надеждността може да се използва „Монте Карло“ симулация за генериране на средното време между сривовете и средното време за ремонт на компонентите.

Компютърна графика

Path tracing, понякога наричан „Монте Карло“ рейтрейсинг, изобразява 3D сцена, като произволно проследява възможни пътища на светлината. Многократното пробонабиране на даден пиксел в крайна сметка може да доведе до средната стойност на пробите, която приближава до правилното решение на уравнението на изобразяване, което го прави един от физически най-точните методи за рендиране на 3D графика.

Изкуствен интелект за игри

Чрез методите „Монте Карло“ е разработена техника, наречена търсене в дърво „Монте Карло“, която е полезна за търсене на най-добрия ход в играта. Възможните ходове се организирани в структурата от данни дърво и голям брой от случайни симулации са използвани за оценяване в дългосрочен план потенциала на всеки ход.

Търсене в дърво „Монте Карло“ има четири стъпки:

1. Започвайки от корена на дървото, избиране на оптималните деца до достигането на листото.
2. Разширяване на листото и избиране на едно от децата му.
3. Симулативна игра, започващо от избраното дете.
4. Използване на резултата от симулативната игра, за да се обнови текущото листо и предците му.

Търсене в дърво „Монте Карло“ е успешно използван в игрите Го, Боен кораб(Battleship) и други.

Дизайн и визия

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

Полза в математиката

Общо взето, методите „Монте Карло“ са използвани в математиката да разрешават различни проблеми, генерирайки подходящи случайни числа.

Методът е полезен за получаване на числени решения на проблеми, които са твърде сложни да се решат аналитично. Най-често срещаното приложение на метод „Монте Карло“ е „Монте Карло“ интеграция (обединяване).

Интеграция

Числено интегрираните алгоритми работят добре в малки размери, но се натъкваме на два проблема, когато функциите имат много променливи. Първо – ако 10 теста осигуряват адекватна точност в едно измерение, тогава 10¹⁰⁰ точки са нужни за 100 измерения – което е твърде много да бъде изчислено. Това се нарича „проклятие на размерност“. Второ – границата на многомерния окръг може да бъде много сложна, така че може би не е много вероятно да се намали проблемът на итерирания интеграл.

100 измерения, отвсякъде погледнато, са необичайни, тъй като в много физични въпроси „измерението“ е еквивалентно на степен на свобода.

„Монте Карло“ методите се грижат да осигурят изход от увеличаването на времето за изчисление.

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

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

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

Задачата за търговския пътник е пример за конвенционален проблем за оптимизация. Ако знаете разстоянието между всички точки, целта е да се определи възможно най-краткия път при преминаване през всички възможни дестинации. Все пак нека приемем, че вместо да искаме да намалим общото разстояние, което сме преминали за да посетим всяка желана от нас дестинация, ние искаме да намалим общото време, което ни е нужно за достигане на всяка дестинация. Това излиза извън конвенционалната оптимизация, тъй като времето за пътуване е неопределено поради задръствания в трафика, време на деня и т.н. Като резултат, за да определим нашия оптимален път, ние бихме искали да използваме симулация – оптимизация, за да разберем първо обхвата на потенциалните времена, които биха могли да са необходими да стигнем от една точка до друга и след това да оптимизираме нашите маршрутни решения, за да определим най-добрия път, който да следваме, вземайки предвид неопределеността.