Cómo debo probar un algoritmo genético

Question

He hecho algunos algoritmos genéticos; funcionan (encuentran una solución razonable rápidamente). Pero ahora descubrí TDD. ¿Hay alguna manera de escribir un genetic algorithm (que depende en gran medida de números aleatorios) de una manera TDD?

Para plantear la pregunta más en general, ¿Cómo se prueba un método/función no determinista. Esto es lo que he pensado:

1. Utilice una semilla específica. Lo cual no ayudará si cometo un error en el código en primer lugar, pero ayudará a encontrar errores al refactorizar.

2. Utilice una lista de números conocida. Similar a lo anterior, pero podría seguir el código a mano (lo cual sería muy tedioso).

3. Use un número constante. Al menos sé qué esperar. Sería bueno asegurarse de que un dado siempre muestre 6 cuando RandomFloat (0,1) siempre devuelve 1.

4. Intente mover la mayor parte del código no determinista de la GA como sea posible. que parece tonto ya que ese es el núcleo de su propósito.

También se apreciarán los enlaces a libros muy buenos sobre pruebas.

Answer 1

Me parece que la única manera de probar su lógica coherente es aplicar datos consistentes, ... o tratar cada iteración como un único autómata cuyo estado se prueba antes y después de esa iteración, girando el sistema general no determinista en componentes comprobables basados ​​en valores de iteración determinista.

Para variaciones/reproducción/la herencia de atributos en iteraciones, probar esos valores en los límites de cada iteración y probar el resultado global de todas las iteraciones basado en conocida de entrada/salida de éxito de iteración-subpruebas ...

Debido el algoritmo es iterativo puede usar inducción en su prueba para asegurarse de que funciona por 1 iteración, n + 1 iteraciones para probar que producirá resultados correctos (independientemente del determinismo de datos) para un rango/dominio de entrada dado y las restricciones posibles valores en la entrada.

Editar Encontré este strategies for testing nondeterministic systems que podría proporcionar alguna información. Podría ser útil para el análisis estadístico de los resultados en vivo una vez que el proceso TDD/desarrollo demuestre que la lógica es sólida.

Answer 2

Puede escribir una red neuronal redundante para analizar los resultados de su algoritmo y clasificar el resultado en función de los resultados esperados. :)

Rompa su método tanto como pueda. Luego, también puede realizar una prueba unitaria alrededor de la parte aleatoria para verificar el rango de valores. Incluso haga que la prueba se ejecute varias veces para ver si el resultado cambia.

Answer 3

Una prueba de que el algoritmo le da el mismo resultado para la misma entrada podría ayudarlo pero a veces hará cambios que cambien el comportamiento de selección de resultados del algoritmo.

Haré el mayor esfuerzo para tener una prueba que asegure que el algoritmo le da un resultado correcto.Si el algoritmo le da un resultado correcto para un número de semillas estáticas y valores aleatorios, el algoritmo funciona o no se rompe a través de los cambios realizados.

Otra posibilidad en TDD es la posibilidad de evaluar el algoritmo. Si puede verificar automáticamente qué tan bueno es el resultado, puede agregar pruebas que demuestren que un cambio no ha disminuido las cualidades de sus resultados o aumentado su tiempo de cálculo de manera irracional.

Si desea probar su algoritmo con muchas semillas base, tal vez quiera probar un traje que ejecute una prueba rápida para comenzar después de cada guardado para asegurarse de que no ha roto nada y un traje que corre por un tiempo más largo para una evaluación posterior

Answer 4

Verificaría las funciones aleatorias probándolas varias veces y analizando si la distribución de los valores de retorno cumple con las expectativas estadísticas (esto implica algo de conocimiento estadístico).

Answer 5

Si hablas de TDD, yo diría que definitivamente comienzas seleccionando un número constante y haciendo crecer tu suite de pruebas desde allí. He hecho TDD en algunos problemas altamente matemáticos y es útil tener algunos casos constantes que conoces y que hayas resuelto a mano para ejecutar desde el principio.

W/R/T su cuarto punto, sacando el código no determinista de la GA, creo que este es probablemente un enfoque que vale la pena considerar. Si puede descomponer el algoritmo y separar las preocupaciones no deterministas, debería hacer que probar las partes deterministas sea sencillo. Siempre y cuando tengas cuidado acerca de cómo nombras las cosas, no creo que estés sacrificando mucho aquí. A menos que te esté malinterpretando, la AG todavía delegará en este código, pero vive en otro lado.

