Methode de monte-carlo
1
Introduction :
Jusqu’a les ann´es 1940, Les probl`mes rencontr´s en physique sont clase e e si?´s en deux grandes cat´gories : les probl`mes th´oriques, et les probl`mes e e e e e exp´rimentaux. Mais avec le rapide progr`s des ordinateurs, une troisi`me cat´gorie e e e e a ´tait introduit : la simulation par ordinateur. Cette nouvelle cat´gorie ne peut e e pas regard´ comme un rempla¸antdes deux premi`res cat´gories, mais comme e c e e un compl´ment de l’´tude th´orique et exp´rimentale d’un probl`me [Sadu09]. e e e e e De mani`re g´n´rale, la simulation permet d’´tudier et exp´rimenter un e e e e e syst`me donn´ dont on connaˆ les interactions complexes, de mesurer les e?ets e e ?t de certains changements dans les interactions sur le comportement du syst`me, e d’exp´rimenter denouvelles situations. Lorsque dans la simulation intervient un e ´l´ment al´atoire, on parle de simulation al´atoire. ee e e Les exemples d’application sont tr`s vari´s, citons par exemple : la simulation e e de ?les d’attente, de r´seaux, la recherche d’´tat stationnaire en physique. e e Remarquons de plus que si l’on cherche une repr´sentation ?d`le des ph´nom`nes e e e e observ´s, on estrapidement confront´ ` des di?cult´s dues aux calculs non explie ea e cites. Les techniques de simulation vont nous permettre d’approcher num´riquement e ces calculs. Nous allons d´velopper ici (dans ce mini-projet) les m´thodes de e e Monte-Carlo qui ont pour essence l’utilisation d’exp´riences r´p´t´es pour ´valuer e e ee e une quantit´, r´soudre un syst`me d´terministe[ELI01]. e e e e Ainsi nousrepr´sentons ici la m´thode de l’optimisation dite ”algorithme de e e recuit simul´ ” qui base sur l’algorithme de Metropolis, cet algorithme est une e application directe de la m´thode de Monte Carlo dans le domaine de l’optimie sation multi-objectif.
1.1
Historique de la m´thode de monte Carlo : e
On fait remonter la naissance de la m´thode de Monte-Carlo au comte de e Bu?on qui, en 1777, ad´crit une m´thode rest´e c´l`bre de calcul de ? bas´e sur e e e ee e la r´alisation d’exp´riences r´p´t´es. Mais la vraie naissance de la m´thode de e e e ee e Monte-Carlo est li´e ` l’apparition des premiers ordinateurs et ` leur utilisation e a a ´ dans le cadre des projets secrets du d´partement de la d´fense des Etats Unis e e dans les ann´es 40-45 en vue de la conception des premi`res bombesatomiques. e e L’un des premiers articles sur le sujet fut publi´ en 1949.Les pr´curseurs de ces e e m´thodes s’appellent Ulam, Von Neumann, Metropolis [LAP98]. e Dans les ann´es 1950, les physiciens : N. Metropolis, A. Rosenbluth, M. e Rosenbluth, A.Teller, et E. Teller, r´alis`rent la simulation d’un liquide simple e e (disques durs se d´pla¸ant en deux dimensions) par la m´thode de MC. Ils e ce propos`rent ce qui porte d´sormais le nom de MC Metropolis et qui est devenu e e la base des simulations MC des syst`mes de particules en interaction. e En arrivant aux ann´es 1980, les statisticiens et les informaticiens d´veloppent e e la m´thode de MC pour r´soudre des probl`mes en di?´rents domaine, tel que e e e e l’optimisation combinatoire, probabilit´, analyse de statistique g´n´tique.. . . . . e e e Dans les ann´es 1990, la m´thode de MC commence ` jouer un rˆle tr`s ime e a o e portant dans la computation en science biologique, elle est utilis´e pour l’analyse e 1
g´n´alogique complexe [Liu01]. e e Le terme ”Monte Carlo” ` ´tait introduit en 1944 par Von Neumann et a e Ulam comme un code secret de leur travail, ce nom fait allusion aux jeux de hasard pratiqu´s `Monte-Carlo, et publi´ pour la premi`re fois en 1949 dans e a e e un article co´crit avec Stanislas Ulam [Sadu09]. e
1.2
D´?nition et Description du MC : e
D´?nition : On d´signe par Monte Carlo, toute m´thode d’approximae e e tion de la solution d’un probl`me math´matique par l’utilisation d’un processus e e al´atoire. La m´thode peut garantie que l’erreur est plus petite d’une valeur e e…