Importância da qualidade do gerador de números aleatórios no desempenho dos algoritmos de otimização

Introdução

Quando se trata de aplicar algoritmos de otimização, muitos leitores de artigos se interessam em saber qual é a importância de usar um gerador de números aleatórios de alta qualidade. A resposta a essa pergunta não é tão simples quanto pode parecer à primeira vista. Porém, é intuitivamente óbvio que a qualidade dos números aleatórios se reflete de forma significativa na capacidade de busca dos algoritmos, já que os algoritmos populacionais se baseiam principalmente na busca estocástica.

Tentemos responder a essa pergunta juntos, mas, antes de começarmos, vamos aprender sobre os diferentes tipos de geradores de números aleatórios, como afetam os resultados e onde encontrar versões confiáveis.

Os geradores de números aleatórios (GNA) são algoritmos ou dispositivos que criam uma sequência de números ou valores que aparentam ser aleatórios. É importante destacar que, nas ciências da computação e na matemática, essas sequências são geralmente chamadas de 'pseudoaleatórias', pois são geradas por algoritmos determinísticos, e não por processos verdadeiramente aleatórios.

São dois os principais tipos de geradores de números aleatórios:

1. Geradores pseudoaleatórios (PRGs). Esses geradores usam fórmulas matemáticas ou algoritmos para criar uma sequência de números que parecem aleatórios. Eles são inicializados com um valor inicial conhecido como semente e, cada vez que o gerador é chamado, ele produz o próximo número da sequência. Com a escolha certa do algoritmo e do grão, os PSGs podem ser úteis para diversas aplicações em que é necessária uma sequência pseudoaleatória.
2. Geradores de números aleatórios verdadeiros (TRNGs). Esses geradores usam processos verdadeiramente aleatórios, como ruído de decaimento radioativo ou ruído de fenômenos quânticos, para criar números aleatórios. Esses geradores são comumente usados em criptografia, loterias e outros campos em que é necessário um alto grau de aleatoriedade.

No campo da programação, são frequentemente utilizados geradores pseudoaleatórios, como os geradores integrados nas bibliotecas padrão das linguagens de programação.

A precisão dos geradores de números aleatórios integrados nas linguagens de programação depende da implementação específica e do algoritmo utilizado para a geração dos números aleatórios. A maioria das linguagens de programação modernas, como MQL5, Python, C++, C#, Java, entre outras, oferece geradores pseudoaleatórios embutidos que fornecem uma qualidade de números aleatórios suficientemente boa para a maioria das aplicações comuns.

Em geral, os geradores de números aleatórios embutidos nas linguagens de programação são adequados para a maioria das tarefas comuns. No entanto, para aplicações que exigem um alto nível de aleatoriedade ou segurança, é aconselhável considerar soluções especializadas.

Para tarefas que exigem um alto nível de aleatoriedade e segurança, podem ser utilizadas soluções especializadas para a geração de números aleatórios. Algumas dessas soluções incluem:

1. Geradores criptográficos de números aleatórios. Esses geradores são projetados para uso em aplicações criptográficas, onde é necessário um alto nível de segurança. Eles garantem aleatoriedade, resistência à previsão e robustez contra criptoanálise.
2. Geradores de números aleatórios baseados em hardware. Esses geradores utilizam processos físicos, como ruído térmico ou fenômenos quânticos, para criar números aleatórios. Eles produzem números verdadeiramente aleatórios e são amplamente utilizados em áreas que exigem um alto grau de aleatoriedade.
3. Bibliotecas para geração de números aleatórios. Existem bibliotecas especializadas que oferecem algoritmos mais avançados para a geração de números aleatórios do que os geradores padrão embutidos nas linguagens de programação. Por exemplo, a biblioteca OpenSSL fornece funções criptográficas, incluindo a geração de números aleatórios.

Alguns dos algoritmos comuns que podem ser utilizados nos geradores de números aleatórios embutidos nas linguagens de programação são:

1. Método congruente linear (Linear Congruential Generator, LCG). Este é um dos algoritmos mais simples e amplamente utilizados para a geração de números pseudoaleatórios. No entanto, apresenta desvantagens, como período curto e baixa qualidade de aleatoriedade.
2. Mersenne Twister. Este algoritmo possui um longo período e boa qualidade de aleatoriedade, sendo frequentemente utilizado em muitas linguagens de programação.
3. Xorshift. Esta é uma família de algoritmos para geração de números pseudoaleatórios que oferece boa qualidade de aleatoriedade e alta velocidade de execução.
4. PCG (Permuted Congruential Generator). Esta classe relativamente nova de geradores apresenta um bom equilíbrio entre a qualidade da aleatoriedade e o desempenho.

A escolha do gerador de números aleatórios depende dos requisitos específicos das suas tarefas. Aqui estão algumas considerações que podem ajudar na tomada de decisão:

1. Qualidade da aleatoriedade. Se a sua aplicação exige um alto nível de aleatoriedade, especialmente para fins criptográficos, é melhor utilizar geradores de números aleatórios criptograficamente seguros, como os Cryptographically Secure Pseudo-Random Number Generators (CSPRNGs).
2. Desempenho. Se a velocidade de geração de números aleatórios é importante para você, algoritmos com desempenho superior, como Xorshift ou PCG, podem ser preferíveis.
3. Período e qualidade. Alguns algoritmos, como o Mersenne Twister, possuem um longo período e uma boa qualidade de aleatoriedade.
4. Facilidade de uso. Para alguns desenvolvedores, é importante que o gerador de números aleatórios seja facilmente acessível e simples de usar. Geradores embutidos, como os fornecidos pelas bibliotecas padrão das linguagens de programação, podem ser convenientes nesses casos.

Se você precisa de um nível criptográfico de segurança, recomenda-se utilizar geradores de números aleatórios criptográficos especializados, como o CryptoRandom em Python ou o SecureRandom em Java. Se você busca um equilíbrio entre desempenho e qualidade da aleatoriedade, algoritmos como o Mersenne Twister ou PCG podem ser boas opções.

É também importante lembrar que segurança e aleatoriedade desempenham um papel decisivo para garantir a confiabilidade e segurança do sistema. Por isso, a escolha do gerador deve ser cuidadosa e atender aos requisitos específicos da tarefa. No entanto, neste artigo, estamos interessados em saber como a qualidade dos geradores de números aleatórios afeta os resultados dos algoritmos de otimização, e focaremos nossa pesquisa exclusivamente neste contexto.

Mersenne Twister

Entre os muitos geradores de números aleatórios disponíveis, não é fácil encontrar um que ofereça alta qualidade, mantendo uma velocidade de geração aceitável. Afinal, a velocidade tem um impacto significativo no tempo total de execução do processo de otimização.

Dessa forma, a escolha de um gerador confiável é uma questão importante, que exige um equilíbrio entre a qualidade dos números aleatórios e a velocidade de geração. É necessário encontrar uma boa solução que ofereça qualidade suficiente na geração, sem consumir tempo excessivo neste processo.

Como os geradores baseados em hardware são de difícil acesso para a maioria dos usuários, vamos excluí-los imediatamente como candidatos para análise neste artigo. Entre os geradores de software, um gerador de qualidade amplamente reconhecido é o Mersenne Twister.

O Mersenne Twister (Mersenne Twister) é um algoritmo de geração de números pseudoaleatórios, desenvolvido por Makoto Matsumoto e Takuji Nishimura em 1997. Ele é um dos algoritmos de geração de números aleatórios mais amplamente utilizados, graças à sua boa combinação de período longo, qualidade elevada de aleatoriedade e desempenho relativamente alto.

Principais características do Mersenne Twister:

• Período longo. O Mersenne Twister possui um período muito longo, o que significa que ele pode gerar uma enorme quantidade de números pseudoaleatórios únicos antes que a sequência comece a se repetir.
• Boa qualidade de aleatoriedade. O algoritmo oferece uma boa qualidade de aleatoriedade, o que significa que os números gerados devem atender às propriedades estatísticas dos números aleatórios.
• Desempenho. O Mersenne Twister tem um bom desempenho, tornando-o uma escolha atraente para muitas tarefas.

