Como faço para testar a unidade de um algoritmo heurístico?

Digamos que temos nosso algoritmo de localização de rotas:

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

Agora queremos fazer o teste de unidade:

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

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

A questão é que, para um algoritmo TSP não heurístico, podemos fornecer uma variedade de gráficos e verificar se eles sempre retornam absolutamente a rota mais curta.

Mas como um algoritmo heurístico, embora ainda seja determinístico, é menos previsível, serve apenas para entender como o algoritmo está funcionando e para encontrar esses casos extremos?

Para um algoritmo heurístico que supostamente não retorna a solução ideal, mas uma solução "suficientemente boa", você teria vários casos de teste e checaria

1. a solução é realmente válida? Você certamente deseja garantir que seu algoritmo de localização de rotas não retorne caminhos impossíveis ou que não conduzem do início ao fim. Você pode não conseguir provar que a solução é ideal, mas pelo menos deve poder verificar se o valor de retorno é realmente uma solução.
2. a solução é "boa o suficiente"? Você deve ter alguns requisitos que definam quão pior o algoritmo pode ser do que a solução ideal. Você deve ter casos de teste em que a solução ideal seja conhecida (ou pelo menos uma solução que seja considerada boa o suficiente para ser usada como padrão de comparação) e confirmar que a solução fornecida pelo algoritmo não seja x% pior.
3. O algoritmo é rápido o suficiente? Você costuma usar uma abordagem heurística quando presume que eles compensam a falta de precisão por serem muito mais rápidos. Para verificar isso, você deve medir o tempo de execução e garantir que eles sejam realmente mais rápidos que um algoritmo que obtém a solução exata. As medições de tempo de execução são sempre um pouco imprecisas, portanto, exceder o tempo de execução esperado deve ser um aviso, não um erro (quando sua estrutura de teste de unidade permite diferir entre avisos e erros).

A maioria dos algoritmos de otimização (incluindo heurística) funciona em algumas configurações (no seu exemplo, uma rota) aplicando operações nelas. As operações por si só devem garantir que eles entreguem apenas configurações válidas; portanto, primeiro deve haver testes de unidade para cada uma delas. Quando você tem certeza de que o algoritmo de otimização usa apenas essas operações, normalmente não há necessidade de um teste de validade do resultado do algoritmo.

Para criar bons testes de unidade para qualquer tipo de algoritmo mais complexo, é preciso conhecer o próprio algoritmo em detalhes . Para heurísticas simples como "escalada", normalmente você pode prever o resultado para pequenas entradas. Por exemplo, para rotas iniciais de 3 a 5 pontos, quando fornecidas em uma determinada ordem, você pode prever o que acontecerá. Isso permanecerá verdadeiro para a maioria dos algoritmos heurísticos determinísticos que conheço, portanto esse é provavelmente um bom lugar para começar.

Para algoritmos mais complexos e tamanho maior da entrada, quando você apenas insere a entrada no algoritmo e tenta verificar a saída, na verdade você não está mais fazendo um teste de unidade, está fazendo um teste de aceitação ou integração. A razão pela qual você tem problemas para "testar a unidade" é algo que geralmente consiste em várias partes menores (unidades individuais). Portanto, para testar realmente esse algoritmo, você precisará identificar essas partes e testá-las individualmente. Além disso, você pode usar a cobertura de código ou técnicas de cobertura de filial para garantir que você tenha casos de teste suficientes.

Se você não está procurando testes de unidade, mas testes de aceitação ou integração automatizados, pode tentar o que o @Phillip sugeriu em (2) ou (3) .