El papel de la calidad del generador de números aleatorios en la eficiencia de los algoritmos de optimización

Introducción

A la hora de utilizar algoritmos de optimización, muchos lectores se preguntan hasta qué punto es importante utilizar un generador de números aleatorios de alta calidad. La respuesta a esta pregunta no es tan sencilla como podría parecer a primera vista. Sin embargo, es intuitivo que la calidad de los números aleatorios puede tener un impacto significativo en las capacidades de búsqueda de los algoritmos, ya que los algoritmos de población se basan abrumadoramente en la búsqueda estocástica.

Analicemos juntos este asunto. Antes de empezar, debemos considerar los distintos tipos de generadores de números aleatorios, su impacto en los resultados y dónde encontrar opciones fiables.

Los generadores de números aleatorios (RNG) son algoritmos o dispositivos que crean una secuencia de números o valores y los números parecen aleatorios. Es importante señalar que en informática y matemáticas este tipo de secuencias suelen denominarse «pseudoaleatorias» porque se generan mediante algoritmos deterministas y no mediante procesos verdaderamente aleatorios.

Existen dos tipos principales de generadores de números aleatorios:

1. Generadores pseudoaleatorios (PRGs). Estos generadores utilizan ecuaciones matemáticas o algoritmos para crear una secuencia de números que parecen aleatorios. Se inicializan con un valor inicial conocido como «semilla», y cada vez que se llama al generador, éste produce el siguiente número de la secuencia. Con la elección correcta de un algoritmo y una semilla, PRG puede ser útil para muchas aplicaciones en las que se requiere una secuencia pseudoaleatoria.
2. Generadores de números aleatorios reales (TRNG). Estos generadores utilizan procesos verdaderamente aleatorios, como el ruido de desintegración radiactiva o el ruido cuántico, para generar números aleatorios. Estos generadores se utilizan habitualmente en criptografía, loterías y otros ámbitos en los que se requiere un alto grado de aleatoriedad.

Los generadores de números pseudoaleatorios se utilizan a menudo en programación, como los integrados en librerías de lenguajes de programación estándar.

La precisión de los generadores de números aleatorios integrados en los lenguajes de programación depende de la implementación específica y del algoritmo que se utilice para generar los números aleatorios. La mayoría de los lenguajes de programación modernos, como MQL5, Python, C++, C#, Java y otros, proporcionan generadores de números pseudoaleatorios incorporados que proporcionan números aleatorios de bastante buena calidad para las aplicaciones más comunes.

En general, los generadores de números aleatorios incorporados en los lenguajes de programación suelen ser adecuados para las tareas más comunes, pero para las tareas que requieren un alto nivel de aleatoriedad o seguridad, merece la pena buscar soluciones especializadas.

Para tareas que requieren un alto nivel de aleatoriedad y seguridad, se pueden utilizar soluciones especializadas para generar números aleatorios. Algunas de estas soluciones son:

1. Generadores criptográficos de números aleatorios. Estos generadores están pensados para su uso en aplicaciones criptográficas en las que se requiere un alto nivel de seguridad. Proporcionan aleatoriedad, resistencia a la predicción y resistencia al criptoanálisis.
2. Generadores de números aleatorios por hardware. Estos generadores utilizan procesos físicos, como ruido térmico o fenómenos cuánticos, para crear números aleatorios. Proporcionan números verdaderamente aleatorios y se utilizan ampliamente en ámbitos en los que se requiere un alto grado de aleatoriedad.
3. Librerías para generar números aleatorios. Existen librerías especializadas que proporcionan algoritmos más complejos para generar números aleatorios que los generadores estándar incorporados en los lenguajes de programación. Por ejemplo, la librería OpenSSL proporciona funciones criptográficas, incluida la generación de números aleatorios.

Algunos de los algoritmos más comunes que pueden utilizarse en los generadores de números aleatorios incorporados en los lenguajes de programación son:

