Método Monte Carlo - Monte Carlo method

Os métodos de Monte Carlo , ou experimentos de Monte Carlo , são uma ampla classe de algoritmos computacionais que dependem de amostragem aleatória repetida para obter resultados numéricos. O conceito subjacente é usar a aleatoriedade para resolver problemas que podem ser determinísticos em princípio. Eles são freqüentemente usados ​​em problemas físicos e matemáticos e são mais úteis quando é difícil ou impossível usar outras abordagens. Os métodos de Monte Carlo são usados ​​principalmente em três classes de problemas: otimização , integração numérica e geração de sorteios a partir de uma distribuição de probabilidade .

Em problemas relacionados à física, os métodos de Monte Carlo são úteis para simular sistemas com muitos graus de liberdade acoplados , como fluidos, materiais desordenados, sólidos fortemente acoplados e estruturas celulares (consulte o modelo celular de Potts , sistemas de partículas em interação , processos McKean-Vlasov , modelos cinéticos de gases ).

Outros exemplos incluem fenômenos de modelagem com incerteza significativa nas entradas, como o cálculo de risco nos negócios e, em matemática, avaliação de integrais definidos multidimensionais com condições de contorno complicadas . Na aplicação a problemas de engenharia de sistemas (espaço, exploração de petróleo , projeto de aeronaves, etc.), as previsões baseadas em Monte Carlo de falhas, estouros de custos e estouros de cronograma são rotineiramente melhores do que a intuição humana ou métodos alternativos "suaves".

Em princípio, os métodos de Monte Carlo podem ser usados ​​para resolver qualquer problema de interpretação probabilística. Pela lei dos números grandes , as integrais descritas pelo valor esperado de alguma variável aleatória podem ser aproximadas tomando a média empírica (também conhecida como média da amostra) de amostras independentes da variável. Quando a distribuição de probabilidade da variável é parametrizada, os matemáticos costumam usar um amostrador Monte Carlo de cadeia de Markov (MCMC). A ideia central é projetar um modelo de cadeia de Markov criterioso com uma distribuição de probabilidade estacionária prescrita . Ou seja, no limite, as amostras sendo geradas pelo método MCMC serão amostras da distribuição desejada (alvo). Pelo teorema ergódico , a distribuição estacionária é aproximada pelas medidas empíricas dos estados aleatórios do amostrador MCMC.

Em outros problemas, o objetivo é gerar desenhos a partir de uma sequência de distribuições de probabilidade que satisfaça uma equação de evolução não linear. Esses fluxos de distribuições de probabilidade podem sempre ser interpretados como as distribuições dos estados aleatórios de um processo de Markov cujas probabilidades de transição dependem das distribuições dos estados aleatórios atuais (ver processos de McKean-Vlasov , equação de filtragem não linear ). Em outros casos, recebemos um fluxo de distribuições de probabilidade com um nível crescente de complexidade de amostragem (modelos de espaços de caminho com um horizonte de tempo crescente, medidas de Boltzmann-Gibbs associadas a parâmetros de temperatura decrescentes e muitos outros). Esses modelos também podem ser vistos como a evolução da lei dos estados aleatórios de uma cadeia de Markov não linear. Uma maneira natural de simular esses sofisticados processos não lineares de Markov é amostrar várias cópias do processo, substituindo na equação de evolução as distribuições desconhecidas dos estados aleatórios pelas medidas empíricas amostradas . Em contraste com as metodologias tradicionais de Monte Carlo e MCMC, essas técnicas de partículas de campo médio dependem de amostras de interação sequencial. O campo médio da terminologia reflete o fato de que cada uma das amostras (também conhecidas como partículas, indivíduos, caminhantes, agentes, criaturas ou fenótipos) interage com as medidas empíricas do processo. Quando o tamanho do sistema tende para o infinito, essas medidas empíricas aleatórias convergem para a distribuição determinística dos estados aleatórios da cadeia de Markov não linear, de modo que a interação estatística entre as partículas desaparece.

Apesar de sua simplicidade conceitual e algorítmica, o custo computacional associado a uma simulação de Monte Carlo pode ser incrivelmente alto. Em geral, o método requer muitas amostras para obter uma boa aproximação, o que pode resultar em um tempo de execução total arbitrariamente grande se o tempo de processamento de uma única amostra for alto. Embora esta seja uma limitação severa em problemas muito complexos, a natureza embaraçosamente paralela do algoritmo permite que esse grande custo seja reduzido (talvez a um nível viável) por meio de estratégias de computação paralela em processadores locais, clusters, computação em nuvem, GPU, FPGA etc.

Visão geral

Os métodos de Monte Carlo variam, mas tendem a seguir um padrão específico:

1. Defina um domínio de possíveis entradas
2. Gere entradas aleatoriamente a partir de uma distribuição de probabilidade no domínio
3. Execute um cálculo determinístico nas entradas
4. Agregue os resultados

Por exemplo, considere um quadrante (setor circular) inscrito em um quadrado unitário . Dado que a proporção de suas áreas éπ/4, o valor de π pode ser aproximado usando um método de Monte Carlo:

1. Desenhe um quadrado e inscreva um quadrante dentro dele
2. Espalhe uniformemente um determinado número de pontos no quadrado
3. Conte o número de pontos dentro do quadrante, ou seja, tendo uma distância da origem menor que 1
4. A proporção da contagem interna e da contagem total da amostra é uma estimativa da proporção das duas áreas, π/4. Multiplique o resultado por 4 para estimar π .

Neste procedimento, o domínio das entradas é o quadrado que circunscreve o quadrante. Geramos entradas aleatórias espalhando grãos no quadrado e, em seguida, executamos um cálculo em cada entrada (teste se ela cai dentro do quadrante). Agregar os resultados produz nosso resultado final, a aproximação de π .

Existem duas considerações importantes:

1. Se os pontos não estiverem uniformemente distribuídos, a aproximação será ruim.
2. Existem muitos pontos. A aproximação é geralmente pobre se apenas alguns pontos são colocados aleatoriamente em todo o quadrado. Em média, a aproximação melhora à medida que mais pontos são colocados.

Os usos dos métodos de Monte Carlo requerem grandes quantidades de números aleatórios, e foi seu uso que estimulou o desenvolvimento de geradores de números pseudo-aleatórios , que eram muito mais rápidos de usar do que as tabelas de números aleatórios que haviam sido usadas anteriormente para amostragem estatística.

História

Antes do método de Monte Carlo ser desenvolvido, as simulações testavam um problema determinístico previamente compreendido e a amostragem estatística era usada para estimar as incertezas nas simulações. As simulações de Monte Carlo invertem essa abordagem, resolvendo problemas determinísticos usando metaheurísticas probabilísticas (ver recozimento simulado ).

Uma variante inicial do método de Monte Carlo foi desenvolvida para resolver o problema da agulha de Buffon , no qual π pode ser estimado deixando-se cair 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.

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 de 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 físsil. 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 foram incapazes de resolver o problema usando métodos matemáticos convencionais determinísticos. Ulam propôs o uso de experimentos aleatórios. Ele reconta sua inspiração da seguinte forma:

Os primeiros pensamentos e tentativas que fiz para praticar [o Método de Monte Carlo] foram sugeridos por uma pergunta que me ocorreu em 1946 quando eu estava convalescendo de uma doença e jogando paciência. A questão era quais são as chances de que um paciência Canfield com 52 cartas saia com sucesso? Depois de passar muito tempo tentando estimá-los por meio de cálculos combinatórios puros, me perguntei se um método mais prático do que o "pensamento abstrato" não seria expô-lo, digamos, cem vezes e simplesmente observar e contar o número de jogadas bem-sucedidas. Isso já era possível imaginar com o início da nova era de computadores rápidos, e eu imediatamente pensei em problemas de difusão de nêutrons e outras questões de física matemática e, de forma mais geral, como mudar os processos descritos por certas equações diferenciais em uma forma equivalente interpretável como uma sucessão de operações aleatórias. Mais tarde [em 1946], descrevi a ideia a John von Neumann e começamos a planejar cálculos reais.

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 , que se refere ao Casino Monte Carlo em Mônaco, onde o tio de Ulam pedia dinheiro emprestado a parentes para jogar. Usar listas de números aleatórios "verdadeiramente aleatórios" era extremamente lento, mas Von Neumann desenvolveu uma maneira de calcular números pseudo-aleatórios , usando o método do quadrado do meio . Embora este método tenha sido criticado como bruto, von Neumann estava ciente disso: ele o justificou como sendo mais rápido do que qualquer outro método à sua disposição, e também observou que quando dava errado, o fazia obviamente, ao contrário dos métodos que poderiam ser sutilmente incorretos .

Os métodos de Monte Carlo foram fundamentais para as simulações necessárias para o Projeto Manhattan , embora severamente limitados pelas ferramentas computacionais da época. Na década de 1950, eles foram usados ​​em Los Alamos para os primeiros trabalhos relacionados ao desenvolvimento da bomba de hidrogênio e se popularizaram nos campos da física , físico-química e pesquisa operacional . A Rand Corporation e a Força Aérea dos Estados Unidos foram duas das principais organizações responsáveis ​​por financiar e disseminar informações sobre os métodos de Monte Carlo durante esse tempo, e começaram a encontrar ampla aplicação em muitos campos diferentes.

A teoria de métodos de Monte Carlo de partículas do tipo campo médio mais sofisticados certamente começou em meados da década de 1960, com o trabalho de Henry P. McKean Jr. nas interpretações de Markov de uma classe de equações diferenciais parciais parabólicas não lineares que surgem na mecânica dos fluidos. Também citamos um artigo pioneiro anterior de Theodore E. Harris e Herman Kahn, publicado em 1951, usando métodos de Monte Carlo do tipo genético de campo médio para estimar as energias de transmissão de partículas. Metodologias de Monte Carlo do tipo genético de campo médio também são usadas como algoritmos de busca natural heurística (também conhecida como metaheurística ) na computação evolucionária. As origens dessas técnicas computacionais de campo médio podem ser rastreadas até 1950 e 1954 com o trabalho de Alan Turing em máquinas de aprendizagem de seleção de mutação de tipo genético e os artigos de Nils Aall Barricelli no Institute for Advanced Study em Princeton, New Jersey .

