Comparación de dos algoritmos genéticos

Question

Tengo dos implementaciones de un algoritmo genético que se supone que se comportan de forma equivalente. Sin embargo, debido a restricciones técnicas que no se pueden resolver, su resultado no es exactamente el mismo, dada la misma entrada.

Aun así, me gustaría demostrar que no hay una diferencia de rendimiento significativa.

Tengo 20 ejecuciones con la misma configuración para cada uno de los dos algoritmos, utilizando diferentes semillas de números aleatorios iniciales. Para cada ejecución y la generación el error mínimo aptitud del mejor individuo de la población se registró. El algoritmo emplea un mecanismo de preservación de la élite, por lo que la aptitud del mejor individuo es monotónicamente decreciente. Una tirada consta de 1000 generaciones, por lo que tengo 1000 valores por tirada. No puedo obtener más datos, ya que los cálculos son muy costosos.

¿Qué prueba debo emplear? Una forma fácil sería probablemente comparar sólo el error en las generaciones finales (de nuevo, ¿qué prueba utilizaría aquí)? Pero también se podría pensar en comparar el comportamiento de la convergencia en general.

Answer 1

Eliminación gaussiana en un $n \times n$ matriz toma del orden de $n^3$ operaciones, donde una operación es una suma, una resta, una multiplicación o una división. En cambio, el cálculo de determinantes mediante la expansión de cofactores requiere $n!$ operaciones, que es mucho, mucho más largo.

Por ejemplo, considere un $100 \times 100$ matriz. Entonces $100^3$ es un millón, y un millón de operaciones puede ser realizado por un ordenador portátil típico en menos de un segundo; pero $100!$ es aproximadamente $1$ seguido de $158$ ceros, lo que llevaría incluso a un superordenador más tiempo que la edad del universo.

De hecho, creo que lo contrario de tu afirmación es cierto: si quieres calcular determinantes, la mejor manera es reducir a la forma escalonada.

Answer 2

Probar algoritmos estocásticos puede ser bastante complicado.

Trabajo en biología de sistemas y hay muchos simuladores estocásticos disponibles para simular un modelo. Probar estos simuladores es complicado, ya que dos realizaciones de un mismo modelo suelen ser diferentes.

En el dsmts hemos calculado (analíticamente) el valor esperado y la varianza de un modelo concreto. A continuación, realizamos una prueba de hipótesis para determinar si un simulador difiere de la verdad. La sección 3 del guía del usuario da los detalles. Básicamente, hacemos una prueba t para los valores medios y una prueba chi-cuadrado para las varianzas.

En su caso, está comparando dos simuladores, por lo que debería utilizar una prueba t de dos muestras.