Méthode de Monte-Carlo cinétique

La méthode de Monte-Carlo cinétique, kinetic Monte Carlo en anglais, est une méthode de Monte-Carlo de simulation informatique servant à simuler des processus ayant lieu à des taux connus.



Catégories :

Algorithme numérique - Probabilités - Hasard et aléatoire - Physique statistique

Page(s) en rapport avec ce sujet :

  • Ces deux champs de connaissances, stabilité des alliages et cinétique, sont les .... méthode de Monte - Carlo dans les alliages évalue les barrières... (source : cmla.ens-cachan)

La méthode de Monte-Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte-Carlo de simulation informatique servant à simuler des processus ayant lieu à des taux connus. En cela elle sert à simuler précisément le comportement de dispositifs évoluant selon une équation maîtresse.

C'est une méthode peu gourmande en temps de calcul permettant d'explorer des échelles de temps et d'espace importantes. Elle permet surtout d'étudier des phénomènes à probabilité faible.

Les taux doivent être connus à l'avance, l'algorithme ne fait que les utiliser.

L'algorithme Monte-Carlo cinétique porte plusieurs noms : algorithme à temps de résidence residence-time algorithm, Bortz-Kalos-Liebowitz (BKL) (Bortz 1975), n-fold way algorithme, algorithme ou méthode de Monte-Carlo dynamique ou encore algorithme de Gillespie (Gillespie 1976), ...

Algorithme

Taux de transfert indépendants du temps

À chaque étape, le dispositif dispose de plusieurs états accessibles, les taux de transferts vers chacun des états étant supposés connus.

L'algorithme de Monte-Carlo cinétique est utilisé pour modéliser les sauts aléatoires d'un dispositif d'un état d'origine vers un ensemble d'états finaux envisageables, le nombre total Nt de sauts effectués à un instant t étant modélisé par un processus de Poisson. À l'issue de chaque saut, on évalue les conséquences de la transition entre l'état d'origine et le nouvel état : arrêt de la simulation, nouvelle étape de simulation avec ou sans changement des taux de transfert, etc.

Choix de l'état final : une variable aléatoire est tirée entre 0 et Γtot ; la probabilité que le dispositif évolue vers l'état i est proportionnelle à Γi.

Pour se familiariser avec l'algorithme, on suppose dans cette section que les taux de transfert restent constants pendant l'intervalle de temps séparant deux sauts successifs, ce qui correspond à un processus de Poisson homogène. L'algorithme est donné par les étapes suivantes :

  1. On note t0 le temps actuel.
  2. On forme une liste de la totalité des taux de transfert Γi du dispositif, i = 1, ..., N, et on note Γtot = ∑ Γi le taux de transfert total.
  3. Le temps T au bout duquel le dispositif quitte son état d'origine est donné par la formule T = – ln (U) /Γtot, où U est une variable aléatoire uniformément répartie entre 0 et 1.
  4. On choisit un deuxième nombre aléatoire U' uniformément réparti entre 0 et Γtot qui va servir à tirer au hasard l'état final de la transition (voir la figure ci-contre).
  5. Si U' est compris entre 0 et Γ1, le dispositif transite vers l'état 1 ; entre Γ1 et Γ12 le dispositif transite vers l'état 2 ; et si U' est entre Si-1 et Si, où S0 = 0 et  S_i = \textstyle\sum_{j=1}ˆi \Gamma_j , le dispositif transite vers l'état i.
  6. Prendre en compte cette transition en effectuant les calculs correspondants.
  7. Changer le temps en t0+T et recommencer l'étape 1.
Justification de l'étape 3 
La variable aléatoire T représente le temps d'attente avant que le dispositif quitte l'état d'origine. Sa densité de probabilité est ρT (t) = Γtotexp (− Γtott) pour t ∈ [0, +∞[. La formule utilisée dans l'étape 3 correspond au changement de variable U = exp (– ΓtotT) , ce qui donne bien la même densité de probabilité : \rho_T(t) = \rho_U(u) \left|\frac{du}{dt} \right| si on considère ρU (u) = 1 sur ]0, 1].
Justification de l'étape 5 
La probabilité que l'état final soit l'état i est pi = ΓiΓtot, ce qui est égal à
p_i = \frac {\Gamma_i} {\Gamma_\text{tot}} = \frac {S_i-S_{i-1}} {\Gamma_\text{tot}} = \int_{S_{i-1}}ˆ{S_i} \frac{1}{\Gamma_\text{tot}}du' = P(S_{i-1}<U'<S_i)


Cet algorithme simule l'évolution du dispositif au cours du temps et n'a pas a priori de condition d'arrêt. En pratique, on arrête la boucle quand le temps dépasse une certaine valeur ou quand le dispositif a effectué un certain nombre de sauts ; la suite des états i suivis par le dispositif au cours du temps est nommée une trajectoire Monte-Carlo ; on répète ensuite cette boucle de façon à obtenir un nombre important de trajectoires, auxquelles on peut appliquer une analyse statistique. Puisque les trajectoires sont indépendantes les unes des autres, il est facile de paralléliser l'algorithme de Monte-Carlo cinétique.

Taux de transfert variants au cours du temps

L'algorithme est principalement le même si on suppose que les Γi dépendent du temps, mais les formules reliant U et U' à T ainsi qu'à l'état final i sont différentes :


Autres algorithmes

Un algorithme particulièrement identique est l'algorithme de première réaction First Reaction Method (FRM) . Il consiste à choisir la réaction i arrivant la première, tout en utilisant un côté probabiliste stochastique pour ne pas oublier les autres réactions. Pour cela on choisit N nombres au hasard ui et on choisit le temps de réaction Δti qui est le temps minimal parmi ceux déterminés par les N formules

 \int_{t_0}ˆ{t_0+\Delta t_i} \Gamma_i(t) dt =  -\log u_i

Si les taux Γi sont indépendant du temps les algorithmes KMC et FRM se simplifient naturellement et un autre algorithme fréquemment plus rapide existe dit de sélection aléatoire Random Selection Method (RSM) . Contrairement aux deux autres algorithmes il ne donne pas, à chaque pas de temps, obligatoirement lieu à une réaction. Au contraire, il calcule un intervalle de temps  \Delta t = \min_i \, 1/\Gamma_i où une seule réaction au maximum est envisageable. Il choisit ensuite au hasard (entre 1 et N) une réaction envisageable i et un nombre aléatoire associé u. Si u / Γi < ?t la réaction est effectuée, elle ne l'est pas dans le cas opposé. Dans l'ensemble des cas on met à jour le temps.

Utilisation

L'algorithme Monte-Carlo cinétique est utilisé pour simuler les phénomènes physiques tels que la diffusion de surface, l'épitaxie, l'évolution et la croissance de domaines ou la mobilité des agrégats.

Bien entendu cette méthode est parfois utilisée de façon bien plus large dès qu'un dispositif évolue selon une équation maîtresse, c'est-à-dire si les processus d'évolution suivent une loi de Poisson et sont non corrélés ; dans ce cas, la méthode de Monte-Carlo cinétique donne le résultat exact de l'évolution du dispositif au cours du temps.

Notes et références


Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Monte-Carlo_cin%C3%A9tique.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu