Пређи на садржај

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

С Википедије, слободне енциклопедије
(преусмерено са Monte Carlo method)
Не поистовећивати са Монте Карло алгоритам.
Рачунарска физика

Нумеричка анализа · Рачунарска симулација

Анализа података · Научна визуелизација
Потенцијали
Морзеов/дугометни потенцијал · Ленард-Џонсов потенцијал · Јукава потенцијал · Морзеов потенцијал
Динамика флуида
Метода коначних разлика · Метода коначних запремина

Метода коначних елемената · Метод граничних елемената

Метода Болцаманове решетке · Риманов решавалац

Динамике честичне дисипације

Хидродинамика глатких честица

Моделинг турбуленције
Монте Карло метод
Интеграција Монте Карло · Гибсово узорковање · Метрополис-Хастингс алгоритам
Честице
Симулација Н-тела · Метод честичне ћелије Молекулска динамика
Научници
Сергеј К. Годунов · Станислав Улам · Џон фон Нојман · Борис Галеркин · Едвард Нортон Лоренц

Монте Карло методе (или Монте Карло експерименти) чини група рачунарских алгоритама који се ослањају на понављање случајних покушаја да би се добили нумерички резултати. Често се користе у решавању физичких и математичких проблемима и веома су корисни у случајевима када је немогуће користити друге математичке методе. Ове методе се најчешће користе у три класе случаја:[1] оптимизацији, нумеричкој интеграцији и генерисању узорака код расподеле вероватноће.

У физичким проблемима, Монте Карло методе су веома корисне код симулације система са више степена слободе, као што су флуиди, јако везани раствори и ћелијске структуре (види ћелијски Потсов модел, интерактивне честичне системе, МекКин—Власове процесе, кинетичке моделе гасова). Остали примери укључују моделовање феномена са несигурним улазима попут висине ризика у бизнису или у математици, процене вичедимензионалних одрећених интеграла са сложеним граничним условима. У применама у свемирским и нафтним истраживањима, Монте—Карло базирана предвиђања неуспеха, прекорачења трошкова и неслагање са распоредом су много боља него људска интуиција или алтернативни „меки“ методи.[2]  

У принципу, Монте Карло методе се могу користити за решавање многих проблема с пробабилистичком интерпретацијом. По закону великих бројева, интеграли описани очекиваном вредношћу неке рандомне променљиве се могу апроксимирати узимањем емпиријског просека (а.к.а. просека узорка) независних узорака променљиве. Када је расподела вероватноће променљиве веома сложена, математичари често користе генератор узорака Монте Карло Марковог ланца (MCMC).[3][4][5][6] Главна идеја је стварање модела Марковог ланца са прописаним стационарним расподелама вероватноће. Та тај начин генерисани узорци у знатној мери ће одражавати жењену (циљну) дистрибуцију[7]. По ергодичној теореми, стационарна раподела вероватноће је апроксимирана емпиријским мерама случајних стања MCMC семплера.   

Код осталих пролема заинтересовани смо са генерисање узорака из низова расподеле вероватноће који задовољавају нелинеарне еволуционе једначине. Ови токови расподеле вероватноће увек могу бити интерпретиране као расподеле случајних стања Марковог процеса чија промена расподеле вероватноће зависи од расподеле тренутних  случајних стања ( види МекКин-Власов процесе, нелинерне филтер једначине)[8][9] . У осталим инстанцама  говоримо о току у расподели вероватноће са растућим нивоом сложености (модели простора са растућим временом, Болцман-Гибсове мере повезане са опадајућим температурним параметрима и многи други).[9][10] Ови модели се могу такође посматрати као развој случајних стања нелинеарног ланца Маркова.[10] Природни начин симулирања ових софистицираних процеса ланаца Маркова је узорковање великог броја копија процеса, заменом непознатих расподела  случајних стања у једначинама од стране емпиристичких мера. У супротности са традиционалним Монте Карло и ланцима Маркова методологијама ове технике честичног поља се ослањају на секвенцијалне интерагујуће узорке. Терминологија поља означава чињеницу да сваки од узорака (честице, индивидуе, шетачи, агенти, створења или фенотип) интерагује са емпиријским мерама процеса. Када величина система тежи бесконачности, ове случајне емпиријске мере конвергирају ка детерминистичкој расподели случајних стања ланаца Маркова, тако да се статистичка интеракција између честица губи.

Увод

[уреди | уреди извор]
Монте Карло метода примењена на апроксимацију вредности π. Након уцртавања 30000 произвољних тачака, процена π је у 0,07% од праве вредности. Ово се дешава са могућношћу процене од 20%

Монте Карло методе варирају, али теже да испрате одређени образац:

  1. Дефинише се домен улаза 
  2. Генерише се низ случајних улаза помоћу раподеле вероватноће 
  3. Изврши се детерминистички прорачуни 
  4. Изврши се сажимање резултата

На пример, узмимо у обзир круг уписан у квадрат. С обзиром на то да је однос ових површина π/4, вредност π се може апроксимирати употребом Монте Карло методе:[11]

  1. Нацртајмо квадрат на земљи, затим упишимо круг у њему 
  2. Равномерно проспимо неке објекте једнаке величине (зрна песка или пиринча) преко квадрата
  3. Преброји се број зрна у кругу и укупан број зрна однос два пребрајања је процена односа две површине тј. π/4. Помножи се резултат са 4, чиме се добија π.

