thumb|300px|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. Em suma, utilizam a aleatoriedade de dados para gerar um resultado para problemas que a priori são determinísticos. São utilizados mais comumente em problemas de física e de matemática onde são muito difíceis ou impossível de serem resolvidos com outros métodos.
O método de Monte Carlo tem sido utilizado há muito 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.
Em princípio, métodos de Monte Carlo podem ser usados para resolver quaisquer problemas com um interpretação probabilística. Pela Lei dos Grandes Números, integrais descritas pelo valor esperado de alguma variável aleatória podem ser aproximadas obtendo a média empírica de amostras independentes de variáveis. Quando a distribuição de probabilidade da variável é parametrizada, normalmente é utilizada o gerador de amostras Markov chain Monte Carlo (MCMC), tendo assim, que no limite, as amostras geradas serão amostras da distribuição desejada.
História 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, Stanisław 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 nêutron 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.
Antes do método de Monte Carlo ser desenvolvido, as simulações possuíam um problema determinístico devido a amostragem estatística que era usada para estimar as incertezas nas simulações. As simulações de Monte Carlo invertem essa abordagem, resolvendo problemas determinísticos usando probabilidades meta-heurísticas.
Uma variante inicial do método de Monte Carlo foi desenvolvida para resolver o problema da agulha de Buffon, no qual Pi () pode ser estimado jogando agulhas em um piso feito de tiras equidistantes paralelas. Na década de 1930, Enrico Fermi experimentou pela primeira vez o método Monte Carlo enquanto estudava a difusão de nêutrons, mas não publicou este trabalho.Metropolis, N. (1987). "The beginning of the Monte Carlo method" (PDF). Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125–130.
No final dos anos 1940, Stanislaw Ulam inventou a versão moderna do método Markov Chain Monte Carlo enquanto trabalhava em projetos de armas nucleares no Laboratório Nacional Los Alamos. Imediatamente após a descoberta de Ulam, John von Neumann compreendeu sua importância. Von Neumann programou o computador ENIAC para realizar cálculos de Monte Carlo. Em 1946, físicos de armas nucleares em Los Alamos estavam investigando a difusão de nêutrons em material fissionável. Apesar de ter a maioria dos dados necessários, como a distância média que um nêutron viajaria em uma substância antes de colidir com um núcleo atômico e quanta energia o nêutron provavelmente emitiria após uma colisão, os físicos de Los Alamos não foram capazes de resolver o problema usando métodos matemáticos convencionais determinísticos. Ulam propôs então o uso de experimentos aleatórios.Eckhardt, Roger (1987). "Stan Ulam, John von Neumann, and the Monte Carlo method" (PDF). Los Alamos Science (15): 131–137.
Por ser secreto, o trabalho de von Neumann e Ulam exigia um codinome. Um colega de von Neumann e Ulam, Nicholas Metropolis, sugeriu usar o nome Monte Carlo. Se referindo ao Cassino Monte Carlo em Mônaco. Usar listas de números aleatórios "verdadeiramente aleatórios" era extremamente lento, mas Von Neumann desenvolveu uma maneira de calcular números pseudoaleatórios usando o método do quadrado do meio. Embora este método tenha sido criticado como bruto, von Neumann justificava como sendo o método mais rápido disponível na época.Peragine, Michael (2013). The Universal Mind: The Evolution of Machine Intelligence and Human Psychology. Xiphias Press. Retrieved 2018-12-17.Mazhdrakov, Metodi; Benov, Dobriyan; Valkanov, Nikolai (2018). The Monte Carlo Method. Engineering Applications. ACMO Academic Press. p. 250. ISBN 978-619-90684-3-4.
Exemplos
Estimativa da população de peixes em um lago Um exemplo clássico do uso do método de Monte Carlo é a estimativa da população de peixes em um lago. Nesse método é feita uma primeira etapa de identificação: são pescados diversos peixes que são marcados por meio de um anel. Nessa etapa é importante saber exatamente o número de peixes que foram identificados dessa forma.
Na segunda etapa são pescados novamente uma certa quantidade de peixes aleatoriamente, anotando respectivamente aqueles que estavam identificados com o anel e aqueles que não estavam identificados.
É esperado que a proporção entre peixes pescados com a identificação e o número total de peixes pescados siga a mesma proporção entre o número total de peixes com a identificação e o número total de peixes, como mostra a relação:
Sendo o número de peixes pescados que estavam marcados, o número total de peixes pescados, o número total de peixes marcados e o número total de peixes.
Por meio desta relação é possível obter o número total de peixes no lago , já que , e são dados do experimento.
Estimativa para o valor de Um exemplo simples de simulação seria o cálculo de . Modelamos um círculo de raio unitário inscrito em um quadrado e geramos pontos aleatórios dentro desse quadrado, que podem assim estar dentro ou fora do círculo. Com uma amostragem grande o suficiente de pontos, a razão dos pontos dentro do círculo pelo total de pontos gerados se aproxima de um quarto da razão da área do círculo pela área do quadrado (já que o quadrado terá área igual a 4 unidades de medida de área). Assim, estimamos o valor de numericamente, como demonstrado nos códigos abaixo, utilizando a geração de números pseudo-aleatórios em uma distribuição uniforme entre 0 e 1. Como todos os números gerados no código apresentado são positivos, a área analisada é apenas a do primeiro quadrante. Contudo, isso não interfere na razão entre o número de pontos dentro do círculo e o número de pontos dentro do quadrado já que ambos, tanto o círculo quanto o quadrado, têm sua área reduzida em um quarto, mantendo a razão constante.
Pseudocódigo 1. Inicializar pontos_círculo, pontos_quadrado e número de pontos a serem gerados N.
2. Para i <= N:
3. Gerar ponto x aleatório.
4. Gerar ponto y aleatório.
5. Calcular d = x*x + y*y.
6. Se d <= 1, incrementar pontos_círculo.
7. Calcular pi = 4*(pontos_círculo/pontos_quadrado).
8. Encerrar
Exemplo em python import numpy as np
N = 100000 # número de iterações n = 0 #gerando as coordenadas dos pontos no quadrado unitário seguindo uma distribuição uniforme entre 0 e 1.
x = np.random.uniform(size=N) y = np.random.uniform(size=N)
#percorrendo as listas geradas de x e y, se o ponto gerado estiver dentro do primeiro quadrante do círculo, somo 1 no contador n. for i in range(N): if x[i]**2 + y[i]**2 < 1: n+=1 #como a área de um quadrante do círculo é pi/4, multiplicamos a razão n/N por 4 pi = 4*n/N
Exemplo em R N <- 100000 # número de iterações n <- 0
# coordenadas dos pontos no quadrado unitário # seguindo uma distribuição uniforme entre 0 e 1 x <- runif(N) y <- runif(N)
# percorrento x e y e realizando a contagem # de quantos pontos estão no círculo unitário (n) for (i in 1:N){ if (x[i]^2 + y[i]^2 < 1){ n <- n + 1
# Como a área de um quadrante é pi/4, # a razão n/N é multiplicada por 4 pi <- 4*n/N
Método de integração por Monte Carlo No exemplo anterior, foi utilizado o método de integração por Monte Carlo para obter o valor da área correspondente ao valor de . Esse método de integração pode ser utilizado analogamente em qualquer outra função dentro dos requisitos de integração. Segue um exemplo de código e pseudocódigo para uma função estritamente positiva dentro de um intervalo definido.
Pseudocódigo 1. Definir a função, o intervalo de integração [a,b], o número de iterações N e o número de contagem n=0.
2. Para i <= N:
3. Gerar ponto x0 aleatório entre a e b
4. Gerar ponto y0 aleatório entre 0 e o máximo da função no intervalo max_y
5. Calcular f(x0)
6. Se y0 < = f(x0), incrementar n.
7. Calcular área = max_y*(b-a)*(n/N).
8. Encerrar
Exemplo em Python import numpy as np
def f(x): # função a ser integrada y=1+x**2 return y
a = 5 # limite inferior do intervalo b = 10 # limite superior do intervalo N = 1000000 # numero de interacoes n = 0 # contagens entre a funcao e y=0
x = a+(b-a)*np.random.uniform(size=N) # pontos aleatorios entre a e b max_y=max([f(x[i]) for i in range(N)]) # encontrando o maximo da funcao no intervalo y = max_y*np.random.uniform(size=N) # pontos aleatorios entre 0 e max_y
for i in range(N): if y[i] < f(x[i]): n+=1
# a area da integracao em relacao a area do retangulo segue a proporcao n/N A = max_y*(b-a)*(n/N) print(A)
Classes do algoritmo Monte Carlo Existem três classes de algoritmos Monte Carlo: Erro-Unilateral, Erro-Bilateral e Erro-Não-Limitado.
Monte Carlo de Erro-Unilateral Seja um problema e A um algoritmo aleatório, A é um algoritmo Monte Carlo de Erro-Unilateral que resolve se
i) para toda configuração que é solução de , , e
ii) para toda configuração que não é solução de , .
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 Um algoritmo aleatório A é um algoritmo de Monte Carlo de Erro-Bilateral que computa o problema se existe um número real positivo , tal que para toda instância de
Monte Carlo de Erro-Não-Limitado 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
Números aleatórios A ideia principal por trás deste método é que seus resultados são baseados em amostragens aleatórias e análises estatísticas, de forma que o método gera experimentos aleatórios, onde seus resultados são desconhecidos. Desta forma, é necessário utilizar métodos de geração de sequências de números aleatórios ou, no caso de computadores, números pseudo-aleatórios, permitindo acesso ao estado inicial do gerador, facilitando a reprodução da simulação. Simulações de Monte Carlo de qualidade devem ter certas características:
O gerador deve ter um longo "período" antes que a sequência dos números se repita; O gerador deve produzir números que passam em testes de aleatoriedade; Existem amostras suficientes para obter resultados acurados; O algoritmo utilizado é válido para o que está sendo modelado; Simula o fenômeno em questão; O método de amostragem correto é utilizado.
Algoritmo de Metropolis direita|miniatura|400px|Fluxograma para o algoritmo de Metropolis.