logo标签列表

如何测试遗传算法？

unit-testinglanguage-agnosticgenetic-algorithmnon-deterministic
54

我曾经制作过一些遗传算法；它们有效（能快速找到合理的解）。但我现在发现了TDD。是否有一种方式可以以TDD的方式编写遗传算法（这种算法严重依赖于随机数）？

更普遍地说，如何测试一个非确定性的方法/函数。以下是我的想法：

  1. 使用特定种子。如果我在代码中犯了错误，这种方法将无济于事，但可以帮助在重构时发现错误。

  2. 使用已知的数字列表。类似于上面的方法，但我可以手动跟踪代码（这将非常繁琐）。

  3. 使用恒定的数字。至少我知道可以期望什么结果。确保骰子总是读取6，当RandomFloat(0,1)始终返回1时，这将是有益的。

  4. 尽量将非确定性代码从GA中移出。这似乎很愚蠢，因为那是其核心目的。

也欢迎提供有关测试的优秀书籍的链接。

10个回答
14

在我看来，测试它的一致逻辑的唯一方法是应用一致输入，... 或将每个迭代视为单个自动机，测试其状态在该迭代之前和之后，基于确定性迭代值将整个非确定性系统转化为可测试的组件。

对于变化/交叉/属性继承的迭代，测试每个迭代边界上的值，并基于成功的迭代子测试的已知输入/输出测试所有迭代的全局输出...

由于算法是迭代的，因此您可以使用归纳在测试中确保它适用于1个迭代、n+1个迭代，以证明它将为给定的输入范围/域和输入可能值的约束条件生成正确的结果（无论数据是否确定）。

编辑我发现这篇测试非确定性系统的策略，这可能会提供一些见解。一旦TDD/开发过程证明逻辑是正确的，它可能有助于对实时结果进行统计分析。

1
谢谢您的回答。我原本希望有什么万能方案，但我认为这并不是一件容易测试的事情。如果我仔细地选择随机数，就可以测试每个执行路径。我还将进行一个已知适应性景观的测试，以便了解它的表现如何。 - James Brooks
@James，只要记住在非确定性算法中，“测试逻辑”和“测试预期结果”之间有明显的区别。先做一件事，再做另一件事。如果第一个出了问题，第二个就没有意义了。 - Aiden Bell
4
我会通过多次测试随机函数并分析返回值的分布是否符合统计预期来进行测试（这需要一些统计知识）。
这难道不仅仅是评估值的分布是否符合正态分布，而不是算法在正确分布周围的适应性吗？如果一个算法有问题，那么无论你运行多少次它都还是有问题的。如果它只是搜索结果，那就像检查结果中包含关键字作为搜索顺序的验证一样。 - Aiden Bell
我并没有说正态分布，我是说分布应该符合统计期望，即如果你需要一个随机函数返回例如玻尔兹曼分布对应的随机值，你应该检查是否有足够数量的测试运行形成这样的分布。 - Svante
我明白了。我认为这对于TDD来说可能有点容易出错。我甚至认为，基于图形的统计分析（如我链接的论文中所述）不应该是逻辑单元/功能测试的首要选择，而应该是针对实时数据结果的测试。 - Aiden Bell
2
我对遗传算法非确定性函数进行单元测试的方法之一是将随机数的选择放在逻辑中使用该随机数的另一个函数中。
例如，如果您有一个函数，它接受一个基因（某些向量）并获取基因的两个随机点以对它们进行某些操作（变异或其他操作），您可以将生成随机数的过程放在一个函数中，然后将其与基因一起传递到另一个包含该数字的逻辑的函数中。
这样，您就可以使用逻辑函数进行TDD，并传递特定的基因和特定的数字，确切地知道在给定数字的情况下逻辑应该对基因进行什么操作，并能够编写修改后的基因的断言。
另一种测试生成随机数的方法是将其外部化到另一个类中，该类可以通过上下文访问或从配置值中加载，并为测试执行使用不同的类。该类将有两个实现，一个用于生产，生成实际的随机数，另一个用于测试，将接受稍后要生成的数字的方式。然后在测试中，您可以提供该类将提供给被测试代码的某些数字。
2
如果您在谈论TDD，我建议一定要从选取一个固定的数字开始，并从那里逐步扩展您的测试套件。我曾经在几个高度数学化的问题上进行过TDD，从一开始就有几个您知道并且已经手动解决的常量案例可以使用。
关于你提到的第四点，将不确定性代码移出GA，我认为这可能是值得考虑的方法。如果您可以分解算法并分离不确定性问题，则应该使测试确定性部分变得简单明了。只要您小心命名事物，我认为您在这里牺牲的并不多。除非我误解了您的意思，否则GA仍将委托给此代码，但它存在于其他地方。
至于（开发人员）测试的非常好的书籍链接，我的收藏包括：
1