У овој процедури домен улаза је квадрат који описујемо око круга. Генеришемо број улаза просипањем преко квадрата, затим извршимо прорачуне на сваки улаз (питамо се да ли је зрно пало у круг). Напокон, сажимамо резултате да би добили коначан резултат, апроксимацију π. Овде имамо две битне напомене: прво, ако зрна нису равномерно расподељена, онда је наша апроксимација непотпуна. Друго, мора да постоји велики број улаза. Апроксимација је генерално лоша само ако је пар зрна пало у цео квадрат. У просеку квалитет процене се повећава са већим бројем зрна у квадрату. Употреба Монте Карло методе захтева велику количину бројева, што је проузроковало формирање генератора псеудобројева чијом употребом је прорачунавање олакшано.

Историја

[уреди | уреди извор]

Пре него што је Монте Карло метода развијена, симулације су тестирале претходно дефинисане детерминистичке проблеме и статистичко узорковање је коришћено за процену неисигурности у симулацији. Монте Карло симулације су окренуле овај приступ, решавајући детерминистичке проблеме употребом вероватноће.[12]

Рана верзија Монте Карло метода се могла видети у Буфоновом експерименту игле, у ком је π апроксимирано бацањем игала на под који је направљен од паралелних трака једнаког растојања. У 30-им годинама 20. века, Енрико Ферми је први експериментисао са Монте Карло методом проучавајућу неутронску дифузију, али није објавио тај рад.

Модерна верзија ланаца Маркова Монте Карло метода је измишљена крајем 1940-их од стране Станислава Улама, док је радио на пројектима нуклеарног наоружања у Националној лабораторији Лос Аламос. Након Уламовог продора, Џон фон Нојман је разумео његову важност па је програмирао ENIAC рачунар да врши Монте Карло прорачуне. Годие 1946. физичари и лабораторији Лос Аламос су проучавали заштиту од радијације и дистанцу коју неутрон пређе при проласку кроз различите материјале. И поред познавања већине података, попут просечне дистанце коју неутрон пређе у материји пре судара са атомским језгром или колико енергије неутрон ослобађа при судару, физичари Лос Аламоса нису могли да реше проблем користећи конвенционалне детерминистичке методе. Станислав Улам је имао идеју која се базирала на вероватноћи, он то овако описује:

Прве мисли и покушаји да развијем овај метод су настале из питања које ми је пало на памет 1946. док сам се опорављао од болести и играо солитер. Питање је било: које су шансе да се Кенфилд солитер добије са 52 карте? Након што сам провео доста времена покушавајући да израчунам помоћу обичног математичког рачуна, питао сам се да ли би практичнији начин од оног "апстрактног" био да извршим 1000 покушаја и избројим успешне покушаје. Ово је већ било могуће урадити са почетком нове ере брзих рачунара и моментално сам почео да разматрам питање неутронске дифузије и многа друга питања математичке физике, и генерално како да проблеме дефинисане помоћу сигурних диференцијалних једначина интерпретирам помоћу сукцесије случајних операција. Касније (1946) описао сам ову идеју Џону фон Нојман и почели смо да радимо на прорачунима.[13]

Тајни рад Нојмана и Улама је захтевао тајно шифровано име. Њихов колега, Николас Метрополис, је предложио да то буде Монте Карло, по познатом Монте Карло казину у Монаку где је Уламов стриц позајмљивао новац од рођака за коцку.[12] Употреба листе "случајних" бројева је била изузетно спора па је Нојман развио начин да израчуна псеудо бројеве, употребом методе средњег квадрата. Иако је ова метода критикована као сирова, Нојман је то оправдавао њеном брзином у тој позицији, и такође приметио да ова метода прави очигледне грешке за разлику од неких чије су грешке тешко приметне.

Монте Карло методе су биле основне методе у раду компјутерских симулација Менхетн пројекта, иако ограничени од стране рачунарских алата у то време. У 50-им годинама 20. века коришћени су у лабораторији Лос Аламос при развоју хидрогенске бомбе и постале су популарне у физици, физичкој хемији и операционим истраживањима. Корпорација Ранд и Америчко ратно ваздухопловство су биле главне организације одоговорне за финансирање и пропаганду Монте Карло метода током тог времена и почеле су да налазе примену у многим областима.

Теорија поља честичног типа Монте Карло методе је почела да се развија крајем 60-их година радом Хенрија П. МекКина Јуниора на Марковим интерпретацијама класа нелинеарних параболичних парцијалних диференцијалних једначина произашлих из механике флуида.[14][15] Такође ћемо навести пионирски чланак Теодора Хариса и Хермана Кана, објављеног 1951., о коришћењу поља генетичког типа Монте Карло метода за процену преноса енергије честица.[16] Поље генетичког типа Монте Карло методологија је такође коришћено у еволуционом рачунарству код алгоритама природне хеуристичке претраге (Метахеуристичке). Основе ових техника се могу наћи још у 50-им годинама у раду Алана Тјуринга на генетском типу машина за мутациону-селекцију[17] и чланци Нилса Аала Баричелија са Института за напредне студије на Принстону, у Њу Џерзију.[18][19]

Квантни Монте Карло, и посебно Дифузиони Монте Карло методи се такође могу интерпетирати као поље честичних Монте Карло метода у апроксимацији Фејнман-Кацових интеграла.[20][21][22][23][24][25][26] Почеци ових метода се приписују Енрику Фермију и Роберту Ричмајеру који су развили 1948 честичну интерпретацију неутронске-ланчане реакције,[27] али први хеуристички алгоритми и генетски честични алгоритми за процену стања енергије квантних система (у редукованој матрици) су дело Џека Х. Хетерингтона 1948. године.[28] У молекуларној хемији, употреба генетских хеурситичких честичних методологија се може следити све до 1955. и рада МАршала Н. Розенблута и Аријане В. Розенблут.

