单元测试近似算法

Question

我正在开发一个基于一些流行的Python包的开源图形和网络近似算法库。主要目标是包含最新的图形和网络NP完全问题的近似算法。原因在于1）我还没有看到一个很好（现代化的）综合套件来覆盖这个领域，2）它将是一个很好的教学工具，用于学习NP难优化问题上的近似算法。

在构建这个库时，我使用单元测试进行检查（像任何合格的开发者一样）。由于近似算法的本质，我对我的单元测试有些谨慎，因为它们可能无法返回正确的解决方案。目前，我通过手动解决一些小实例，并确保返回结果与之匹配来进行检查，但这不是理想的，在实现方面也不可扩展。

什么是对近似算法进行单元测试的最佳方法？生成随机实例并确保返回的结果小于算法所保证的界限？那似乎会有虚假阳性（测试只是那次运行幸运，不能保证所有实例都在界限以下）。

- Nicholas Mancuso

---

如果你为NP完全问题生成“随机实例”，那么你如何知道真正的答案以便测试边界？在我看来，你仍然需要仔细选择测试用例。选择一些你可以作为人类眼睛看出真正答案的情况，但这可能会对近似算法构成困难或至少进行测试。这样的情况仍然可以通过编程方式生成，以便足够大并具有现实意义。它们只是不应该是“随机”的。 - Ray Toal

在@Ray Toal的评论基础上，有一些种类的难题如果你生成了问题，就会变得容易；例如，分解pq是困难的，除非你已经知道p和q因为你生成了它们。类似的原则是否可以应用于您的图形/网络问题？ - Tom Zych

+1 汤姆，这正是我所说的通过编程生成已知案例。目前我有些犹豫是否要回答，因为我不是这个领域的权威；也许会有经验丰富的人前来解答。我只是想在“随机”一词周围发出警告。 - Ray Toal

Answer 1

你需要分离两个问题：近似算法的质量和实现这些算法的正确性。

测试近似算法的质量通常不适用于软件开发中使用的单元测试方法。例如，您需要生成具有代表实际问题大小的随机问题。您可能需要进行数学工作以获取一些上下界来判断无解大实例的算法质量。或者使用已知或最佳解决方案的问题测试集，并比较您的结果。但是，在任何情况下，单元测试都无法帮助您改进近似算法的质量。这就是您在优化和数学方面的领域知识将有所帮助的地方。

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

另外一个切割这两个部分的问题是性能。您无法可靠地使用小型玩具问题测试性能。同时，快速实现使性能显着下降的更改非常有用。一旦您拥有算法的运行版本，就可以创建更大的测试问题来测量性能，并将其自动化为性能/集成测试。您可以较少经常地运行它们，因为它们需要更多的时间，但至少会在重构或算法新功能添加期间尽早通知您新引入的性能瓶颈。

- derdo

Answer 2

检查生成的解的有效性是显然的第一步。

此外，攻击的一个角度可能是使用已知期望近似解的实例进行回归测试（例如通过手动执行算法或使用同一算法的其他人的实现获得）。

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

如果对于所讨论的算法存在已知的上界，则生成许多随机实例并将启发式解与上界验证可能会产生成果。如果您确实这样做，我建议您使运行可重复（例如始终使用相同的随机数生成器和种子）。

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

- NPE

Answer 3

通常情况下，你可以检查一些东西 - 比如说，你的算法是否总是返回满足其约束条件的解，即使它们不是最优的。你还应该在每个可能的机会上放置断言检查 - 这些将是特定于你的程序的，但可能会检查某些数量是否被保留，或者某些应该增加或最坏情况下保持不变的东西没有减少，或者某些所谓的局部最优确实是局部最优。

在进行这些类型的检查以及你已经提到的边界检查之后，我更喜欢在大量随机生成的小问题上运行测试，使用随机种子选择，以便如果它在问题102324上失败，你可以重复那个失败以进行调试，而不必运行前面的102323个问题。通过大量的问题，你增加了一个潜在的错误将导致一个明显的错误来失败你的检查的机会。通过小问题，你增加了找到和修复错误的机会。

- mcdowella