Quantum Monte Carlo e, mais especificamente, os métodos de difusão de Monte Carlo também podem ser interpretados como uma aproximação Monte Carlo de partícula de campo médio de integrais de caminho de Feynman - Kac . As origens dos métodos Quantum Monte Carlo são frequentemente atribuídas a Enrico Fermi e Robert Richtmyer, que desenvolveram em 1948 uma interpretação de partícula de campo médio de reações em cadeia de nêutrons, mas o primeiro algoritmo de partícula do tipo heurístico e genético (também conhecido como Reamostragem ou Reconfiguração Monte Carlo métodos) para estimar as energias do estado fundamental de sistemas quânticos (em modelos de matriz reduzida) é devido a Jack H. Hetherington em 1984 Na química molecular, o uso de metodologias de partículas semelhantes a heurísticas genéticas (também conhecidas como estratégias de poda e enriquecimento) pode ser rastreado até 1955 com o trabalho seminal de Marshall N. Rosenbluth e Arianna W. Rosenbluth .

O uso de Monte Carlo Sequencial no processamento avançado de sinais e inferência Bayesiana é mais recente. Foi em 1993 que Gordon et al. Publicaram em seu trabalho seminal a primeira aplicação de um algoritmo de reamostragem de Monte Carlo em inferência estatística bayesiana. Os autores chamaram seu algoritmo de 'filtro de bootstrap' e demonstraram que, em comparação com outros métodos de filtragem, seu algoritmo de bootstrap não requer nenhuma suposição sobre aquele espaço de estado ou o ruído do sistema. Citamos também outro artigo pioneiro neste campo de Genshiro Kitagawa sobre um "filtro Monte Carlo" relacionado, e os de Pierre Del Moral e Himilcon Carvalho, Pierre Del Moral, André Monin e Gérard Salut sobre filtros de partículas publicados em meados da década de 1990 . Filtros de partículas também foram desenvolvidos no processamento de sinais em 1989-1992 por P. Del Moral, JC Noyer, G. Rigal e G. Salut no LAAS-CNRS em uma série de relatórios de pesquisa restritos e classificados com STCAN (Service Technique des Constructions et Armes Navales), a empresa de TI DIGILOG e o LAAS-CNRS (Laboratório de Análise e Arquitetura de Sistemas) sobre problemas de processamento de sinais de radar / sonar e GPS. Essas metodologias de Monte Carlo sequencial podem ser interpretadas como um amostrador de aceitação-rejeição equipado com um mecanismo de reciclagem interativo.

De 1950 a 1996, todas as publicações sobre metodologias Sequential Monte Carlo, incluindo os métodos de poda e reamostragem de Monte Carlo introduzidos na física computacional e na química molecular, apresentam algoritmos naturais e heurísticos aplicados a diferentes situações sem uma única prova de sua consistência, nem uma discussão sobre o viés das estimativas e sobre algoritmos baseados em árvore genealógica e ancestral. Os fundamentos matemáticos e a primeira análise rigorosa desses algoritmos de partículas foram escritos por Pierre Del Moral em 1996.

Metodologias de partículas do tipo ramificado com tamanhos variados de população também foram desenvolvidas no final da década de 1990 por Dan Crisan, Jessica Gaines e Terry Lyons, e por Dan Crisan, Pierre Del Moral e Terry Lyons. Outros desenvolvimentos neste campo foram desenvolvidos em 2000 por P. Del Moral, A. Guionnet e L. Miclo.

Definições

Não há consenso sobre como Monte Carlo deve ser definido. Por exemplo, Ripley define a maioria da modelagem probabilística como simulação estocástica , com Monte Carlo sendo reservado para integração de Monte Carlo e testes estatísticos de Monte Carlo. Sawilowsky distingue entre uma simulação , um método de Monte Carlo e uma simulação de Monte Carlo: uma simulação é uma representação fictícia da realidade, um método de Monte Carlo é uma técnica que pode ser usada para resolver um problema matemático ou estatístico e uma simulação de Monte Carlo usa amostragem repetida para obter as propriedades estatísticas de algum fenômeno (ou comportamento). Exemplos:

• Simulação: O desenho de uma variável uniforme pseudo-aleatória do intervalo [0,1] pode ser usado para simular o lançamento de uma moeda: Se o valor for menor ou igual a 0,50 designe o resultado como cara, mas se o valor for maior de 0,50 designa o resultado como caudas. Esta é uma simulação, mas não uma simulação de Monte Carlo.
• Método de Monte Carlo: colocar uma caixa de moedas sobre a mesa e depois calcular a proporção de moedas que caem cara versus coroa é um método de Monte Carlo para determinar o comportamento de lançamentos repetidos de moeda, mas não é uma simulação.
• Simulação de Monte Carlo: Desenho de um grande número de variáveis ​​uniformes pseudo-aleatórias do intervalo [0,1] de uma vez, ou uma vez em vários momentos diferentes, e atribuindo valores menores ou iguais a 0,50 como cara e maior que 0,50 como coroa , é uma simulação de Monte Carlo do comportamento de jogar uma moeda repetidamente.