Употреба секвенцијалног Монте Карла у напредној обради сигнала и Бајесовој интерференцији је све већа. Године 1993, Гордон и остали су објавили свој први рад[29] са првом применом овог метода у Бајесовој статистичкој интерференцији. Аутори су назвали свој алгоритам „бутстреп филтер“ и показали да у поређењу са другим филтерима, њихов алгоритам не захтева никакву процену о стању-простору или буци система. Такође ћемо цитирати још један пионирски чланак у овој области аутора Геншира Китагаве о поменутим „Монте Карло филтерима“,[30] и оне Пјера дел Морала[31] и Химилкона Карваља, Пјера дел Морала, Андреа Монина и Џерарда Салута[32] о честичним филтерима објављеним средином 90-их. Честични филтери су такође развијени у обради сигнала у периоду 1989-1992 од стране П. дел Морала, Џ. С. Нојера, Г. Ригала и Џ. Салута у ЛААС-ЦНРС у серији тајних пројеката СТЦАН, ИТ компаније ДИГИЛОГ, и ЛААС-ЦНРС (ЛАбораторија за анализу и архитектуру система) о проблемима процесије РАДАР/СОНАР и ГПС сигнала.[33][34][35][36][37][38] Ове секвенцијалне Монте Карло методологије могу се интерпретирати као семплери прихватања-одбијања са интерактивним обновљивим системом.

Од 1950. до 1996. године, све публикације на тему секвенцијалне Монте Карло методологије, укључујући и прераде и модификације Монте Карло методе уведене у рачунарској физици и молекуларнокј хемији, су предтавиле природни и хеуристичке алгоритми који се примењују у различитим ситуацијама без иједног доказа о њиховој доследности, нити расправа о пристрасности процена генеалошких и предачких стабала на бази алгоритама. Математичке основе и прву ригорозну анализу ових честица алгоритама су дело Пјера дел Мораа[31][39] из 1996. Честичне методологије са гранањем са различитим величинама популације су такође развијене крајем 1990. од стране Дена Крисана, Џесике Гејнс и Терија Лајонса[40][41][42][43] и Ден Крисана, Пјера дел Морала и Терија Лајона. [тражи се извор] Даљи развој у овој области су извршени 2000. од стране П. дел Морала, А. Гуионета и Л. Мицла .[21][44][45]

Дефиниција

[уреди | уреди извор]

Не постоји консензус о томе како треба да буду дефинисани Монте Карло методи. На пример, Рипли[46] дефинише моделирање највише вероватноће као стохастичку симулацију, док је Монте Карло резервисан за Монте Карло интеграције и Монте Карло статистичке тестове. Савиловски[47] разликује симулације, методе Монте-Карло, и Монте Карло симулације: симулација је измишљена представа стварности, метод Монте Карло је техника која се може користити за решавање математичког или статистичког проблем, а Монте Карло симулација користи поновио узорковање за утврђивање својства неке појаве (или понашања). Примери:

  • Симулација: Генерисање једне псеудо-случајне јединствене променљиве из интервала [0,1] коришћеног за симулацију бацања новчића: Ако је вредност мања или једнака 0,50 одреди исход као главу, али ако је вредност већа од 0,50 одредити исход као писмо. Ово је симулација, али не и Монте Карло симулација
  • Монте Карло метода: проспимо кутију кованица на сто, а затим израчунавање односа кованица са главом у односу на писма је Монте Карло метод за одређивања понашања поновљених бацања новчића, али није симулација.
  • Монте Карло симулација: Цртање великог броја псеудо-случајних јединствених варијабли из интервала [0,1], и додељивање вредности мањих или једнаких 0,50 као главе и већи од 0,50 као писма, је Монте Карло симулација понашања у више наврата бацања новчића.

Калос и Витлок[11] истичу да такве разлике нису увек лаке за одржавање. На пример, емисија зрачења код атома је природан стохастички процес. Може се симулирати директно или њено просечно понашање може бити описано стохастичим једначинама које се саме решавају коришћењем Монте Карло метода. "Заиста, исти рачунарски код може се истовремено посматрати као „природна симулација“ или као решењње једначина путем природног узорковања."

Монте Карло и случајни бројеви

[уреди | уреди извор]

Монте Карло симулације методе не захтевају увек истински случајне бројеве да би била корисне -док за неке примене, као што је тестирање узорака, непредвидивост је од виталног значаја.[48] Многе од најкориснијих техника користе детерминистичке, псеудослучајне секвенце, што олакшава тестирање и поновне симулације. Једини квалитет обично потребан да се направи добре симулације је да се у псеудо-случајном редоследу појави "довољно случајни" у одређеном смислу. Шта то значи зависи од апликације, али обично треба да прође низ статистичких тестова. Тестирања да су бројеви равномерно распоређени или прате другу жељену раподелу када је довољан велики број елемената у низу се сматрају једним од најједноставнијих и најчешћих. Слабе корелације између узастопних узорака је често пожељно / неопходно

Савиловски наводи карактеристике квалитетне Монте Карло симулације:[47]

  • је (псеудо-случајни) генератор бројева има одређене карактеристике (нпр дуг "рок" пред понављања секвенце)
  • је (псеудо-случајни) генератор бројева који производи вредности које пролазе тестове случајности
  • има довољно узорака како би се осигурали тачни резултати
  • користи се правилна техника узорковања
  • алгоритам се користи за оно за шта је моделиран
  • симулира феномен у питању.

Алгоритми узорковања псеудо-случајних бројева се користе за трансформацију равномерно распоређених псеудо-случајних бројева у бројеве који се дистрибуирају према датој расподели вероватноће. Секвенце мале несразмерности се често користе уместо случајног узорка јер имају бољу покривеност и обично имају бржи ред конвергенције од Монте Карло симулације помоћу случајних или псеудослучајних секвенци. Методе засноване на њиховој употреби се називају квази-Монте Карло методе.

