Monte Carlo method/cs

From Simulace.info
Revision as of 16:19, 15 June 2015 by Xzizl00 (talk | contribs) (Created page with "=Úvod= Metoda Monte Carlo je souhrnné označení pro soubor algoritmů využívajících generování pseudonáhodných čísel pro an...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Úvod

Metoda Monte Carlo je souhrnné označení pro soubor algoritmů využívajících generování pseudonáhodných čísel pro analýzu jevů, na které mají vliv náhodné faktory. Metoda je založena na statistickém přístupu, kde se na základě mnohokrát opakovaných náhodných pokusech získají obecné charakteristiky, pomocí kterých bude možné popsat modelovaný jev.[1] Samotné dílčí pokusy nemají velkou vypovídající hodnotu, avšak mnohonásobné opakování těchto pokusů přináší použitelné výsledky díky platnosti zákona velkých čísel. Metoda Monte Carlo patří mezi stochastické simulační metody, protože opakování celé simulace se stejnými parametry vede k různým výsledkům. Metoda však umožňuje získání alespoň přibližných výsledků v situacích, kdy jsou běžné analytické přístupy příliš složité či nemožné. Při simulaci se metoda Monte Carlo spoléhá na pravděpodobnost, modelování náhodných veličin a statistické odhady jejich charakteristik.[2] Metodu Monte Carlo lze také použít pro simulaci deterministických úloh, které nepracují s náhodnými veličinami. Růst výpočetního výkonu počítačů se výrazným způsobem projevil na nárůstu popularity metody Monte Carlo v posledních letech. Široké uplatnění nachází zejména v matematice, statistice, fyzice, informatice a finančním inženýrství.

Historie

Georges Louis Leclerc de Buffon
Buffon.jpg
Datum narození:
  • 7. září 1707
  • Montbard, Burgundy, Francie

Datum úmrtí:

  • 16. duben 1788 (ve věku 80 let)
  • Paříž, Francie

Povolání: přírodovědec, matematik

Obr. 1: Buffonova jehla v reálném experimentu

Počátky použití typu analýzy, která později dostane název metoda Monte Carlo, lze vysledovat již v 18. století. Za první problém řešený pomocí přístupu Monte Carlo se považuje matematická úloha nazvaná Buffonova jehla. Úlohu v roce 1733 navrhl francouzský přírodovědec a matematik Georges Louis Leclerc de Buffon.[3] Zadaní úlohy zní: „Máme k dispozici jehlu a list papíru, na kterém jsou vyobrazeny rovnoběžné linky. Vzdálenost mezi jednotlivými linkami se rovná délce jehly. Na papír opakovaně házíme jehlu. Jaká je pravděpodobnost, že jehla po dopadu překříží některou z linek?“ Pomocí této úlohy je možné odhadnout hodnotu π. Pro lepší představu si tento experiment předvedeme, místo jehly však budou použita párátka s délkou 6 cm. Vzdálenosti mezi jednotlivými linkami jsou také 6 cm.

Vzorec pro výpočet hodnoty π:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \pi = \dfrac{2*n}{k}}

n... počet hodů

k... počet překřížení

Celkem bylo uskutečněno 20 hodů s párátky. Párátka překřížila některou z linek v 11 případech. Všechna překřížení jsou vyznačena na obrázku Obr. 1.

Nyní můžeme dosadit hodnoty z experimentu do vzorce:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \pi = \dfrac{2*20}{11} = 3,6364}

Výsledný odhad hodnoty π činí 3,6364. Odhad je nadhodnocený o přibližně 15,8 %, protože skutečná hodnota π se rovná 3,1416.


Stanislaw Ulam
Ulam.jpg
Datum narození:
  • 13. duben 1909
  • Lvov, Rakousko-Uhersko

Datum úmrtí:

  • 13. květen 1984 (ve věku 75 let)
  • Santa Fe, Nové Mexiko, USA

Povolání: matematik

