Méthode de Monte Carlo

La méthode de Monte Carlo peut être illustré comme un jeu de cuirassé. D'abord, un joueur fait quelques coups aléatoires. Suivant le joueur applique des algorithmes (ie. Un cuirassé est de quatre points dans le sens vertical ou horizontal). Enfin basée sur les résultats de l'échantillonnage aléatoire et l'algorithme le joueur peut déterminer les emplacements probables des navires de l'autre joueur.

Une méthode de Monte Carlo est un calcul algorithme qui se appuie sur répétée échantillonnage aléatoire pour calculer ses résultats. Méthodes de Monte Carlo sont souvent utilisés lorsque simulant physiques et mathématiques des systèmes. En raison de leur dépendance sur le calcul répétée et aléatoire ou nombres pseudo-aléatoires, les méthodes de Monte Carlo sont les plus adaptés à un calcul par ordinateur . Méthodes de Monte Carlo ont tendance à être utilisé lorsqu'il est impossible ou impossible de calculer un résultat exact avec un algorithme déterministe.

Le terme de Monte-Carlo a été inventé dans les années 1940 par des physiciens travaillant sur des projets d'armes nucléaires dans la Los Alamos National Laboratory.

Vue d'ensemble

Il n'y a aucune méthode de Monte Carlo unique; à la place, le terme décrit une classe importante et largement utilisé des approches. Cependant, ces approches ont tendance à suivre un modèle particulier:

1. Définir un domaine d'entrées possibles.
2. Générer entrées au hasard dans le domaine, et d'effectuer un calcul déterministe sur eux.
3. Agréger les résultats des calculs individuels dans le résultat final.

Par exemple, la valeur de π peuvent être estimés à l'aide d'une méthode Monte Carlo. Dessinez un carré sur le sol, puis inscrire un cercle en son sein. Maintenant, saupoudrez quelques petits objets (par exemple, des grains de riz ou de sable) à travers la place. Si les objets sont dispersés uniforme, alors la proportion d'objets dans le cercle doit être d'environ π / 4, qui est le rapport de la superficie du cercle à l'aire de la place. Ainsi, si l'on compte le nombre d'objets dans le cercle, multiplier par quatre, et diviser par le nombre d'objets dans la place, nous allons obtenir une approximation de π.

Remarquez comment l'approximation de π suit la tendance générale des algorithmes de Monte Carlo. Premièrement, nous définissons un domaine d'entrées: dans ce cas, ce est la place qui entoure notre cercle. Ensuite, nous générons entrées au hasard (dispersent grains individuels au sein de la place), puis effectuer un calcul sur chaque entrée (test si elle tombe dans le cercle). A la fin, nous agrégeons les résultats dans notre résultat final, le rapprochement des π. Notez également deux autres propriétés communes des méthodes de Monte Carlo: la dépendance du calcul sur de bons nombres aléatoires, et sa convergence lente à une meilleure approximation que plusieurs points de données sont échantillonnées. Si nous suffit de déposer nos grains dans le centre du cercle, ils pourraient tout simplement se accumulent dans une pile dans le cercle: ils ne seront pas répartis uniformément, et ainsi de notre rapprochement seront loin. Mais se ils sont uniformément réparties, les plus de grains que nous baisser, le plus précis de notre rapprochement des π deviendront.

Histoire

Méthodes de Monte Carlo ont été initialement pratiquées sous des noms plus génériques comme "échantillonnage statistique". Le nom «Monte Carlo» a été popularisé par les chercheurs en physique Stanislaw Ulam, Enrico Fermi, John von Neumann , et Nicholas Metropolis, entre autres; le nom est une référence à un célèbre casino de Monaco qui l'oncle de Ulam serait emprunter de l'argent pour jouer au. L'utilisation de le hasard et la nature répétitive du processus sont analogues aux activités menées dans un casino.

Méthodes aléatoires de calcul et d'expérimentation (généralement considérées comme des formes de simulation stochastique) peut être sans doute remonter aux premiers pionniers de la théorie des probabilités (voir, par exemple, Aiguille de Buffon, et le travail sur de petits échantillons par William Gosset), mais sont plus spécifiquement remonte à l'ère de l'informatique pré-électronique. La différence générale habituellement décrit d'une forme de Monte Carlo de la simulation, ce est qu'il "inverse" systématiquement le mode typique de simulation, le traitement des problèmes déterministes en trouvant d'abord une analogique probabiliste. Les procédés antérieurs de simulation et de l'échantillonnage statistique fait généralement le contraire: en utilisant la simulation pour tester un problème déterministe précédemment compris. Bien que des exemples d'une approche «inversé» ne existent historiquement, ils ne étaient pas considérés comme une méthode générale jusqu'à ce que la popularité de la méthode de Monte Carlo propagation.

Peut-être le plus célèbre utilisation précoce était par Enrico Fermi en 1930, quand il a utilisé une méthode aléatoire pour calculer les propriétés de la nouvellement découvert neutrons . Méthodes de Monte Carlo ont été au centre de la simulations requises pour la Manhattan Project, mais ont été sévèrement limitée par les outils informatiques à l'époque. Par conséquent, ce ne est qu'après les ordinateurs électroniques ont d'abord été construits (à partir de 1945) que les méthodes de Monte Carlo ont commencé à être étudié en profondeur. Dans les années 1950, ils ont été utilisés au Los Alamos pour les premiers travaux portant sur le développement de la bombe à hydrogène, et est devenu popularisé dans les domaines de la physique , chimie physique, et la recherche opérationnelle . Le Rand Corporation et le US Air Force étaient deux des principales organisations responsables du financement et de la diffusion d'informations sur les méthodes de Monte Carlo pendant ce temps, et ils ont commencé à trouver une large application dans de nombreux domaines différents.

Utilisations des méthodes de Monte Carlo nécessitent de grandes quantités de nombres aléatoires, et ce était leur utilisation qui a stimulé le développement de nombre pseudo-aléatoires générateurs, qui étaient beaucoup plus rapide à utiliser que les tableaux de nombres aléatoires qui avait été précédemment utilisés pour l'échantillonnage statistique.

Applications

Méthodes de simulation de Monte Carlo sont particulièrement utiles dans l'étude des systèmes avec un grand nombre de degrés de liberté couplés, tels que les liquides, les matériaux désordonnés, solides fortement couplés, et les structures cellulaires (voir cellulaire modèle de Potts). Plus largement, méthodes de Monte Carlo sont utiles pour la modélisation de phénomènes avec significative l'incertitude dans les intrants, tels que le calcul de risques dans les affaires (pour son utilisation dans l'industrie de l'assurance, voir la modélisation stochastique). Une utilisation classique est pour l'évaluation des intégrales définies , en particulier intégrales multidimensionnelles avec des conditions aux limites complexes.

Méthodes de Monte Carlo en finance sont souvent utilisés pour calculer la valeur des entreprises, d'évaluer les investissements dans des projets au niveau de l'entreprise ou pour évaluer des produits financiers dérivés. La méthode de Monte Carlo est destiné aux analystes financiers qui veulent construire des modèles stochastiques financiers ou probabilistes par opposition aux modèles statiques et déterministes traditionnels.

Méthodes de Monte Carlo sont très importants dans physique computationnelle, chimie physique, et des domaines connexes, appliquées et ont diverses applications de compliqué chromodynamique quantique calculs à la conception boucliers thermiques et formes aérodynamiques.

Méthodes de Monte Carlo ont également prouvé son efficacité dans la résolution des équations différentielles intégrales couplées de champs de rayonnement et transport d'énergie, et donc ces méthodes ont été utilisées dans calculs de l'illumination globale qui produisent des images photoréalistes de modèles virtuels en 3D, avec des applications dans les jeux vidéo , l'architecture , conception, généré par ordinateur films , effets spéciaux du cinéma, des affaires, de l'économie et d'autres domaines.

Méthodes de Monte Carlo sont utiles dans de nombreux domaines des mathématiques de calcul, où un choix chanceux peut trouver le bon résultat. Un exemple classique est L'algorithme de Rabin pour les tests de primalité: pour tout n qui ne est pas premier, un x aléatoire a au moins une chance de prouver que n de 75% ne est pas premier. Par conséquent, si n ne est pas premier, mais x dit qu'il pourrait être, nous avons observé au plus un événement 1-en-4. Si 10 différents x aléatoires disent que «n est probablement premier" quand il ne est pas, nous avons observé un événement-in-a-million. En général, un algorithme de Monte Carlo de ce genre produit une bonne réponse avec une garantie n est composite, et x prouve donc, mais une autre sans, mais avec une garantie de ne pas obtenir cette réponse quand il a tort trop souvent - dans ce cas au plus 25% du temps. Voir également Algorithme Las Vegas pour un connexe, mais différent, idée.

Les domaines d'application

Domaines d'application comprennent:

• Graphiques, en particulier pour ray tracing; une version de la Algorithme de Metropolis-Hastings est également utilisé pour lancer de rayon où il est connu sous le nom Transport léger Metropolis
• transport léger de modélisation dans les tissus biologiques
• Méthodes de Monte Carlo en finance
• l'ingénierie de la fiabilité
• Dans recuit simulé pour la prédiction de la structure des protéines
• Dans la recherche de dispositif à semiconducteur, pour modéliser le transport de porteurs de courant
• Sciences de l'environnement, portant sur le comportement des contaminants
• Méthode de Monte Carlo en physique statistique; en particulier, Monte Carlo modélisation moléculaire comme une alternative de calcul pour la dynamique moléculaire.
• Recherche et sauvetage et lutte contre la pollution. Modèles utilisés pour prédire la dérive d'un radeau de sauvetage ou un mouvement d'une nappe d'hydrocarbures en mer.
• En Conception probabiliste pour simuler et de comprendre les effets de la variabilité
• En Chimie physique, en particulier pour les simulations impliquant des agrégats atomiques
• En informatique
  • Algorithme Las Vegas
  • LURCH
  • Computer Go
• Modélisation du mouvement des atomes d'impureté (ou ions) dans les plasmas de tokamaks existants et (par exemple: DIVIMP).
• Dans expérimentale en physique des particules , de la conception détecteurs, comprendre leur comportement et la comparaison des données expérimentales à la théorie
• Codes physique nucléaire et des particules en utilisant la méthode de Monte Carlo:
  • GEANT - La simulation du CERN de particules de haute énergie interagissent avec un détecteur.
  • CompHEP, PYTHIA - générateurs Monte-Carlo de collisions de particules
  • MCNP (X) - les codes de transport de rayonnement de LANL
  • EGS - Le code de simulation de Stanford pour le transport couplé d'électrons et de photons
  • L'outil de Monte Carlo de LLNL pour les calculs de dose de radiothérapie - Peregrine
  • BEAMnrc - Monte Carlo système de code pour la modélisation des sources de radiothérapie ( De LINAC)
  • PENELOPE - Monte Carlo pour le transport couplé de photons et d'électrons, avec des applications en radiothérapie
  • MONK - le code de Serco Assurance pour le calcul de k-efficace des systèmes nucléaires
  • Modélisation de structures en mousse cellulaires et
  • Modélisation de tissu morphogenèse

D'autres procédés employant Monte Carlo

• Modèles aléatoires assorties, par exemple criticité auto-organisée
• Simulation directe Monte Carlo
• Dynamic méthode de Monte Carlo
• Kinetic Monte Carlo
• Quantum Monte Carlo
• Méthode quasi-Monte Carlo en utilisant séquences à faible divergence et auto évitant promenades
• Semiconductor transport de charge, etc.
• Interactions faisceau d'échantillons microscopie électronique
• Optimisation stochastique
• Modèle cellulaire Potts
• Chaîne de Markov Monte Carlo
• Croix-Entropy Méthode
• Economie Appliquée de l'information

Utilisez en mathématiques

En général, les méthodes de Monte Carlo sont utilisés en mathématiques pour résoudre divers problèmes en générant des nombres aléatoires appropriées et en observant cette fraction des numéros obéissant à certains biens ou propriétés. La méthode est utile pour obtenir des solutions numériques à des problèmes qui sont trop compliqués pour résoudre analytiquement. L'application la plus courante de la méthode de Monte Carlo est l'intégration de Monte Carlo.

Intégration

Les méthodes déterministes de l'intégration numérique fonctionnent en prenant un certain nombre d'échantillons régulièrement espacés d'une fonction. En général, cela fonctionne très bien pour les fonctions d'une variable. Toutefois, pour les fonctions de vecteurs , les méthodes de quadrature déterministes peuvent être très inefficaces. Pour intégrer numériquement en fonction d'un vecteur à deux dimensions, la grille équidistants points sur une surface à deux dimensions sont nécessaires. Par exemple, une grille de 10x10 nécessite 100 points. Si le vecteur possède 100 dimensions, le même espacement sur la grille exigerait 10 ¹⁰⁰ Points beaucoup trop nombreux pour être calculée. 100 dimensions ne est nullement déraisonnable, puisque dans de nombreux problèmes physiques, une "dimension" est équivalente à une degré de liberté. (Voir Malédiction de la dimension.)