Kalos e Whitlock apontam que tais distinções nem sempre são fáceis de manter. Por exemplo, a emissão de radiação de átomos é um processo estocástico natural. Ele pode ser simulado diretamente, ou seu comportamento médio pode ser descrito por equações estocásticas que podem ser resolvidas usando métodos de Monte Carlo. "Na verdade, o mesmo código de computador pode ser visto simultaneamente como uma 'simulação natural' ou como uma solução das equações por amostragem natural."

Monte Carlo e números aleatórios

A ideia principal por trás desse método é que os resultados são calculados com base em amostragem aleatória repetida e análise estatística. A simulação de Monte Carlo é, na verdade, experimentações aleatórias, no caso em que os resultados dessas experiências não são bem conhecidos. As simulações de Monte Carlo são tipicamente caracterizadas por muitos parâmetros desconhecidos, muitos dos quais são difíceis de obter experimentalmente. Os métodos de simulação de Monte Carlo nem sempre requerem números verdadeiramente aleatórios para serem úteis (embora, para algumas aplicações, como teste de primalidade , a imprevisibilidade seja vital). Muitas das técnicas mais úteis usam sequências pseudo-aleatórias determinísticas , tornando mais fácil testar e executar novamente as simulações. A única qualidade geralmente necessária para fazer boas simulações é que a sequência pseudo-aleatória pareça "aleatória o suficiente" em um certo sentido.

O que isso significa depende da aplicação, mas normalmente eles devem passar por uma série de testes estatísticos. Testar se os números estão uniformemente distribuídos ou seguem outra distribuição desejada quando um número grande o suficiente de elementos da sequência é considerado é um dos mais simples e comuns. Correlações fracas entre amostras sucessivas também são frequentemente desejáveis ​​/ necessárias.

Sawilowsky lista as características de uma simulação de Monte Carlo de alta qualidade:

• o gerador de número (pseudo-aleatório) tem certas características (por exemplo, um longo "período" antes que a sequência se repita)
• o gerador de número (pseudo-aleatório) produz valores que passam nos testes de aleatoriedade
• existem amostras suficientes para garantir resultados precisos
• a técnica de amostragem adequada é usada
• o algoritmo usado é válido para o que está sendo modelado
• ele simula o fenômeno em questão.

Algoritmos de amostragem de número pseudo-aleatório são usados ​​para transformar números pseudo-aleatórios uniformemente distribuídos em números que são distribuídos de acordo com uma determinada distribuição de probabilidade .

As sequências de baixa discrepância são frequentemente usadas em vez da amostragem aleatória de um espaço, pois garantem uma cobertura uniforme e normalmente têm uma ordem de convergência mais rápida do que as simulações de Monte Carlo usando sequências aleatórias ou pseudo-aleatórias. Os métodos baseados em seu uso são chamados de métodos quase Monte Carlo .

Em um esforço para avaliar o impacto da qualidade dos números aleatórios nos resultados da simulação de Monte Carlo, pesquisadores astrofísicos testaram números pseudo-aleatórios criptograficamente seguros gerados por meio do conjunto de instruções RDRAND da Intel , em comparação com aqueles derivados de algoritmos, como o Mersenne Twister , em simulações de Monte Carlo de sinalizadores de rádio de anãs marrons . RDRAND é o gerador de números pseudoaleatórios mais próximo de um gerador de números aleatórios verdadeiro. Nenhuma diferença estatisticamente significativa foi encontrada entre os modelos gerados com geradores de números pseudo-aleatórios típicos e RDRAND para ensaios que consistem na geração de 10 ⁷ números aleatórios.

Simulação de Monte Carlo versus cenários "e se"

Existem maneiras de usar probabilidades que definitivamente não são simulações de Monte Carlo - por exemplo, modelagem determinística usando estimativas de ponto único. Cada variável incerta dentro de um modelo é atribuída a uma estimativa de "melhor estimativa". Os cenários (como o melhor, o pior ou o caso mais provável) para cada variável de entrada são escolhidos e os resultados registrados.

Em contraste, as simulações de Monte Carlo fazem a amostragem de uma distribuição de probabilidade para cada variável para produzir centenas ou milhares de resultados possíveis. Os resultados são analisados ​​para obter probabilidades de ocorrência de diferentes resultados. Por exemplo, uma comparação de um modelo de construção de custo de planilha executado usando cenários "e se" tradicionais e, em seguida, executando a comparação novamente com a simulação de Monte Carlo e distribuições de probabilidade triangulares mostra que a análise de Monte Carlo tem um intervalo mais estreito do que o "e se" análise. Isso ocorre porque a análise "e se" dá peso igual a todos os cenários (consulte a quantificação da incerteza em finanças corporativas ), enquanto o método de Monte Carlo dificilmente obtém amostras nas regiões de probabilidade muito baixa. As amostras nessas regiões são chamadas de "eventos raros".