最易测试的部分是适应度函数，这里包含了所有的逻辑。在某些情况下，这可能相当复杂（您可能会根据输入参数运行各种模拟），因此您需要确保所有这些内容都可以通过大量单元测试来验证，并且这项工作可以遵循任何方法。

关于测试GA参数（变异率、交叉策略等），如果您自己实现这些东西，您肯定可以进行测试（您可以再次对变异逻辑等进行单元测试），但您将无法测试GA的“微调”。

换句话说，您将无法通过找到的解的好坏以外的方式测试GA的实际表现。

1
你可以编写一个冗余的神经网络来分析算法的结果，并根据预期的结果对输出进行排序。:)
尽量将方法拆分得更细致一些。然后，你还可以围绕随机部分编写单元测试，以检查值的范围。甚至可以多次运行该测试，看结果是否会变化。
1
你所有的函数都应该是完全确定性的。这意味着你正在测试的函数中不应该生成随机数。你需要将其作为参数传递。这样，当你的程序基于你的随机数做出决策时，你可以传入代表性数字来测试该数字的预期输出。唯一不确定的是你实际的随机数生成器，但你不需要太担心它，因为你不应该自己编写它。只要它是一个已经建立的库，你就可以假设它能正常工作。
这是针对你的单元测试。对于集成测试，如果你正在进行这样的测试，你可能需要考虑模拟你的随机数生成，用一个算法替换它，为你需要生成的每个随机数返回从0到n的已知数字。
1
我写了一个C# TDD遗传算法教学应用程序： http://code.google.com/p/evo-lisa-clone/ 让我们来看看应用程序中最简单的随机结果方法：PointGenetics.Create，它根据边界创建一个随机点。对于这个方法，我使用了5个测试，其中没有一个依赖于特定的种子。

http://code.google.com/p/evo-lisa-clone/source/browse/trunk/EvoLisaClone/EvoLisaCloneTest/PointGeneticsTest.cs

随机性测试很简单：对于一个大的边界（许多可能性），连续生成的两个点不应该相等。其余的测试检查其他约束条件。
1
谢谢回复，我稍后会查看代码。我已经完成了测试，并使用了与您类似的方法。我测试了一些我知道应该发生的事情，当我为我的“随机”数字指定特定值时。然后，我检查了在10,000次试验中分布是否接近我预期的结果。虽然不完美，但已经足够了。 - James Brooks
0
我强烈建议你在单元测试中使用模拟对象（http://en.wikipedia.org/wiki/Mock_object）。你可以使用它们来模拟那些进行随机猜测的对象，以便让你得到预期的结果。
0

一个测试算法在相同输入下是否给出相同结果的方法可以帮助你，但有时你会进行更改，这些更改会改变算法的结果选择行为。

我会尽最大努力进行测试，以确保算法给出正确的结果。如果算法对于一些静态种子和随机值都能给出正确的结果，那么算法就是有效的或者说没有因为所做的更改而出现问题。

TDD 中的另一个机会是评估算法的可能性。如果您可以自动检查结果的好坏，您可以添加测试来显示更改没有降低结果的质量或不合理地增加计算时间。

如果您想使用许多基础种子测试您的算法，您可能需要有两个测试套件：一个套件用于每次保存后运行快速测试以确保您没有破坏任何东西，另一个套件用于稍后进行更长时间的评估。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接