Monte Carlo meetodid

Allikas: Vikipeedia

Monte Carlo meetodid on rühm arvutialgoritme, mis kasutavad korduvat juhuslikku valimit tulemuste arvutamiseks. Kõige enam kasutatakse Monte Carlo meetodeid arvutisimulatsioonides matemaatiliste ja füüsikaliste süsteemide jaoks. Need meetodid on eelkõige mõeldud arvutiga arvutamiseks ja neid kasutatakse siis, kui deterministliku algoritmiga (sama sisend annab alati sama väljundi) täpse vastuse saamine on teostamatu. [1]

Monte Carlo meetodi defineerimisel puudub konsensus.

Monte Carlo meetodid on eriti kasulikud paardunud vabadusastmetega süsteemide, näiteks vedelike ja rakustruktuuride simuleerimiseks. Neid kasutatakse suure sisendmääramatusega nähtuste modelleerimiseks, näiteks ärinduses riski arvutamiseks. Samuti kasutatakse neid rohkesti matemaatikas, näiteks paljumõõtmeliste (mitmekordsete) ja keeruliste ääretingimustega määratud integraali lahendamiseks.

Nimetuse „Monte Carlo meetod“ võtsid kasutusele John von Neumann, Stanislaw Ulam ja Nicholas Metropolis 1940. aastatel, kui nad tegelesid Manhattani projektiga. Nimetus tuli Monte Carlo kasiino järgi, kus Ulami onu tihti oma raha maha mängis. [2]

Monte Carlo meetodeid on mitmesuguseid, kuid nad kipuvad järgima teatud raamistikku:

  1. defineerida sisendite määramispiirkond
  2. genereerida juhusliku jaotusega sisendväärtusi üle määramispiirkonna
  3. arvutada sisendid deterministlikult
  4. koondada tulemused.

π arvutamise näide[muuda | redigeeri lähteteksti]

Olgu vaja arvutada π väärtus. Selleks võib lähtuda pildist, millel on kujutatud ruudu sisse kujundatud ring:

Cricumsquares.png

Lihtsuse mõttes võib sellest pildist kasutada ainult veerandit, sest ülejäänud veerandid on samasugused:

Quarter.png

Kui nüüd joonist pimesi nooltega loopida, siis nende noolte arv, mis tabasid ruutu, ja nende noolte arv, mis tabasid värvitud veerandringi, on propotsionaalsed vastavate pindaladega ehk

 \frac{\text{noolte arv värvitud alas}}{\text{noolte arv kogu ruudus}} = \frac{\text{värvitud ala pindala}}{\text{kogu ruudu pindala}} .

Pindala valemeid mäletades saame:

 \frac{\text{noolte arv värvitud alas}}{\text{noolte arv kogu ruudus}} = \frac{1/4 \pi r^2}{r^2} = \frac{1}{4} \pi, millest \pi = 4 \frac{\text{noolte arv värvitud alas}}{\text{noolte arv kogu ruudus}}.

Värvitud ala tabamuste suhe möödavisetega on ¼ π väärtusest. Et saada mõistlik tulemus π väärtusele, peaks noolte arv olema suur.

Ise seda teha on raske ja selleks kasutatakse lihtsaid arvutialgoritme, nagu näiteks:

Olgu ringi raadius 1 ühik. Iga viske jaoks saab genereerida kaks juhuarvu, mida kasutatakse x- ja y-koordinaadina. Seejärel saab Pythagorase teoreemi abil leida kauguse koordinaatide alguspunktist (0,0). Kui see on \leqslant 1 , on see värvitud ala sees ja loeb. Tehes seda tuhandeid või rohkem kordi, saame päris mõistliku väärtuse π jaoks.

Ajalugu[muuda | redigeeri lähteteksti]

Monte Carlo meetodi algset varianti võib näha Buffoni nõela eksperimendis, kus saab leida π ligikaudse väärtuse, pillates nõelu paralleelsete puitplaatidega põrandale. 1930-ndatel eksperimenteeris Enrico Fermi Monte Carlo meetodiga, esimest korda neutronite difusiooniga katsetades, kuid ei avaldanud midagi sellekohast.[2]