Formulários

Os métodos de Monte Carlo são especialmente úteis para simular fenômenos com incerteza significativa em entradas e sistemas com muitos graus de liberdade acoplados . As áreas de aplicação incluem:

Ciências físicas

Física computacional
Mecânica  · Eletromagnética  · Termodinâmica  · Simulação
Potenciais Potencial Morse / de longo alcance  · Potencial Lennard-Jones  · Potencial Yukawa  · Potencial Morse
Dinâmica de fluidos Diferença finita  · Volume finito Elemento finito  · Elemento limite Malha Boltzmann  · Solucionador de Riemann Dinâmica de partículas dissipativas Hidrodinâmica de partículas suavizadas Modelos de turbulência
Métodos de Monte Carlo Integração  · Amostragem de Gibbs  · Algoritmo Metropolis
Partícula N-corpo  · Dinâmica molecular de partícula na célula
Cientistas Godunov  · Ulam  · von Neumann  · Galerkin  · Lorenz  · Wilson  · Amieiro  · Richtmyer
v t e

Os métodos de Monte Carlo são muito importantes em física computacional , físico-química e campos aplicados relacionados, e têm diversas aplicações, desde cálculos cromodinâmicos quânticos complicados até o projeto de escudos térmicos e formas aerodinâmicas , bem como na modelagem de transporte de radiação para cálculos de dosimetria de radiação. Em física estatística, a modelagem molecular de Monte Carlo é uma alternativa à dinâmica molecular computacional , e os métodos de Monte Carlo são usados ​​para computar teorias de campo estatísticas de sistemas simples de partículas e polímeros. Métodos Quantum Monte Carlo resolvem o problema de muitos corpos para sistemas quânticos. Na ciência dos materiais de radiação , a aproximação de colisão binária para simular a implantação de íons é geralmente baseada em uma abordagem de Monte Carlo para selecionar o próximo átomo em colisão. Na física de partículas experimental , os métodos de Monte Carlo são usados ​​para projetar detectores , entender seu comportamento e comparar os dados experimentais com a teoria. Na astrofísica , eles são usados ​​de maneiras tão diversas que modelam a evolução da galáxia e a transmissão da radiação de microondas através de uma superfície planetária rugosa. Os métodos de Monte Carlo também são usados ​​nos modelos de conjunto que formam a base da previsão do tempo moderna .

Engenharia

Os métodos de Monte Carlo são amplamente usados ​​em engenharia para análise de sensibilidade e análise probabilística quantitativa no projeto de processos . A necessidade surge do comportamento interativo, colinear e não linear de simulações de processo típicas. Por exemplo,

• Na engenharia microeletrônica , os métodos de Monte Carlo são aplicados para analisar variações correlacionadas e não correlacionadas em circuitos integrados analógicos e digitais .
• Em geoestatística e geometalurgia , os métodos de Monte Carlo sustentam o projeto de fluxogramas de processamento mineral e contribuem para a análise de risco quantitativa .
• Na análise de rendimento de energia eólica , a produção de energia prevista de um parque eólico durante sua vida útil é calculada dando diferentes níveis de incerteza ( P90 , P50, etc.)
• os impactos da poluição são simulados e o diesel é comparado com a gasolina.
• Em dinâmica de fluidos , em particular na dinâmica de gases rarefeitos , onde a equação de Boltzmann é resolvida para fluxos de fluido de número Knudsen finito usando o método de simulação direta de Monte Carlo em combinação com algoritmos computacionais altamente eficientes.
• Na robótica autônoma , a localização de Monte Carlo pode determinar a posição de um robô. É frequentemente aplicado a filtros estocásticos, como o filtro de Kalman ou filtro de partículas que forma o coração do algoritmo SLAM (localização e mapeamento simultâneos).
• Em telecomunicações , ao planejar uma rede sem fio, o design deve ser comprovado para funcionar em uma ampla variedade de cenários que dependem principalmente do número de usuários, de suas localizações e dos serviços que desejam usar. Os métodos de Monte Carlo são normalmente usados ​​para gerar esses usuários e seus estados. O desempenho da rede é então avaliado e, caso os resultados não sejam satisfatórios, o projeto da rede passa por um processo de otimização.
• Na engenharia de confiabilidade , a simulação de Monte Carlo é usada para calcular a resposta no nível do sistema dada a resposta no nível do componente. Por exemplo, para uma rede de transporte sujeita a um evento de terremoto, a simulação de Monte Carlo pode ser usada para avaliar a confiabilidade do terminal k da rede, dada a probabilidade de falha de seus componentes, por exemplo, pontes, estradas, etc. Outro exemplo profundo é a aplicação do método de Monte Carlo para resolver a equação G-Renovação do processo de renovação generalizada .
• Em processamento de sinal e inferência Bayesiana , filtros de partículas e técnicas sequenciais de Monte Carlo são uma classe de métodos de partículas de campo médio para amostragem e computação da distribuição posterior de um processo de sinal, dadas algumas observações parciais e ruidosas usando medidas empíricas interativas .
• Na modelagem de águas subterrâneas , os métodos de Monte Carlo são utilizados para gerar um grande número de realizações de campo de parâmetro heterogêneo para quantificação de incerteza de modelo ou inversão de parâmetro.