O princípio de funcionamento do Mersenne Twister é baseado em um método recursivo linear de geração de números pseudoaleatórios. O algoritmo usa um número grande (geralmente de 32 bits ou 64 bits) como o estado do gerador, que é então transformado por meio de operações complexas para obter o próximo número pseudoaleatório. No nosso caso, usaremos o gerador de 64 bits.

Vamos analisar a classe "MersenneTwister64", que implementa um gerador de números pseudoaleatórios baseado no algoritmo Mersenne Twister para números de 64 bits. A seguir, uma breve descrição de seus métodos e funcionalidades:

• Init - Método de inicialização do gerador de números aleatórios. Aceita como argumento a semente (seed) e configura as variáveis internas da classe. Preenche o array MT (array Mersenne) com valores, com base na semente.
• RND_ulong - Método que retorna um número inteiro sem sinal de 64 bits aleatório. Se o índice atual (index) exceder 312, o método twist() é chamado para atualizar os valores no array MT. Em seguida, são realizadas várias operações de deslocamento de bits e XOR bit a bit para obter o número aleatório. O valor do índice é incrementado em 1 antes de retornar o resultado.
• RND_ulong_In_Range - Método que retorna um número inteiro sem sinal de 64 bits aleatório dentro de um intervalo especificado (incluindo os limites). Se min e max forem iguais, min é retornado. Se min for maior que max, os valores de min e max são trocados. Em seguida, o método RND_ulong() é chamado para gerar um número aleatório, que é então deslocado e escalado para se enquadrar no intervalo especificado.
• twist - Método interno que realiza a operação de "embaralhamento" do array MT. Para cada elemento do array, ocorre a combinação dos elementos vizinhos usando operações de deslocamento de bits e XOR bit a bit. O valor do índice é definido como 0 após a execução da operação de "embaralhamento".

//——————————————————————————————————————————————————————————————————————————————
class MersenneTwister64
{
public: //--------------------------------------------------------------------

  void Init (ulong seed)
  {
    index = 312;

    MT [0] = seed;
    for (int i = 1; i < 312; i++)
    {
      MT [i] = (6364136223846793005 * (MT [i - 1] ^ (MT [i - 1] >> 62)) + i) & 0xFFFFFFFFFFFFFFFF;
    }
  }

  //from 0 to 18 446 744 073 709 551 615
  ulong RND_ulong ()
  {
    if (index >= 312)
    {
      twist ();
    }

    ulong y = MT [index];
    y = y ^ (y >> 29) & 0x5555555555555555;
    y = y ^ (y << 17) & 0x71D67FFFEDA60000;
    y = y ^ (y << 37) & 0xFFF7EEE000000000;
    y = y ^ (y >> 43);

    index++;
    return y;
  }

  ulong RND_ulong_In_Range (ulong min, ulong max)
  {
    if (min == max) return min;
    if (min > max)
    {
      ulong temp = min;
      min = max;
      max = temp;
    }
    return min + RND_ulong () % (max - min + 1);
  }

private: //-------------------------------------------------------------------
  ulong MT [312];
  int index;

  void twist ()
  {
    for (int i = 0; i < 312; i++)
    {
      ulong y = (MT [i] & 0x8000000000000000) + (MT [(i + 1) % 312] & 0x7FFFFFFFFFFFFFFF);
      MT [i] = MT [(i + 156) % 312] ^ (y >> 1);
      if (y % 2 != 0)
      {
        MT [i] = MT [i] ^ 0xB5026F5AA96619E9;
      }
    }
    index = 0;
  }
};
//——————————————————————————————————————————————————————————————————————————————

Comparação de geradores de números aleatórios e resultados dos testes

