单元测试近似算法

Question

我正在使用一些流行的python包作为基础,为图形和网络开发一个开源近似算法库.主要目标是在图形和网络上包含NP-Complete问题的最新近似算法.原因是1)我还没有看到一个很好的(现代)整合软件包来涵盖这个和2)它将是一个很好的教学工具,用于学习NP-Hard优化问题的近似算法.

在构建这个库时,我使用单元测试来进行健全性检查(正如任何适当的开发人员所做的那样).我对我的单元测试有些谨慎,因为它们本质上是近似算法可能无法返回正确的解决方案.目前我正在手工解决一些小实例,然后确保返回的结果与之匹配,但这在实现意义上是不可取的,也不是可扩展的.

单元测试近似算法的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的界限？这似乎有误报(测试时间很幸运,并不能保证所有实例都低于限制).

Answer 1

您需要在这里区分两个问题。近似算法的质量以及这些算法实现的正确性。

测试近似算法的质量通常不适合软件开发中使用的单元测试方法。例如，您需要生成代表问题实际规模的随机问题。您可能需要进行数学工作以获得一些上限/下限，以判断无法解决的大型实例的算法的质量。或者使用具有已知或最著名解决方案的问题测试集并比较您的结果。但无论如何，单元测试对提高近似算法的质量没有多大帮助。这就是您在优化和数学方面的领域知识将发挥作用的地方。

实现的正确性是单元测试真正有用的地方。您可以在此处使用玩具大小的问题，并将已知结果（手动解决，或通过代码中仔细的逐步调试进行验证）与代码生成的结果进行比较。在这里，出现小问题不仅足够，而且也是可取的，这样测试才能快速运行，并且可以在开发周期中多次运行。这些类型的测试可确保整体算法得出正确的结果。它介于单元测试和集成测试之间，因为您正在将大部分代码作为黑盒进行测试。但我发现这些类型的测试在优化领域非常有用。对于此类测试，我建议做的一件事是通过随机数生成器的固定种子消除算法中的所有随机性。这些测试应始终以确定性方式运行，并 100% 给出完全相同的结果。我还建议在算法的较低级别模块进行单元测试。隔离为图表上的弧分配权重的方法，并检查是否分配了正确的权重。隔离您的目标函数值计算函数并对其进行单元测试。你明白我的意思了。

削减这两个部分的另一个问题是性能。您无法通过小问题来可靠地测试性能。此外，快速实现会显着降低工作算法性能的更改也是非常理想的。一旦有了算法的运行版本，您就可以创建更大的测试问题，在其中测量性能并将其自动化为性能/集成测试。您可以降低运行频率，因为它们会花费更多时间，但至少会尽早通知您重构过程中新引入的性能瓶颈或向算法添加新功能