How to Unit Test a Heuristic Algorithm

heuristicsunit testing

Say we have our route finding algorithm:

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

Now we want to unit test this:

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

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

The question is, for a non-heuristic TSP algorithm, we can give a variety of graphs and check that they always return absolutely the shortest route.

But because a heurtistic algorithm, while is still deterministic, is less predictable, are simply meant to understand how the algorithm is meant to be working, and find those edge cases?

Best Answer

For a heuristic algorithm which is supposed to not return the ideal but a "good enough" solution, you would have various test-cases and check

  1. is the solution actually valid? You certainly want to make sure your route-finding algorithm doesn't return paths which are impossible or which don't actually lead from start to finish. You might not be able to prove that the solution is ideal, but you should at least be able to verify that the return value actually is a solution.
  2. is the solution "good enough"? You should have some requirements which define how much worse the algorithm may be than the ideal solution. You should have test cases where the ideal solution is known (or at least a solution which is considered good enough to be used as a comparison standard) and confirm that the solution provided by the algorithm is not more than x% worse.
  3. Is the algorithm fast enough? You often use a heuristic approach when you presume that they make up for their lack of precision by being much faster. To verify this you should measure their runtime and make sure they are indeed faster than an algorithm which gets the exact solution. Runtime measurements are always a bit fuzzy, so exceeding the expected runtime should be a warning, not an error (when your unit testing framework allows to differ between warnings and errors).
Related Topic