Metoda Monte Carlo

Monte Carlo je třída algoritmů pro simulaci systémů. Jde o stochastické metody používající pseudonáhodná čísla. Typicky využívány pro výpočet integrálů, zejména vícerozměrných, kde běžné metody nejsou efektivní. Metoda Monte Carlo má široké využití od simulací experimentů přes počítání určitých integrálů až třeba po řešení diferenciálních rovnic. Základní myšlenka této metody je velice jednoduchá, chceme určit střední hodnotu veličiny, která je výsledkem náhodného děje. Vytvoří se počítačový model toho děje a po proběhnutí dostatečného množství simulací se mohou data zpracovat klasickými statistickými metodami, třeba určit průměr a směrodatnou odchylku.

Historie

Metoda Monte Carlo byla formulována již ve 40. letech 20. století a svého využití se dočkala ještě v průběhu druhé světové války. Jejím zakladatelem byl Stanisław Marcin Ulam a John von Neumann, kteří v té době pracovali v americké Národní laboratoři Los Alamos, kde zkoumali chování neutronů, především je zajímalo, jaké množství neutronů projde různými materiály (např. nádrží vody).^[1]

Přes velké množství informací nebylo možné tento problém vyřešit teoreticky ani prakticky. K výsledku dopomohla až metoda Monte Carlo, kdy se autoři nechali inspirovat kolem rulety (odtud také název Monte Carlo). Bylo jim známo, že k pohlcení neutronu jiným atomem dojde v přibližně jednom případu ze sta. Každé roztočení rulety by simulovalo pohyb neutronu, pokud by se zastavila na dílku, který znázorňuje pohlcení neutronu, neutron by cestu neprošel. To by se opakovalo vždy tak dlouho, dokud by neutron nebyl pohlcen nebo dokud by úspěšně prošel celou cestu.^[2]

Ač je tento příklad velmi zjednodušený, podstatu metody Monte Carlo vystihuje. Simulace by byla pochopitelně velmi časově náročná, pokud by se skutečně pokaždé točilo ruletou. V té době však již vznikaly první počítače, které tyto simulace výrazně zkrátily.

Buffonova jehla a výpočet hodnoty π

Vzdáleným předchůdcem metody Monte Carlo je tzv. Buffonova jehla. Je to úloha z roku 1777, jejímž autorem je francouzský matematik Georges Louis Leclerc de Buffon. Jde o pokus, kdy se na arch papíru, který je rozdělen rovnoběžnými linkami, hází jehlou, která má stejnou délku, jako je vzdálenost mezi čárami. Lze spočítat, že pravděpodobnost, že jehla některou čáru protne, je 2/π. Z toho se dá na základě několika opakovaných pokusů odhadnout hodnota π.

Také dnes se princip metody Monte Carlo často demonstruje na následujícím odhadu hodnoty Ludolfova čísla π. (V praxi se ovšem metoda Monte Carlo k tomuto účelu nepoužívá, protože výpočet Ludolfova čísla jinými metodami je mnohem efektivnější.) Základem je čtverec, kterému je vepsaná čtvrtkružnice. Analogicky jako u Buffonovy jehly je možné jeho hodnotu zjistit náhodným házením drobnými předměty do prostoru čtverce, a výsledný poměr hodů do čtvrtkruhu ku počtu všech hodů dá odhad čtvrtiny čísla π.^[3] Rychlejší je ovšem napsat počítačový program, který házení předmětů simuluje pomocí generátoru pseudonáhodných čísel.

obsah čtvrtkružnice: ${\displaystyle S_{1}={\frac {\pi r^{2}}{4}}}$

obsah čtverce: ${\displaystyle S_{2}=r^{2}}$

jejich poměr je pak :${\displaystyle {\frac {S_{1}}{S_{2}}}={\frac {\pi r^{2}}{4r^{2}}}={\frac {\pi }{4}}}$

pak ${\displaystyle \pi =4{\frac {S_{1}}{S_{2}}}}$

Program v jazyce Python 3, který tento výpočet realizuje a je obohacený o výpočet standardní chyby, skutečné chyby a intervalu spolehlivosti odhadu, může vypadat takto:

import random, math
def mc_pi(n=100):
    """ Odhad čísla pí na základě n pokusů metodou Monte Carlo."""
    print ("Odhad Ludolfova čísla na základě", n, "pokusů:\n")
    v_ctvrtkruhu = 0  # čítač bodů, které padly do čtvrtkruhu
    for i in range(n):  # opakování experimentu n-krát
        x, y = random.random(), random.random()  # generuje náhodný bod
        if x * x + y * y < 1:  # test, zda bod padl do čtvrtkruhu
            v_ctvrtkruhu += 1  # pokud ano, tak aktualizace čítače
    podil = v_ctvrtkruhu / n  # podil bodů v čtvrtkruhu            
    odhad_pi = 4 * podil  # odhad pí
    sdt_err = 4 * math.sqrt(podil * (1 - podil) / n)  # std. chyba odhadu 
    chyba = odhad_pi - math.pi  # skutečná chyba odhadu
    print ("  ", odhad_pi, "\n")
    print ("95% interval spolehlivosti je", odhad_pi - 1.96 * sdt_err, 
           "až", odhad_pi + 1.96 * sdt_err)
    print ("Skutečná chyba je", chyba, "- tedy", 100 * chyba / math.pi, "%")
    return odhad_pi

mc_pi(n=10000)

Aplikace

Přesnost a efektivnost celého výpočtu metodou Monte Carlo pomocí výpočetní techniky je dána těmito faktory:^[4]

• kvalitou generátoru náhodných čísel, resp. pseudonáhodných čísel
• výběrem racionálního algoritmu výpočtu
• kontrolou přesnosti získaného výsledku.

Metoda MC zahrnuje:

• vytvoření modelu skutečného systému, se stejnými pravděpodobnostními charakteristikami jako má reálný systém (vliv náhody - náhodná čísla)
• model musí zahrnovat veškeré relevantní skutečnosti, podstatně ovlivňující reálný systém
• experimentování s modelem, mnohanásobné zkoumání chování modelu
  • s pevným časovým krokem – sledujeme chování systému po určitých konstantních časových intervalech a zjišťujeme, zda došlo ke změnám)
  • s proměnným časovým krokem – generujeme interval, po který v systému nedojde k žádným změnám

Schéma postupu metody Monte Carlo

Řešení problému metodou Monte Carlo můžeme rozdělit do tří kroků:^[5]

• Rozbor problému a návrh modelu - z hlediska řešení problému se jedná o nejdůležitější krok. I když je MMC použitelná prakticky u všech problémů a její formulace není složitá, nalezení vhodného postupu může nezkušenému řešiteli dělat problémy.
• Generování náhodných veličin, jejich transformace na veličiny s daným pravděpodobnostním rozdělením. Rychlost konvergence chyby výsledku k nulové hodnotě je u MMC rovna přibližně převrácené hodnotě odmocniny z počtu realizovaných pokusů N, z čehož plyne, že nepatří mezi metody nejefektivnější.
• Statistické zpracování výsledků - hledaná hodnota je zpravidla dána některým z momentů statistických veličin, nejčastěji střední hodnotou.

Oblasti použití

Metoda Monte Carlo má širokou možnost využití. Obecně se dá říci, že je možné ji použít všude tam, kde je řešení možné nalézt pomocí mnohokrát opakovaných náhodných pokusů. Jelikož se jedná o metodu stochastickou, je nutné znát pravděpodobnostní rozdělení sledovaných veličin. Tyto problémy lze nalézt ve všech oborech, nejen v matematice, ale také v oblasti financí a obchodu, fyzice a fyzikální chemii, ve výpočetní technice a hrách apod.

Matematika

Metoda Monte Carlo je použitelná nejen k řešení jednoduchých určitých i vícerozměrných integrálů, parciálních diferenciálních rovnic, ale třeba také řešení systémů lineárních rovnic, či hledání kořenů rovnic.^[4]

Numerická matematika

Příkladem použití metody Monte Carlo je Rabinův-Millerův test prvočíselnosti. Používá se k rychlému rozhodnutí, zda je dané celé kladné číslo N prvočíslem nebo zda je složené. Počítá několik mocnin čísla b modulo N, první exponent je číslo N-1, každý další exponent je polovina předcházejícího, pokud je předcházející exponent sudý. Test končí ve chvíli, kdy je odpovídající mocnina různá od jedné i od minus jedné modulo N a číslo je správně klasifikováno jako složené, nebo v okamžiku, kdy buď už exponent nelze dělit dvěma, nebo se mocnina rovná minus jedné modulo N a tehdy se číslo označuje jako silné pseudoprvočíslo při bázi b. Pravděpodobnost, že silné pseudoprvočíslo není prvočíslem, je menší, než jedna osmina. Opakujeme-li tedy test s jinými volbami báze, a vždy dostáváme odpověď, že se jedná o silné pseudoprvočíslo, pravděpodobnost, že se skutečně jedná o prvočíslo, prudce vzrůstá.^[6]

Rozlišují se dvě varianty metody Monte Carlo, analogový a neanalogový model.

Analogový model

Musíme umět modelovat celou situaci na počítači, to znamená například znát všechna pravděpodobnostní rozložení zkoumaných jevů a fyzikální zákonitosti, kterými se řídí. Provedením této simulace získáme výsledek, realizaci jakési náhodné veličiny ${\displaystyle \xi }$. Tuto simulaci spustíme n-krát a získáme soubor historií x₁ ...x_n . Odhad střední hodnoty ${\displaystyle \xi }$ se určí :