Metoda Monte Carlo byla objevena ve 40. letech 20 století v Národní laboratoři Los Alamos v USA. O její vznik a následný rozvoj se zasloužili Stanislaw Ulam a John von Neumann, kteří v té době pracovali na vývoji atomové bomby v rámci projektu Manhattan. Zkoumali chování neutronů při průchodu různými druhy materiálů. Cílem jejich pokusů bylo předpovídání trajektorií neutronů. Společně vytvořili model života neutronů, který byl založen na ruletě. Jednotlivé etapy života neutronů byly reprezentovány různými ruletami. Každá ruleta měla své dílky rozdělena podle pravděpodobnosti, s jakou nastane daný jev.[2] Například bylo zjištěno, že v jednom případě ze sta došlo k pohlcení neutronu atomem vodíku při jejich vzájemné srážce. Každé roztočení kola rulety simulovalo pohyb neutronu. Roztáčení rulety probíhalo do doby, než byl neutron pohlcen nebo dokud se mu nepodařilo projít celou cestu.[4] Tímto způsobem bylo možné zjistit trajektorii pohybu každého neutronu. Metoda poté dostala název Monte Carlo. John von Neumann vytvořil program, který pomáhal s výpočty metody Monte Carlo na počítači ENIAC.


Popis metody Monte Carlo

John von Neumann
Neumann.gif
Datum narození:
  • 28. prosinec 1903
  • Budapešť, Rakousko-Uhersko

Datum úmrtí:

  • 8. únor 1957 (ve věku 53 let)
  • Washington, D.C., USA

Povolání: matematik, informatik, fyzik, statistik, ekonom

Obecný postup při řešení úloh

  1. stanovení cíle
  2. příprava dat a výběr nástroje
  3. rozbor problému
  4. stanovení pravděpodobnostního rozdělení náhodných veličin
  5. vytvoření modelu
  6. vygenerování mnoha scénářů
  7. statistické zpracování výsledků

Nejdříve si stanovíme cíl simulace. Je potřeba si uvědomit, za jakým účelem simulaci provádíme a čeho má být simulací dosaženo. Dále je vhodné mít kvalitní soubor dat, ze kterých se bude při simulaci vycházet. Poté zvolíme vhodný nástroj pro simulaci Monte Carlo, například MS Excel, MATLAB, SAS apod. Následně rozebereme problém a zvolíme klíčové parametry, které budeme používat v simulaci. Určíme náhodné veličiny a stanovíme jejich pravděpodobnostní rozdělení. Při stanovování pravděpodobnostního rozdělení náhodných veličin se vychází z historických dat. Pokud historická data nejsou k dispozici, lze využít znalostí a zkušeností expertů na danou oblast. Poté pomocí matematických vzorců vytvoříme model a vygenerujeme velké množství scénářů. Doporučuje se nejprve vygenerovat menší počet scénářů a ujistit se, že simulace pracuje správně.[2] Scénář vznikne tak, že se vygeneruje náhodná kombinace hodnot vstupních náhodných veličin podle jejich rozdělení pravděpodobností. Každý scénář tak představuje jeden možný vývoj reálné situace.[5] Nakonec statisticky zpracujeme výsledky a vyvodíme z nich závěry.

Časté chyby

Nevhodný výběr pravděpodobnostního rozdělení podstatně zkreslí výsledky a může způsobit, že simulace bude nepoužitelná. Generátory náhodných čísel ve skutečnosti negenerují zcela náhodná čísla, z tohoto důvodu se označují jako generátory pseudonáhodných čísel. Přímým důsledkem potom je, že některé generátory pseudonáhodných čísel generují „náhodnější“ čísla než jiné generátory. Nedostatečné opakování scénářů způsobí velmi nepřesné výsledky, z nichž se nedá vyvodit věrohodný závěr. Opomenutí důležitých veličin či špatný odhad neznámých veličin povede k nereálným výsledkům simulace.

Nevýhody metody Monte Carlo

Kvalita celé simulace Monte Carlo se odvíjí od přesnosti a správnosti dat, ze kterých se při simulaci vychází. Jedná se o metodu založenou na statistických principech, proto všechny získané výsledky mají omezenou přesnost a spolehlivost.[1] Dalším nedostatkem metody Monte Carlo je obtížnost stanovení pravděpodobnostního rozdělení náhodných faktorů spolu s respektováním jejich závislostí.