Vamos tentar comparar visualmente o funcionamento de dois geradores de números aleatórios: o embutido no MQL5 (a que nos referiremos como "padrão") e o Mersenne Twister. Para isso, geramos duas imagens e analisamos sua aparência. À primeira vista, ambas as imagens parecem desprovidas de padrões e periodicidades, e seu desenho é homogêneo. Visualmente, não observamos diferenças claras entre os geradores.

Imagem gerada pelo gerador padrão.

Imagem gerada pelo gerador Mersenne Twister.

No entanto, para uma comparação mais objetiva dos geradores de números aleatórios, recomenda-se o uso de testes estatísticos, que permitem avaliar o grau de aleatoriedade e as propriedades estatísticas dos números gerados. É importante notar que a avaliação visual pode ser limitada e nem sempre consegue detectar desvios sistemáticos ocultos da verdadeira aleatoriedade.

Assim, para uma comparação mais precisa dos geradores, realizaremos uma análise adicional usando um teste estatístico para obter resultados mais confiáveis. Nosso interesse é na uniformidade, por isso usaremos o teste qui-quadrado, que é um teste estatístico que permite avaliar o quão uniformes são os números gerados aleatoriamente. Neste caso, foram realizados 10.000 observações, cada uma contendo 10.000 valores gerados.

O teste qui-quadrado (χ²-test) é usado para verificar a uniformidade da distribuição dos dados. Ele permite determinar o quão bem as frequências observadas correspondem às esperadas em uma distribuição uniforme.

O valor crítico para o nível de significância de 0,05 no teste qui-quadrado (χ²-test) com 9.999 graus de liberdade (10.000 observações menos 1) é 10.232,73727. Esse valor é uma constante que é usada para comparar as frequências observadas com as esperadas no teste qui-quadrado. Ele é retirado da tabela de distribuição qui-quadrado e ajuda a determinar a significância das diferenças entre os valores observados e esperados.

Quando realizamos o teste qui-quadrado, comparamos a estatística calculada com o valor crítico. Se a estatística calculada for maior que o valor crítico, podemos rejeitar a hipótese nula, que afirma que a distribuição é consistente com a esperada. Caso contrário, a hipótese nula é aceita.

Vamos analisar um trecho do código do script de teste (em geral, o script constrói imagens, mede o tempo de execução dos geradores e calcula o teste qui-quadrado).

São criados e inicializados dois arrays: "observed" e "expected". O array "observed" será usado para armazenar a contagem observada da ocorrência de números aleatórios em cada um dos intervalos de "BoxesNumber". O array "expected" conterá a contagem esperada de ocorrências de números aleatórios em cada intervalo, caso os geradores funcionassem com uma distribuição uniforme ideal.

Em seguida, o código verifica o valor da variável "StandardRND", que indica qual gerador de números aleatórios usar. Se "StandardRND" for igual a true, então o gerador de números aleatórios padrão do MQL5 é utilizado. Caso contrário, é utilizado o gerador Mersenne Twister. Dentro do loop, números aleatórios são gerados e o elemento correspondente do array "observed" é incrementado para o intervalo respectivo.

Após a geração dos números aleatórios, é realizado o cálculo da estatística qui-quadrado. Para cada intervalo, calcula-se o valor de "(observado - esperado)^2 / esperado", que é somado na variável "chiSquareStatistic". Em seguida, é definido o valor crítico "chiSquareCriticalValue" para o nível de significância de 0,05*.

Ao final do código, são exibidos os resultados da comparação. Se o valor de "chiSquareStatistic" for maior que "chiSquareCriticalValue", é exibida uma mensagem indicando que rejeitamos a hipótese nula: a distribuição difere da esperada. Caso contrário, é exibida uma mensagem indicando que não rejeitamos a hipótese nula: a distribuição é consistente com a esperada.