Монте Карло методе против „шта ако“ сценарија

[уреди | уреди извор]

Постоје начини коришћења вероватноће које дефинитивно нису Монте Карло симулације - на пример, детерминистичко моделирање користи процене једне тачке. Свакој неизвесној променљивој у оквиру модела је додељена процена "најбоље претпоставке" . Сценарији (као што су најбољи, најгори, или највероватнији случај) за сваку улазну променљиву се бирају и резултати чувају.[49] Насупрот томе, узорак Монте Карло симулација из расподеле вероватноће за сваку променљиву произведе стотине или хиљаде могућих исхода. Резултати су анализирани да би се увидело да се јављају вероватноће различитих исхода.[50] На пример, поређење модела изградње табела трошкова користећи традиционални „шта ако“ сценаријо, а затим покретање поређења Монте Карло симулацијом, троугаона дистрибуција вероватноће показује да Монте Карло анализа има ужи опсег него "шта ако" анализа. Нпр. „шта ако“ анализа даје једнаку тежину свим сценаријима (види квантификативна несигурност у корпоративним финансијама), док је методом Монте Карло дају узорци у веома ниској вероватноћи региона. Узорци у таквим областима називају се „ретки догађаји“.

Примена

[уреди | уреди извор]

Монте Карло методе су посебно корисне за симулацију феномена са неизвесношћу улаза и системима са великим бројем спрегнутих степена слободе. Области примене укључују:

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

[уреди | уреди извор]
Види још: Монте Карло методе у статистичкој физици

Монте Карло методе су веома важне у рачунарској физици, физичкој хемији и сродним примењеним областима, и имају различите примене у комплексним квантним хромодинамичким прорачунима у дизајнирању топлотних штитова и аеродинамичких облика као и у моделирању транспорта зрачења у дозиметријским прорачунима.[51][52][53] У статистичкој физици Монте Карло молекуларно моделирање је алтернатива молекуларне рачунарске динамике, такође се користе за израчунавања у области статистичких теорија једноставних честица и полимерних система.[28][54] Квантне Монте Карло методе решавају проблем многих тела за квантне системе.[8][9][20] У експерименталној физици честица, Монте Карло методе се користе за израду детектора, разумевања њиховог понашања и поређења експерименталних података у теорији. У астрофизици, они се користе у различитим начинима моделирања еволуције галаксија[55] и микроталасном преносу зрачења кроз тешке планетарне површине. [тражи се извор] Монте Карло методе се користе у ансамблу модела који чине основу савремене нумеричкевременске прогнозе.

Инжењерство

[уреди | уреди извор]

Монте Карло методе су у широкој употреби у инжењерству у анализи осетљивости и квантитативним анализама вероватноће у процесу пројектовања. Потреба произилази из интерактивног, ко-линеарног и нелинеарног понашања симулација типичних процеса. На пример,

Рачунарска биологија

[уреди | уреди извор]

Монте Карло методе се користе у разним областима рачунарске биологије, на пример код Бајесових закључка у филогени, или за проучавање биолошких система као што су геноми, протеини,[60] или мембране.[61] Ови системи се могу проучавати у грубим or ab initiio оквирима у зависности од жељене прецизности. Компјутерске симулације нам омогућавају да пратимо локалну средину одређеног молекула и видимо да ли се нека хемијска реакција дешава, на пример. У случајевима где није изводљиво да се спроведе физички експеримент, мисаони експерименти се могу спроводити (на пример: разбијање веза, увођење нечистоће на одређеним местима, мењање локалних / глобалних структура, односно увођење спољних поља).

Рачунарска графика

[уреди | уреди извор]

Праћење пута, повремено називано Монте Карло праћење стазе, чини 3Д приказ случајног праћењу узорака могућих светлсоних стаза. Поновљено узорковање сваког пиксела на крају ће довести до тога да просечни узорци конвергирају ка исправном решењу једначине рендеровања, што га чини једним од најзначајнијих физички тачних метода за приказивање 3Д графике у реалности.

Примењена статистика

[уреди | уреди извор]

У примењеној статистици, Монте Карло методе се генерално користе у две сврхе:

  1. За поређење конкурентских статистика на малим узорцима под реалним условима података. Иако Тип 1 грешака и снага својства статистичких података се може израчунати за податке извучене из класичних теоријских расподела (нпр нормална крива, Кошијеве дистрибуције) за асимптотске услове (нпр. бесконачне величине узорка и бесконачно мали ефекат третмана), реални подаци често немају такве расподеле.[62]
  2. Да обезбеди имплементације хипотеза тестова који су ефикаснији од егзактних тестова, као што су пермутација тестова (које је често немогуће израчунати) док је прецизнији од критичних вредности за асимптотске расподеле.

Монте Карло методе су такође компромис између приближне случајности и тестова пермутација.Тестови приближне случајности се заснивају на одређеном подскупу свих пермутација (који подразумева потенцијално огроман уређивање од којих су пермутације сматра). Монте Карло приступ се заснива на одређеном броју насумично извучених пермутација (размену мањих губитака у прецизности ако се пермутација два пута извршава - или чешће-за ефикасност не морају да прате које су већ изабране пермутација).

Вештачка интелигенција код игрица

[уреди | уреди извор]
Главни чланак: Монте Карло претрага стабала

Монте Карло методе су развијене у техници под називом метод Монте-Карло претрага стабала који је користан за тражење најбољег потеза у игри. Могући потези су организовани у претрагу стабла и велики број случајних симулација се користи за процену дугорочног потенцијала сваког потеза. Симулатор црне кутије представља противникове потезе.[63] Монте Карло претрага стабала (МЦТС) има четири корака:[64]

  1. Почевши од корена стабла, изаберите оптималне наследнике чворова док се не нађе лист чвор.
  2. Проширите лист чвор и одаберите једно од његове деце.
  3. Започните симулирану игру почевши од тог чвора
  4. Користите резултате симулиране игре за ажурирање чвора и његових предака.