Praktická aplikace

Obr. 2: Buffonova jehla v prostředí MS Excel
Obr. 3: Ukázka elegantnějšího řešení Buffonovy jehly v prostředí MS Excel
Obr. 4: Řešení Buffonovy jehly metodou Monte Carlo v prostředí MS Excel

Jako příklad aplikace metody Monte Carlo na konkrétní problém nám opět poslouží úloha Buffonova jehla. Tentokrát ji ale budeme řešit prostřednictvím počítače. Budeme simulovat 20 hodů jehlou, tento scénář poté zopakujeme 1 000 krát a odhadneme přibližnou hodnotu π. Pravděpodobnost, že jehla překříží některou z linek je 63,6619 %, pokud se délka jehly rovná vzdálenosti rovnoběžných linek.[6] Nejdříve převedeme výše provedený reálný experiment s Buffonovou jehlou do prostředí MS Excel, neboť realita a počítačová simulace se v některých ohledech liší. Při řešení úlohy v Excelu je například nutné znát, s jakou pravděpodobností jehla po dopadu na papír překříží některou linku, abychom mohli rozhodnout, zda náhodně vygenerovaná hodnota bude spadat do intervalu „překříží“ nebo „nepřekříží“ (viz obrázek Obr. 2). Pro uskutečnění reálného experimentu jsme však nic podobného nepotřebovali znát. Vytvoření simulace podle kroků z reálného experimentu je sice dostatečně srozumitelné pro pochopení, avšak poněkud těžkopádné, protože nelze změnit počet hodů bez výraznějšího zásahu do kódu. Existuje elegantnější řešení, které využívá pravděpodobnostní rozdělení (viz obrázek Obr. 3). Hod jehlou je příkladem binomického rozdělení, protože výsledkem musí být buď „překříží“ nebo „nepřekříží“, jednotlivé hody jsou na sobě navzájem nezávislé a pravděpodobnost překřížení je v každém hodu stejná. Řešení Buffonovy jehly prostřednictvím metody Monte Carlo ukazuje obrázek Obr. 4. Scénář, ve kterém bylo simulováno 20 hodů jehlou, byl nejdříve zopakován 1 000 krát, a poté 10 000 krát. Vícenásobné opakování přináší přesnější výsledky. Odhad hodnoty π dle samotného 1. scénáře je 3,33, zatímco po tisícinásobném zopakování výsledný odhad činí 3,15 a po 10 000 opakování to je již 3,14.

Redukce rozptylu

Podrobnější informace o způsobech redukce rozptylu

Redukce rozptylu odhadovaných veličin v simulaci zvyšuje přesnost metody Monte Carlo. Existují dvě hlavní strategie redukce rozptylu: snížení proměnlivosti vstupů nebo upravení výstupů simulace.[7] Mezi nejvíce používané způsoby redukce rozptylu patří antitetické proměnné, metoda řídicích proměnných, metoda momentů, výběr podle důležitosti a stratifikovaný výběr.[8]

Interpretace výsledků

Podrobnější informace o interpretaci výsledků metody Monte Carlo

Před samotnou interpretací výsledků je vhodné provést validaci a verifikaci modelu. Validací se rozumí kontrola, zda má model smysl a chová se v souladu s realitou. Verifikace je kontrola počítačového kódu modelu, která ověřuje, zda model funguje přesně podle našich představ a provádí veškeré operace požadovaným způsobem. Také se doporučuje provést kontrolu přesnosti odhadů.[9]

Oblasti použití

Podrobnější informace o oblastech použití metody Monte Carlo

Metoda Monte Carlo nachází široké uplatnění v mnoha oborech lidské činnosti. Nejčastěji bývá využívána v následujících oblastech:

Matematika