Mudança climática e forçante radiativa

O Painel Intergovernamental sobre Mudanças Climáticas baseia-se nos métodos de Monte Carlo na análise da função densidade de probabilidade do forçamento radiativo .

Função de densidade de probabilidade (PDF) de ERF devido ao total de GEE, forçamento de aerossol e forçamento antrópico total. O GEE consiste em WMGHG, ozônio e vapor de água estratosférico. Os PDFs são gerados com base nas incertezas fornecidas na Tabela 8.6. A combinação dos agentes de RF individuais para derivar o forçamento total sobre a Era Industrial é feita por simulações de Monte Carlo e com base no método de Boucher e Haywood (2001). PDF do ERF de mudanças de albedo de superfície e rastros combinados e cirrus induzido por rastros estão incluídos no forçamento antropogênico total, mas não são mostrados como um PDF separado. Atualmente, não temos estimativas de ERF para alguns mecanismos de força: ozônio, uso da terra, energia solar, etc.

Biologia Computacional

Os métodos de Monte Carlo são usados ​​em vários campos da biologia computacional , por exemplo, para inferência Bayesiana na filogenia , ou para estudar sistemas biológicos, como genomas, proteínas ou membranas. Os sistemas podem ser estudados em estruturas de granulação grossa ou ab initio dependendo da precisão desejada. Simulações de computador nos permitem monitorar o ambiente local de uma molécula em particular para ver se alguma reação química está acontecendo, por exemplo. Nos casos em que não é possível realizar um experimento físico, experimentos mentais podem ser realizados (por exemplo: quebra de ligações, introdução de impurezas em locais específicos, alteração da estrutura local / global ou introdução de campos externos).

Gráficos de computador

O rastreamento de caminho , ocasionalmente conhecido como rastreamento de raios de Monte Carlo, renderiza uma cena 3D ao rastrear aleatoriamente amostras de possíveis caminhos de luz. A amostragem repetida de qualquer pixel dado eventualmente fará com que a média das amostras convirja para a solução correta da equação de renderização , tornando-a um dos métodos de renderização de gráficos 3D mais precisos fisicamente existentes.

Estatísticas aplicadas

Os padrões para experimentos de Monte Carlo em estatísticas foram estabelecidos por Sawilowsky. Em estatísticas aplicadas, os métodos de Monte Carlo podem ser usados ​​para pelo menos quatro finalidades:

1. Para comparar estatísticas concorrentes para pequenas amostras em condições de dados realistas. Embora o erro tipo I e as propriedades de poder das estatísticas possam ser calculadas para dados extraídos de distribuições teóricas clássicas ( por exemplo , curva normal , distribuição de Cauchy ) para condições assintóticas ( isto é , tamanho de amostra infinito e efeito de tratamento infinitesimalmente pequeno), dados reais costumam fazer não tem tais distribuições.
2. Para fornecer implementações de testes de hipótese que são mais eficientes do que testes exatos, como testes de permutação (que muitas vezes são impossíveis de calcular), embora sejam mais precisos do que valores críticos para distribuições assintóticas .
3. Fornecer uma amostra aleatória da distribuição posterior na inferência Bayesiana . Este exemplo, então, aproxima e resume todas as características essenciais do posterior.
4. Para fornecer estimativas aleatórias eficientes da matriz Hessiana da função de log-verossimilhança negativa que pode ser calculada para formar uma estimativa da matriz de informação de Fisher .

Os métodos de Monte Carlo também são um meio-termo entre a randomização aproximada e os testes de permutação. Um teste de randomização aproximada é baseado em um subconjunto especificado de todas as permutações (o que implica em uma gestão potencialmente enorme, da qual as permutações foram consideradas). A abordagem de Monte Carlo é baseada em um número especificado de permutações desenhadas aleatoriamente (trocando uma pequena perda de precisão se uma permutação for desenhada duas vezes - ou mais frequentemente - pela eficiência de não ter que rastrear quais permutações já foram selecionadas).

Inteligência artificial para jogos

Os métodos de Monte Carlo foram desenvolvidos em uma técnica chamada pesquisa de árvore de Monte-Carlo, que é útil para pesquisar o melhor movimento em um jogo. Os movimentos possíveis são organizados em uma árvore de busca e muitas simulações aleatórias são usadas para estimar o potencial de longo prazo de cada movimento. Um simulador de caixa preta representa os movimentos do oponente.

O método de pesquisa em árvore Monte Carlo (MCTS) tem quatro etapas:

1. Começando no nó raiz da árvore, selecione os nós filhos ideais até que um nó folha seja alcançado.
2. Expanda o nó folha e escolha um de seus filhos.
3. Jogue um jogo simulado começando com esse nó.
4. Use os resultados desse jogo simulado para atualizar o nó e seus ancestrais.

O efeito líquido, ao longo de muitos jogos simulados, é que o valor de um nó que representa um movimento irá subir ou descer, correspondendo esperançosamente a se esse nó representa ou não um bom movimento.

Monte Carlo Tree Search foi usado com sucesso para jogos como Go , Tantrix , Battleship , Havannah e Arimaa .

Design e visual

Os métodos de Monte Carlo também são eficientes na resolução de equações diferenciais integrais acopladas de campos de radiação e transporte de energia e, portanto, esses métodos têm sido usados ​​em cálculos de iluminação global que produzem imagens foto-realistas de modelos virtuais 3D, com aplicações em videogames , arquitetura , design , filmes gerados por computador e efeitos especiais cinematográficos.

Busca e resgate

A Guarda Costeira dos EUA utiliza métodos de Monte Carlo em seu software de modelagem de computador SAROPS para calcular as prováveis ​​localizações das embarcações durante as operações de busca e resgate . Cada simulação pode gerar até dez mil pontos de dados que são distribuídos aleatoriamente com base nas variáveis ​​fornecidas. Os padrões de pesquisa são então gerados com base nas extrapolações desses dados para otimizar a probabilidade de contenção (POC) e a probabilidade de detecção (POD), que juntas equivalem a uma probabilidade geral de sucesso (POS). Em última análise, isso serve como uma aplicação prática de distribuição de probabilidade a fim de fornecer o método mais rápido e conveniente de resgate, salvando vidas e recursos.

Finanças e negócios

A simulação de Monte Carlo é comumente usada para avaliar o risco e a incerteza que afetariam o resultado de diferentes opções de decisão. A simulação de Monte Carlo permite ao analista de risco de negócios incorporar os efeitos totais da incerteza em variáveis ​​como volume de vendas, preços de commodities e mão de obra, taxas de juros e de câmbio, bem como o efeito de eventos de risco distintos como o cancelamento de um contrato ou a mudança de uma lei tributária.

Os métodos de Monte Carlo em finanças são freqüentemente usados ​​para avaliar investimentos em projetos em uma unidade de negócios ou nível corporativo, ou outras avaliações financeiras. Eles podem ser usados ​​para modelar cronogramas de projeto , onde as simulações agregam estimativas para o pior caso, o melhor caso e durações mais prováveis ​​para cada tarefa para determinar os resultados para o projeto geral. [1] Os métodos de Monte Carlo também são usados ​​na precificação de opções e na análise de risco de inadimplência. Além disso, eles podem ser usados ​​para estimar o impacto financeiro das intervenções médicas.

Lei

Uma abordagem de Monte Carlo foi usada para avaliar o valor potencial de um programa proposto para ajudar peticionários do sexo feminino em Wisconsin a serem bem-sucedidos em seus pedidos de ordens de restrição de assédio e violência doméstica . Foi proposto ajudar as mulheres a terem sucesso em suas petições, proporcionando-lhes maior defesa, reduzindo potencialmente o risco de estupro e agressão física . No entanto, havia muitas variáveis ​​em jogo que não puderam ser estimadas com perfeição, incluindo a eficácia das ordens de restrição, a taxa de sucesso dos peticionários com e sem defesa e muitos outros. O estudo fez testes que variaram essas variáveis ​​para chegar a uma estimativa geral do nível de sucesso do programa proposto como um todo.

Use em matemática

Em geral, os métodos de Monte Carlo são usados ​​em matemática para resolver vários problemas gerando números aleatórios adequados (consulte também Geração de números aleatórios ) e observando aquela fração dos números que obedece a alguma propriedade ou propriedades. O método é útil para obter soluções numéricas para problemas muito complicados para resolver analiticamente. A aplicação mais comum do método Monte Carlo é a integração de Monte Carlo.

Integração

Os algoritmos de integração numérica determinística funcionam bem em um pequeno número de dimensões, mas encontram dois problemas quando as funções têm muitas variáveis. Primeiro, o número de avaliações de função necessárias aumenta rapidamente com o número de dimensões. Por exemplo, se 10 avaliações fornecem precisão adequada em uma dimensão, então 10 ¹⁰⁰ pontos são necessários para 100 dimensões - muitos para serem computados. Isso é chamado de maldição da dimensionalidade . Em segundo lugar, o limite de uma região multidimensional pode ser muito complicado, portanto pode não ser viável reduzir o problema a uma integral iterativa . 100 dimensões não é de forma alguma incomum, já que em muitos problemas físicos, uma "dimensão" é equivalente a um grau de liberdade .

Os métodos de Monte Carlo fornecem uma saída para esse aumento exponencial no tempo de computação. Contanto que a função em questão seja razoavelmente bem-comportada , ela pode ser estimada selecionando pontos aleatoriamente no espaço de 100 dimensões e tomando algum tipo de média dos valores da função nesses pontos. Pelo teorema do limite central , este método exibe convergência - isto é, quadruplicar o número de pontos amostrados reduz o erro pela metade, independentemente do número de dimensões. ${\ displaystyle \ scriptstyle 1 / {\ sqrt {N}}}$

