Rascunhos sobre geração de números aleatórios
Tabela de conteúdo |
Aline
Referência:
PERIN FILHO, Clovis. Introdução à Simulação de Sistemas. Editora da Unicamp, Campinas, 1995
Geração de variáveis aleatórias
Para se realizar simulações é necessário utilizar sequências de variáveis aleatórias. Para obter tais sequências, é possível utilizar três métodos:
- Uso de sequências de observaçoes efetuadas previamente;
- Uso de sequências geradas aleatoriamente a partir de distribuições empíricas construídas a partir de observações efetuadas previamente;
- Uso de sequências geradas aleatoriamente a partir de distribuições clássicas cujos parâmetros foram estimados de acordo com observações efetuadas previamente.
A primeira alternativa torna-se inviável em uma simulação de sistemas por ser um processo demorado e que exige muita memória.
Para a segunda e terceira alternativas é necessário usar um gerador de números aleatórios, ferramenta que permite obter valores de variáveis aleatórias com a distribuição desejada.
Muitos dos geradores de números aleatórios são baseados em eventos físicos, utilizando equipamentos simples, tasi 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.
No entanto, estes números gerados computacionalmente são denominados pseudo-aleatórios, por serem gerados de 'modo determinístico a partir de uma semente, necessária para iniciar o processo de geração de números aleatórios por computador.'
Muitas vezes, a semente é um número inteiro formado por uma parte dos bits do registrador do relógio interno do computador. É possível dizer que as variáveis geradas se comportam como se fossem verdadeiramente aleatórias.
Números aleatórios
Um gerador de números aleatórios gera uma sequência de números inteiros e uma sequência de números reais a partir de uma semente inteira. Os números inteiros gerados são referente à ordem em que foram gerados.
Os números reais obtidos pelo gerador encontram-se no intervalo entre 0 e 1. "Cada gerador de números aleatórios utiliza uma função de atualização que a aprtir de um número inteiro (...) retorna outro número inteiro."
Sendo S uma sequência infinita dos números inteiros gerador, pode-se afirmar que esta sequência apresentará repetição de valores em modo cíclico. Denomina-se período a quantidade de valores em cada ciclo.
Pode-se reproduzir uma mesma sequência utilizando a mesma semente, e obtém-se sequências distintas utilizando sementes também distintas. Porém, sequências de sementes distintas podem ter o mesmo ciclo.
Um bom gerador de números aleatórios deve fornecer sequências com períodos grandes e valores uniformemente distribuídos e, ao mesmo tempo, requerir 'pouca' memória e ser facilmente reproduzido.
Apesar de os geradores de números aleatórios serem usualmente determinísticos, estatisticamente as sequências geradas são tão aleatórias quanto uma sequência verdadeiramente aleatória.
Métodos de Congruência
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. O número inteiro gerado é obtido através da equação:
<math> s_{i} = (\beta *s_{i-1}) mod \alpha </math>
em que mod é o operador de resto
O número inteiro gerado é obtido pela parte não inteira da divisão
<math> \beta *s_{i-1} / \alpha </math>
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 podeser 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 sequê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.
<math> s_{i} = (\theta* si-1² + \gamma si-1 + \beta) mod \alpha </math>
Métodos de Partição de Palavra
Ana
Os números pseudo-aleató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 pseudo-aleatórios são desejáveis:
- As seqüências de números pseudo-aleatórios não devem ser correlacionadas.
- O gerador utilizado deve ser capaz de produzir seqüências durante um longo período sem repetição.
- A seqüência gerada deve ser uniforme e imparcial.
- O gerador deve ser eficiente
Gerador Linear-Congruente
<math> x_{n+1} = (Ax_n + C) (mod\ M) </math>
O numero inteiro aleatório <math>x_{n+1}</math> é gerado a partir do número aleatório anterior, <math>x_n</math> , das constantes inteiras A e C e do módulo inteiro M. Depois que o inteiro <math>Ax_n + C</math> é gerado, o módulo aritmético é realizado a partir do módulo M para produzir o novo inteiro aleatório <math>x_{n+1}</math> . Uma característica desse tipo de gerador é que o próximo número aleatório <math>x_{n+1}</math> depende exclusivamente do inteiro antecessor, <math>x_n</math> , o que minimiza a necessidade de armazenamento, mas isso impõe algumas restições no período. Com <math>x_n</math> determinado, é possível gerar um número real correspondente da seguinte forma:
<math>R_n = \frac{x_n}{float(M)}</math> (para valores distribuídos no intervalo [0,1))
<math>R_n = \frac{x_n}{float(M-1)}</math> (para valores distribuídos no intervalo [0,1])
Para inicializar, o algoritmo requer uma semente inicial <math>x_0</math>, que deve ser fornecida através de algum meio. Para satisfazer condições de períodos para qualquer módulo M, a semente deve ser definida para um valor constante inicial, como um grande número primo (a semente deve ser ímpar, para satisfazer as condições de qualquer módulo). Uma sugestão para se obter a semente x0:
<math>x_0 = ano + 100 * (mês – 1 + 12 * (dia – 1 + 31 * (hora + 24 * (min + 60 * seg))))</math>
onde as variáveis ano, mês, dia, hora, min e seg são valores inteiros.
O método mais comum para se gerar números pseudo-aleatórios usa uma técnica recursiva chamada gerador linear-congruente, ou gerador de Lehmer. A seqüência é definida numa coleção de inteiros através da fórmula de recursão:
<math> x_{n+1} = (Ax_n + C) (mod\ M) </math>
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...
Referência:
WARNOCK, Tony. Random-Number Generators. Los Alamos Science, Los Alamos, no. 15, p. 125-130, 1987. Disponível em: < http://library.lanl.gov/cgi-bin/getfile?15-12.pdf >. Acesso em: 05 set. 2010.
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 pseudo-aleatórios.
O método de Monte Carlo usa números aleatórios para tomar decisões ao longo da simulação. Para simular as funções de distribuição de probabilidade específica de cada tipo de decisão é necessário que esses números sejam distribuídos de forma não uniforme.
Uma vez conhecido um algoritmo que desenvolva uma série de números aleatórios de forma uniforme, é possível transformá-los em não uniformes, pois a função f necessária para esta transformação é a inversa da função de distribuição não uniforme, g. Isto é, f=g-1.
Referência(s):
TAHA, Hamdy A. Operations research: an introduction . 6.ed. Upper Saddle River: Prentice Hall, c1997.
Luis
A maioria das linguagens de computador possui uma subrotina, objeto e/ou função que irá gerar números aleatórios.
Uma sequência de números aleatórios devem ser uniformes e independentes.
Ao se utilizar um método de geração de números, geram-se números pseudo-aleatórios, pois será possível replicar o conjunto de números aleatórios utilizando o mesmo método e parâmetros iniciais.
A geração de números pseudo-aleatórios pode acarretar problemas se comparado a números verdadeiramente aleatórios. Alguns problemas são:
1.Os números podem não estar distribuídos uniformemente
2.Os valores podem ser discretos, ao invés de contínuos
3.A média pode ser muito alta ou muito baixa
4.A variância pode ser muito alta ou muito baixa
5.Pode ocorrer dependência entre os números
No entando, existem técnicas para verificar se um gerador de números aleatórios é aceitável ou não.
Caracteristicas básicas de um gerador de números aleatórios:
1. A rotina de geração de números aleatórios deve ser rápida. Operações individuais são pouco custosas, mas para uma simulação que pode requerir milhares de números, o custo pode ser caro.
2.A rotina deve ser portátil para diferentes computadores e, idealmente, para diferentes linguagens de programação. Isso é necessário para garantir que o simulador produza os mesmos resultados em qualquer máquina que o execute.
3.A rotina deve ter um ciclo suficientemente grande, ou seja, deve demorar-se muito tempo para que os números começem a se repetir.
4.Os números aleatórios devem ser replicáveis. Se dadas as condições iniciais deve ser possivel gerar o mesmo conjunto de números aleatórios, completamente idependente do sistema que está sendo simulado. Ideal para comparação de sistemas e debugging.
5.Os números gerados devem estar proximos das condições ideias de uniformidade e independencia.
Inventar tecnicas que aparentam gerar numeros aleatorios é fácil, mas gerar uma sequência que pareçam independentes, distribuidos uniformemente pode ser incrivelmente díficil. Há uma vasta literatura sobre o tópico, estabelecendo caracteristicas e propriedades de vários geradores.
Técnicas para se gerar números aleatórios
1. Método de congruência linear
O método de congruência linear produz uma sequência de integrais X1,X2,...., entre zero e m-1 sempre seguindo a relação recursiva:
<math>Xi+1 = (aXi + c) mod m, i=0,1,2,....</math>
Mod fornece o resto da divisão de (aXi + c) por m.
Sendo o valor inicial Xo a semente, a é chamado de multiplicador, c o incremento e m é o modulo. Se c =/= 0 a forma é chamada de mixed congruential method (método de congruência mista) e quando c=0 a forma é chamada de multiplicative conguential method (método de conguência multiplicativa). A escolha de Xo, a, c e m afeta drasticamente as propriedades estatisticas e a duração do ciclo de geração de números aleatórios. Variações da fórmula acima são comuns na geração de números aleatórios.
A fórmula acima gera integrais randômicas ao invés de váriaveis aleatórias. Podem-se gerar variáveis aleatórias entre 0 e 1 com a fórmula:
<math>Ri = Xi/m , i=0,1,2.....</math>
Além disso devemos verificar se os números R1, R2,... possuem uma uniformidade e independência aproximadas. Além disso há várias propiedades secundárias que devem ser consideradas e essas incluem densidade máxima e máximo período.
Densidade máxima se refere que os valores de Ri, i =1,2,...., não deixarão espaçamentos grandes no intervalo [0,1].
Máximo Périodo pode ser conseguido com uma escolha apropriada para a,c,m e Xo. Isso permite conseguir densidade máxima e evita a recorrência de uma mesma sequência de números gerados (também chamado de cycling).
2. Geradores de conguência linear combinados
Com o aumento do poder computacional a complexidades dos sistemas capazes de serem simulados também aumentou. O gerador anterior pode não ser ideal para todas as aplicações necessárias. Uma das soluções encontradas foi combinar dois ou mais geradores de congruência multiplicativa de tal modo que ,quando combinados, possuam boas propriedades estatísticas e períodos muito maiores. O seguinte resultado de L'Ecuyer[1988] sugere que se Wi,1; Wi,2;...;Wi,k são quaisquer váriaveis randomicas discretas e independentes, mas apenas pelo menos uma delas também é uniformemente distribuída nos intervalos 0 a m1 - 2, então:
Wi = (soma_de_j=0_até_k_em_Wij)_mod_(m1_-_1)
é uniformemente distribuida nas integrais de 0 a m1-2.
Testes de Uniformidade e Independencia
1. Teste de Frequência Um teste básico que deve ser feito para validar um novo gerador é o teste de uniformidade. A partir deste é possível medir o nível de aceitação entre a distribuição da amostra dos números gerados e a distribuição uniforme teorizada. Dois diferentes testes podem ser realizados : O Kolmogorov-Smirnov e o teste to qui-quadrado.
1.1 Teste Kolmogorov-Smirnov Este teste compara a função contínua e uniformemente distribuída F(x)com a função empírica Sn(x) obtida das amostras de N observações. Por definição
F(x) = x ; 0 <= x <= 1
Se a amostra dos números gerados é R1,R2,...,Rn, então a função empírica Sn(x) pode ser definida por:
Sn(x) = (números de R1,R2,...,Rn que são <= x) / N
Conforme N aumenta, Sn(x) deve se tornar uma aproximação melhor de F(x), contanto que a hipótese de que a uniformidade exista seja verdadeira. O teste de Kolmogrov-Smirnov é baseado na maior diferença entre F(x) e Sn(x). Ou seja:
D = max |F(x) - Sn(x)|
Esse valor é então tabelado em função de N na tabela de Kolmogrov-Smirnov. Para testar a uniformidade de uma função, seguem-se as seguintes etapas:
Etapa 1: Arrumam-se os valores obtidos em ordem crescente, sendo que o valor R(i) denotará sempre o menor i-ésimo valor das observações:
R1 <= R2 <= .... <= Rn
Etapa 2: Computa-se:
D+ = max(1<= i <=N) {i/n - R(i)} D- = max (1 <= i <=N) {R(i) - (i-1)/N}
Etapa 3: Computar D = max(D+;D-)
Etapa 4: Localizar na tabela o valor critico de D(alpha) para o nível específico de significância alpha e o tamanho da amostra N.
Etapa 5: Se a amostra estatisca D é maior que o valor crítico D(alpha) então a hipótese de que a amostra provém de uma distribuição uniforme é rejeitada. Se D<= D(alpha) então conclui-se que não detectou-se diferenças entre a distruibuição da amostra e a distruibuição uniforme desejada.
Referência:
Banks, Jerry. Discrete-Event System Simulation . 4.ed. Upper Saddle River: Prentice Hall