Нето ефекат, током многих симулација игре, је да вредност чвора који представља потез ће ићи горе или доле, при чему ће чвор представити добар или лош потез Монте Карло претрага стабла се успешно користи за играње игара као што су Го.[65] Тантрикс,[тражи се извор] Оклопњача,[66] Хавана,[67] и Аримаа[68]

Види још: Computer Go

Дизајн и визуелизација

[уреди | уреди извор]

Монте Карло методе су ефикасне у решавању спрегнутих интегралних диференцијалних једначина поља зрачења и преноса енергије, и на тај начин ове методе су коришћени у прорачунима Глобалног осветљења које производе фото-реалистичне слике виртуелних 3Д модела, са применама у видео играма, архитектури, дизајну, компјутерски генерисаним Филмовима, и филмским специјалним ефектима.[69]

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

[уреди | уреди извор]
Види још: Монте Карло методе у финансијама, Квази Монте Карло методе у финансијама, Монте Карло методе у формирању цена, Стоџастичко моделовање (осигурање) и Стохастички модел улагања

Монте Карло методе у финансијама се често користе за процену улагања у пројекте на пословном или корпоративном нивоу, или при процени финансијских производа. Могу се користити за моделовање распореда пројеката, где симулације сажима процене у најгорем случају, најбољем случају, као и исхода пројеката. Монте Карло методе користе се и код одређивања цена, анализе подразумеваних ризика .[70][71][72]

Примена у математици

[уреди | уреди извор]

У принципу, Монте Карло методе се користе у математици за решавање разних проблема кроз стварање одговарајућих случајних бројева (види Генерисање случајних бројева) и посматрање оних фракцију бројева који покорава неку имовину или имовине. Поступак је користан за добијање нумеричких решења за проблеме превише компликоване за аналитичко решавање. Најчешћи примена методе Монте Карло је Монте Карло интеграција.

Интеграција

[уреди | уреди извор]
Главни чланак: Интеграција Монте Карло
Монте Карло интеграција ради по принципу поређења произвоиљнх тачака са вредношћу функције
Грешке редуковане фактором

Алгоритми детерминистичке нумеричке интеграције раде добро у малом броју димензија, али наилазе на два проблема када функције имају много променљивих. Прво, број потребних процена функције рапидно се повећава са бројем димензија. На пример, ако 10 евалуација пруже адекватну тачност у једној димензији, за 100 димензија потребно је 10100 евалуације-исувише прорачуна. Ово се зове проклетство димензионалности. Друго, граница мултидимензионалног региона може бити врло компликована, тако да не би било могуће да се проблем смањи на итеративни интеграл.[73] 100 димензија никако није необично, јер у многим физичким проблемима, "димензија" је еквивалент степена слободе.

Монте Карло методе пружају излаз из овог експоненцијалног повећања рачунања времена. Докле год је функција са регулисаним начином понашања, може се проценити насумично одабиром процена у 100-димензионалном простору, и узимајући неку врсту просека вредности функције у тим местима. До централне граничне теореме, овај метод приказује конвергенције-нпр учетворостручавањем броја узоркованих процена преполовљава се грешка, без обзира на број димензија.[73]

Префињеност овог метода, позната као значај узорковања у статистици, подразумева узорковање процена случајно, али чешће где је интегранта велика. Да бисте то урадили управо један би морао да има ве познати интеграл, али може се приближно апроксимирати интегралу сличне функције или користити адаптивне рутине као што су 'стратификовано узорковање, рекурзивно слојевито узорковање, прилагодљиво кишобран узорковања[74][75] или ВЕГАС алгоритам.

Сличан приступ, квази-Монте Карло метода, користи ниске неслагања секвенци. Ове секвенце боље "попуњавају" област и узоркују најважније тачке, па квази-Монте-Карло методи брже конвергирају.

Друга класа метода за узимање узорака у запремини је да се симулира случајни пролаз кроз њега (уметање). Такве методе укључују Метрополис-Хастингс алгоритам, Гибсово узорковање, Ванг и Ландау алгоритам и сарадње MCMC методологије, као што су секвенцијални Монте Карло семплери.[76]

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

[уреди | уреди извор]
Главни чланак: Стохастичка оптимизација

Још једна снажна и врло популарна примена за случајне бројеве у нумеричким симулацијама је код нумеричких оптимизација. Проблем је да се минимизирају (или повећају) функције неког вектора који често има велики број димензија. Многи проблеми могу бити формулисана на овај начин: на пример, рачунарски шаховски програм се може посматрати како покушава да пронађе скуп, рецимо, 10 потеза који даје најбоље функције евалуације на крају. Код проблема трговачких путника циљ је да се минимизира удаљеност. Постоји примена у инжењерском дизајну, као што је дизајн мултидисциплинарне оптимизације. Она је примењена са квази-једнодимензионалним моделима за решавање динамичких проблема честица ефикасним истраживањем велике конфигурације простора.

Проблем трговачког путника је оно што се зове конвенционални проблем оптимизације. Циљ је одредити растојања између сваког одредишта потребног за утврђивање оптималног пута најмањом укупном међусобном удаљеношћу. Међутим претпоставимо да уместо најмање укуоне удаљености тражимо најкраће време за обилазак. Ово превазилази конвенционалне оптимизације, јер је путовање кроз време инхерентно неизвесно (саобраћајне гужве, доба дана, итд). Као резултат тога, за одређивање оптималне путање користимо симулацију - оптимизацију прво да би разумели низ потенцијалних времена потребних за кретање од једне до друге тачке (представљених расподелом вероватноће у овом случају пре него одређеном удаљеношћу) и онда оптимизовањем наше одлуке идентификујемо најбољи пут уз узимање фактора неизвесност у обзир.