Um refinamento desse método, conhecido como amostragem de importância em estatística, envolve amostrar os pontos aleatoriamente, mas com mais frequência onde o integrando é grande. Para fazer isso precisamente um teria que já sabe a integral, mas pode-se aproximar a integral por uma integral de uma função semelhante ou usar rotinas adaptativas, tais como amostragem estratificada , amostragem estratificada recursiva , amostragem guarda-chuva adaptativa ou o algoritmo VEGAS .

Uma abordagem semelhante, o método quase Monte Carlo , usa sequências de baixa discrepância . Essas sequências "preenchem" melhor a área e amostram os pontos mais importantes com mais frequência, de modo que os métodos quase-Monte Carlo podem convergir para a integral mais rapidamente.

Outra classe de métodos para amostrar pontos em um volume é simular passeios aleatórios sobre ele ( cadeia de Markov Monte Carlo ). Tais métodos incluem o algoritmo de Metropolis-Hastings , amostragem de Gibbs , Wang e Landau algoritmo , e interagindo tipo MCMC metodologias, tais como os sequenciais de Monte Carlo amostradores.

Simulação e otimização

Outra aplicação poderosa e muito popular para números aleatórios em simulação numérica é a otimização numérica . O problema é minimizar (ou maximizar) as funções de algum vetor que geralmente possui muitas dimensões. Muitos problemas podem ser formulados desta forma: por exemplo, um programa de xadrez de computador pode ser visto como uma tentativa de encontrar o conjunto de, digamos, 10 movimentos que produzam a melhor função de avaliação no final. No problema do caixeiro viajante, o objetivo é minimizar a distância percorrida. Existem também aplicações para projetos de engenharia, como a otimização de projetos multidisciplinares . Ele foi aplicado com modelos quase unidimensionais para resolver problemas de dinâmica de partículas explorando com eficiência grandes espaços de configuração. Referência é uma revisão abrangente de muitas questões relacionadas à simulação e otimização.

O problema do caixeiro viajante é o que se chama de problema de otimização convencional. Ou seja, todos os fatos (distâncias entre cada ponto de destino) necessários para determinar o caminho ideal a seguir são conhecidos com certeza e o objetivo é percorrer as opções de viagem possíveis para chegar àquele com a menor distância total. No entanto, vamos supor que, em vez de querer minimizar a distância total percorrida para visitar cada destino desejado, quiséssemos minimizar o tempo total necessário para chegar a cada destino. Isso vai além da otimização convencional, pois o tempo de viagem é inerentemente incerto (congestionamentos, hora do dia, etc.). Como resultado, para determinar nosso caminho ideal, gostaríamos de usar simulação - otimização para primeiro entender a gama de tempos potenciais que poderia levar para ir de um ponto a outro (representado por uma distribuição de probabilidade, neste caso, em vez de uma distância específica) e então otimizar nossas decisões de viagem para identificar o melhor caminho a seguir levando essa incerteza em consideração.

Problemas inversos

A formulação probabilística de problemas inversos leva à definição de uma distribuição de probabilidade no espaço do modelo. Esta distribuição de probabilidade combina informações anteriores com novas informações obtidas medindo alguns parâmetros observáveis ​​(dados). Como, no caso geral, a teoria que liga os dados aos parâmetros do modelo é não linear, a probabilidade posterior no espaço do modelo pode não ser fácil de descrever (pode ser multimodal, alguns momentos podem não ser definidos, etc.).

Ao analisar um problema inverso, a obtenção de um modelo de máxima verossimilhança geralmente não é suficiente, pois normalmente também desejamos ter informações sobre o poder de resolução dos dados. No caso geral, podemos ter muitos parâmetros de modelo, e uma inspeção das densidades marginais de probabilidade de interesse pode ser impraticável ou mesmo inútil. Mas é possível gerar pseudo-aleatoriamente uma grande coleção de modelos de acordo com a distribuição de probabilidade posterior e analisar e exibir os modelos de tal forma que as informações sobre as probabilidades relativas das propriedades do modelo sejam transmitidas ao espectador. Isso pode ser realizado por meio de um método de Monte Carlo eficiente, mesmo nos casos em que nenhuma fórmula explícita para a distribuição a priori esteja disponível.

O método de amostragem de importância mais conhecido, o algoritmo Metropolis, pode ser generalizado, e isso fornece um método que permite a análise de problemas inversos (possivelmente altamente não lineares) com informações a priori complexas e dados com uma distribuição de ruído arbitrária.

Filosofia

A exposição popular do Método Monte Carlo foi conduzida por McCracken. A filosofia geral do método foi discutida por Elishakoff e Grüne-Yanoff e Weirich.

Veja também

Referências

Citações

Fontes

links externos

• Mídia relacionada ao método Monte Carlo no Wikimedia Commons