* - O nível de significância de 0,05 (ou 5%) é um dos níveis de significância mais comumente utilizados e é amplamente aplicado em diversas áreas de pesquisa científica. Isso significa que, ao realizar um teste estatístico com um nível de significância de 0,05, admitimos uma probabilidade de 5% de cometer um erro do tipo I. O nível de significância (significance level) em estatística é um valor limiar utilizado para tomar decisões sobre a significância estatística dos resultados. Ele é geralmente denotado por α (alfa) e representa a probabilidade de cometer um erro do tipo I, ou seja, a probabilidade de rejeitar uma hipótese nula verdadeira.

int observed [];
ArrayResize     (observed, BoxesNumber);
ArrayInitialize (observed, 0);

int expected [];
ArrayResize     (expected, BoxesNumber);
ArrayInitialize (expected, ThrowsNumber / BoxesNumber);

if (StandardRND)
{
  Print ("Standard, ", ThrowsNumber, " throws, ", BoxesNumber, " boxes");
  for (int i = 0; i < ThrowsNumber; i++)
  {
    observed [rndS.RNDintInRange (0, BoxesNumber - 1)]++;
  }
}
else
{
  Print ("Mersenne, ", ThrowsNumber, " throws, ", BoxesNumber, " boxes");
  for (int i = 0; i < ThrowsNumber; i++)
  {
    observed [(int)rndM.RND_ulong_In_Range (0, BoxesNumber  - 1)]++;
  }
}

// Calculate the chi-square statistic
double chiSquareStatistic = 0;
for (int i = 0; i < ArraySize(observed); i++)
{
  chiSquareStatistic += MathPow(observed[i] - expected[i], 2) / expected[i];
}

// Critical value for the significance level of 0.05
double chiSquareCriticalValue = 10232.73727; //10000

// Output results
if (chiSquareStatistic > chiSquareCriticalValue)
{
  Print("We reject the null hypothesis: The distribution differs from the expected one.");
}
else
{
  Print("We do not reject the null hypothesis: The distribution is consistent with the expected one.");
}

Executaremos o script 5 vezes para calcular a estatística e o tempo de execução do gerador padrão. Ao mesmo tempo, também será medido o tempo de execução do gerador Mersenne Twister. Calculamos a diferença no tempo de execução como a razão entre o tempo de execução do Mersenne Twister e o tempo de execução do gerador padrão.

2024.03.18 20:54:33.456    stand: 120353 mcs
2024.03.18 20:54:33.456    mers : 397920 mcs
2024.03.18 20:54:33.456    diff : 3.3062740438543283
2024.03.18 20:54:33.459    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:33.854    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:38.802    stand: 121670 mcs
2024.03.18 20:54:38.802    mers : 403180 mcs
2024.03.18 20:54:38.802    diff : 3.3137174323991125
2024.03.18 20:54:38.805    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:39.194    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:43.767    stand: 121222 mcs
2024.03.18 20:54:43.767    mers : 400986 mcs
2024.03.18 20:54:43.767    diff : 3.3078649090099157
2024.03.18 20:54:43.770    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:44.156    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:48.476    stand: 119246 mcs
2024.03.18 20:54:48.476    mers : 400319 mcs
2024.03.18 20:54:48.476    diff : 3.3570853529678146
2024.03.18 20:54:48.479    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:48.873    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:53.144    stand: 119309 mcs
2024.03.18 20:54:53.144    mers : 404502 mcs
2024.03.18 20:54:53.144    diff : 3.390372897266761
2024.03.18 20:54:53.148    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:53.553    We reject the null hypothesis: The distribution differs from the expected one.

Infelizmente, o gerador de números aleatórios padrão não passou em nenhum dos cinco testes quando verificado com o teste qui-quadrado, o que indica a presença de desvios sistemáticos em relação à distribuição uniforme aleatória esperada.

Agora, vamos realizar o teste com o Mersenne Twister, continuando a medir o tempo de execução de ambos os geradores.