Инверзни проблеми

[уреди | уреди извор]

Формулација вероватноће инверзног проблема доводи до дефиниције расподеле вероватноће у модела простора. Ова расподела комбинује претходне информације са новим информацијама добијеним мерењем неког видљивог параметара (подаци). Како, у општем случају, теорија која повезује податке са параметрима модела је нелинеарна, па се крајња вероватноћа у моделу простора не може лако описати (може бити мултимодална, неки тренуци се не могу дефинисати, итд).

Када се анализира инверзни проблем, добијање максималне веродостојности модела обично није довољна, као што обично и желите да имате информације о снази резолуције података. У општем случају имамо велики број параметара модела и претрага маргиналних густина вероватноће од интереса може бити непрактична, или чак бескорисна. Али, могуће је псеудонасумично генеришемо велику колекцију модела према задњој расподели вероватноће и да анализирамо и прикажемо моделе на такав начин да информације о релативним својставима модела преносе на гледаоца. Ово се може постићи помоћу ефикасног Монте Карло метода, чак и у случајевима када је доступна експлицитна формула за а приори расподелу .

Најпознатији значај метода узорковања, Метрополис алгоритам, може се генерализовати, и то даје метод који омогућава анализу (евентуално високо нелинеарних) инверзних проблема са сложеним а приори информацијама и податацима произвољне дистрибуције буке.[77][78]

Управљање залихама нафте

[уреди | уреди извор]

Монте Карло методе су веома популарне у управљању резервоарима угљоводоника у контексту нелинеарних инверзних проблема. Ово укључује стварање рачунарских модела нафтних и гасних резервоара са доследношћу посматраних података о производњи. Са циљем доношења одлука и проценом неизвесности, Монте Карло методе се користе за генерисање више геолошких реализација.[79]

У култури

[уреди | уреди извор]
  • Монте Карло Метод је албум јужнокалифорнијског рок бенда "Ништа обојено у плаво" из 1998. године.

Види још

[уреди | уреди извор]

Референце

