Monografia Final
(→Geração de Números Aleatórios) |
(→Geradores Lineares (Congruentes)) |
||
| Linha 176: | Linha 176: | ||
==Geradores Lineares (Congruentes)== | ==Geradores Lineares (Congruentes)== | ||
| + | |||
| + | Dentre os métodos existentes para a geração de números aleatórios, o da congruência multiplicativa é o mais empregado. Este método utiliza dois parâmetros inteiros (alfa e beta) além da semente s0 (Perin Filho, 1995). | ||
| + | |||
| + | O número inteiro gerado é obtido através da equação: | ||
| + | |||
| + | Inserir fórmula. | ||
| + | |||
| + | em que mod é o operador de resto. | ||
| + | |||
| + | O número inteiro gerado é obtido pela parte não inteira da divisão | ||
| + | |||
| + | Inserir fórmula. | ||
| + | |||
| + | Definir parâmetros alfa e beta que gerem números aleatórios para quaisquer sementes é difícil. Uma regra geral é a de que beta não pode ser divisível por alfa, evitando-se assim que si = 0. | ||
| + | |||
| + | |||
| + | Nota-se também que o menor i para o qual si = s0 equivale ao período da seqüência. | ||
| + | |||
| + | Usualmente, os métodos de congruência utilizam regras de atualização conforme equação abaixo, nas quais alfa, beta, gama e teta são parâmetros inteiros. | ||
| + | |||
| + | Inserir fórmula. | ||
| + | |||
| + | Outro tipo de gerador é gerador de Lehmer. A seqüência é definida numa coleção de inteiros através da fórmula de recursão: | ||
| + | |||
| + | Inserir fórmula. | ||
| + | |||
| + | |||
| + | onde: xn = é o enésimo membro da seqüência A, C, M = são parâmetros que podem ser ajustados por conveniência e para assegurar a natureza pseudo-aleatória da seqüência. | ||
| + | |||
| + | Por exemplo: M, o módulo, é freqüentemente o tamanho de uma palavra no computador e A, o multiplicador, é escolhido para produzir um longo período de seqüência e boas propriedades estatísticas. Exemplo prático: x0 = 13, A = 21, C = 1, M = 32 Seqüência produzida: 13, 18, 24, 25, 14, 7, 20, 5, 10... | ||
==Testando Geradores de Números aleatórios== | ==Testando Geradores de Números aleatórios== | ||
Edição de 08h35min de 6 de novembro de 2010
Tabela de conteúdo |
Introdução
Uma simulação é uma imitação de uma operação ou sistema do mundo real em função do tempo. Uma simulação envolve gerar e observar uma história artificial do sistema estudado podendo assim traçar diversas conclusões sobre a operação do sistema no mundo real (BANKS et al.,2005, p.3).
Para tal estudo, é necessário fazer “suposições” sobre o sistema a ser estudado. Tais “suposições” são normalmente feitas através de relações lógicas ou matemáticas, sendo estas chamadas de modelos. Para casos onde o modelo é simples, é possível utilizar métodos analíticos para se determinar a informação “exata” que se precisa, porém casos no mundo real costumam ser complexos demais para se obter uma solução analítica e, portanto, utiliza-se uma simulação realizada em computador. Em uma simulação computacional avalia-se um modelo numericamente e os dados obtidos são utilizados para “estimar” características do sistema (LAW e KELTON, 2000).
Simulação torna-se uma ferramenta apropriada para modificar e estudar interações internas dentro de um sistema muito complexo permitindo prever alterações que ocorreriam no mundo real. Simulação ainda pode ser utilizada como apoio pedagógico para reforçar metodologias de solução analítica (BANKS et. al, 2005, p.4).
Além disso, diversos sistemas modernos (projeto e análise de fábricas, determinação de requisitos de hardware, protocolos para redes de comunicação, projeto e operação de sistemas de transporte como aeroportos, rodovias, portos e metrôs, etc.) são complexos demais, logo suas interações internas podem ser tratadas apenas por via de simulações (BANKS et al., 2005, p.4).
Sistemas e Modelos de Simulação
De acordo com Schmidt e Taylor (apud LAW e KELTON, 2000) um 'sistema' é uma coleção de entidades que agem juntas e interagem para um mesmo fim lógico. Já que um sistema é o conjunto de variáveis que descrevem o sistema em um determinado instante.
O sistema pode ainda ser classificado entre discreto e contínuo. Um sistema discreto é aquele cujas variáveis mudam instantaneamente em certos tempos, enquanto em um sistema contínuo o estados das variáveis se altera continuamente. Um sistema dificilmente será totalmente discreto ou totalmente contínuo, mas é possível realizar tal classificação de acordo com o tipo de mudança predominante (LAW e KELTON, 2000).
Para se simular o sistema desejado é necessário criar um modelo de tal sistema. Um modelo é a representação de um sistema com o propósito de estudar o sistema. Para a maioria dos estudos, é necessário apenas considerar os aspectos do sistema que afetam o problema sob investigação (BANKS,2005,p. 12). Modelos ainda podem ser classificados entre matemáticos ou físicos. Modelos matemáticos utilizam notação matemática representando as relações lógicas e qualitativas do sistema. Modelos de simulação são um tipo específico de modelo de sistema.
Tais modelos de simulação ainda podem ser classificados como estáticos ou dinâmicos, determinísticos ou estocásticos. Os modelos de simulação estáticos representam o sistema em um ponto específico no tempo onde a decorrência do tempo não é relevante. Já os modelos de simulação dinâmicos representam sistemas que evoluem com o tempo. Modelos de simulação que não contém variáveis aleatórias são chamados de modelos determinísticos, enquanto que modelos estocásticos possuem uma ou mais variáveis aleatórias (LAW e KELTON, 2000).
Proposta
Apresentação didática do Método de Monte Carlo, seus aspectos históricos e aplicações, discutindo a essência do método num ambiente computacional, que é a geração de números pseudo aleatórios e suas limitações. Para tanto será realizado um estudo da fila do restaurante universitário do campus Curitiba da UTFPR a fim de colocar e demonstrar na prática o Método.
Justificativa
O Método de Monte Carlo é utilizado em diversas áreas do conhecimento, desde a própria informática, através da qual o método foi desenvolvido, até a administração. Entretanto, o método é normalmente usado puramente como uma ferramenta, não havendo uma preocupação de entendê-lo.
Considerando importante não apenas utilizar uma ferramenta, mas também entender seus fundamentos, é necessária uma abordagem didática do assunto. É a isto que este trabalho se propõe, expor didaticamente os fundamentos do Método de Monte Carlo para que as pessoas que o utilizam como ferramenta possam entender um pouco mais de seus princípios.
Objetivos
O objetivo geral deste trabalho é a apresentação didática do Método de Monte Carlo. Para tal, foram definidos os seguintes objetivos específicos:
- Estudo do Método de Monte Carlo no contexto de simulações;
- Estudo da fila do restaurante universitário, de modo a ilustrar o método.
Procedimentos
Os procedimentos podem ser divididos em duas seções: os procedimentos para a elaboração da monografia e os procedimentos para a elaboração dos aplicativos.
Para a elaboração da monografia, os procedimentos metodológicos constituem-se de três etapas:
- Pesquisa bibliográfica;
- Definição do sumário e;
- Edição e Revisão do texto.
Método de Monte Carlo
Segundo Prado (2009), o Método de Monte Carlo pode ser definido como “uma maneira de transformar um conjunto de números aleatórios em outro conjunto de variáveis , com a mesma distribuição da variável considerada.”
Para Machline (1985), dá-se o nome de Monte Carlo ao “método de simulação que consiste em gerar eventos aleatórios com dados”.
Nota-se que em ambos os conceitos estão presentes variáveis aleatórias, sendo este um ponto fundamental do Método. Trata-se de um método de várias aplicabilidades e que teve surgimento na década de 40, logo após a Segunda Guerra Mundial.
Aspectos Históricos
O método de Monte Carlo surgiu em meados dos anos 40, durante o projeto Manhattan da Segunda Guerra Mundial. Foi aplicado na pesquisa em fusão nuclear para construção da bomba atômica, mais especificamente, no estudo do comportamento dos nêutrons nas reações em cadeia em dispositivos de fissão.
Stanislaw Ulam foi um matemático americano que gostava de analisar, estatisticamente, situações cotidianas. Ao analisar, através de análise combinatória, a probabilidade de se ganhar uma partida de Paciência , perdeu muito tempo efetuando cálculos até perceber que seria mais produtivo realizar várias partidas e anotar os resultados, mas naquela época as técnicas de amostragem estatística tinham caído em desuso devido aos cálculos serem cansativos e volumosos.
Paralelamente a isso, um time de cientistas, engenheiros e técnicos trabalhava na construção do primeiro computador eletrônico – o ENIAC – na Universidade da Pensilvânia, na Filadélfia. Os mentores da equipe se inspiraram para a criação do computador elétrico ao ver filas e filas de mulheres fazendo contas em suas calculadoras de mesa. O computador eletrônico seria construído para lidar com tais processos.
Com a criação do ENIAC, Stanislaw Ulam viu a possibilidade de trazer de volta as técnicas de amostragem estatísticas e discutiu a idéia com John von Neumann, consultor em Aberdeen e Los Alamos. Ao ver a relevância da sugestão feita por Ulam, Neumann enviou uma carta às autoridades explicando uma possível aproximação estatística para o contorno do problema da difusão dos nêutrons em materiais físseis, encontrado durante a construção da bomba atômica.
Nesta carta, Neumman relacionou o problema de difusão dos nêutrons a uma partida de Paciência e relacionou também uma rodada aleatória das cartas a números aleatórios necessários para se tomar decisões ao longo do caminho, no caso do problema em questão. Por isso a necessidade de se ter uma fonte de números aleatórios distribuídos de forma não uniforme.
Muitas pessoas se interessaram pelo método sugerido por Neumman em sua carta e foi então que Nicholas Metropolis sugeriu um nome: método de Monte Carlo.
O Método
Os métodos de Monte Carlo utilizam experimentos de amostras estatísticas para determinar soluções aproximadas para uma variedade de problemas matemáticos. Tais métodos podem ser definidos como métodos de simulação estatística, onde o termo simulação estatística é aplicado genericamente a qualquer método que utilize uma sequência de números aleatórios para realizar uma simulação. Portanto, métodos de Monte Carlo realizam basicamente o mesmo processo.
O processo consiste em realizar diversas simulações utilizando números aleatórios e probabilidade para se obter uma aproximação da solução do problema. Como a solução é aproximada, analisar o erro é um fator importante para se obter uma solução apropriada. A tentativa de se minimizar esse erro é a razão para se haver tantos métodos de Monte Carlo diferentes.
Técnicas de Monte Carlo
Em situações onde o cálculo de uma integral pode se tornar algo extremamente complexo, Monte Carlo se torna uma ferramenta valiosa, pois pode provir uma solução aproximada com muito mais rapidez se comparada há outras técnicas.
Serão avaliados três diferentes métodos de Monte Carlo. A razão de se avaliar três métodos diferentes é que existem muitas considerações a serem feitas ao se utilizar Monte Carlo para se obter uma aproximação. Uma das principais, é minimizar o erro e obter uma aproximação válida. Outra preocupação é sobre qual método é melhor apropriado para o problema em questão e qual fornecerá o melhor resultado. Portanto, serão analisados quatro métodos diferentes, cada um com seus benefícios e requerimentos.
Monte Carlo (Crude Monte Carlo)
Utilizaremos está técnica para resolver a integral :
Inserir fórmula.
Uma descrição básico do método consiste em selecionar um número N, das amostras randômicas onde a ¡= s(valor da amostra) ¡= b. Para cada amostra, acha-se o valor de f(s), então soma-se todos os valores de f(s) obtidos e dividi-se por N, para obter uma média das amostras. Multiplica-se o valor obtido pelo intervalo (b-a) para se obter a integral (Pengelly, 2002).
Representação Matemática:
Inserir fórmula.
É possível determinar a variância das amostras pela fórmula seguinte:
Inserir fórmula.
Utilizando essa informação é possível determinar os intervalos de confiança e determinar o quão precisa a solução obtida é.
Aceitação e Rejeição de Monte Carlo
Considere a mesma integral do método anterior. No intervalo (a,b) deve-se encontrar o limite superior da função f(x) para qualquer valor de x. O intervalo (a,b) é então fechado por um retângulo que deve ser alto o suficiente para estar acima do limite superior. Assim é possível afirmar que toda a função f(x) no intervalo (a,b) está contida dentro do retângulo.
A partir disso, escolhem-se pontos randômicos de dentro do retângulo e verifica-se se estão abaixo ou acima do limite superior. Se o ponto estiver abaixo do limite superior, ele é tratado como uma amostra bem sucedida. Portanto, escolhem-se N pontos randomicamente e verifica-se quantos pontos foram amostras bem sucedidas. Ao finalizar a contagem, o valor da integral I é aproximado pela área do retângulo multiplicado pelo número de sucessos e dividido pelo número N de tentativas.
Representação matemática:
Inserir fórmula.
Sendo k o número de amostras bem sucessividades, N o número de tentativas, M é a área do retângulo feito.
Utilizando a mesma fórmula de variância do método anterior é possível analisar o erro deste método. Dos quatro métodos analisados este é a que possui a pior aproximação.
Amostra Estratificada
O principio básico desta técnica consiste separar o intervalo (a,b) em intervalos menores e realizar uma análise de Monte Carlo para cada subintervalo.
A razão para utilizar esse método é que ao invés de calcular a variância de uma só vez, é possível calcular a variância em intervalos menores e depois somá-los. Isso se torna útil caso a função possua trechos em que ela possua uma tendência a permanecer constante , ou seja, trechos onde a variância é pequena. Essa é a vantagem da amostra estratificada, pois ao dividir o intervalo é possível que haja certas propriedades vantajosas ao se analisar os intervalos.
Representação Matemática:
Inserir fórmula.
Com o intervalo (a,b) dividido em dois intervalos menores: (a,c) e (c,b).
Aplicações e Problemas Específicos
De acordo com Barros (2005), há duas aplicações básicas para o Método de Monte Carlo. A primeira delas diz respeito à avaliação empírica de uma distribuição estatística teórica. Esta é uma aplicação bastante utilizada no ensino estatístico. A segunda aplicação, e mais comum, é o uso do Método de Monte Carlo para estudar os efeitos que estão por trás de determinadas estatísticas.
Agulha de Buffon
O problema da agulha de Buffon data de 1777 e é um dos problemas mais antigos na área de probabilidade e geometria (ROSA et al., 2002). No problema da agulha de Buffon, observa-se que quando uma agulha de comprimento k é aleatoriamente lançada em direção a linhas paralelas com 2k de distância umas das outras, a razão entre o número de lançamentos pelo número de 'acertos' (número de vezes em que a agulha cruza uma linha) se aproxima do valor de PI. (BARROS, 2005). A ilustração abaixo mostra os conceitos do problema da agulha de Buffon:
Inserir imagem.
Figura 01: Agulha de Buffon Fonte: Rosa et al. (2002).
Cálculo do Pi
De acordo com Rosa et al, é possível calcular o valor de pi através do Método de Monte Carlo, inicialmente considerando uma circunferência inscrita em um quadrado. Ou seja, o lado do quadrado será o dobro do raio da circunferência.
Sabendo-se que a área da circunferência Ac = PI R² e a área do quadrado Aq = l² = (2R)² = 4R², temos que a relação entre as duas áreas é
Inserir fórmula.
Logo,
Inserir fórmula.
Isolando PI, temos que
Inserir fórmula.
Com o Método de Monte Carlo, é possível gerar números aleatórios que seriam 'lançados' na área do quadrado. Portanto
Inserir fórmula.
Limitações
Para Lawrence (2004), O método de Monte Carlo tem algumas limitações atribuídas. Elas são ligadas ao seu procedimento intrinsecamente estatístico mecânico, resultando em um escopo de sua resposta que pode ser demasiado abrangente para certas aplicações.
Ainda, a eficácia do método está diretamente correlacionada com a estatística disponível do processo em questão, podendo ser utilizado somente em casos que a mesma seja suficientemente abundante. esta forma, o método de Monte Carlo é limitado por sua abordagem estatística. Entretanto, em certos casos pode ser a única alternativa, ou ainda, reduzir bastante a complexidade da resolução.
Geração de Números Aleatórios
De acordo com Taha (1997), os números pseudoaleatórios utilizados pelo método de Monte Carlo são usados para determinar atributos (como energia, direção de escape, etc.) de uma partícula lançada e interações da partícula com o meio. Analisando essa situação, as seguintes propriedades de números pseudoaleatórios são desejáveis:
- As sequências de números pseudoaleatórios não devem ser correlacionadas.
- O gerador utilizado deve ser capaz de produzir sequências durante um longo período sem repetição.
- A sequência gerada deve ser uniforme e imparcial.
- O gerador deve ser eficiente.
Para Warnock (1987), verdadeiros números aleatórios podem ser gerados somente por dispositivos eletrônicos mas como os modelos de simulação são executados em computadores, isso torna-se inviável por ser lento para esse propósito. Outra desvantagem é que as etapas de depuração, verificação e validação dos modelos de simulação, às vezes, exigem que as sequências possam ser repetidas e como os dispositivos eletrônicos são regidos pela lei do acaso, torna-se impossível duplicá-las. A saída para esse impasse é gerar os números aleatórios baseando-se em operações aritméticas, conhecidos como pseudoaleatórios
Perin Filho (1995), afirma que muitos dos geradores de números aleatórios são baseados em eventos físicos, utilizando equipamentos simples, tais como roletas, ou complexos, como dispositivos eletrônicos ou radioativos. Porém, estes geradores raramente são utilizados em uma simulação de sistema, por serem 'lentos, dispendiosos e de difícil implementação'. Utiliza-se normalmente rotinas computacionais em simulação, sendo divididas em duas fases: a primeira na qual são gerados números aleatórios com distribuição uniforme, e a segunda na qual tais números são transformados em um valor da variável desejada.
Geradores Lineares (Congruentes)
Dentre os métodos existentes para a geração de números aleatórios, o da congruência multiplicativa é o mais empregado. Este método utiliza dois parâmetros inteiros (alfa e beta) além da semente s0 (Perin Filho, 1995).
O número inteiro gerado é obtido através da equação:
Inserir fórmula.
em que mod é o operador de resto.
O número inteiro gerado é obtido pela parte não inteira da divisão
Inserir fórmula.
Definir parâmetros alfa e beta que gerem números aleatórios para quaisquer sementes é difícil. Uma regra geral é a de que beta não pode ser divisível por alfa, evitando-se assim que si = 0.
Nota-se também que o menor i para o qual si = s0 equivale ao período da seqüência.
Usualmente, os métodos de congruência utilizam regras de atualização conforme equação abaixo, nas quais alfa, beta, gama e teta são parâmetros inteiros.
Inserir fórmula.
Outro tipo de gerador é gerador de Lehmer. A seqüência é definida numa coleção de inteiros através da fórmula de recursão:
Inserir fórmula.
onde: xn = é o enésimo membro da seqüência A, C, M = são parâmetros que podem ser ajustados por conveniência e para assegurar a natureza pseudo-aleatória da seqüência.
Por exemplo: M, o módulo, é freqüentemente o tamanho de uma palavra no computador e A, o multiplicador, é escolhido para produzir um longo período de seqüência e boas propriedades estatísticas. Exemplo prático: x0 = 13, A = 21, C = 1, M = 32 Seqüência produzida: 13, 18, 24, 25, 14, 7, 20, 5, 10...