2024.03.18 20:55:48.133    stand: 115447 mcs
2024.03.18 20:55:48.133    mers : 413258 mcs
2024.03.18 20:55:48.133    diff : 3.57963394458063
2024.03.18 20:55:48.138    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:55:49.504    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:55:56.340    stand: 117433 mcs
2024.03.18 20:55:56.340    mers : 402337 mcs
2024.03.18 20:55:56.340    diff : 3.4260982858310696
2024.03.18 20:55:56.346    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:55:57.717    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:56:05.837    stand: 120129 mcs
2024.03.18 20:56:05.837    mers : 400705 mcs
2024.03.18 20:56:05.837    diff : 3.3356225391037966
2024.03.18 20:56:05.843    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:56:07.219    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:56:12.206    stand: 119980 mcs
2024.03.18 20:56:12.206    mers : 397436 mcs
2024.03.18 20:56:12.206    diff : 3.312518753125521
2024.03.18 20:56:12.211    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:56:13.582    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:56:18.837    stand: 118140 mcs
2024.03.18 20:56:18.837    mers : 397565 mcs
2024.03.18 20:56:18.837    diff : 3.3652023023531403
2024.03.18 20:56:18.842    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:56:20.220    We do not reject the null hypothesis: The distribution is consistent with the expected one.

O Mersenne Twister conseguiu passar em todos os cinco testes (execuções do teste qui-quadrado). No entanto, observamos que esse gerador possui uma desvantagem significativa: ele é aproximadamente 3,4 vezes mais lento que o gerador padrão, o que pode impactar de forma notável a velocidade dos algoritmos de otimização.

Agora chegou o momento mais interessante, o ponto culminante desta análise: vamos realizar testes para determinar o quanto a qualidade dos geradores de números aleatórios afeta os resultados da otimização. Lembro que o gerador padrão cria números no intervalo [0;32767], enquanto o Mersenne Twister de 64 bits gera números no intervalo [0;18446744073709551615].

Para conduzir o experimento, selecionamos 50 funções Hilly e realizamos 10.000 iterações para cada função. Por que escolhemos exatamente 50 funções Hilly e por que Hilly? Primeiro, essa quantidade foi escolhida de modo que o algoritmo não conseguisse atingir 100% de convergência no número limitado de execuções da função fitness. Isso permitiu observar a diferença na aplicação de diferentes tipos de geradores de números aleatórios. Segundo, a escolha das funções Hilly deve-se à sua suavidade, evitando a dispersão sistemática dos resultados, que não estaria relacionada à geração de números aleatórios, caso tivéssemos aplicado uma função de teste discreta. Repetimos o experimento 20 vezes e calculamos a média dos resultados para obter dados mais confiáveis e estatisticamente significativos. Como algoritmo de otimização, escolhemos o BGA, que ocupa o primeiro lugar na nossa tabela de classificação e apresenta uma variação muito pequena dos resultados em funções suaves.

A partir da análise dos resultados impressos, nota-se que os resultados da otimização, tanto com o gerador de números aleatórios padrão quanto com o Mersenne Twister, são praticamente idênticos para o algoritmo BGA. As diferenças observadas estão apenas na terceira casa decimal, o que não é crítico para nossos objetivos e é considerado suficientemente pequeno.

//Standard
C_AO_BGA:50:50:1.0:3:0.001:0.7:16
=============================
50 Hilly's; Func runs: 10000; result: 0.9257245560389498
=============================
All score: 0.92572

//Mersenne
C_AO_BGA:50:50:1.0:3:0.001:0.7:16
=============================
50 Hilly's; Func runs: 10000; result: 0.9221148477644971
=============================
All score: 0.92211

Ao visualizar o funcionamento do algoritmo, não encontramos desvios significativos ao usar os dois diferentes tipos de geradores de números aleatórios na lógica do algoritmo, e a diferença na dispersão dos resultados se encaixa perfeitamente na variabilidade natural do próprio algoritmo.

Execução do BGA com o gerador padrão. 

Execução do BGA com o Mersenne Twister.

A conclusão preliminar é a seguinte: a qualidade dos geradores de números aleatórios não afeta o desempenho dos algoritmos de otimização.