1. Generador Congruencial Lineal (LCG). Se trata de uno de los algoritmos más sencillos y utilizados para generar números pseudoaleatorios. Tiene desventajas, como un periodo corto y un bajo grado de aleatoriedad.
2. Mersenne Twister. Este algoritmo tiene un periodo largo y un buen grado de aleatoriedad, y se utiliza a menudo en muchos lenguajes de programación.
3. Xorshift. Se trata de una familia de algoritmos de generación de números pseudoaleatorios que tienen un buen grado de aleatoriedad y alta velocidad.
4. Generador Congruencial Permutado (PCG). Esta clase relativamente nueva de generadores tiene un buen equilibrio entre calidad de aleatoriedad y rendimiento.

La elección de un generador de números aleatorios depende de los requisitos específicos de sus tareas. A continuación se exponen algunas consideraciones que pueden ayudarle a tomar una decisión:

1. Calidad de la aleatoriedad. Si su aplicación requiere un alto nivel de aleatoriedad, especialmente con fines criptográficos, entonces es mejor utilizar generadores de números aleatorios criptográficos especializados, como los generadores de números pseudoaleatorios criptográficamente seguros (CSPRNG).
2. Rendimiento. Si la velocidad de generación de números aleatorios es importante para usted, entonces pueden ser preferibles algoritmos de mayor rendimiento como Xorshift o PCG.
3. Periodo y calidad. Algunos algoritmos, como Mersenne Twister, tienen un periodo largo y una buena calidad de aleatoriedad.
4. Facilidad de uso. Para algunos desarrolladores, es importante que el generador de números aleatorios sea fácilmente accesible y fácil de usar. Los generadores incorporados, como los que ofrecen las bibliotecas de lenguajes de programación estándar, pueden resultar prácticos en estos casos.

Si necesita un nivel de seguridad criptográfico, se recomienda utilizar generadores de números aleatorios criptográficos especializados, como CryptoRandom en Python o SecureRandom en Java. Si quieres un equilibrio entre rendimiento y calidad de aleatoriedad, entonces algoritmos como Mersenne Twister o PCG pueden ser buenas opciones.

También es importante recordar que la seguridad y la aleatoriedad desempeñan un papel clave en la fiabilidad y seguridad del sistema, por lo que la elección del generador debe ser meditada y adecuada a los requisitos de la aplicación específica. Pero en este artículo nos interesa la influencia de la calidad del RNG en los resultados de los algoritmos de optimización. Llevaré a cabo mi investigación exclusivamente en este contexto.

Mersenne Twister

Entre los muchos generadores de números aleatorios disponibles, no es fácil encontrar uno que proporcione una generación de alta calidad manteniendo una velocidad aceptable. Después de todo, la velocidad de generación tiene un impacto significativo en el tiempo total de ejecución del proceso de optimización.

Por lo tanto, elegir un generador fiable es una cuestión importante que requiere un equilibrio entre la calidad de los números aleatorios y su velocidad de generación. Es necesario encontrar una solución óptima que garantice una calidad de generación suficiente sin dedicar tiempo innecesario a este proceso.

Los generadores de hardware son de difícil acceso para la mayoría de los usuarios, por lo que aquí los descartamos de inmediato. Entre los generadores de software, el generador Mersenne de alta calidad es ampliamente conocido.

Mersenne Twister es un algoritmo de generación de números pseudoaleatorios desarrollado por Makoto Matsumoto y Takuji Nishimura en 1997. Es uno de los algoritmos de generación de números aleatorios más utilizados debido a su buena combinación de periodo largo, buena calidad de aleatoriedad y rendimiento relativamente alto.

Principales características del Twister Mersenne:

• Periodo largo. El Mersenne Twister tiene un periodo muy largo, lo que significa que puede generar una gran cantidad de números pseudoaleatorios únicos antes de que la secuencia comience a repetirse.
• Buena calidad de aleatoriedad. El algoritmo garantiza una buena calidad de la aleatoriedad, lo que significa que los números generados deben ajustarse a las propiedades estadísticas de los números aleatorios.
• Rendimiento. El Mersenne Twister tiene un buen rendimiento, lo que lo convierte en una opción atractiva para muchas aplicaciones.

El principio de funcionamiento del Mersenne Twister se basa en un método lineal recurrente de generación de números pseudoaleatorios. El algoritmo utiliza un número grande (normalmente de 32 o 64 bits) como estado del generador, que luego se transforma mediante operaciones complejas para producir el siguiente número pseudoaleatorio. En nuestro caso, utilizaremos un generador de 64 bits.