Aastal 1946 uurisid füüsikud Los Alamose teaduslaboratooriumis radioaktiivse kiirguse varjestust ja distantsi, mida neutronid tõenäoliselt eri materjalides läbiksid. Kuigi oli olemas enamik vajalikke andmeid, nagu keskmine vaba tee pikkus, mida neutron tõenäoliselt aines läbiks enne aatomituumaga kokkupõrkamist, ja kui palju energiat neutron tõenäoliselt kokkupõrke järel välja annaks, ei suutnud füüsikud lahendada probleemi traditsiooniliste deterministlike matemaatiliste meetodite abil. Poola-ameerika matemaatikul Stanisław Ulamil tekkis idee kasutada juhuslikke eksperimente. Ta kirjeldas enda inspiratsiooni tekkimist järgmiselt:

„Esimesed ideed ja katsed Monte Carlo meetodi praktiseerimiseks ilmnesid mulle aastal 1946 haigusest toibudes ja pasjanssi mängides ühe küsimuse näol. See küsimus on järgmine: "Mis on tõenäosus 52 kaardi väljaladumisel Canfieldi pasjanss edukalt lõpetada?" Kui ma olin juba kulutanud tükk aega, proovides arvutada tõenäosust puhtalt kombinatoorsete kalkulatsioonide kaudu, murdsin ma pead, üritades otsustada, kas poleks näiteks kaartide 100-kordne väljaladumine ja tulemuste jälgimine praktilisem meetod kui puhas abstraktne mõtlemine. Katse ja eksituse meetodit oli kerge ette kujutada tänu kiirete arvutite ajastu algusele ning ma hakkasin kohe mõtlema probleemidest füüsika valdkonnas, näiteks neutronite hajumisele ja teistele küsimustele matemaatilises füüsikas, ning üldisemalt: kuidas muuta diferentsiaalvõrrandite kirjeldatud protsesse niisugusse vormi, mida saaks tõlgendada juhuslike operatsioonide järgnevusena. Hiljem [aastal 1946] kirjeldasin ma oma ideed John von Neumannile ja me hakkasime kavandama tegelikke arvutusi.“

Stanisław Ulam[3]

Kuna von Neumanni ja Ulami töö oli salajane, vajas see varjunime, milleks von Neumann valis Monte Carlo. Nimi viitab Monte Carlo kasiinole Monacos, kus Ulami onu laenas raha õnnemängude jaoks.[1] Von Neumann arendas meetodi pseudojuhuslike arvude kalkuleerimiseks, kasutades ruutkeskmise meetodit, kuna tõeliselt juhuslike numbrite loendi kasutamine oli väga aeglane[4]. Kuigi seda meetodit peeti algeliseks, oli von Neumann sellest teadlik. Ta õigustas selle kasutamist, kuna see oli kiirem kui kõik teised tema käsutuses olevad meetodid, ja väärtulemused olid ilmselged, erinevalt teistest meetoditest, mille tulemused võisid olla märkamatult väärad.

Monte Carlo meetodid olid Manhattani projekti simulatsioonide keskmeks, kuigi piiratud tollaste arvutusvahendite poolt. 1950. aastatel kasutati neid Los Alamosel vesinikpommi arenduse varastes arengustaadiumides ning need muutusid populaarseks füüsika, füüsikalise keemia ja tegevusanalüüsi valdkonnas. Sellel ajal vastutasid Monte Carlo meetodite rahastamise ja leviku eest ettevõte RAND ja Ameerika Ühendriikide Õhujõud ning nende rakendus hakkas levima järjest kiiremini ja järjest rohkematesse valdkondadesse.

Monte Carlo meetodite kasututamine vajab suurtes kogustes juhuarve ja nende kasutuselevõtt ergutas pseudojuhuslike arvude generaatorite arendust, mis omakorda olid mitu korda kiiremad kui juhuarvude tabelid, mida varem statistikas kasutati.

Rakendused[muuda | redigeeri lähteteksti]

Monte Carlo meetodid on eriti kasulikud selleks, et simuleerida nähtusi, millel on suure määramatusega sisendid, ja süsteeme, millel on suur hulk paardunud vabadusastmeid. Peamised kasutusalad on

  • tehnika
  • arvutusbioloogia
  • rakendusstatistika
  • arvutimängud
  • disain
  • rahandus
  • telekommunikatsioon.

Rakendused matemaatikas[muuda | redigeeri lähteteksti]

Monte Carlo meetodeid kasutatakse matemaatikas mitmesuguste ülesannete lahendamiseks. Genereeritakse sobilikke juhuslikke arve ja jälgitakse seda arvude osa, mis käitub mingile omadusele kohaselt. Meetod on kasulik arvuliste lahendite leidmiseks probleemidele, mida on liiga keeruline analüütiliselt lahendada. Kõige kasutatum Monte Carlo meetod on Monte Carlo integreerimine.

