Kineetiline Monte Carlo

Kineetilise Monte Carlo (KMC) meetod on üldise Monte Carlo arvutusalgoritmika allharu. Kineetilise Monte Carlo arvutisimulatsioone kasutatakse mõne looduses esineva protsessi ajalise käitumise uurimiseks. Enamasti on tegu selliste protsessidega, milles esinevad teatud suurustega parameetrid, mis iseloomustavad üleminekut eri olekute vahel. Need üleminekusuurused on Kineetilise Monte Carlo arvutusalgoritmide tarvilikud algparameetrid – neid selle metoodikaga ennustada ei saa.
Kineetilise Monte Carlo arvutused käsitlevad uuritavat süsteemi kui potentsiaalse energia miinimumide pinda. Süsteemi ajaline käitumine tähendab sisuliselt hüppeid miinimumpotentsiaalide vahel. Sellist hüpet nimetatakse KMC elementaarsündmuseks. Neid hüppeid vaadeldakse stohhastiliste protsessidena ning vastavad algoritmid kasutavad juhuslikke arve, tegemaks kindlaks, millal hüpped toimuvad ning millisesse naabermiinimumi hüppe toimumine on eelistatud. Juhuslikkude arvude kasutamisest hoolimata koonduvad protsessid süsteemienergia miinimumi suunas – lahend koondub ega ole juhuslik. Fikseeritud algolekule vastab kindel lõppolek, juhuslikud arvud valivad koondumisparameetrid.
Kineetilise Monte Carlo arvutustega saab uurida näiteks pinnareaktsioonide kineetikat. Kineetilise Monte Carlo simulatsioonid võimaldavad oluliselt vähendada vaid tasakaaluparameetritel põhinevatel arvutustel tekkivaid lahknevusi makroskoopiliste kineetiliste ja atomaarskaalaliste protsesside vahel.

Ajalugu

1966. aastal avaldasid Young ja Elcock esimese kineetilise Monte Carlo arvutusmeetodi põhijooni käsitleva artikli. Nende tööst sõltumatult arendasid Bortz, Kalos ning Lebowitz KMC algoritmi Isingi mudeli simuleerimiseks, mille nad nimetasid n-fold way’ks. Selle algoritmi põhijooned on sarnased nagu eelmainitul, ent meetod on palju detailsemalt kirjeldatud.
Aasta hiljem publitseeris Dan Gillespie tänapäeval tuntud Gillespie algoritmi keemiliste reaktsioonide kirjeldamiseks. Algoritm sarnaneb KMC-ga, kusjuures ajalisest küljest on lähenemine sama.

Algoritmid

Kineetilise Monte Carlo algoritmid võib üldjoontes liigitada kaheks: rejection-KMC ja rejection-free-KMC.

Rejection-free KMC (rfKMC)

rfKMC algoritm mingi süsteemi ajalise evolutsiooni simuleerimiseks järgib järgnevaid põhilisi alapunkte. Eeldus on, et teame võimalike protsesside toimumistõenäosusi r.
1. Ajalise nullpunkti t=0 valimine
2. Algoleku k valimine
3. Moodustada nimekiri kõikidest Nₖ võimalikust üleminekutõenäosusest süsteemis rₖᵢ , kus süsteem läheb olekust k mingisse
olekusse i. Lõppolekud i, kuhu olekust k ei saa minna, omavad üleminekutõenäosust rₖᵢ =0.
4. Kumulatiivse funktsiooni Rₖᵢ = (j=1,i)Ξ rₖⱼ iga i=1, … , Nₖ arvutamine. Ülemineku kogutõenäosust kirjeldab parameeter Qₖ = Rₖ, Nₖ.
5. Juhusliku reaalarvu u võtmine vahemikust (0,1].
6. Ülemineku ki selekteerimine, leides i, mille jaoks Rk,i-1 < uQk < Rₖᵢ
7. Ülemineku ki läbiviimine ehk uueks algolekuks k valitakse saadud lõppolek i.
8. Uue juhusliku reaalarvu u₂ võtmine vahemikust (0,1].
9. Ajafaktori uuendamine üleminku t=t+dt jaoks, kus dt=Qₖ⁻¹ ln(1/u₂)
10. Minek astmesse 3.

