referaty.sk – Všetko čo študent potrebuje
Irma
Štvrtok, 14. novembra 2024
Algoritmus Monte Carlo
Dátum pridania: 15.11.2004 Oznámkuj: 12345
Autor referátu: gregina
 
Jazyk: Slovenčina Počet slov: 419
Referát vhodný pre: Vysoká škola Počet A4: 1.6
Priemerná známka: 2.97 Rýchle čítanie: 2m 40s
Pomalé čítanie: 4m 0s
 

Algoritmus Monte Carlo sa všeobecne používa vo výpočtoch proteínovej štruktúry, na skúmanie účinného prispôsobenia (a tiež v mnohých iných optimalizačných problémoch) na zistenie globálneho minima na hyperpovrchu mnohorozmernej potenciálnej energie. Jednoduché minimalizačné gradientné metódy vedú len k nájdeniu najbližšieho v lokálneho minima.
Všeobecne, metódy Monte Carlo využívajú náhodné čísla na riešenie problémov pre ktoré je nemožné nájsť globálne minimum experimentálnymi rigoróznimy metódami. Pomenovanie bolo vymyslené J. von Neumannom, odvolávajúce sa na používanie generátorov náhodných čísel v známych hazardných hrách – kasínach.
K použitiu techniky Monte Carlo na nájdenie minima funkcie mnohých premenných – napríklad, minimálnej energie proteínu ako funkcie premennej, ktorú definuje jej prispôsobenie, - predpokladá že usporiadanie systému je označené pomocou premennej x, a to pre každú hodnotu z týchto premenných, môžeme vypočítať energiu zhody E(x).

Potom procedúru Metropola prepisujeme:
1. Generovať náhodné nastavenia hodnôt x, na zabezpečenie úvodnej štruktúry. Výpočet energie z tejto štruktúry E = E(x)
2. Zmeniť premenné: x ->x`, na vytvorenie nových polôh
3. Výpočet energie z nových štruktúr, x(x`)
4. Rozhodnutie či akceptovať krok: zmena x->x`, alebo zostať pri x a vyskúšať inú zmenu
a/ Ak energia ubudla t.j. E= E(x)> E (x`) ju vždy akceptujeme, t.j. x` -> x a E = E(x`)
b/ Ak sa energia zvýšila alebo zastala nezmenená: to je E(x)≤ E(x) inými slovami, krok vedie k vzrastu energie – niekedy akceptujeme túto novú štruktúru.
Ozn. ∆ = E(x`) – E(x), potom akceptuj krok s pravdepodobnosťou exp [∆/(kT)], kde k je Boltzmanovská konštanta a T je teplota, v Kelvinovej škále.
5. Návrat ku kroku 2

Hlavným rozdielom oproti gradientným metódam je v kroku 4b, lebo má potenciál k prekonaniu prekážok, mimo prekážok v lokálnom minime. Teplota T, kontroluje možnosť, že vzostup bude akceptovaný. T nie je fyzikálna teplota, na ktorej si prajeme predpovedať proteínovú štruktúru, ale zjednodušene číselný parameter, ktorý dohliada nad výpočtom . Pre každú teplotu, pri ktorých rastie rozdiel energii, je menšia pravdepodobnosť že krok bude akceptovaný.

Pre nejakú hodnotu x, ak T je nižšia, potom E(x)/(kT) bude vyššia, a exp [-E(x)/ (kT)] bude relatívne nižší. Ak T je vyššia, potom E(x)/ (kT) bude nižšia a exp [-E(x)/ (kT)] bude relatívne vyššia. Zvýšenie teploty, zvýši pravdepodobnú akceptáciu vzostupných pohybov.
Táto relatívne jednoduchá myšlienka dokázala mimoriadne účinne s úspešným usporiadaním vrátane, ale vôbec nie ohraničene vypočítať proteínové štruktúry.
Metóda simulované žihanie využíva myšlienku Monte Carlo pre behu ktorého sa počiatočne nastavená teplota na vyššie hodnoty klesá zvyčajne k nulovej teplote. Pri tomto algoritme je v počiatočnej fáze umožnené prekonávať vyššie energetické bariéry a pri postupnom „ochladzovaní“ nájsť globálne minimum.

 
Copyright © 1999-2019 News and Media Holding, a.s.
Všetky práva vyhradené. Publikovanie alebo šírenie obsahu je zakázané bez predchádzajúceho súhlasu.