单元测试近似算法

Question

我正在使用一些流行的python软件包作为基础，为图形和网络开发开源的近似算法库。主要目标是涵盖图形和网络上NP完全问题的最新近似算法。原因是：1）我还没有看到涵盖此内容的不错的（现代）合并程序包； 2）这将是学习NP-Hard优化问题的近似算法的理想教学方法。

在构建此库时，我正在使用单元测试进行完整性检查（就像任何适当的开发人员一样）。对于单元测试，我有些谨慎，因为就其本质而言，近似算法可能无法返回正确的解决方案。目前，我正在手工解决一些小实例，然后确保返回的结果与之匹配，但这不是理想的，而且在实现意义上也是不可扩展的。

单元测试近似算法的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的范围？似乎有误报（该时间测试很幸运，不能保证所有实例都在边界以下）。

Answer 1

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

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

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

削减这两个方面的另一个问题是性能。您无法通过玩具问题可靠地测试性能。还非常希望实现一种改变，该改变会迅速降低正在运行的算法的性能。一旦有了运行版本的算法，就可以创建更大的测试问题，在其中可以测量性能并将其自动化为性能/集成测试。您可以较少地运行它们，因为它们将花费更多时间，但至少会在重构或算法的新功能添加时尽早通知您新引入的性能瓶颈

Answer 2

检查生产的溶液的有效性是显而易见的第一步。

此外，可以使用预期近似解决方案的实例来回归测试是已知的（例如，通过手动执行算法或使用其他人对同一算法的实现获得）。

也存在具有已知（最佳）解决方案的问题实例的存储库，例如 TSPLIB 用于类似TSP的问题。也许这些可以被利用。

如果该算法有已知的上限，则生成许多随机实例并针对上限验证启发式解法可能会很有用。如果这样做，我强烈建议您使运行可重复（例如，始终使用相同的随机数生成器和种子）。

最后一点：对于某些问题，平均而言，完全随机的实例很容易找到良好的近似解决方案。具有均匀和独立选择的电弧权重的不对称TSP就是这样的例子。我之所以提及这一点，是因为它可能会影响您的测试策略。

Answer 3

通常可以检查一些内容-例如，即使算法不是最佳算法，算法也始终返回满足其约束的解决方案。您还应该在所有可能的机会上进行断言检查-这些检查将特定于您的程序，但可能会检查是否保留了一定数量，或者应增加的数量或在最坏的情况下不会减少的数量，或者某些假定的局部负载最优确实是局部最优。

鉴于这些检查以及您已经提到的边界检查，我倾向于在大量随机产生的小问题上运行测试，并选择随机种子，以使其在问题102324上失败您可以重复该故障进行调试，而无需先解决102323问题。由于存在大量问题，因此您增加了潜在的错误会导致显而易见的错误而导致检查失败的机会。遇到小问题，您将有更多机会找到并修复该错误。