${\displaystyle \xi \approx {\frac {1}{N}}\sum _{i=1}^{N}x_{i}}$

a směrodatná odchylka se určí jednoduše jako

${\displaystyle \sigma ={\sqrt {\frac {\sum _{i=1}^{n}({\bar {x}}-x_{i})^{2}}{n-1}}}}$

Neanalogový model

Tak se nazývá případ, kdy při výpočtu nepoužíváme model reálného děje. Například výpočet určitého integrálu, případně obsahu ohraničeného útvaru.

Integrace metodou Monte Carlo

Metody typu Monte Carlo lze úspěšně využít také pro numerickou integraci. Hlavní článek o Monte Carlo integrování.

Matematická statistika

Metoda Monte Carlo se v matematické statistice používá například k počítání přesnosti odhadů (resampling, bootstrapping) nebo pro výpočty v bayesovské statistice (MCMC a jiné).

Přesnost metody Monte Carlo

K odhadu chyby výsledku získaného metodou Monte Carlo se většinou používá střední kvadratická chyba aritmetického průměru. Chyba výsledku získaného pomocí n historií je úměrná ${\displaystyle 1/{\sqrt {n}}}$. Takže aby se zlepšil výsledek o jeden řád musí se počet historií zvýšit alespoň o dva řády. Abychom získali výsledek s přesností na 6 desetinných míst, což odpovídá přesnosti jiných metod musíme získat 10¹² historií.

Další použití metody

• Buffonova úloha
• projekt Manhattan
• Millerův-Rabinův test prvočíselnosti

Fyzika

Kromě již zmíněné fyzikální chemii se metoda Monte Carlo používá ke složitým výpočtům v kvantové chromodynamice, aerodynamice, dále ve fyzice polymerů, statistické fyzice, fyzice částic. Monte Carlo najde uplatnění i při předpovědi počasí.

Počítačová grafika

Zejména metoda Quasi Monte Carlo se využívá při renderování ve 3D modelech. Grafické programy mají funkci, která vytváří odrazy světla od různých ploch, Monte Carlo je generuje náhodně v rámci polokulové distribuce, Quasi Monte Carlo je vytváří pravidelně. Využití – počítačové hry, grafika, animace, filmové efekty, architektura apod. Jedna z metod renderování je radiozita, vychází ze zákona zachování energie a definuje se jako:

${\displaystyle B_{i}=E_{i}+R_{i}\int _{j}B_{j}F_{i}j}$

kde: B_i je radiozita plošky i. E_i je vyzařovaná energie této plošky. R_i je odrazivost plošky. integrál reprezentuje součet energií přicházejících na plošku i ze všech ostatních plošek. F_ij je konfigurační faktor mezi ploškami i a j (vliv plošky j na plošku i).

Hazardní hry

Hazardní hry jsou založeny na náhodě, tak jako u jiných her je popsána systémem pravidel a je posloupností tahů. Právě výsledky tahů jsou u hazardních her zcela náhodné – náhodné tahy, u jiných her, kde jsou tahy ovlivněny vůlí hráče, je označujeme jako osobní tahy. Monte Carlo je ukázkou procesů, kdy systém osobních tahů bude simulovat systém náhodných tahů. Právě hazardní hry byly východiskem pro vznik a rozvoj teorie pravděpodobnosti. Monte Carlo resp. generátory náhodných a pseudonáhodných čísel umožňují mechanizovat hazardní hry, protože umožňují nastavit všem alternativám stejnou pravděpodobnost.^[7]

Finance a pojišťovnictví

V oblasti ekonomiky je možné metodu Monte Carlo využít pro oceňování opcí, investic a jiných finančních derivátů, analýzu rizika, pro zjištění optimální hodnoty portfolia, pro rozhodování či zajišťování.

Analýza rizika

Metoda Monte Carlo dává nejpřesnější pravděpodobnosti ve srovnání s jinými metodami. I přes značné výhody naráží na řadu překážek:^[8]

• vysoká citlivost výsledků metody Monte Carlo k zákonům pravděpodobnostního rozdělení a typu závislostí vstupních proměnných;
• i když současné programy umožňují vzít v úvahu zákony rozdělení pravděpodobnosti, provést korelaci mezi vstupními proměnnými a zhodnotit jejich spolehlivost, v praxi to obvykle není možné, protože ve většině případů analytici stanoví změny základních proměnných makro a mikro prostředí, vybírají zákony rozdělení pravděpodobnosti a statistické vztahy mezi proměnnými subjektivně.
• V důsledku výše uvedených důvodů je přesnost výsledných odhadů do značné míry závislá na kvalitě základních předpokladů a vzájemných souvislostech vstupních proměnných, což může vést k významným chybám ve výsledcích.

