Método de Monte Carlo

O método de Monte Carlo pode ser ilustrado como um jogo de navio de guerra. Primeiro, um jogador faz alguns disparos aleatórios. Em seguida aplica-se o jogador algoritmos (isto é. Um navio de guerra é quatro pontos na direcção vertical ou horizontal). Finalmente com base no resultado da amostragem e o algoritmo, o jogador pode determinar os locais prováveis de navios do outro jogador.

Um método de Monte Carlo é um computacional algoritmo que se baseia em repetido amostragem aleatória para calcular seus resultados. Métodos de Monte Carlo são frequentemente utilizados quando simulando físicos e matemáticos sistemas. Por causa de sua dependência de computação repetida e aleatória ou números pseudo-aleatórios, métodos de Monte Carlo são mais adequados para cálculo de um computador . Métodos de Monte Carlo tendem a ser usado quando for inviável ou impossível de calcular um resultado exato com uma algoritmo determinista.

O termo foi cunhado Monte Carlo em 1940 por físicos que trabalham em projetos de armas nucleares no Los Alamos National Laboratory.

Visão global

Não existe um único método de Monte Carlo; em vez disso, o termo descreve uma classe grande e amplamente utilizada de abordagens. No entanto, estas abordagens tendem a seguir um padrão em particular:

1. Definir um domínio de possíveis entradas.
2. Gerar insumos aleatoriamente a partir do domínio, e executar uma computação determinístico sobre eles.
3. Agregar os resultados dos cálculos individuais para o resultado final.

Por exemplo, o valor de π pode ser aproximada através de um método de Monte Carlo. Desenhe um quadrado no chão, em seguida, inscrever um círculo dentro dele. Agora, espalhe alguns pequenos objetos (por exemplo, grãos de arroz ou areia) em toda a praça. Se os objectos são espalhados uniformemente, então a proporção de objectos dentro do círculo deve ser aproximadamente π / 4, que é a razão entre a área do círculo para a área do quadrado. Assim, se contarmos o número de objetos no círculo, multiplicar por quatro, e dividir pelo número de objetos na praça, teremos uma aproximação de π.

Observe como a aproximação π segue o padrão geral de algoritmos de Monte Carlo. Primeiro, vamos definir um domínio de entradas: neste caso, é a praça que circunscreve nosso círculo. Em seguida, vamos gerar entradas aleatoriamente (espalhar grãos individuais dentro do quadrado), em seguida, executar um cálculo em cada entrada (teste se ele cai dentro do círculo). No final, nós agregar os resultados em nosso resultado final, a aproximação de π. Note, também, duas outras propriedades comuns de métodos de Monte Carlo: confiança da computação em bons números aleatórios, e sua convergência lenta para uma melhor aproximação à medida que mais pontos de dados são amostrados. Se nós simplesmente colocar nossos grãos no centro do círculo, eles podem simplesmente acumular-se em uma pilha dentro do círculo: não será distribuído uniformemente, e por isso a nossa aproximação será longe. Mas se eles são distribuídos uniformemente, em seguida, os mais grãos que caem, mais precisa a nossa aproximação de π se tornará.

História

Métodos de Monte Carlo foram originalmente praticado sob nomes mais genéricas, como "amostragem estatística". O nome "Monte Carlo" foi popularizado por pesquisadores de física Stanislaw Ulam, Enrico Fermi, John von Neumann , e Nicholas Metropolis, entre outros; o nome é uma referência a um famoso casino em Monaco que o tio de Ulam iria pedir dinheiro emprestado para jogar em. O uso de aleatoriedade e a natureza repetitiva do processo são análogos às actividades realizadas num casino.

Métodos aleatórios de computação e experimentação (geralmente consideradas formas de simulação estocástica) pode ser indiscutivelmente rastreada até os pioneiros da teoria das probabilidades (ver, por exemplo, Agulha de Buffon, eo trabalho em pequenas amostras por William Gosset), mas são mais especificamente rastreados para a era da computação pré-eletrônica. A diferença geral geralmente descrito sobre uma forma de simulação de Monte Carlo é que ele sistematicamente "inverte" o modo típico de simulação, o tratamento de problemas determinísticos pelo primeiro encontrar um análogo probabilística. Métodos anteriores de simulação e amostragem estatística geral fez o oposto: utilizando simulação para testar um problema determinístico anteriormente compreendida. Embora exemplos de uma abordagem "invertido" não existem historicamente, eles não foram considerados um método geral até que a popularidade do método de propagação Monte Carlo.

