unidad de prueba de aproximación Algoritmos

Question

Estoy trabajando en una biblioteca de algoritmos de aproximación de código abierto para gráficos y redes que usan algunos paquetes python populares como base. El objetivo principal es abarcar algoritmos de aproximación actualizados para problemas NP-Complete sobre gráficos y redes. La razón de esto es 1) No he visto un buen paquete consolidado (moderno) que cubra esto y 2) sería una buena herramienta pedagógica para aprender acerca de los algoritmos de aproximación en problemas de optimización NP-Hard.

En la construcción de esta biblioteca que estoy usando unidad de pruebas a prueba de cordura (como lo haría cualquier desarrollador adecuada). Soy un poco cauteloso con respecto a las pruebas unitarias porque, por su propia naturaleza, los algoritmos de aproximación pueden no dar la solución correcta. Actualmente resuelvo algunas instancias pequeñas a mano y luego me aseguro de que el resultado devuelto coincida con eso, pero esto no es deseable ni escalable en un sentido de implementación.

¿Cuál sería la mejor manera de probar los algoritmos de aproximación de prueba? ¿Genera instancias aleatorias y garantiza que los resultados devueltos sean inferiores al límite garantizado por el algoritmo? Eso parece tener falsos positivos (la prueba acaba de tener suerte ese momento, no se garantiza que todas las instancias estén por debajo del límite).

Answer 1

Tiene que separar dos preocupaciones aquí. La calidad de sus algoritmos de aproximación y la corrección de la implementación de esos algoritmos.

Prueba de la calidad de un algoritmo de aproximación por lo general no se presta a los métodos de prueba unitarios utilizados en el desarrollo de software. Por ejemplo, necesitaría generar problemas aleatorios que sean representativos del tamaño real de los problemas. Es posible que necesite hacer un trabajo matemático para obtener un límite superior/inferior para juzgar la calidad de sus algoritmos para instancias grandes e irresolubles. O use conjuntos de pruebas problemáticas que tengan soluciones conocidas o las más conocidas y compare sus resultados. Pero en cualquier caso, las pruebas unitarias no lo ayudarían mucho a mejorar la calidad de los algoritmos de aproximación. Aquí es donde el conocimiento de tu dominio en optimización y matemática te ayudará.

Lo correcto de su implementación es que las pruebas unitarias serán realmente útiles. Puede usar problemas de tamaño de juguete aquí y comparar resultados conocidos (resolver a mano, o verificar mediante la depuración cuidadosa paso a paso en el código) con lo que genera su código. Tener pequeños problemas no solo es suficiente sino que también es deseable aquí para que las pruebas se ejecuten rápidamente y puedan ejecutarse muchas veces durante el ciclo de desarrollo. Este tipo de pruebas asegura que el algoritmo general llegue al resultado correcto.Está en algún lugar entre una prueba de unidad y una prueba de integración, ya que está probando una gran parte del código como una caja negra. Pero he encontrado que estos tipos de pruebas son extremadamente útiles en el dominio de optimización. Una cosa que recomiendo hacer para este tipo de pruebas es eliminar toda la aleatoriedad en sus algoritmos a través de semillas fijas para generadores de números aleatorios. Estas pruebas siempre deben ejecutarse de manera determinista y dar exactamente el mismo resultado el 100% del tiempo. También recomiendo pruebas unitarias en los módulos de nivel inferior de sus algoritmos. Aísle el método que asigna pesos a los arcos en el gráfico y verifique si se asignan los pesos correctos. Aísle la función de cálculo del valor de la función objetivo y la prueba unitaria. Entiendes mi punto.

Otra preocupación que corta estos dos cortes es el rendimiento. No se puede evaluar de manera confiable el rendimiento con pequeños problemas de juguete. También es muy deseable realizar un cambio que degrade significativamente el rendimiento de un algoritmo de trabajo. Una vez que tenga una versión en ejecución de sus algoritmos, puede crear problemas de prueba más grandes donde mida el rendimiento y lo automatice para que sea su prueba de rendimiento/integración. Puede ejecutarlos con menos frecuencia, ya que llevarán más tiempo, pero al menos le avisarán con anticipación sobre cuellos de botella de rendimiento recientemente introducidos durante la refactorización o nuevas funciones adicionales a los algoritmos

Answer 2

Comprobar la validez de las soluciones producidas es el primer paso obvio.

Además, un ángulo de ataque podría ser regression testing usando instancias para las cuales se conoce la solución aproximada esperada (por ejemplo, obtenida ejecutando el algoritmo a mano o usando la implementación de otro por parte del mismo algoritmo).

También existen depósitos de casos de problemas con las soluciones conocidas (óptimos), tales como TSPLIB para los problemas de TSP-como. Tal vez estos podrían ser de alguna utilidad.

Si se conocen los límites superiores para el algoritmo en cuestión, a continuación, la generación de muchos casos al azar y la verificación de las soluciones heurísticas contra los límites superior puede resultar fructífera. Si haces esto, te recomiendo que hagas que las tiradas sean reproducibles (por ejemplo, siempre usando el mismo generador de números aleatorios y semilla).

Una última nota: para algunos problemas, casos totalmente al azar son, en promedio, bastante fácil de encontrar buenas soluciones aproximadas para. El TSP asimétrico con pesos de arco elegidos de forma independiente e independiente es uno de esos ejemplos. Menciono esto ya que puede afectar su estrategia de prueba.

Answer 3

Por lo general, puede verificar algo, por ejemplo, que su algoritmo siempre devuelve soluciones que satisfacen sus limitaciones, incluso si no son óptimas. También debe colocar comprobaciones de afirmación en cada oportunidad posible; estas serán específicas de su programa, pero podrían verificar que se conserve alguna cantidad, o que algo que debería aumentar o, en el peor de los casos, permanecer igual no disminuya, o que algún supuesto óptimo realmente es un óptimo local.

Dado este tipo de comprobaciones y verificaciones de límites que ya ha mencionado, estoy a favor de ejecutar pruebas en una gran cantidad de pequeños problemas generados aleatoriamente, con semillas elegidas de manera que si falla en el problema 102324 puede repetir ese error para la depuración sin correr a través de los problemas 102323 antes. Con una gran cantidad de problemas, aumenta la posibilidad de que un error subyacente cause un error lo suficientemente obvio como para que falle su comprobación. Con pequeños problemas, aumenta las posibilidades de que pueda encontrar y corregir el error.