Método de Monte Carlo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Aplicação do método de Monte Carlo para determinar a área de um lago.

Designa-se por método de Monte Carlo (MMC) qualquer método de uma classe de métodos estatísticos que se baseiam em amostragens aleatórias massivas para obter resultados numéricos, isto é, repetindo sucessivas simulações um elevado numero de vezes, para calcular probabilidades heuristicamente, tal como se, de facto, se registassem os resultados reais em jogos de casino (daí o nome). Este tipo de método é utilizado em simulações estocásticas com diversas aplicações em áreas como a física, matemática e biologia[1] . O método de Monte Carlo tem sido utilizado há bastante tempo como forma de obter aproximações numéricas de funções complexas em que não é viável, ou é mesmo impossível, obter uma solução analítica ou, pelo menos, determinística.

De acordo com (HAMMERSELEY,1964) o nome "Monte Carlo" surgiu durante o projeto Manhattan na Segunda Guerra Mundial. No projeto de construção da bomba atómica, Ulam, von Neumann e Fermi consideraram a possibilidade de utilizar o método, que envolvia a simulação direta de problemas de natureza probabilística relacionados com o coeficiente de difusão do neutron em certos materiais. Apesar de ter despertado a atenção desses cientistas em 1948, a lógica do método já era conhecida há bastante tempo. Por exemplo, existe um registro de um artigo escrito por Lord Kelvin dezenas de anos antes, que já utilizava técnicas de Monte Carlo em uma discussão das equações de Boltzmann. (Fonte Mundo PM)

Existem três classes de algoritmos Monte Carlo: Erro-Unilateral, Erro-Bilateral e Erro-Não-Limitado.

Monte Carlo de Erro-Unilateral[editar | editar código-fonte]

Seja P um problema e A um algoritmo aleatório, A é um algoritmo Monte Carlo de Erro-Unilateral que resolve P se

i) para toda configuração x que é solução de P, prob(A(x = SIM)) \geq \frac{1}{2}, e

ii) para toda configuração x que não é solução de P, prob(A(x = NÃO)) = 1.

Ou seja, sempre que a resposta é NÃO, o algoritmo garante a certeza da resposta.

Contudo, se a resposta for SIM, o algoritmo não garante que a resposta está correta.

Monte Carlo de Erro-Bilateral[editar | editar código-fonte]

Um algoritmo aleatório A é um algoritmo de Monte Carlo de Erro-Bilateral que computa o problema F se existe um número real positivo \epsilon, tal que para toda instância x de F

prob(A(x) = F(x)) \geq \frac{1}{2} + \epsilon

Monte Carlo de Erro-Não-Limitado[editar | editar código-fonte]

Os algoritmos Monte Carlo de Erro-Não-Limitado são comumente chamados de Algoritmos Monte Carlo.

Um algoritmo aleatório A é um algoritmo de Monte Carlo se para qualquer entrada x do problema F

prob(A(x) = F(x)) > \frac{1}{2}

Algoritmo de Metropolis[editar | editar código-fonte]

O algoritmo de Metropolis, também conhecido por Algoritmo de Metropolis-Hastings, apresentado inicialmente em 1953 num artigo [2] de Nicholas Metropolis, Arianna Rosenbluth, Marshall Rosenbluth, Augusta Teller e Edward Teller, e generalizado em 1970 por W. K. Hastings [3] , é provavelmente o método Monte Carlo mais utilizado na Física, e tem como objetivo determinar valores esperados de propriedades do sistema simulado, através de uma média sobre uma amostra. O algoritmo é concebido de modo a se obter uma amostra que siga a distribuição de Boltzmann.

Para se determinar a probabilidade de uma dada configuração, seria necessário conhecer a chance de ocorrência de todas as outras configurações. No caso de variáveis contínuas, seria necessário uma integração da densidade de probabilidade sobre todo o espaço de configurações, mas esse procedimento fica muito custoso quando se utiliza um número de variáveis da ordem de centenas.

A eficiência do algoritmo de Metropolis está diretamente ligada ao fato de não levar em conta a probabilidade das configurações em si, mas sim a razão entre elas, pois a razão entre as probabilidades de duas dadas configurações pode ser determinada independentemente das outras. Dadas duas configurações m e n quaisquer, a razão entre a probabilidade da configuração m, P_m, e a probabilidade da configuração n, P_n, pode ser escrita como


  \frac{P_m}{P_n}      =     \frac{      exp\left(-\frac{U_m}{k_bT}\right)     }{
  exp\left(-\frac{U_n}{k_bT}\right) } = exp\left(-\frac{U_m-U_n}{k_bT}\right)

A partir dessa igualdade, o algoritmo de Metropolis pode ser implementado através do seguinte conjunto de regras:

(a) Geração de uma configuração inicial aleatória, ou seja, com valores aleatórios para todos os graus de liberdade do sistema, respeitando as suas restrições. Vamos atribuir o índice m a essa configuração, que é aceita para a amostra.

(b) Geração de uma nova configuração-tentativa de índice n, resultado de pequenas alterações nas coordenadas da configuração m.

(c) Se a energia da configuração n for menor que a da configuração m, inclui-se a configuração n na nossa amostra, e se atribui a ela o índice m a partir desse momento. Caso contrário, realizam-se os passos descritos nos subitems (c1) e (c2) abaixo:

(c1) Gera-se um número aleatório entre 0 e 1;

(c2) Se esse número aleatório for menor que \frac{P_n}{P_m}, aceita-se na amostra a configuração n, e se atribui a ela o índice m. Caso contrário, o índice m permanece designando a configuração original.

(d) Repete-se os passos (b) e (c) até que algum critério de parada seja satisfeito. Cada uma dessas repetições é dita um passo Monte Carlo (MC).

Fluxograma para o algoritmo de Metropolis. Fonte: Wikimedia, criador: Leonardo Castro.

Referências[editar | editar código-fonte]

  1. J. Hromkovic, Algorithms for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. [S.l.]: Springer-Verlag, London - Berlin - Heidelberg - New York, 2001.
  2. N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, Equation of State Calculations by Fast Computing Machines, Journal of Chemical Physics 21, 1087 (1953).
  3. W. K. Hastings, Monte Carlo Sampling Methods Using Markov Chains and Their Applications, Biometrika 57 (1), 97 (1970).