Méthodes de Monte Carlo fournissent un moyen de sortir de ce temps-augmentation exponentielle. Aussi longtemps que la fonction en question est raisonnablement bien élevé, il peut être estimé par des points de sélection au hasard dans l'espace 100 dimensions, et de prendre une sorte de moyenne des valeurs de la fonction en ces points. Par le loi des grands nombres, cette méthode affiche convergence-à-dire quadrupler le nombre de points échantillonnés se réduire de moitié l'erreur, quel que soit le nombre de dimensions.

Un raffinement de cette méthode est de faire en quelque sorte des points aléatoire, mais plus susceptibles de provenir de régions de forte contribution à l'intégrale que de régions de faible contribution. En d'autres termes, les points doivent être tirées d'une distribution de forme semblable à la fonction à intégrer. Naturellement, en faisant cela précisément est tout aussi difficile que la résolution de l'intégrale, en premier lieu, mais il existe des méthodes approximatives disponibles: de la simple constituant une fonction intégrable pensé pour être similaire, à l'une des routines d'adaptation discutés dans les sujets énumérés ci-dessous.

Une approche similaire consiste à utiliser faible écart-séquences à la place du méthode quasi-Monte Carlo. Méthodes quasi-Monte Carlo peuvent souvent être plus efficace à l'intégration numérique parce que la séquence "remplit" mieux la région dans un sens et des échantillons plus des points les plus importants qui peuvent faire la simulation converge vers la solution souhaitée plus rapidement.

méthodes d'intégration

• Méthodes d'échantillonnage directs
  • Échantillonnage d'importance
  • L'échantillonnage stratifié
  • Échantillonnage stratifié récursive
  • Algorithme VEGAS
• Marche aléatoire Monte Carlo y compris Chaînes de Markov
  • Algorithme de Metropolis-Hastings
• Échantillonnage de Gibbs

Optimisation

Une autre application puissant et très populaire pour les nombres aléatoires dans la simulation numérique est en optimisation numérique. Ces problèmes utilisent des fonctions de certains vecteur souvent de grandes dimensions qui doivent être réduits au minimum (ou maximisé). Beaucoup de problèmes peuvent être formulées de cette manière: par exemple un programme d'échecs de l'ordinateur pourrait être perçu comme essayant de trouver l'ensemble optimal de, disons, 10 se déplace ce qui produit la meilleure fonction d'évaluation à la fin. Le problème du voyageur de vendeur est un autre problème d'optimisation. Il ya aussi des applications à la conception d'ingénierie, tels que optimisation de la conception pluridisciplinaire.

La plupart des méthodes d'optimisation de Monte Carlo sont basées sur marches aléatoires. Essentiellement, le programme se déplacer un marqueur dans l'espace multi-dimensionnel, tendant à déplacer dans des directions qui conduisent à une fonction inférieure, mais se déplaçant parfois à contre- gradient.

méthodes d'optimisation

• Stratégie Evolution
• Les algorithmes génétiques
• Trempe parallèle
• Recuit simulé
• Optimisation stochastique
• Tunneling stochastique

Problèmes inverses

Formulation probabiliste de problèmes inverses conduit à la définition d'une distribution de probabilité dans l'espace du modèle. Cette distribution de probabilités moissonneuses-batteuses une information a priori avec de nouvelles informations obtenues en mesurant certains paramètres observables (données). Comme, dans le cas général, la théorie de liaison de données avec les paramètres du modèle est non linéaire, la probabilité a posteriori dans l'espace de modèle peut ne pas être facile de décrire (il peut être multimodal, des moments ne peuvent être définis, etc.).

Lorsque l'on analyse un problème inverse, l'obtention d'un modèle de vraisemblance maximale est généralement pas suffisant, comme on voudra normalement également avoir des informations sur le pouvoir de résolution des données. Dans le cas général, nous pouvons avoir un grand nombre de paramètres du modèle, et une inspection des densités de probabilité marginales d'intérêt peut être difficile, voire inutile. Mais il est possible de produire des pseudo-aléatoire une grande collection de modèles en fonction de la distribution de probabilité postérieure, et pour analyser et afficher les modèles de manière à ce que les informations sur les probabilités relatives des propriétés modèle est transporté vers le spectateur. Ceci peut être accompli au moyen d'une méthode de Monte Carlo efficace, même dans le cas où pas de formule explicite pour la distribution a priori ne est disponible.