[уреди | уреди извор]
  1. ^ Kroese, D. P.; Brereton, T.; Taimre, T.; Botev, Z. I. (2014). „Why the Monte Carlo method is so important today”. WIREs Comput Stat. 6: 386—392. doi:10.1002/wics.1314. 
  2. ^ Hubbard 2009
  3. ^ Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward (1. 6. 1953). „Equation of State Calculations by Fast Computing Machines”. The Journal of Chemical Physics. 21 (6): 1087—1092. Bibcode:1953JChPh..21.1087M. ISSN 0021-9606. doi:10.1063/1.1699114. 
  4. ^ Hastings, W. K. (1. 4. 1970). „Monte Carlo sampling methods using Markov chains and their applications”. Biometrika. 57 (1): 97—109. ISSN 0006-3444. doi:10.1093/biomet/57.1.97. 
  5. ^ Liu, Jun S.; Liang, Faming; Wong, Wing Hung (1. 3. 2000). „The Multiple-Try Method and Local Optimization in Metropolis Sampling”. Journal of the American Statistical Association. 95 (449): 121—134. ISSN 0162-1459. doi:10.1080/01621459.2000.10473908. 
  6. ^ Martino, Luca; Read, Jesse (11. 7. 2013). „On the flexibility of the design of multiple try Metropolis schemes”. Computational Statistics. 28 (6): 2797—2823. ISSN 0943-4062. doi:10.1007/s00180-013-0429-2. 
  7. ^ Spall, J. C. (2003). „Estimation via Markov chain Monte Carlo”. IEEE Control Systems. 23 (2): 34—45. doi:10.1109/MCS.2003.1188770. 
  8. ^ а б Kolokoltsov 2010
  9. ^ а б в Del Moral, Pierre (2013). Mean field simulation for Monte Carlo integration. Chapman & Hall/CRC Press. стр. 626. „Monographs on Statistics & Applied Probability” 
  10. ^ а б Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2006). „Sequential Monte Carlo Samplers”. Journal of the Royal Statistical Society Series B: Statistical Methodology. 68 (3): 411—436. doi:10.1111/j.1467-9868.2006.00553.x. 
  11. ^ а б Kalos & Whitlock 2008
  12. ^ а б Metropolis 1987
  13. ^ Eckhardt 1987
  14. ^ McKean, Henry, P. (1967). „Propagation of chaos for a class of non-linear parabolic equations”. Lecture Series in Differential Equations, Catholic Univ. 7: 41—57. 
  15. ^ McKean, Henry, P. (1966). „A class of Markov processes associated with nonlinear parabolic equations” (PDF). Proc. Nat. Acad. Sci. USA. 56 (6): 1907—1911. Bibcode:1966PNAS...56.1907M. PMC 220210 Слободан приступ. PMID 16591437. doi:10.1073/pnas.56.6.1907. 
  16. ^ Herman, Kahn; Harris, Theodore, E. (1951). „Estimation of particle transmission by random sampling” (PDF). Natl. Bur. Stand. Appl. Math. Ser. 12: 27—30. 
  17. ^ Turing, Alan M. „Computing machinery and intelligence”. Mind. LIX (238): 433—460. doi:10.1093/mind/LIX.236.433. 
  18. ^ Barricelli, Nils Aall (1954). „Esempi numerici di processi di evoluzione”. Methodos: 45—68. 
  19. ^ Barricelli, Nils Aall (1957). „Symbiogenetic evolution processes realized by artificial methods”. Methodos: 143—182. 
  20. ^ а б Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. стр. 575. „Series: Probability and Applications” 
  21. ^ а б Del Moral, Pierre; Miclo, Laurent (2000). Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering. (PDF). Lecture Notes in Mathematics. 1729. стр. 1—145. doi:10.1007/bfb0103798. 
  22. ^ Del Moral, Pierre; Miclo, Laurent (2000). „A Moran particle system approximation of Feynman-Kac formulae.”. Stochastic Processes and their Applications. 86 (2): 193—216. doi:10.1016/S0304-4149(99)00094-0. 
  23. ^ Del Moral, Pierre (2003). „Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups” (PDF). ESAIM Probability & Statistics. 7: 171—208. doi:10.1051/ps:2003001. 
  24. ^ Assaraf, Roland; Caffarel, Michel; Khelif, Anatole (2000). „Diffusion Monte Carlo Methods with a fixed number of walkers” (PDF). Phys. Rev. E. 61: 4566—4575. Bibcode:2000PhRvE..61.4566A. doi:10.1103/physreve.61.4566. Архивирано из оригинала (PDF) 07. 11. 2014. г. Приступљено 15. 11. 2015. 
  25. ^ Caffarel, Michel; Ceperley, David; Kalos, Malvin (1993). „Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms”. Phys. Rev. Lett. 71: 2159. Bibcode:1993PhRvL..71.2159C. doi:10.1103/physrevlett.71.2159. 
  26. ^ Hetherington, Jack, H. (1984). „Observations on the statistical iteration of matrices”. Phys. Rev. A. 30 (2713): 2713—2719. Bibcode:1984PhRvA..30.2713H. doi:10.1103/PhysRevA.30.2713. 
  27. ^ Fermi, Enrique; Richtmyer, Robert, D. (1948). „Note on census-taking in Monte Carlo calculations” (PDF). LAM. 805 (A). „Declassified report Los Alamos Archive” 
  28. ^ а б Rosenbluth, Marshall, N.; Rosenbluth, Arianna, W. (1955). „Monte-Carlo calculations of the average extension of macromolecular chains”. J. Chem. Phys. 23: 356—359. Bibcode:1955JChPh..23..356R. doi:10.1063/1.1741967. 
  29. ^ Gordon, N.J.; Salmond, D.J.; Smith, A.F.M. (1993). „Novel approach to nonlinear/non-Gaussian Bayesian state estimation”. Radar and Signal Processing, IEE Proceedings F. 140 (2): 107—113. ISSN 0956-375X. doi:10.1049/ip-f-2.1993.0015. 
  30. ^ Kitagawa, G. (1996). „Monte carlo filter and smoother for non-Gaussian nonlinear state space models”. Journal of Computational and Graphical Statistics. 5 (1): 1—25. JSTOR 1390750. doi:10.2307/1390750. 
  31. ^ а б Del Moral, Pierre (1996). „Non Linear Filtering: Interacting Particle Solution.” (PDF). Markov Processes and Related Fields. 2 (4): 555—580. Архивирано из оригинала (PDF) 04. 03. 2016. г. Приступљено 15. 11. 2015. 
  32. ^ Carvalho, Himilcon; Del Moral, Pierre; Monin, André; Salut, Gérard (1997). „Optimal Non-linear Filtering in GPS/INS Integration.” (PDF). IEEE-Trans. on Aerospace and electronic systems. 33 (3). Архивирано из оригинала (PDF) 10. 11. 2022. г. Приступљено 15. 11. 2015. 
  33. ^ P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : An unified framework for particle solutions LAAS-CNRS, Toulouse, Research Report no. 91137, DRET-DIGILOG- LAAS/CNRS contract, April (1991).
  34. ^ P. Del Moral, G. Rigal, and G. Salut. Nonlinear and non Gaussian particle filters applied to inertial platform repositioning. LAAS-CNRS, Toulouse, Research Report no. 92207, STCAN/DIGILOG-LAAS/CNRS Convention STCAN no. A.91.77.013, (94p.) September (1991).
  35. ^ P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Experimental results. Convention DRET no. 89.34.553.00.470.75.01, Research report no.2 (54p.), January (1992).
  36. ^ P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Theoretical results Convention DRET no. 89.34.553.00.470.75.01, Research report no.3 (123p.), October (1992).
  37. ^ P. Del Moral, J.-Ch. Noyer, G. Rigal, and G. Salut. Particle filters in radar signal processing : detection, estimation and air targets recognition. LAAS-CNRS, Toulouse, Research report no. 92495, December (1992).
  38. ^ P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Studies on: Filtering, optimal control, and maximum likelihood estimation. Convention DRET no. 89.34.553.00.470.75.01. Research report no.4 (210p.), January (1993).
  39. ^ Del Moral, Pierre (1998). „Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems”. Annals of Applied Probability (Publications du Laboratoire de Statistique et Probabilités, 96-15 (1996) изд.). 8 (2): 438—495. doi:10.1214/aoap/1028903535. 
  40. ^ Crisan, Dan; Gaines, Jessica; Lyons, Terry (1998). „Convergence of a branching particle method to the solution of the Zakai”. SIAM Journal on Applied Mathematics. 58 (5): 1568—1590. doi:10.1137/s0036139996307371. 
  41. ^ Crisan, Dan; Lyons, Terry (1997). „Nonlinear filtering and measure-valued processes”. Probability Theory and Related Fields. 109 (2): 217—244. doi:10.1007/s004400050131. 
  42. ^ Crisan, Dan; Lyons, Terry (1999). „A particle approximation of the solution of the Kushner–Stratonovitch equation”. Probability Theory and Related Fields. 115 (4): 549—578. doi:10.1007/s004400050249. 
  43. ^ Crisan, Dan; Del Moral, Pierre; Lyons, Terry (1999). „Discrete filtering using branching and interacting particle systems” (PDF). Markov Processes and Related Fields. 5 (3): 293—318. 
  44. ^ Del Moral, Pierre; Guionnet, Alice (1999). „On the stability of Measure Valued Processes with Applications to filtering”. C.R. Acad. Sci. Paris. 39 (1): 429—434. 
  45. ^ Del Moral, Pierre; Guionnet, Alice (2001). „On the stability of interacting processes with applications to filtering and genetic algorithms”. Annales de l'Institut Henri Poincaré. 37 (2): 155—194. doi:10.1016/s0246-0203(00)01064-5. 
  46. ^ Ripley 1987
  47. ^ а б Sawilowsky 2003
  48. ^ Davenport 1992
  49. ^ Vose 2000, стр. 13
  50. ^ Vose 2000, стр. 16
  51. ^ „GPU-based high-performance computing for radiation therapy”. Physics in Medicine and Biology. 59: R151—R182. Bibcode:2014PMB....59R.151J. doi:10.1088/0031-9155/59/4/R151. 
  52. ^ „Advances in kilovoltage x-ray beam dosimetry”. Physics in Medicine and Biology. 59: R183—R231. Bibcode:2014PMB....59R.183H. doi:10.1088/0031-9155/59/6/R183. 
  53. ^ „Fifty years of Monte Carlo simulations for medical physics”. Physics in Medicine and Biology. 51: R287—R301. Bibcode:2006PMB....51R.287R. doi:10.1088/0031-9155/51/13/R17. 
  54. ^ Baeurle 2009
  55. ^ MacGillivray & Dodd 1982
  56. ^ Int Panis et al. 2001
  57. ^ Int Panis et al. 2002
  58. ^ G. A. Bird, Molecular Gas Dynamics, Clarendon, Oxford (1976)
  59. ^ Dietrich, S.; Boyd, I. (1996). „A Scalar optimized parallel implementation of the DSMC technique”. Journal of Computational Physics. 126: 328—42. Bibcode:1996JCoPh.126..328D. doi:10.1006/jcph.1996.0141. 
  60. ^ Ojeda & et al. 2009,
  61. ^ Milik & Skolnick 1993
  62. ^ Sawilowsky & Fahoome 2003
  63. ^ (PDF) http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf.  Недостаје или је празан параметар |title= (помоћ)
  64. ^ „Monte Carlo Tree Search - About”. Архивирано из оригинала 29. 11. 2015. г. Приступљено 15. 11. 2015. 
  65. ^ Chaslot, Guillaume M. J. -B.; Winands, Mark H. M.; Van Den Herik, H. Jaap (2008). „Parallel Monte-Carlo Tree Search”. Computers and Games. Lecture Notes in Computer Science. 5131. стр. 60—71. ISBN 978-3-540-87607-6. doi:10.1007/978-3-540-87608-3_6. 
  66. ^ „Архивирана копија” (PDF). Архивирано из оригинала (PDF) 18. 07. 2016. г. Приступљено 15. 11. 2015. 
  67. ^ Lorentz, Richard J. (2011). „Improving Monte–Carlo Tree Search in Havannah”. Computers and Games. Lecture Notes in Computer Science. 6515. стр. 105—115. ISBN 978-3-642-17927-3. doi:10.1007/978-3-642-17928-0_10. 
  68. ^ (PDF) http://www.arimaa.com/arimaa/papers/ThomasJakl/bc-thesis.pdf.  Недостаје или је празан параметар |title= (помоћ)
  69. ^ Szirmay-Kalos 2008
  70. ^ Carmona, René; Del Moral, Pierre; Hu, Peng; Oudjane, Nadia (2012). Carmona, René A.; Moral, Pierre Del; Hu, Peng; Oudjane, Nadia, ур. „An Introduction to Particle Methods with Financial Applications”. Numerical Methods in Finance. Springer Proceedings in Mathematics. Springer Berlin Heidelberg. 12: 3—49. ISBN 978-3-642-25745-2. doi:10.1007/978-3-642-25746-9_1. 
  71. ^ „Numerical Methods in Finance - Springer”. link.springer.com. doi:10.1007/978-3-642-25746-9. 
  72. ^ Kroese, D. P.; Taimre, T.; Botev, Z. I. (2011). Handbook of Monte Carlo Methods. John Wiley & Sons. 
  73. ^ а б Press et al. 1996
  74. ^ MEZEI, M (31. 12. 1986). „Adaptive umbrella sampling: Self-consistent determination of the non-Boltzmann bias”. Journal of Computational Physics. 68 (1): 237—248. Bibcode:1987JCoPh..68..237M. doi:10.1016/0021-9991(87)90054-4. 
  75. ^ Bartels, Christian; Karplus, Martin (31. 12. 1997). „Probability Distributions for Complex Systems: Adaptive Umbrella Sampling of the Potential Energy”. The Journal of Physical Chemistry B. 102 (5): 865—880. doi:10.1021/jp972280j. 
  76. ^ „Sequential Monte Carlo samplers - Del Moral - Doucet - Jasra- 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library”. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 68: 411—436. doi:10.1111/j.1467-9868.2006.00553.x. 
  77. ^ Mosegaard & Tarantola 1995
  78. ^ Tarantola 2005
  79. ^ Shirangi, M. G., History matching production data and uncertainty assessment with an efficient TSVD parameterization algorithm, Journal of Petroleum Science and Engineering, http://www.sciencedirect.com/science/article/pii/S0920410513003227

Литература

[уреди | уреди извор]
Монте Карло метода на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Монте_Карло_метода&oldid=27808402”