我正在使用一些流行的 python 包作为基础，为图形和网络开发一个开源近似算法库。主要目标是包含针对图和网络上的 NP 完全问题的最新近似算法。这样做的原因是 1）我还没有看到一个很好的（现代）整合包来涵盖这个和 2）这将是一个很好的教学工具，用于学习 NP-Hard 优化问题的近似算法。
在构建这个库时，我使用单元测试来进行完整性检查（就像任何合适的开发人员一样）。我对我的单元测试有些谨慎，因为就其本质而言，近似算法可能不会返回正确的解决方案。目前我正在手动解决一些小实例，然后确保返回的结果与之匹配，但这是不可取的，在实现意义上也不可扩展。
对近似算法进行单元测试的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的界限？这似乎有误报（那个时候测试很幸运，不能保证所有实例都低于界限）。
您需要在这里分离两个关注点。您的近似算法的质量以及这些算法实现的正确性。
测试近似算法的质量通常不适用于软件开发中使用的单元测试方法。例如，您需要生成代表问题实际规模的随机问题。您可能需要做一些数学工作来获得一些上限/下限来判断无法解决的大型实例的算法质量。或者使用具有已知或最知名解决方案的问题测试集并比较您的结果。但无论如何，单元测试对提高近似算法的质量没有多大帮助。这是您在优化和数学方面的领域知识将有所帮助的地方。
实现的正确性是单元测试真正有用的地方。您可以在这里使用玩具大小的问题，并将已知结果（手动解决，或通过代码中仔细的逐步调试验证）与您的代码生成的结果进行比较。有小问题不仅足够，而且在这里也是可取的，这样测试可以快速运行，并且可以在开发周期中运行多次。这些类型的测试可确保整体算法得出正确的结果。它介于单元测试和集成测试之间，因为您将大部分代码作为黑盒进行测试。但我发现这些类型的测试在优化领域非常有用。我建议为此类测试做的一件事是通过随机数生成器的固定种子来消除算法中的所有随机性。这些测试应始终以确定性方式运行，并在 100% 的时间内给出完全相同的结果。我还建议在算法的较低级别模块中进行单元测试。隔离为图形上的弧分配权重的方法，并检查是否分配了正确的权重。隔离您的目标函数值计算函数并对其进行单元测试。你明白我的意思。
削减这两个部分的另一个问题是性能。您无法可靠地测试小玩具问题的性能。还非常希望实现快速显着降低工作算法性能的变化。一旦您拥有了算法的运行版本，您就可以创建更大的测试问题，在其中测量性能并将其自动化为您的性能/集成测试。您可以不那么频繁地运行它们，因为它们会花费更多时间，但至少会在重构期间尽早通知您新引入的性能瓶颈或算法的新功能添加
检查生成的解决方案的有效性显然是第一步。
此外，一种攻击角度可以是使用已知预期近似解的实例进行回归测试（例如，通过手动执行算法或使用其他人的相同算法实现来获得）。
还存在具有已知（最佳）解决方案的问题实例存储库，例如类似TSPLIBTSP 的问题。也许这些可以派上用场。
如果所讨论的算法有已知的上限，那么生成许多随机实例并针对上限验证启发式解决方案可能会证明是富有成效的。如果您这样做，我会敦促您使运行可重现（例如，始终使用相同的随机数生成器和种子）。
最后一点：对于某些问题，完全随机的实例平均而言很容易找到好的近似解。具有统一且独立选择的弧权重的非对称 TSP 就是一个这样的例子。我之所以提到这一点，是因为它可能会影响您的测试策略。
There is usually something you can check - for instance, that your algorithm always returns solutions that satisfy their constraints, even if they are not optimal. You should also put in assertion checks at every possible opportunity - these will be specific to your program, but might check that some quantity is conserved, or that something that should increase or at worst stay the same does not decrease, or that some supposed local optimum really is a local optimum.
Given these sorts of checks, and the checks on bounds that you have already mentioned, I favour running tests on a very large number of randomly generated small problems, with random seeds chosen in such a way that if it fails on problem 102324 you can repeat that failure for debugging without running through the 102323 problems before it. With a large number of problems, you increase the chance that an underlying bug will cause an error obvious enough to fail your checks. With small problems, you increase the chance that you will be able to find and fix the bug.