En cuanto a los enlaces a libros muy buenos sobre (desarrollador) probar mis favoritos son:

• Test Driven por Lasse Kosela
• Working Effectively with Legacy Code por las plumas Michael
• XUnit Test Patterns por Gerard Meszaros
• Next Generation Java™ Testing: TestNG and Advanced Concepts por Cédric Beust & Hani Suleiman

Answer 6

Todas sus funciones deben ser completamente deterministas. Esto significa que ninguna de las funciones que está probando debe generar el número aleatorio dentro de la función en sí. Querrá pasar eso como un parámetro. De esta forma, cuando su programa tome decisiones basadas en sus números aleatorios, puede pasar números representativos para probar el resultado esperado para ese número. Lo único que no debería ser determinista es su generador de números aleatorios real, del cual no necesita preocuparse demasiado porque no debería escribirlo usted mismo. Debería poder asumir que funciona siempre que sea una biblioteca establecida.

Eso es para sus pruebas unitarias. Para sus pruebas de integración, si lo hace, puede buscar burlarse de su generación de números aleatorios, reemplazándola con un algoritmo que devolverá números conocidos de 0..n por cada número aleatorio que necesite generar.

Answer 7

me escribió una C# TDD Algoritmo Genético aplicación didáctica: http://code.google.com/p/evo-lisa-clone/

Tomemos el método aleatorio simple resultado de la aplicación: PointGenetics.Create, lo que crea un punto al azar, teniendo en cuenta los límites.Por este método que utiliza 5 pruebas, y ninguno de ellos se basa en una semilla específica:

http://code.google.com/p/evo-lisa-clone/source/browse/trunk/EvoLisaClone/EvoLisaCloneTest/PointGeneticsTest.cs

La prueba de aleatoriedad es simple: para un gran límite (muchas posibilidades), dos consecutiva genera puntos no deben ser iguales . Las pruebas restantes verifican otras restricciones.

Answer 8

Sugeriría encarecidamente buscar en el uso de objetos simulados para los casos de prueba de su unidad (http://en.wikipedia.org/wiki/Mock_object). Puede usarlos para simular objetos que hacen suposiciones aleatorias para provocar que obtenga los resultados esperados.

Answer 9

Bueno, la parte más comprobable es la función de acondicionamiento físico, donde estará toda su lógica. esto puede ser en algunos casos bastante complejo (puede que esté ejecutando todo tipo de simulaciones basadas en parámetros de entrada) por lo que quiere asegurarse de que todo eso funcione con un montón de pruebas unitarias, y este trabajo puede seguir cualquier metodología.

Con respecto a probar los parámetros de GA (tasa de mutación, estrategia cruzada, lo que sea) si usted mismo está implementando eso usted puede probarlo (puede volver a tener pruebas unitarias sobre lógica de mutación, etc.) no podrá probar el "ajuste fino" de la GA.

En otras palabras, no podrá probar si GA realmente se comporta de otra manera que no sea por la bondad de las soluciones encontradas.

Answer 10

Una forma en que hago para la prueba unitaria de funciones no deterministas de algoritmos GA es poner la elección de números aleatorios en una función diferente de la lógica que usa números aleatorios.

Por ejemplo, si tiene una función que toma un gen (vector de algo) y toma dos puntos aleatorios del gen para hacer algo con ellos (mutación o lo que sea), puede poner la generación de los números aleatorios en una función, y luego pasarlos junto con el gen a otra función que contiene la lógica dado que los números.

De esta forma puedes hacer TDD con la función lógica y pasarle ciertos genes y ciertos números, sabiendo exactamente lo que la lógica debería hacer en el gen dado que los números y poder escribir afirman en el gen modificado.

Otra forma, probar con la generación de números aleatorios es externalizar esa generación a otra clase, que se puede acceder a través de un contexto o cargar desde un valor de configuración, y usar una diferente para las ejecuciones de prueba. Habría dos implementaciones de esa clase, una para producción que genera números aleatorios reales y otra para pruebas, que tendría formas de aceptar los números que luego generaría. Luego, en la prueba, puede proporcionar ciertos números que la clase proporcionará al código probado.