Consideremos la clase MersenneTwister64, que implementa un generador de números pseudoaleatorios basado en el algoritmo Mersenne Twister para números de 64 bits. A continuación se describen brevemente sus métodos y funciones:

• Init - método de inicialización del generador de números aleatorios. Toma una semilla (valor inicial) como argumento y establece las variables internas de la clase. La matriz MT (matriz Mersenne) se rellena con valores basados en la semilla.
• RND_ulong - método que devuelve un número entero sin signo de 64 bits aleatorio. Si el índice actual es mayor que 312, se llama al método twist() para actualizar los valores del array MT. Después, se realizan varias operaciones de desplazamiento de bits (bit-shift) y XOR de bits para producir un número aleatorio. El valor del índice se incrementa en 1 antes de devolver el resultado.
• RND_ulong_In_Range - método que devuelve un número entero sin signo de 64 bits aleatorio dentro de un rango dado (incluyendo los límites). Si min y max son iguales, se devuelve min. Si min es mayor que max, se intercambian los valores de min y max. A continuación, se llama al método RND_ulong() para generar un número aleatorio desplazado y escalado para que caiga dentro del rango especificado.
• twist - método interno que realiza la operación de «mezcla» de la matriz MT. Para cada elemento de la matriz, se produce una combinación de elementos vecinos mediante operaciones de desplazamiento y XOR a nivel de bit. El valor del índice se establece en 0 después de realizar la operación de mezcla.

//——————————————————————————————————————————————————————————————————————————————
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;
  }
};
//——————————————————————————————————————————————————————————————————————————————

Comparación de generadores de números aleatorios y resultados de las pruebas

Intentemos comparar visualmente el trabajo de dos generadores de números aleatorios: el incorporado en MQL5 (en adelante llamado «estándar») y el Mersenne Twister. Para ello, generamos dos imágenes y analizamos su aspecto. A primera vista, ambas imágenes carecen de patrones y periodicidad, y su diseño es homogéneo. No observamos diferencias visuales evidentes entre los generadores.

La imagen generada por el generador estándar

La imagen generada por el generador Mersenne Twister

Sin embargo, para una comparación más objetiva de los generadores de números aleatorios, se recomienda utilizar pruebas estadísticas que nos permitan evaluar el grado de aleatoriedad y las propiedades estadísticas de los números generados. Es importante señalar que la evaluación visual puede ser limitada y no siempre capaz de detectar desviaciones sistemáticas ocultas de la verdadera aleatoriedad.

Así pues, para una comparación más precisa de los generadores, realizaremos un análisis adicional utilizando una prueba estadística para obtener resultados más fiables. Nos interesa la uniformidad, por lo que utilizaremos la prueba chi-cuadrado, que es una prueba estadística que evalúa el grado de uniformidad de los números generados aleatoriamente. En este caso, había 10.000 observaciones, cada una de las cuales contenía 10.000 valores generados.

La prueba chi-cuadrado (χ²) se utiliza para comprobar la uniformidad de la distribución de los datos. Permite determinar en qué medida las frecuencias observadas se corresponden con las esperadas en una distribución uniforme.

El valor crítico para el nivel de significación de 0.05 en la prueba chi-cuadrado (χ²) con 9999 grados de libertad (10.000 observaciones menos 1) es 10232,73727. Este valor es una constante que se utiliza para comparar las frecuencias esperadas con las observadas en la prueba chi-cuadrado. Se extrae de la tabla chi-cuadrado de la distribución y ayuda a determinar lo significativas que son las diferencias entre los valores observados y los esperados.

Cuando realizamos la prueba chi-cuadrado, comparamos la estadística calculada con el valor crítico. Si el estadístico calculado es mayor que el valor crítico, podemos rechazar la hipótesis nula de que la distribución coincide con la esperada. En caso contrario, se acepta la hipótesis nula.

Veamos una sección del código del script de prueba (en general, el script construye imágenes, mide el tiempo de ejecución de los generadores y calcula la prueba chi-cuadrado).

