16

我们有几种不同的优化算法，每次运行都会产生不同的结果。例如，优化的目标可能是找到函数的最小值，其中 0 是全局最小值。优化运行返回如下数据：

[0.1, 0.1321, 0.0921, 0.012, 0.4]

这非常接近全球最小值，所以这没关系。我们的第一种方法是只选择一个阈值，如果结果太高，则让单元测试失败。不幸的是，这根本不起作用：结果似乎具有高斯分布，因此，尽管不太可能，但有时即使算法仍然很好而我们运气不好，测试也会失败。

那么，我该如何正确测试呢？我认为这里需要相当多的统计数据。同样重要的是测试仍然很快，只是让测试运行几百次然后取平均值会太慢。

以下是一些进一步的说明：

  • 例如，我有一个算法可以将一个圆拟合到一组点中。它非常快，但并不总是产生相同的结果。我想写一个单元测试来保证在大多数情况下它已经足够好了。

  • 不幸的是，我无法为随机数生成器选择固定种子，因为我不想测试算法是否产生与以前完全相同的结果，但我想测试类似“90% 确定我得到 0.1 或更好的”。

4

7 回答 7

15

听起来您的优化器需要两种测试：

  1. 测试算法的整体有效性
  2. 测试算法实现的完整性

由于该算法涉及随机化，因此 (1) 难以进行单元测试。随机过程的任何测试都会在一定比例的时间内失败。您需要了解一些统计数据才能了解失败的频率。有一些方法可以在测试的严格程度和失败的频率之间进行权衡。

但是有一些方法可以为 (2) 编写单元测试。例如，您可以在运行单元测试之前将种子重置为特定值。那么输出是确定性的。这不允许您评估算法的平均有效性，但这是针对 (1) 的。这样的测试将充当绊脚石：如果有人在维护期间将错误引入代码中，则确定性单元测试可能会捕获该错误。

可能还有其他可以进行单元测试的东西。例如，也许无论随机部分发生什么，您的算法都可以保证返回某个范围内的值。也许一些价值应该总是积极的，等等。

更新：我在 Beautiful Testing 一书中写了一个关于这个问题的章节。请参阅第 10 章：测试随机数生成器。

于 2009-01-14T14:19:05.310 回答
7

单元测试不应该有未知的通过/失败状态。如果您的算法在多次使用相同的输入运行时返回不同的值，那么您可能在算法中做了一些奇怪的事情。

我将采用 5 种优化算法中的每一种并对其进行测试，以确保在给定一组输入 x 的情况下，您每次都能获得优化的 y 值。

编辑：要解决系统的随机组件，您可以引入传递种子以供使用的随机数生成器的能力，或者您可以利用模拟库（ala RhinoMocks）强制它在以下情况下使用特定数字RNG 被要求提供一个随机数。

于 2009-01-14T14:02:34.627 回答
7

您的算法可能有一个随机分量。把它控制住。

你可以

  1. 允许调用者选择随机数生成器的种子。然后在测试中使用硬编码的种子。
  2. 让调用者提供一个随机数生成器。然后在测试中使用假随机数生成器。

第二个选项可能是最好的，因为这将使您更容易推断算法的正确结果是什么。

在对算法进行单元测试时，您要验证的是您是否正确实现了算法。不是算法是否做了它应该做的事情。单元测试不应将被测代码视为黑盒。

您可能希望有一个单独的“性能”测试来比较不同算法的执行方式（以及它们是否真的有效），但您的单元测试实际上是为了测试您的算法实现。

例如，在实现 Foo-Bar-Baz 优化算法 (TM) 时，您可能不小心写成了 x:=x/2 而不是 x:=x/3。这可能意味着该算法运行速度较慢，但​​仍会找到相同的算法。您将需要白盒测试来发现这样的错误。

编辑：

不幸的是，我无法为随机数生成器选择固定种子，因为我不想测试算法是否产生与以前完全相同的结果，但我想测试类似“90% 确定我得到 0.1 或更好的”。

我看不到任何方法可以进行自动验证和随机的测试。如果您想有任何机会将真实错误与统计噪声区分开来，尤其如此。

如果您想测试“有 90% 的把握，我会得到 0.1 或更好的结果”，我会建议如下：

double expectedResult = ...;
double resultMargin = 0.1;
int successes = 0;
for(int i=0;i<100;i++){
  int randomSeed = i;
  double result = optimizer.Optimize(randomSeed);
  if(Math.Abs(result, expectedResult)<resultMargin)
    successes++; 
}
Assert.GreaterThan(90, successes);

（请注意，此测试是确定性的）。

于 2009-01-14T14:12:31.503 回答
5

让测试运行，如果其中任何一个失败，只重新运行这些测试50 次，看看它们失败的时间比例。（当然，以自动化的方式。）

于 2009-01-14T13:56:23.780 回答
1

我建议，与其针对产生高斯分布的代码运行测试，不如创建一个多次运行该方法的蒙特卡罗类型算法，然后使用适当的分布模型测试结果的整体分布。例如，如果它是一个平均值，那么您将能够针对一个固定阈值进行测试。如果它更复杂，您将需要创建对适当分布建模的代码（例如，值 < x 是否占我结果的 y%）。

请记住，您不是在测试数字生成器，而是在测试生成值的单元！

于 2009-01-14T14:27:13.500 回答
1

感谢所有答案，我现在正在这样做：

  1. 运行测试 5 次并取中值结果。
  2. 如果中值结果低于某个阈值，则测试成功。
  3. 如果阈值失败，请再次测试，直到达到阈值（测试成功）或直到我完成了如此多的迭代（大约 100 次左右），我可以非常确定中位数不再低于阈值。

这样，每当一个测试看起来要失败时，它就会经常重新计算，直到它非常确定它确实失败了。

这似乎可行，但我不太满意，因为我只测试中值结果。

于 2009-01-15T07:36:13.160 回答
0

jUnit 和 NUnit 都可以断言具有容差/增量值的浮点数据类型。即您测试输出是否是正确的值，给出或取一些小数。在您的情况下，您要检查的正确值是 0，如果您希望给定输出中的所有值都通过（或 0.20，公差为 +/-0.20），则公差为 0.5。

由于结果的随机性，您可能需要对算法的某些部分进行单元测试，以确保它确实完成了预期的工作。

于 2009-01-14T14:27:58.930 回答