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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

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

Въведение[редактиране | редактиране на кода]

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

  1. Дефиниране на областта на възможната входяща информация.
    Метод Монте Карло се прилага за приравняване на стойността на π. След поставянето 30000 произволни точки, прогнозата за π е в рамките на 0.07% от действителната стойност.
  2. Генериране на входяща информация на случаен принцип от вероятностно разпределение върху областта.
  3. Извършване на детерминистични изчисляваня на входящата информация .
  4. Съвкупност на резултатите .

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

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

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

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

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

История[редактиране | редактиране на кода]

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

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

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

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

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

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

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

Дефиниции[редактиране | редактиране на кода]

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

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

Монте Карло и случайни числа[редактиране | редактиране на кода]

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

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

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

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

Монте Карло симулации срещу "какво ако" сценарии[редактиране | редактиране на кода]

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

Приложения[редактиране | редактиране на кода]

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

Физика[редактиране | редактиране на кода]

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

Инженерство[редактиране | редактиране на кода]

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

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

Компютърна графика[редактиране | редактиране на кода]

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

Изкуствен интелект за игри[редактиране | редактиране на кода]

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

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

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

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

Дизайн и визия[редактиране | редактиране на кода]

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

Полза в математиката[редактиране | редактиране на кода]

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

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

Интеграция[редактиране | редактиране на кода]

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

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

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

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

Симулация и оптимизация[редактиране | редактиране на кода]

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

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