Talvez o mais famoso uso precoce foi por Enrico Fermi, em 1930, quando ele usou um método aleatório para calcular as propriedades do recém-descoberto de nêutrons . Métodos de Monte Carlo foram fundamentais para o simulações necessário para o Manhattan Project, que foram severamente limitada pelas ferramentas computacionais na época. Portanto, foi somente depois que os computadores eletrônicos foram construídos primeiro (a partir de 1945), que métodos de Monte Carlo começou a ser estudado em profundidade. Na década de 1950 foram usados em Los Alamos para trabalho inicial relativo ao desenvolvimento do bomba de hidrogênio, e tornou-se popularizou nos campos da física , físico-química, e operações de investigação . O Rand Corporation e da Força Aérea dos EUA foram dois dos principais organizações responsáveis pelo financiamento e divulgação de informações sobre métodos de Monte Carlo durante este tempo, e eles começaram a encontrar uma ampla aplicação em muitos campos diferentes.

Usos de métodos de Monte Carlo exigem grandes quantidades de números aleatórios, e foi a sua utilização que impulsionou o desenvolvimento de geradores de números pseudo-aleatórios, que eram muito mais rápido de usar do que as tabelas de números aleatórios que tinha sido previamente usados para a amostragem estatística.

Aplicações

Métodos de simulação de Monte Carlo são especialmente útil no estudo de sistemas com um grande número de graus de liberdade acoplados, como líquidos, materiais desordenados, sólidos fortemente acoplados, e estruturas celulares (ver modelo de Potts celular). Mais amplamente, métodos de Monte Carlo são úteis para modelar fenômenos com significativa incerteza em insumos, tais como o cálculo do risco no negócio (para o seu uso na indústria de seguros, ver modelagem estocástica). Um uso clássico é para a avaliação de integrais definidas , particularmente integrais multidimensionais com condições de contorno complicados.

Métodos de Monte Carlo em finanças são muitas vezes utilizados para calcular o valor das empresas, para avaliar os investimentos em projetos em nível corporativo ou para avaliar derivativos financeiros. O método Monte Carlo é destinado a analistas financeiros que querem construir modelos financeiros estocásticos ou probabilísticos em oposição aos modelos tradicionais estáticas e deterministas.

Métodos de Monte Carlo são muito importantes na física computacional, química física e afins campos aplicados, e têm diversas aplicações de complicado cromodinâmica quântica cálculos para projetar escudos de calor e formas aerodinâmicas.

Métodos de Monte Carlo também têm provado eficiente na resolução de equações diferenciais integrais acopladas de campos de radiação e de transporte de energia e, portanto, estes métodos têm sido utilizados em cálculos de iluminação global que produzem imagens fotorrealistas de modelos virtuais 3D, com aplicações em jogos de vídeo , arquitetura , design, gerada por computador filmes , efeitos especiais no cinema, negócios, economia e outros campos.

Métodos de Monte Carlo são úteis em muitas áreas da matemática computacional, onde uma escolha de sorte pode encontrar o resultado correto. Um exemplo clássico é Algoritmo de Rabin para testes primality: para qualquer n que não é primo, um x aleatória tem pelo menos uma chance de 75% de provar que n não é primo. Assim, se n não é primo, mas x diz que poderia ser, temos observado, no máximo, um evento de um-em-4. Se 10 x aleatórios diferentes dizer que "n é provavelmente primo" quando não é, temos observado um evento de um-em-um-milhão. Em geral, um algoritmo de Monte Carlo deste tipo produz uma resposta correta com uma garantia de n é composto, e x comprova isso assim, mas outra sem, mas com a garantia de não obter esta resposta quando é errado muitas vezes - neste caso, no máximo 25% do tempo. Veja também Algoritmo de Las Vegas para um relacionado, mas diferente, idéia.

