Wie teste ich einen heuristischen Algorithmus?

10

Angenommen, wir haben unseren Routenfindungsalgorithmus:

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

Jetzt wollen wir dies testen:

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

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

Die Frage ist, dass wir für einen nicht heuristischen TSP-Algorithmus eine Vielzahl von Diagrammen angeben und überprüfen können, ob sie immer den absolut kürzesten Weg zurückgeben.

Aber weil ein heurtistischer Algorithmus, obwohl er noch deterministisch ist, weniger vorhersehbar ist, soll er einfach verstehen, wie der Algorithmus funktionieren soll, und diese Randfälle finden?

Dwjohnston
quelle

Antworten:

11

Für einen heuristischen Algorithmus, der nicht das Ideal, sondern eine "gut genug" -Lösung zurückgeben soll, hätten Sie verschiedene Testfälle und prüfen

  1. Ist die Lösung tatsächlich gültig? Sie möchten auf jeden Fall sicherstellen, dass Ihr Routenfindungsalgorithmus keine Pfade zurückgibt, die unmöglich sind oder nicht von Anfang bis Ende führen. Sie könnten in der Lage zu beweisen , nicht , dass die Lösung ideal ist, aber man sollte zumindest zu überprüfen , die Lage sein , dass der Rückgabewert tatsächlich ist eine Lösung.
  2. ist die Lösung "gut genug"? Sie sollten einige Anforderungen haben, die definieren, wie viel schlechter der Algorithmus sein kann als die ideale Lösung. Sie sollten Testfälle haben, in denen die ideale Lösung bekannt ist (oder zumindest eine Lösung, die als gut genug angesehen wird, um als Vergleichsstandard verwendet zu werden) und bestätigen, dass die vom Algorithmus bereitgestellte Lösung nicht mehr als x% schlechter ist.
  3. Ist der Algorithmus schnell genug? Sie verwenden häufig einen heuristischen Ansatz, wenn Sie davon ausgehen, dass sie ihre mangelnde Präzision ausgleichen, indem sie viel schneller sind. Um dies zu überprüfen, sollten Sie ihre Laufzeit messen und sicherstellen, dass sie tatsächlich schneller sind als ein Algorithmus, der die genaue Lösung erhält. Laufzeitmessungen sind immer etwas unscharf, daher sollte das Überschreiten der erwarteten Laufzeit eine Warnung und kein Fehler sein (wenn Ihr Unit-Test-Framework zulässt, dass zwischen Warnungen und Fehlern unterschieden wird).
Philipp
quelle
Können Sie vielleicht einen Vorschlag zum Testen machen, wie Sie feststellen würden, ob eine Route gültig ist?
Dwjohnston
@dwjohnston Nehmen Sie einfach Ihr Diagramm, nehmen Sie Ihren Pfad und versuchen Sie, den Pfad über Ihr Diagramm zu durchlaufen. Stellen Sie sicher, dass jede Kante des Pfads vom aktuellen Knoten führt und dass der Pfad an den richtigen Knoten beginnt und endet. Sie können auch überprüfen, ob der Endknoten nicht vor dem Ende erreicht wird.
Philipp
Sie können auch überprüfen, ob kein Knoten in Ihrem Pfad zweimal verwendet wird, da dies auf eine unnötige Schleife hinweist. Es sei denn, Sie haben natürlich einige spezielle Regeln, die Schleifen nützlich machen, wie das UPS-Routenfindungssystem, das drei Rechtskurven gegenüber einer Linkskurve bevorzugt .
Philipp
3

Die meisten Optimierungsalgorithmen (einschließlich Heuristiken) arbeiten mit einigen Konfigurationen (in Ihrem Beispiel einer Route), indem sie Operationen auf sie anwenden. Die Operationen für sich sollten sicherstellen, dass sie nur gültige Konfigurationen liefern, daher sollten zuerst Unit-Tests für jede von ihnen durchgeführt werden. Wenn Sie sicher sind, dass der Optimierungsalgorithmus nur diese Operationen verwendet, sollte normalerweise kein Gültigkeitstest für das Ergebnis des Algorithmus erforderlich sein.

Um gute Komponententests für jede Art von komplexerem Algorithmus zu erstellen, muss man den Algorithmus selbst im Detail kennen . Für einfache Heuristiken wie "Bergsteigen" können Sie normalerweise das Ergebnis für kleine Eingaben vorhersagen. Beispielsweise können Sie für anfängliche Routen mit 3 bis 5 Punkten in einer bestimmten Reihenfolge vorhersagen, was passieren wird. Dies gilt für die meisten mir bekannten deterministischen heuristischen Algorithmen. Das ist also wahrscheinlich ein guter Anfang.

Bei komplexeren Algorithmen und einer größeren Größe der Eingabe führen Sie, wenn Sie nur die Eingabe in den Algorithmus einspeisen und versuchen, die Ausgabe zu überprüfen, keinen Komponententest mehr durch, sondern einen Akzeptanz- oder Integrationstest. Der Grund, warum Sie Probleme haben, einen solchen Algorithmus zu "testen", liegt darin, dass er normalerweise aus einer Handvoll kleinerer Teile (einzelne Einheiten) besteht. Um einen solchen Algorithmus wirklich in Einheiten zu testen, müssen Sie diese Teile identifizieren und einzeln testen. Darüber hinaus können Sie Codeabdeckungs- oder Zweigabdeckungstechniken verwenden, um sicherzustellen, dass Sie über genügend Testfälle verfügen.

Wenn Sie nicht nach Unit-Tests, sondern nach automatisierten Akzeptanz- oder Integrationstests suchen, können Sie versuchen, was @Phillip unter (2) oder (3) vorgeschlagen hat .

Doc Brown
quelle