La méthode échantillonnage d'importance la plus connue, l'algorithme de Metropolis, peut être généralisé, ce qui donne une méthode qui permet d'analyser (éventuellement fortement non linéaires) problèmes inverses avec complexe informations a priori et des données avec une distribution de bruit arbitraire. Pour plus de détails, voir Mosegaard et Tarantola (1995) Ou Tarantola (2005) .

Monte Carlo et nombres aléatoires

Fait intéressant, les méthodes de simulation de Monte Carlo ne nécessitent généralement pas vraiment nombres aléatoires soient utiles - pour les autres applications, telles que tests de primalité, l'imprévisibilité est essentiel (voir Davenport (1995)). Beaucoup des techniques les plus utiles utilisent déterministe, des séquences pseudo-aléatoires, le rendant facile à tester et des simulations de réinstallation. La seule qualité généralement nécessaire de faire bon simulations est pour la séquence pseudo-aléatoire à apparaître "assez aléatoire" dans un certain sens.

Ce que cela signifie dépend de l'application, mais généralement ils doivent passer une série de tests statistiques. Essais que les chiffres sont uniformément répartie ou suivre une autre distribution désirée quand un nombre suffisant d'éléments de la séquence sont considérées est l'un de ceux les plus simples et les plus courants.

Une alternative à la méthode de Monte Carlo de base

Économie de l'information appliquées (AIE) est une méthode d'analyse de décision utilisé dans les affaires et le gouvernement qui répond à certaines des lacunes de la méthode de Monte Carlo - au moins comment il est habituellement utilisé dans des situations pratiques. Les composants les plus importants AIE ajoute à la méthode de Monte Carlo sont:

1) Comptabilisation de l'excès de confiance systémique des estimateurs humaines l'évaluation de la probabilité étalonnée

2) Le calcul de la valeur économique des informations pour guider les mesures empiriques supplémentaires

3) En utilisant les résultats de Monte Carlos en entrée à l'analyse de portefeuille

Lorsque des simulations de Monte Carlo sont utilisées dans la plupart des paramètres d'analyse de décision, des experts des droits sont utilisées pour estimer les probabilités et les gammes dans le modèle. Cependant, la recherche de la psychologie décision dans le domaine des évaluations de la probabilité calibrés montre que les humains - en particulier les experts dans divers domaines - ont tendance à être trop confiant statistiquement. Ce est, ils ont mis une trop forte probabilité qu'un résultat prévu se produit et ils ont tendance à utiliser des plages qui sont trop étroits pour refléter leur incertitude. AIE implique formation estimateurs droits de sorte que les probabilités et les plages qu'ils fournissent reflètent de façon réaliste l'incertitude (ex., Une subjective intervalle de confiance de 90% comme une chance de contenir la valeur réelle de 90%). Sans cette formation, les modèles de Monte Carlo seront toujours sous-estimer l'incertitude d'une décision et donc le risque.

Un autre inconvénient est que, dans la pratique, la plupart des utilisateurs de simulations de Monte Carlo reposent entièrement sur les estimations subjectives initiales et presque jamais suivi avec l'observation empirique. Cela peut être dû à la très grande majorité des variables dans de nombreux modèles et l'incapacité des analystes de choisir les variables économiquement justifiés pour mesurer plus loin. AIE aborde ce en utilisant des méthodes de la théorie de la décision pour calculer la valeur économique de l'information supplémentaire. Ceci élimine habituellement le besoin de mesurer la plupart des variables et met contraintes pragmatiques sur les méthodes utilisées pour mesurer les variables qui ont une valeur de l'information importante.

La dernière lacune adressée par l'AIE est que la sortie d'un Monte Carlo - au moins pour l'analyse des décisions d'affaires - est tout simplement l'histogramme des rendements résultant. N est présenté critères pour déterminer si une distribution particulière des résultats est acceptable ou non. Utilisations de l'AIE Théorie moderne du portefeuille de déterminer quels investissements sont souhaitables et quelles sont leurs priorités relatives devraient être.