As áreas de aplicação

As áreas de aplicação incluem:

• Gráficos, em particular para ray tracing; uma versão do Algoritmo de Metropolis-Hastings também é usado para o traçado de raios, onde é conhecido como Metropolis transporte luz
• Transporte leve modelagem em tecido biológico
• Métodos de Monte Carlo em finanças
• Engenharia de confiabilidade
• Em recozimento simulado para a previsão da estrutura de proteínas
• Na pesquisa de dispositivos de semicondutores, para modelar o transporte de portadores de corrente
• Ciência ambiental, lidar com o comportamento de contaminantes
• Método de Monte Carlo em física estatística; em particular, Modelagem molecular Monte Carlo como uma alternativa para computacional dinâmica molecular.
• Busca e Salvamento e Contra-Poluição. Modelos utilizados para prever a deriva de um bote salva-vidas ou o movimento de uma mancha de óleo no mar.
• Em Projeto probabilística para simular e compreender os efeitos da variabilidade
• Em Físico-química, particularmente para simulações envolvendo aglomerados atômicos
• Em ciência da computação
  • Algoritmo Las Vegas
  • DESAMPARO
  • Computador Go
• Modelagem do movimento de átomos de impureza (ou íons) em plasmas em tokamaks existentes e (por exemplo: DIVIMP).
• Em experimental de física de partículas , para a concepção Detectores, entendendo o seu comportamento e comparando dados experimentais para a teoria
• Códigos de física nuclear e de partículas utilizando o método de Monte Carlo:
  • GEANT - Simulação do CERN de partículas de alta energia que interagem com um detector.
  • CompHEP, Pítia - geradores de Monte-Carlo de colisões de partículas
  • MCNP (X) - códigos de transporte de radiação de LANL
  • EGS - Código de simulação de Stanford para o transporte acoplado de elétrons e fótons
  • Ferramenta de Monte Carlo do LLNL para cálculos de dose de radioterapia - PEREGRINO
  • BEAMnrc - sistema de código de Monte Carlo para fontes de modelagem de radioterapia ( Do LINAC)
  • PENÉLOPE - Monte Carlo para o transporte acoplado de fótons e elétrons, com aplicações em radioterapia
  • MONGE - Código de Serco Assurance para o cálculo do k-eficaz dos sistemas nucleares
  • Modelação de espuma e estruturas celulares
  • Modelagem de tecido morfogênese

Outros métodos que empregam Monte Carlo

• Modelos aleatórios variados, por exemplo, criticalidade auto-organizada
• Simulação direta Monte Carlo
• Método de Monte Carlo Dinâmico
• Kinetic Monte Carlo
• Quantum Monte Carlo
• Método Carlo Monte-Quasi usando sequências de baixa discrepância e auto evitando passeios
• Semiconductor transporte de carga e semelhantes
• Microscopia eletrônica de interacções feixe-amostra
• Otimização estocástica
• Modelo celular Potts
• Cadeia de Markov Monte Carlo
• Cross-Entropy Method
• Economia da Informação Aplicada

Use em matemática

Em geral, os métodos de Monte Carlo são usados em matemática para resolver vários problemas de geração de números aleatórios adequados e observando-se que a fracção dos números obedecendo alguma propriedade ou propriedades. O método é útil para a obtenção de soluções para problemas numéricos que são demasiado complicadas para resolver analiticamente. A aplicação mais comum do método de Monte Carlo é a integração Monte Carlo.

Integração

Métodos determinísticos de integração numérica operam tomando um número de amostras igualmente espaçadas a partir de uma função. Em geral, esta funciona muito bem para as funções de uma variável. No entanto, para as funções de vectores , métodos de quadratura determinísticos pode ser muito ineficiente. Para integrar numericamente uma função de um vector bidimensional, grelha de pontos igualmente espaçados ao longo de uma superfície bidimensional são necessários. Por exemplo, uma grelha 10x10 requer 100 pontos. Se o vector tem 100 dimensões, o mesmo espaçamento da grelha exigiria 10 ¹⁰⁰ Pontos de longe demais para ser computada. 100 dimensões não é de forma pouco razoável, uma vez que em muitos problemas físicos, um "dimensão" é equivalente a uma grau de liberdade. (Ver Maldição da dimensionalidade.)

Métodos de Monte Carlo fornecer uma maneira de sair deste time-aumento exponencial. Enquanto a função em questão é razoavelmente comportou-se bem, pode ser estimada por pontos seleccionando aleatoriamente no espaço 100-dimensional, e tendo algum tipo de média dos valores da função nestes pontos. Pelo lei dos grandes números, este método irá exibir isto é, a convergência-quadruplicação do número de pontos de amostragem vai reduzir a metade o erro, independentemente do número de dimensões.

Um aperfeiçoamento deste método é de alguma forma fazer os pontos aleatório, mas é mais provável de vir de regiões de elevada contribuição para o integral do que a partir de regiões de menor contribuição. Em outras palavras, os pontos devem ser retiradas de uma distribuição semelhante em forma para o integrando. Compreensivelmente, fazendo isso precisamente é tão difícil como resolver a integral em primeiro lugar, mas existem métodos aproximados disponíveis: de simplesmente tornando-se uma função integrável pensado para ser semelhante, para uma das rotinas adaptativos discutidos os tópicos listados abaixo.

Uma abordagem semelhante envolve o uso sequências de baixa discrepância em vez do- método Carlo Monte-quasi. Métodos Monte Carlo-Quasi pode muitas vezes ser mais eficientes na integração numérica, porque a sequência de "preenchimentos" melhor a região num sentido e amostras mais dos pontos mais importantes que podem fazer a simulação convergem para a solução desejada mais rapidamente.

Métodos de integração

• Métodos de amostragem diretos
  • Amostragem importância
  • Amostragem estratificada
  • Amostragem estratificada recursiva
  • Algoritmo VEGAS
• Passeio aleatório Monte Carlo incluindo Cadeias de Markov
  • Algoritmo de Metropolis-Hastings
• Amostragem Gibbs

Otimização

Outra aplicação poderosa e muito popular para números aleatórios na simulação numérica está em otimização numérica. Estes problemas utilizar as funções de algum vetor frequentemente grandes dimensões que devem ser minimizados (ou maximizada). Muitos problemas podem ser formulada da seguinte maneira: por exemplo, um programa de xadrez computador poderia ser visto como uma tentativa de encontrar o melhor conjunto de, digamos, 10 movimentos que produz a melhor função de avaliação no final. O problema do caixeiro viajante é outro problema de otimização. Há também aplicações para o projeto de engenharia, tais como otimização do projeto multidisciplinar.

A maioria dos métodos de optimização de Monte Carlo são baseados em passeios aleatórios. Essencialmente, o programa irá mover-se em torno de um marcador no espaço multidimensional, que tende a mover-se em direcções que conduzem a uma função inferior, mas, por vezes, movendo-se contra o gradiente.

Métodos de otimização

• Estratégia de evolução
• Algoritmos genéticos
• Têmpera Paralela
• Recozimento simulado
• Otimização estocástica
• Tunneling Stochastic

Problemas inversos

Formulação probabilística de problemas inversos leva à definição de uma distribuição de probabilidade no espaço do modelo. Isto combina distribuição de probabilidade informação a priori com novas informações obtidas através da medição de alguns parâmetros observáveis (dados). Como, no caso geral, a teoria da ligação de dados com os parâmetros do modelo não é linear, a probabilidade a posteriori no espaço do modelo pode não ser fácil de descrever (isto pode ser multimodal, alguns momentos não pode ser definido, etc).

Ao analisar um problema inverso, a obtenção de um modelo de probabilidade máxima geralmente não é suficiente, já que, normalmente, também desejam obter informações sobre a capacidade de resolução dos dados. No caso geral, podemos ter um grande número de parâmetros do modelo, e uma inspeção das densidades de probabilidade marginais de interesse pode ser impraticável, ou mesmo inútil. Mas é possível gerar pseudorandomly uma grande colecção de modelos de acordo com a distribuição de probabilidade posterior e para analisar e apresentar os modelos de tal maneira que a informação sobre as probabilidades relativas de propriedades modelo é transportado para o espectador. Isto pode ser conseguido por meio de um método de Monte Carlo eficiente, mesmo em casos em que nenhuma fórmula explícita para a distribuição, a priori, é acessível.