Seda algoritmi tuntakse olenevalt allikast kas residence-time algorithm, n-fold way, või Bortz-Kalos-Lebowitz-algoritmina. On oluline meeles pidada, et siin käsitletav ajasamm on funktsioon tõenäosusest, et kõik sündmused i ei toimunud.

Rejection KMC (rKMC)

Rejection KMC-l on eelmise meetodi kõrval eelis, kuna võimaldab lihtsamat andmetöötlust ja kiiremat arvutamist iga sammu jaoks, kuna sel juhul ei arvutata välja kõiki üleminekutõenäosusi rₖᵢ. Samaaegselt on aga saadavad ajasammud väiksemad kui rfKMC korral. Efektiivsem meetod oleneb seega konkreetselt uuritavast süsteemist ning kasutadaolevast arvutusvõimsusest.
RKMC toimimisprotsessi samal eeldusel, et teame üleminekutõenäosusi r, saab lihtsustada järgmisteks punktideks.
1. Ajalise nullpunkti t=0 valimine
2. Algoleku k valimine
3. Arvutada kõikvõimalike üleminekute arv N süsteemis rₖᵢ , kus süsteem läheb olekust k mingisse olekusse i.
4. Valida juhuslikult kandidaatsündmus i saadud N ülemineku seast.
5. Sündmuse tõenäosusega f=rₖᵢ/R₀ vastuvõtmine. R₀ on sobiv ülemtõenäosus rₖᵢ jaoks.
R₀ on sageli lihtne leida kõiki rₖᵢ-sid arvutamata.
6. Ülemineku ki läbiviimine ehk uueks algolekuks k valitakse saadud lõppolek i.
7. Uue juhusliku reaalarvu u₂ võtmine vahemikust (0,1].
8. Ajafaktori uuendamine üleminku t=t+dt jaoks, kus dt=Qₖ⁻¹ ln(1/u₂)
9. Minek astmesse 3.

Siinjuhul võib R₀ muutuda ühest Monte Carlo astmest järgmisse.

Märkusi algoritmist

Kineetilise Monte Carlo algoritmi iseloomulikuks omaduseks on tõsiasi, et kui sisendväärtustena antavad üleminekutõenäosused on ligilähedaselt õiged ja kui nende üleminekutõenäosustega seotud protsessid on Poissoni protsessid ning eri protsessid on sõltumatud, annab KMC algoritm õige ajaskaala simuleeritava süsteemi evolutsiooni kohta. See kehtib nii rKMC kui rfKMC kohta.
Kui üleminekud uuritavas nähtuses alluvad statistilisele tasakaalule, saab KMC algoritmi kasutada termodünaamilise tasakaaluoleku simuleerimiseks. KMC-d aga kasutatakse laialdaselt ka mittetasakaaluliste protsesside simuleerimiseks. Viimasel juhul ei pea järgima statistilise tasakaalu parameetreid.
RfKMC algoritmi tõhusus väljendub selles, et igas iteratsioonis on mingi ülemineku toimumine garanteeritud. Ülalkirjeldatud protsessiskeemis on iga iteratsiooni jaoks vaja kõigi võimalike hüpete tõenäosused välja arvutada, mis on väga ebaefektiivne. Paljudel juhtudel saab seda protsessi kiirendada, jagades uuritava ruumiosa sektsioonideks ja/või moodustades harulise andmestruktuuri, kus sektsioonide lahenditest pannakse kokku lõpplahend. Siinkohal võib tekkida probleem, et eri sektsioonides hakkab protsess järgima erinevat ajaskaalat. Selliseks lahendusviisiks on aga hiljuti välja arendatud ning testitud pideva aja skaleerimise algoritm.
Suur rfKMC puudus on siiski see, et kõikvõimalikud üleminekutõenäosused rₖᵢ peab algoritmile sisendina ette andma.

Kasutusnäiteid