Metoda Monte Carlo umožňuje řešit jednoduché i vícerozměrné integrály. Využívá se především pro počítání vícerozměrných integrálů, protože jejich způsob výpočtu pomocí běžných numerických metod je složitější než v případě výpočtu jednoduchých integrálů. Metoda Monte Carlo poskytuje lepší výsledky než jiné postupy. Lze ji také použít pro hledání kořenů rovnic nebo pro Millerův-Rabinův test prvočíselnosti, který dokáže rozhodnout, zda je dané celé číslo prvočíslem.[10] Metoda Monte Carlo se také využívá pro řešení úloh optimalizace z operačního výzkumu.[11]

Statistika

Metoda Monte Carlo je založena na statistických přístupech, proto není překvapivé, že se využívá i ve statistice samotné. Nejčastěji se s ní testují statistické hypotézy. Rostoucí popularitu zaznamenává v Bayesovské statistice, kde se využívá pro simulaci složitých modelů, které není možné zpracovat Bayesovskou analýzou.[12] V Bayesovské statistice se používá Markovova metoda Monte Carlo, která je založena na Markovových řetězcích. Markovovův řetězec je náhodný proces, ve kterém pravděpodobnost přechodu mezi dvěma stavy není závislá na předchozích stavech procesu, řídí se tak pouze současným stavem procesu.[13]

Fyzika

Metoda Monte Carlo využívá ve statistické fyzice, fyzikální chemii, kvantové fyzice, aerodynamice, fyzice částic či při předpovědi počasí. Často se využívá v případech, kdy není možné uskutečnit reálný experiment z důvodu nedostatku financí nebo nebezpečnosti. Statistická fyzika se zabývá zjišťováním vlastností makroskopického systému pomocí simulace chování velkého množství mikročástic, což je ideální pole působnosti pro metodu Monte Carlo, proto se zde také nejvíce využívá. Ve fyzikální chemii se pomocí metody Monte Carlo řeší sestavování rovnice modelovaného plynu.[1]

Finanční inženýrství

Ve finančním inženýrství se metoda Monte Carlo používá pro simulaci různých zdrojů nejistoty, které mají vliv na hodnotu finančního instrumentu, portfolia nebo investice. Metoda nachází využití zejména v korporátních financích při oceňování ziskovosti projektů, v investování při predikování cen finančních instrumentů, měnových kurzů či ekonomických ukazatelů i pro oceňování portfolií a finančních derivátů.

Informatika

V počítačové grafice se metoda Monte Carlo využívá při renderování 3D modelů, kde se pomocí metody Monte Carlo náhodně generují odrazy světla od různých ploch.[1] V roce 2006 byla vynalezena metoda, která se nazývá Monte Carlo vyhledávací strom. Využívá se při rozhodování umělé inteligence ve hrách.[14] Metoda umožňuje umělé inteligenci zvolit nejlepší možný tah v dané situaci.

Úloha k procvičení

Obchod zabývající se digitální distribucí počítačových her právě uvádí do prodeje novou RPG hru. Obchod by potřeboval znát, kolik EUR utrží z prodeje této hry každý den. Cena hry se bude pohybovat kolem 40 EUR (+/- 5 EUR z důvodu slevových akcí apod.). Očekává se, že se denně prodá 50 000 (+/- 5 000) kopií hry. Pro zjednodušení předpokládejte normální rozdělení pravděpodobnosti.

Výsledky: File:MC příklad na procvičení (výsledky).xlsx

Zajímavosti

Metoda Monte Carlo dostala název podle slavných kasin v Monte Carlu, protože princip simulací Monte Carlo zahrnuje prvky nahodilosti a opakování obdobně jako ruleta v kasinu. První AAA počítačovou hrou využívající pokročilou umělou inteligenci, která je založena na Monte Carlo rozhodovacích stromech, se stala strategie Total War: Rome II.[14]