O método de amostragem importância mais conhecido, o algoritmo de Metropolis, pode ser generalizado, e isto dá um método que permite a análise de (possivelmente não linear) altamente problemas inversas com um complexo de informação a priori e de dados com uma distribuição de ruído arbitrária. Para mais detalhes, consulte Mosegaard e Tarantola (1995) , Ou TARANTOLA (2005) .

Monte Carlo e números aleatórios

Curiosamente, métodos de simulação de Monte Carlo geralmente não requerem verdadeiramente números aleatórios para ser útil - para outras aplicações, tais como testes de primalidade, a imprevisibilidade é vital (ver Davenport (1995)). Muitas das técnicas mais úteis usar determinista, sequências pseudo-aleatórios, tornando mais fácil para testar e simulações reinstalação. A única qualidade que geralmente necessária para fazer bom simulações é para a seqüência pseudo-aleatório para aparecer "aleatório o suficiente" em certo sentido.

O que isto significa depende da aplicação, mas normalmente eles devem passar por uma série de testes estatísticos. Testando que os números são uniformemente distribuída ou seguir uma outra distribuição desejado quando um grande número suficiente de elementos da seqüência são considerados é um dos mais simples e mais comuns.

Uma alternativa para o método básico de Monte Carlo

Economia de Informação Aplicada (AIE) é um método de análise de decisão utilizado em empresas e governo que aborda algumas das deficiências do método de Monte Carlo - pelo menos como ele é usualmente empregado em situações práticas. Os componentes mais importantes AIE adicionados ao método de Monte Carlo são:

1) Contabilidade para o excesso de confiança sistêmica de estimadores com humanos A avaliação de probabilidade calibrado

2) O cálculo do valor econômico da informação para orientar medidas empíricas adicionais

3) Utilizar os resultados de Monte Carlos como entrada para análise de portfólio

Ao simulação Monte Carlo na maioria usados são configurações análise decisão, especialistas Humanos são usados para estimar os probabilidades e gamas do modelo. No entanto, pesquisas decisão psicologia no campo da avaliação de probabilidade calibrados mostra que os seres humanos - especialmente os peritos em vários campos - tendem a ser estatisticamente excesso de confiança. Isto é, eles colocam muito alta a probabilidade de um resultado previsto irá ocorrer e eles tendem a usar intervalos que são demasiado estreitas para refletir sua incerteza. AIE envolve avaliadores humanos de formação, de modo que as probabilidades e intervalos eles fornecem realisticamente reflectir a incerteza (por exemplo., Um intervalo de confiança de 90% subjetiva como uma chance de 90% de conter o valor true). Sem essa formação, os modelos de Monte Carlo, invariavelmente subestimar a incerteza de uma decisão e, portanto, o risco.

Outra desvantagem é que, na prática, a maioria dos usuários de simulações de Monte Carlo confiar inteiramente nas estimativas subjetivas iniciais e quase nunca o acompanhamento com observação empírica. Isto pode ser devido ao número enorme de variáveis em muitos modelos ea incapacidade dos analistas para escolher variáveis economicamente justificadas para medir mais. AIE aborda esta usando métodos de teoria da decisão para calcular o valor econômico da informação adicional. Isso geralmente elimina a necessidade de medir a maioria das variáveis e coloca restrições pragmáticas sobre os métodos utilizados para medir as variáveis que têm um valor de informações significativas.

A lacuna última dirigida por AIE é que a saída de um Monte Carlo - pelo menos para a análise de decisões de negócio - é simplesmente o histograma dos retornos resultantes. Não é apresentada critérios para determinar se uma distribuição particular de resultados é aceitável ou não. Usos AIE Moderna Teoria do Portfolio para determinar quais os investimentos são desejáveis e quais as suas prioridades relativas deveria ser.