Z praktického hlediska je použitelnost metody Monte Carlo kvůli velkému množství zjednodušených předpokladů modelů značně omezená.

Pravděpodobnostní posudek spolehlivosti

Metoda Monte Carlo může být použita také pro pravděpodobnostní posudek spolehlivosti technických struktur (strojů a jejich částí, stavební konstrukce atd.) Pravděpodobnostní posudek spolehlivosti je pak alternativou ke klasickému staršímu deterministickému posudku spolehlivosti. Jedním z průkopníků pravděpodobnostního posudku spolehlivosti technických struktur byl český inženýr Pavel Marek.

Další možnosti využití

Využití metody Monte Carlo je opravdu velmi široké, musí pouze splňovat výše uvedené předpoklady. Kromě již zmíněného se Monte Carlo používá také:

• ve výzkumu polovodičů k modelování přenosu nabitých částic
• ve studiu životního prostředí, v oblasti znečištění
• tepelné štíty
• při pátracích a záchranných činnostech - modely používané k předpovědím pohybu záchranných člunů nebo rozšiřování ropné skvrny na moři
• předpovědi struktury bílkovin

Optimalizace

Optimalizačních problémů je celá řada, ve všech oborech, např. ve fyzice hledání optimální tloušťky tlakové nádoby, či v umělé inteligenci hledání optimální trajektorie robota apod. Optimalizační problémy se dají řešit buď analyticky, nebo pokud to možné není, je možné je řešit optimalizačními algoritmy (jako např. uvedené příklady). Optimalizační algoritmy převedou daný problém na matematický, jehož optimalizace vede k nalezení argumentů tzv. účelové funkce, což je cílem optimalizace. Optimalizační algoritmy hledají minimum dané účelové funkce.^[9]

Optimalizační metody je možné rozdělit do tří skupin:^[9]

• deterministické – je třeba znát předběžné předpoklady, dávají pouze jedno jediné řešení
  • horolezecký algoritmus
  • metoda větví a mezí - klidně dá všechna řešení
  • simplexová metoda
  • lineární programování
  • matematická analýza - ?
• stochastické – založeny na náhodě
  • simulované žíhání
  • Monte Carlo
  • slepé prohledávání
  • stochastická optimalizace
  • stochastické tunelování
  • greedy neboli hladový algoritmus - Drsná ignorance determinismu. Náhoda a spol. se někdy používají pro výběr z několika nejlepších kroků
• smíšené
  • genetické algoritmy
  • matematické programování
  • evoluční strategie

Optimalizovat se dá i pomocí metastrategií.

Generátory náhodných čísel

Generátory náhodných čísel s definovaným stochastickým rozdělením jsou základem simulačních programů Monte Carlo. Generátory náhodných čísel fungují tak, že nejprve vygenerují posloupnost náhodných čísel s rovnoměrným rozdělením (primární generátor) a poté je z nich transformací vytvořena posloupnost s požadovaným rozdělením. Primární generátory jsou fyzikální nebo pseudonáhodné.^[10]

Fyzikální generátory náhodných čísel

Jako fyzikální generátor náhodných čísel se dá chápat vše, co má charakter náhodnosti, jako např. házení kostkou nebo mincí. Častěji se ale používají generátory založené na kombinaci radioaktivního zářiče a detektoru (vyzařuje částice v náhodném množství). Fyzikální generátory se ale málo používají, jelikož mohou být v závislosti na vnějších vlivech nestabilní, posloupnost čísel se nedá zopakovat a chování se může lišit v důsledku výrobních tolerancí.

Generátory pseudonáhodných čísel

Nejpoužívanějším^[zdroj?] generátorem pseudonáhodných čísel je tzv. kongruentní generátor. Posloupnost lze vyjádřit vztahem:

${\displaystyle X_{n+1}=(aX_{n}+c)mod\ m}$

kde mod m je celočíselný zbytek po dělení a, c, m jsou zvolené konstanty

Generovaná čísla jsou diskrétní z intervalu <0,m). Kvalita generovaných čísel závisí na zvolených konstantách, čím vyšší hodnoty, tím „kvalitnější“ generovaná čísla jsou, ale rychlost generování klesá.

Odkazy

Reference

Literatura

• Hušek R. Ekonometrická analýza. Ekopress, Praha 1999. ISBN 80-86119-19-X

Související články

• Genetický algoritmus - další skupina numerických metod používající sekvence náhodných čísel.

Externí odkazy

• Obrázky, zvuky či videa k tématu Metoda Monte Carlo na Wikimedia Commons