Odkazy

  1. ↑ 1.0 1.1 1.2 1.3 KOŠINA, Martin. Metoda Monte Carlo a její využití ve financích : bakalářská práce [online]. Praha : Vysoká škola ekonomická v Praze, Fakulta informatiky a statistiky, 2014 [cit. 2015-05-22]. Dostupné z: http://www.vse.cz/vskp/show_file.php?soubor_id=1248931.
  2. ↑ 2.0 2.1 2.2 KUCHÁROVÁ, Miroslava. Metody Monte Carlo v systému Matlab : bakalářská práce [online]. Brno : Masarykova univerzita, Přírodovědecká fakulta, 2013 [cit. 2015-05-22]. Dostupné z: http://is.muni.cz/th/379700/prif_b/BakalarskaPraca.pdf.
  3. ↑ SHONKWILER, Ronald W a Franklin MENDIVIL. Explorations in Monte Carlo methods. New York: Springer, 2009, xii, 243 p. Undergraduate texts in mathematics. ISBN 03-878-7837-8.
  4. ↑ SEDLÁČKOVÁ, Barbora. Stanovení číselných charakteristik rizika pomocí simulace Monte Carlo : bakalářská práce [online]. Olomouc : Univerzita Palackého v Olomouci, Přírodovědecká fakulta, 2015 [cit. 2015-06-13]. Dostupné z: http://theses.cz/id/4jlfag/Sedlackova.pdf.
  5. ↑ HÉŽA, Lukáš. Simulace Monte Carlo v MS Excel : diplomová práce [online]. Olomouc : Univerzita Palackého v Olomouci, Přírodovědecká fakulta, 2013 [cit. 2015-05-22]. Dostupné z: http://theses.cz/id/gxbjr4/00172153-589053968.rar.
  6. ↑ WEISSTEIN, Eric W. Buffon's Needle Problem. MathWorld: A Wolfram Web Resource [online]. 2015 [cit. 2015-05-24]. Dostupné z: http://mathworld.wolfram.com/BuffonsNeedleProblem.html
  7. ↑ GLASSERMAN, Paul. Monte Carlo methods in financial engineering. New York: Springer, 2004, xiii, 596 p. ISBN 03-870-0451-3.
  8. ↑ TVRDÍK, Michal. Simulační metody při hodnocení cenných papírů : bakalářská práce [online]. Praha : Univerzita Karlova v Praze, Matematicko-fyzikální fakulta, 2007 [cit. 2015-06-13]. Dostupné z: https://is.cuni.cz/webapps/zzp/download/130014391/?lang=cs.
  9. ↑ BRANDIMARTE, Paolo. Handbook in Monte Carlo simulation: applications in financial engineering, risk management, and economics. New Jersey: John Wiley & Sons, Inc., 2014, xvii, 662 pages. ISBN 978-047-0531-112.
  10. ↑ VOPATOVÁ, Klára. Monte Carlo simulace v ekonometrii : bakalářská práce [online]. Praha : Vysoká škola ekonomická v Praze, Fakulta informatiky a statistiky, 2013 [cit. 2015-05-25]. Dostupné z: http://www.vse.cz/vskp/show_file.php?soubor_id=1210363.
  11. ↑ KOHLAS, Jürg. Monte Carlo Simulation im Operations Research. New York: Springer-Verlag, 1972, vi, 162 p. ISBN 35-400-5736-6.
  12. ↑ ALBERT, Jim. Bayesian computation with R. 2nd ed. New York: Springer, 2009, xii, 298 p. Use R!. ISBN 03-879-2297-0.
  13. ↑ VORÁČOVÁ, Šárka. Stochastické procesy: Markovovy řetězce s diskrétním časem. České vysoké učení technické v Praze: Fakulta dopravní [online]. 2015 [cit. 2015-05-26]. Dostupné z: http://www.fd.cvut.cz/department/k611/pedagog/K611THO_soubory/4_DTMC.pdf
  14. ↑ 14.0 14.1 CHAMPANDARD, Alex J. Monte-Carlo Tree Search in TOTAL WAR: ROME II’s Campaign AI. AiGameDev.com [online]. 2014 [cit. 2015-05-26]. Dostupné z: http://aigamedev.com/open/coverage/mcts-rome-ii/
Retrieved from "http://www.simulace.info/index.php?title=Monte_Carlo_method/cs&oldid=9934"