Kineetilise Monte Carlo arvutust on kasutatud järgmiste süsteemide simuleerimiseks:
1. pinnadifusioon;
2. pindade kasv/areng;
3. vakantsdifusioon sulamites (Kineetilise Monte Carlo arvutuse originaalprobleem);
4. domeenievolutsiooni hõrenemine;
5. defektide mobiilsus, klastrite teke ioonide või neutronitega kiiritatud tahkistes, sealhulgas pinnakahjustuste akumuleerumine, amorfiseerumis- ning rekristalliseerumismudelid;
6. viskoossus ja elastsus füüsiliselt ühendatud võrksüsteemides.

Kineetilise Monte Carlo arvutuste kontekstis on olulised mõisted "objekt" ja "sündmus". Nendest parema ülevaate andmiseks mõelgem läbi üks näide rfKMC-st.
Kujutagem ette, et meil on süsteem, kus aatomid langevad pinnale ükshaaval (näiteks auru ladestumises), kuid samaaegselt saavad juba langenud aatomid mingi teatud hüppetõenäosusega w pinnal võrekonstandi võrra edasi liikuda. Praegusel juhul on "objektide" rollis järelikult individuaalsed aatomid.
Postuleerime, et kui kaks aatomit satuvad kõrvuti, jäävad nad statsionaarseks. Ladestuvate aatomite voog määrab mingi ladestustõenäosuse rlad, ning süsteemi käiku saab kineetilise Monte Carlo arvutusega edasi simuleerida, arvestades liikumatute aatomite ning naabriteta ehk hüppevõimeliste aatomite arvu. Sellisel lähenemisel on igas iteratsioonis kaks võimalikku "sündmust":

1. uus aatom ladestub pinnale, järgidest ladestustõenäosust rlad;
2. juba ladestunud aatom hüppab ühe võrekonstandi võrra edasi tõenäosusega w.

Sündmuste summaarne tõenäosus peab olema 1.
Pärast sündmuse selekteerimist ning läbiviimist KMC algoritmi poolt peab kontrollima, kas vastladestunud või pinnal liikunud aatom on sattunud mõne teise aatomi kõrvale ning seega liikumatuks muutunud. Viimasel juhul tuleb see aatom eemaldada mobiilsete aatomite nimekirjast ning selle liikumised seega eemaldada kõikide võimalike liikumiste nimekirjast.
Kasutades kineetilise Monte Carlo arvutusi füüsika- ning keemianähtuste uurimiseks peab esmalt kaalutlema, kas reaalne süsteem järgib simulatsioonile seatavaid eeldusi piisavalt hästi. Reaalsetel protsessidel ei ole enamasti fikseeritud väärtustega eeldusi. Näiteks ei saa me rangelt öelda, et ülalolevas näites jääb aatomitevoog ajas konstantseks. Osakestehüpped võivad ka näiteks olla suunalt mitte täiesti juhuslikud. Samuti, simuleerides suuremaid ajavahemikke, peab jälgima, et aja jooksul uusi protsesse ei lisandu. Kui mõni neist tingimustest arvestada valesti või jätta arvestamata, annab KMC kummalisi tulemusi, mil ei pruugi reaalsusega mingit seost olla.

Variatsioonid KMC-st

KMC meetodi saab problemaatika dünaamikast lähtuvalt jaotada järgmiselt:
Lattice-KMC – kirjeldab KMC-d, mis kirjeldab evolutsiooni aatomvõredes. Seda nimetatakse sageli ka atomistlikuks KMC-ks. Tüüpiline näide sellest juhust on vakantsdifusioon metallisulamites, kus vakantsil lubatakse võres liikuda, olenevalt lokaalsest elementide aatomite paigutusest.
Object-KMC – kirjeldab defektide või materjali ebapuhtuse liikumist mingil pinnal või mingis võres. Simulatsioonis jälgitakse ainult liikuvaid objekte, taustaks olevatele võreaatomitele ei pöörata tähelepanu.
Event-KMC – kirjeldab object-KMC alaliiki, mille juhul valitakse KMC-ga reaktsioon kahe objekti interaktsioonile, arvestades objektide asukohti. Näiteks kahe liikuva ebapuhtuse kokkupõrge.