¿Cómo pruebo un algoritmo heurístico?

10

Digamos que tenemos nuestro algoritmo de búsqueda de ruta:

def myHeuristicTSP(graph):
    /*implementation*/
    return route

Ahora queremos hacer una prueba unitaria de esto:

class TestMyHeuristicTSP:
    def testNullGraphRaiseValueError(self):
        self.assertRaises(ValueError, myHueristicTSP(None))

    def testSimpleTwoNodeGraphReturnsRoute:
        self.assertEquals(expectedResult, myHeuristicTSP(input))

La pregunta es, para un algoritmo TSP no heurístico, podemos dar una variedad de gráficos y verificar que siempre devuelvan absolutamente la ruta más corta.

Pero debido a que un algoritmo heurtístico, aunque todavía es determinista, es menos predecible, ¿simplemente tiene la intención de comprender cómo debe funcionar el algoritmo y encontrar esos casos límite?

unit-testing heuristics dwjohnston
fuente
1
Relacionado: programmers.stackexchange.com/questions/236925/… , programmers.stackexchange.com/questions/230355/…
Doc Brown

Respuestas:

11

Para un algoritmo heurístico que se supone que no devuelve la solución ideal sino una solución "suficientemente buena", tendría varios casos de prueba y comprobaría

  1. ¿Es la solución realmente válida? Sin duda desea asegurarse de que su algoritmo de búsqueda de ruta no devuelva rutas que son imposibles o que en realidad no conducen de principio a fin. Puede que no seas capaz de demostrar que la solución es ideal, pero al menos debe ser capaz de verificar que el valor de retorno en realidad es una solución.
  2. ¿Es la solución "suficientemente buena"? Debe tener algunos requisitos que definan cuánto peor puede ser el algoritmo que la solución ideal. Debe tener casos de prueba en los que se conoce la solución ideal (o al menos una solución que se considere lo suficientemente buena como para ser utilizada como un estándar de comparación) y confirmar que la solución proporcionada por el algoritmo no es más que x% peor.
  3. ¿Es el algoritmo lo suficientemente rápido? A menudo utiliza un enfoque heurístico cuando presume que compensan su falta de precisión al ser mucho más rápidos. Para verificar esto, debe medir su tiempo de ejecución y asegurarse de que sean más rápidos que un algoritmo que obtenga la solución exacta. Las mediciones de tiempo de ejecución son siempre un poco confusas, por lo que exceder el tiempo de ejecución esperado debería ser una advertencia, no un error (cuando el marco de prueba de la unidad permite diferir entre advertencias y errores).
Philipp
fuente
¿Puede tal vez proporcionar una sugerencia para probar cómo determinaría que una ruta es válida?
dwjohnston
@dwjohnston Simplemente tome su gráfico, tome su camino e intente recorrer el camino sobre su gráfico. Verifique que cada borde de la ruta esté conduciendo desde el nodo actual y que la ruta comience y termine en los nodos correctos. También puede verificar que no se llegue al nodo final antes del final.
Philipp
También puede verificar que ningún nodo en su ruta se use dos veces, porque esto indica un bucle innecesario. A menos, por supuesto, que tenga algunas reglas especiales que hagan que los bucles sean útiles, como el sistema de búsqueda de rutas UPS que prefiere tres giros a la derecha sobre uno a la izquierda .
Philipp
3

La mayoría de los algoritmos de optimización (incluidas las heurísticas) funcionan en algunas configuraciones (en su ejemplo, una ruta) mediante la aplicación de operaciones en ellas. Las operaciones por sí mismas deben garantizar que entreguen solo configuraciones válidas, por lo que primero debe haber pruebas unitarias para cada una de ellas. Cuando sepa con certeza que el algoritmo de optimización usa solo esas operaciones, normalmente no debería ser necesario realizar una prueba de validez del resultado del algoritmo.

Para crear buenas pruebas unitarias para cualquier tipo de algoritmo más complejo, uno tiene que conocer el algoritmo en detalle . Para heurísticas simples como "escalar montañas", generalmente puede predecir el resultado para entradas pequeñas. Por ejemplo, para rutas iniciales de 3 a 5 puntos, cuando se dan en un cierto orden, puede predecir lo que sucederá. Esto seguirá siendo cierto para la mayoría de los algoritmos heurísticos deterministas que conozco, por lo que probablemente sea un buen lugar para comenzar.

Para algoritmos más complejos y un mayor tamaño de la entrada, cuando solo ingresa la entrada en el algoritmo e intenta verificar la salida, en realidad ya no está haciendo una prueba unitaria, está haciendo una prueba de aceptación o integración. La razón por la que tiene problemas para "probar unitariamente" este tipo de algoritmo es porque generalmente consiste en un puñado de partes más pequeñas (unidades individuales). Entonces, para probar realmente un algoritmo de este tipo, tendrá que identificar esas partes y probarlas individualmente. Además, puede usar la cobertura de código o las técnicas de cobertura de sucursal para asegurarse de tener suficientes casos de prueba.

Si no está buscando pruebas unitarias, sino pruebas de aceptación o integración automatizadas, puede probar lo que @Phillip sugirió en (2) o (3) .

Doc Brown
fuente