Vamos considerar a hipótese de que a pequena diferença nos resultados ao aplicar os geradores mencionados no algoritmo de otimização BGA pode estar relacionada ao fato de que, no BGA, cada bit em um cromossomo é gerado independentemente dos demais bits. Essencialmente, o papel dos geradores de números aleatórios é reduzido a uma operação booleana, "sim/não", e a diferença entre a ocorrência de "sim" e "não", embora existente, representa apenas milésimos de porcento.

É certo que, para o algoritmo genético binário, não há diferença significativa no uso dos geradores de números aleatórios, embora essa conclusão não fosse óbvia à primeira vista. Mas será que isso se aplica a outros algoritmos de otimização, especialmente aqueles que utilizam probabilidades contínuas em todo o espaço delimitado pelas coordenadas [min, max]?

Vamos, então, realizar mais alguns experimentos para confirmar ou refutar essa afirmação. Desta vez, utilizaremos o algoritmo (P_O)ES, que está entre os líderes em nossa tabela de classificação e faz uso intensivo de operações com números aleatórios e probabilidades contínuas em todo o espaço de busca.

Execução do (P_O)ES em 5 testes com o gerador padrão de números aleatórios:

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9611258962207798
=============================
All score: 0.96113

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9515388684155862
=============================
All score: 0.95154

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9374143219597522
=============================
All score: 0.93741

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9408961932771648
=============================
All score: 0.94090

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9533447716768805
=============================
All score: 0.95334

Execução do (P_O)ES em 5 testes com o gerador Mersenne Twister:

C_AO_(P_O)ES:100:150:0.02:8.0:10

=============================
50 Hilly's; Func runs: 10000; result: 0.9726583883537465
=============================
All score: 0.97266

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9699307111435692
=============================
All score: 0.96993

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9864631937799934
=============================
All score: 0.98646

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9608040257741147
=============================
All score: 0.96080

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9540192199550924
=============================
All score: 0.95402

Como podemos observar na impressão dos experimentos realizados, a primeira série de testes refere-se ao uso do gerador de números aleatórios padrão no algoritmo. Vemos que o valor médio do resultado está na faixa de 0,95, enquanto o valor médio do resultado com o uso do Mersenne Twister é de 0,96, o que não apresenta uma diferença substancial. No entanto, isso nos mostra que, ainda assim, os resultados dos experimentos são ligeiramente melhores com o Mersenne Twister, mas é importante lembrar que o tempo gasto ao usar esse algoritmo é 3,5 vezes maior do que o tempo de execução com o gerador padrão.

Considerações finais

Realizamos um experimento interessante para esclarecer uma questão que preocupa muitos: a qualidade dos geradores de números aleatórios é importante quando aplicada em conjunto com algoritmos de otimização. Não encontrei pesquisas semelhantes disponíveis publicamente.

Para alguns algoritmos que utilizam operações booleanas, como o BGA, e algoritmos que utilizam números aleatórios em um pequeno intervalo discreto, como o DE (evolução diferencial, onde os números aleatórios são usados para selecionar indivíduos parentais na população), a qualidade do gerador de números aleatórios praticamente não desempenha nenhum papel.

Para outros algoritmos que utilizam números aleatórios para gerar novas soluções em todo o intervalo dos parâmetros a serem otimizados, como o (P_O)ES (ao qual pertencem a maioria dos algoritmos populacionais), a qualidade do gerador de números aleatórios desempenha um papel, mas é muito insignificante e se enquadra na margem de erro das medições. É importante notar que o gerador Mersenne Twister, embora mais qualificado, é 3,5 vezes mais lento que o gerador padrão.

Nas tarefas de otimização, o equilíbrio entre qualidade e tempo de computação desempenha, sem dúvida, um papel crucial no resultado. Neste caso, escolhemos a velocidade. O aumento nos resultados dos algoritmos ao usar geradores de alta qualidade está dentro da margem de erro das medições, enquanto a velocidade de execução cai significativamente.

Um arquivo com os códigos dos testes realizados está anexado ao artigo. As conclusões e julgamentos apresentados no artigo se baseiam nos resultados dos experimentos realizados.