Integreerimine[muuda | redigeeri lähteteksti]

Monte Carlo integreerimine on meetod, millega arvutatakse määratud integraalidele arvulisi lahendeid, kasutades juhuslikke arve. Monte Carlo algoritmid valivad suvalise punkti, kus integraali arvutatakse.[5] See meetod on eriti kasulik kordsete integraalide lahendamiseks.[6]

Ülevaade[muuda | redigeeri lähteteksti]

Deterministlikud arvulised integreerimisalgoritmid töötavad hästi väheste mõõtmete korral, aga esineb kaks probleemi, kui funktsioonidel on mitu muutujat. Esiteks mõõtmete arvu kasvuga suureneb järsult funktsiooni hinnangute arv. Näiteks kui 10 hinnangut tagavad piisava täpsuse ühes mõõtmes, siis 100 mõõtmes on vaja 10100 punkti arvutada, mis nõuab ilmselgelt liiga palju arvutusvõimsust. Teiseks, mitmemõõtelise piirkonna ääretingimus võib olla väga keeruline, seega ei pruugi olla mõistlik lihtsustada probleemi mitmele ühekordsele integraalile. [7] 100 mõõdet ei ole mitte mingil määral ebaharilik, kuna paljudes füüsikalistes probleemides mõõde võrdub vabadusastmega. Monte Carlo meetodid võimaldavad väljapääsu arvutusaja eksponentsiaalsest kasvust.

Olgu hulk \Omega \mathbb{R}^D osahulk, millel kordne määratud integraal

I = \int_{\Omega}f(\bar{\mathbf{x}}) \, d\bar{\mathbf{x}}

arvutatakse ruumipiirkonnas \Omega:

V = \int_{\Omega}d\bar{\mathbf{x}}.

Kõige labasem viis I arvutamiseks on piirkonnas \Omega valimeid võttes [8]: andes N-ile palju kordi valimeid \bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_N\in \Omega. I-le saab hea lähendi kujul:

 I \approx Q_N \equiv V \frac{1}{N} \sum_{i=1}^N f(\bar{\mathbf{x}}_i) = V \langle f\rangle.

Mida suurem hulk valimeid võtta, seda väiksem on kõrvalekalle tegelikust väärtusest:

 \lim_{N \to \infty} Q_N = I.

Funktsiooni lähendi saab leida, valides suvaliselt punkte 100-mõõtmelises ruumis ja leides nende funktsioonide keskmise väärtuse. Keskse piirteoreemi põhjal näitab see meetod \scriptstyle 1/\sqrt{N} koonduvust: kui neljakordistada valimit, väheneb viga kahekordselt, olenemata mõõtmete arvust.[7]

Kui võrrelda Monte Carlo ja Las Vegase algoritmi, siis esimene on mõeldud eelkõige lähendi leidmiseks tegelikule väärtusele ja seda kasutatakse siis, kui ühest funktsiooni ei ole defineeritud. Las Vegase algoritm annab alati õige vastuse või jätab selle andmata. Lisaks võib Las Vegase algoritmi katkestamine anda Monte Carlo meetodile sarnase tulemuse, kuna tulem ei ole enam 100% korrektne.

Viited[muuda | redigeeri lähteteksti]

Kasutatud kirjandus[muuda | redigeeri lähteteksti]

  • Hubbard, Douglas (2007). How to Measure Anything: Finding the Value of Intangibles in Business. John Wiley & Sons. p. 46. 
  • Metropolis, N. (1987). "The beginning of the Monte Carlo method". Los Alamos Science (1987 Special Issue dedicated to Stanisław Ulam): 125–130. 
  • Eckhardt, Roger (1987). "Stan Ulam, John von Neumann, and the Monte Carlo method". Los Alamos Science, Special Issue (15): 131–137. 
  • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). Numerical Recipes: The Art of Scientific Computing (väljaanne 3rd ). New York: Cambridge University Press. ISBN 978-0-521-88068-8. 
  • Newman, MEJ; Barkema, GT (1999). Monte Carlo Methods in Statistical Physics. Clarendon Press. 
  • Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1996) [1986]. Numerical Recipes in Fortran 77: The Art of Scientific Computing. Fortran Numerical Recipes 1 (väljaanne Second ). Cambridge University Press. ISBN 0-521-43064-X. 

Välislingid[muuda | redigeeri lähteteksti]