Se crean e inicializan dos matrices: "observado" y “esperado”. La matriz «observado» se utilizará para almacenar el número observado de números aleatorios en cada uno de los intervalos BoxesNumber. La matriz «esperada» contendrá el número esperado de números aleatorios en cada casilla si los generadores funcionaran con una distribución uniforme perfecta.

A continuación, el código comprueba el valor de la variable StandardRND, que especifica qué generador de números aleatorios utilizar. Si StandardRND es 'true', entonces se utiliza el generador de números aleatorios estándar en MQL5. De lo contrario, se utiliza el generador Mersenne Twister. El bucle genera números aleatorios e incrementa el elemento correspondiente de la matriz «observado» para el intervalo.

Una vez generados los números aleatorios, se calcula el estadístico chi-cuadrado. Para cada intervalo, se calcula el valor «(observado - esperado)^2 / esperado» y se suma en la variable «chiSquareStatistic». A continuación, se establece el valor crítico «chiSquareCriticalValue» para el nivel de significación de 0.05*.

Los resultados de la comparación se muestran al final del código. Si el valor de «chiSquareStatistic» es mayor que «chiSquareCriticalValue», aparece un mensaje que indica que rechazamos la hipótesis nula: la distribución difiere de la esperada. En caso contrario, se muestra un mensaje que indica que no rechazamos la hipótesis nula: la distribución coincide con la esperada.

* - El nivel de significación de 0,05 (o 5%) es uno de los niveles de significación más comunes y se utiliza ampliamente en muchas áreas de la investigación científica. Esto significa que al realizar una prueba estadística con un nivel de significación de 0,05, permitimos un 5% de posibilidades de error de tipo I. El nivel de significación en estadística es un valor umbral utilizado para tomar decisiones sobre la significación estadística de los resultados. Se suele denotar como α (alfa) y representa la probabilidad de un error de tipo I, es decir, la probabilidad de rechazar una hipótesis nula verdadera.

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.");
}

Vamos a ejecutar el script 5 veces para calcular las estadísticas y la ejecución del generador estándar time de ejecución de un generador estándar. Al mismo tiempo se mide el tiempo de ejecución del generador Mersenne Twister. Calcula la diferencia en el tiempo de ejecución como cociente del tiempo de ejecución de Twister y del generador estándar.

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.

Desgraciadamente, el generador de números aleatorios estándar no superó las cinco pruebas cuando se sometió a la prueba de chi-cuadrado, lo que indica que había desviaciones sistemáticas de la distribución aleatoria uniforme esperada.

Ahora probaremos Mersenne Twister, mientras seguimos midiendo el tiempo de ejecución de ambos generadores.

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.

El vórtice de Mersenne superó la tarea en las cinco pruebas (ejecuciones de la prueba chi-cuadrado). Al mismo tiempo, vemos que el generador tiene un inconveniente importante: Twister es aproximadamente 3,4 veces más lento que el estándar, lo que puede afectar significativamente a la velocidad de los algoritmos de optimización.

Ahora llega la parte más interesante, el punto culminante de este estudio: realizaremos pruebas para averiguar en qué medida afecta la calidad de los generadores de números aleatorios a los resultados de la optimización. Como recordarás, el generador estándar crea números en el rango [0;32,767], mientras que el Mersenne Twister de 64 bits - en el rango [0;18,446,744,073,709,551,615].

Para realizar el experimento, seleccionamos 50 funciones Hilly y realizamos 10.000 iteraciones para cada función. ¿Por qué elegí las 50 características de Hilly y por qué Hilly? En primer lugar, este número se eligió de forma que el algoritmo no pudiera alcanzar el 100% de convergencia en un número limitado de ejecuciones de la función de aptitud. Esto permitió observar la diferencia en el uso de distintos tipos de generadores de números aleatorios. En segundo lugar, la elección de las funciones Hilly se debe a su suavidad, que nos permite evitar la dispersión natural de los resultados no asociada a la generación de números aleatorios si utilizáramos una función de prueba discreta. Repetí el experimento 20 veces y promedié los resultados para obtener datos más fiables y estadísticamente significativos. Como algoritmo de optimización, elegimos BGA, que ocupa el primer lugar en nuestra tabla de clasificación y, al mismo tiempo, demuestra una dispersión muy pequeña de los resultados en funciones suaves.

