Jak mogę przetestować algorytm heurystyczny?

Powiedzmy, że mamy nasz algorytm znajdowania trasy:

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

Teraz chcemy to przetestować jednostkowo:

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

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

Pytanie brzmi: w przypadku nieheurystycznego algorytmu TSP możemy podać różnorodne wykresy i sprawdzić, czy zawsze zwracają absolutnie najkrótszą trasę.

Ale ponieważ algorytm heurtystyczny, mimo że jest deterministyczny, jest mniej przewidywalny, ma po prostu zrozumieć, w jaki sposób algorytm ma działać, i znaleźć te przypadki brzegowe?

W przypadku algorytmu heurystycznego, który ma nie zwracać idealnego, ale „wystarczająco dobrego” rozwiązania, masz różne przypadki testowe i sprawdzasz

1. czy rozwiązanie jest rzeczywiście ważne? Na pewno chcesz się upewnić, że algorytm wyznaczania trasy nie zwraca ścieżek, które są niemożliwe lub które w rzeczywistości nie prowadzą od początku do końca. Być może nie będziesz w stanie udowodnić, że rozwiązanie jest idealne, ale powinieneś przynajmniej być w stanie zweryfikować, czy zwracana wartość faktycznie jest rozwiązaniem.
2. czy rozwiązanie jest „wystarczająco dobre”? Powinieneś mieć pewne wymagania, które określają, o ile gorszy może być algorytm niż idealne rozwiązanie. Powinieneś mieć przypadki testowe, w których znane jest idealne rozwiązanie (lub przynajmniej rozwiązanie, które jest uważane za wystarczająco dobre, aby je zastosować jako standard porównawczy) i potwierdzić, że rozwiązanie dostarczone przez algorytm jest nie gorsze niż x%.
3. Czy algorytm jest wystarczająco szybki? Często stosujesz podejście heurystyczne, gdy zakładasz, że nadrabiają brak precyzji, będąc znacznie szybszymi. Aby to sprawdzić, należy zmierzyć ich czas działania i upewnić się, że rzeczywiście są one szybsze niż algorytm, który uzyska dokładne rozwiązanie. Pomiary w środowisku wykonawczym są zawsze nieco rozmyte, więc przekroczenie oczekiwanego czasu wykonywania powinno być ostrzeżeniem, a nie błędem (gdy struktura testów jednostkowych pozwala na rozróżnienie między ostrzeżeniami i błędami).

Większość algorytmów optymalizacyjnych (w tym heurystyk) działa w niektórych konfiguracjach (w twoim przykładzie na trasie) poprzez zastosowanie na nich operacji. Operacje same w sobie powinny gwarantować, że dostarczają tylko prawidłowe konfiguracje, więc najpierw powinny być testy jednostkowe dla każdej z nich. Gdy wiesz na pewno, że algorytm optymalizacji korzysta tylko z tych operacji, zazwyczaj nie powinno być potrzeby sprawdzania poprawności wyniku algorytmu.

Aby utworzyć dobre testy jednostkowe dla każdego rodzaju bardziej złożonego algorytmu, jeden rzeczywiście musi znać algorytm sam w szczegółach . W przypadku prostych heurystyk, takich jak „wspinaczka pod górę”, zwykle można przewidzieć wynik dla niewielkich nakładów. Na przykład dla początkowych tras od 3 do 5 punktów, jeśli podane w określonej kolejności, możesz przewidzieć, co się stanie. To pozostanie prawdziwe w przypadku większości deterministycznych algorytmów heurystycznych, które znam, więc prawdopodobnie jest to dobre miejsce na rozpoczęcie.

W przypadku bardziej złożonych algorytmów i większego rozmiaru danych wejściowych, po prostu wprowadzasz dane wejściowe do algorytmu i próbujesz sprawdzić dane wyjściowe, w rzeczywistości nie wykonujesz już testów jednostkowych, przeprowadzasz test akceptacyjny lub integracyjny. Powodem, dla którego masz problemy z „testowaniem jednostki” takiego algo, jest to, że zazwyczaj składa się on z garści mniejszych części (pojedynczych jednostek). Tak więc, aby naprawdę przetestować taki algorytm, będziesz musiał zidentyfikować te części i przetestować je indywidualnie. Ponadto można użyć technik pokrycia kodu lub technik pokrycia gałęzi, aby upewnić się, że masz wystarczającą liczbę przypadków testowych.

Jeśli nie szukasz testów jednostkowych, ale automatycznych testów akceptacyjnych lub integracyjnych, możesz wypróbować sugestie @Phillip pod (2) lub (3) .