A partir de la impresión de los resultados, se puede observar que los resultados de optimización son casi los mismos para el algoritmo BGA cuando se utiliza tanto un generador de números aleatorios estándar como un generador Mersenne. Sólo se observan diferencias en el tercer decimal, que no son críticas para nuestros fines y se consideran bastante pequeñas.

//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

Al visualizar el funcionamiento del algoritmo, no encontramos desviaciones significativas al utilizar dos tipos distintos de generadores de números aleatorios dentro de la lógica del algoritmo. La diferencia en la dispersión de los resultados está dentro de la variabilidad del propio funcionamiento del algoritmo.

BGA con el generador estándar 

BGA con Mersenne Twister

La conclusión preliminar es la siguiente: la calidad de los generadores de números aleatorios no afecta al rendimiento de los algoritmos de optimización.

Supongamos que la ligera diferencia en los resultados al utilizar los generadores mencionados en el algoritmo de optimización BGA puede deberse al hecho de que en BGA cada bit del cromosoma se genera independientemente de los demás bits. De hecho, el papel de los generadores aleatorios se reduce a la operación booleana «sí/no» y la diferencia entre el número de ocurrencias de «sí» y «no» es sólo de milésimas de porcentaje.

Así pues, para un algoritmo genético binario no hay ninguna diferencia en utilizar generadores de números aleatorios, aunque esta conclusión no era nada evidente a primera vista, pero ¿es esto cierto para otros algoritmos de optimización, especialmente los que utilizan probabilidades continuas en todo el espacio delimitado por [mín, máx] por coordenadas?

Intentemos realizar algunos experimentos más para confirmar la afirmación obtenida o refutarla. Esta vez tomaremos el algoritmo (P_O)ES, que se encuentra entre los líderes de nuestra tabla de clasificación y utiliza un gran número de operaciones con números aleatorios en su lógica, además de aplicar probabilidades continuas en todo el espacio de búsqueda.

(P_O)ES en cinco pruebas realizadas con el generador aleatorio estándar:

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

(P_O)ES en cinco pruebas con el generador 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 se desprende de los resultados de los experimentos realizados, la primera serie de experimentos estaba relacionada con el uso del generador de números aleatorios estándar en el algoritmo. Vemos que el valor medio de los resultados es de aproximadamente 0,95, y el valor medio de los resultados cuando se utiliza el Twister Mersenne es de 0,96, lo que no supone una diferencia significativa, pero nos muestra que los resultados de los experimentos siguen siendo superiores si está presente el Twister Mersenne. Sin embargo, hay que tener en cuenta que el tiempo empleado utilizando este algoritmo supera en 3,5 veces el tiempo de ejecución del algoritmo estándar.

Resumen

Así pues, hemos llevado a cabo un interesante experimento para poner fin a la pregunta que preocupa a muchos operadores: ¿Es importante la calidad de los generadores de números aleatorios cuando se utilizan junto con algoritmos de optimización? Nunca he visto un estudio de este tipo de dominio público.

Para algunos algoritmos que utilizan operaciones booleanas, como BGA, y algoritmos que utilizan números aleatorios en un pequeño rango discreto, como ED (Evolución Diferencial, donde se utilizan números aleatorios para seleccionar los padres en una población), la calidad del RNG casi no juega ningún papel.

Para otros algoritmos que utilizan números aleatorios para generar nuevas soluciones en todo el rango de parámetros optimizados, como (P_O)ES (la mayoría de los algoritmos poblacionales son similares), el RNG juega un papel menor ajustándose al error de medición. Es importante señalar que el generador Mersenne Twister de mayor calidad es 3,5 veces más lento que el estándar.

En los problemas de optimización, el equilibrio entre calidad y tiempo de cálculo desempeña sin duda un papel importante. Finalmente, en este caso elegimos la velocidad. El aumento en los resultados del algoritmo debido al uso de generadores de alta calidad está dentro del margen de error de la medición, mientras que la velocidad disminuye significativamente.

A continuación se adjunta el archivo con los códigos de las pruebas realizadas. Las conclusiones y juicios presentados en el artículo se basan en los resultados de los experimentos.