1

我认为不同的机器对此有不同的答案，让我假设这个测试是在同一台机器上进行的。

实际上我在想是否值得对我的一个问题实施遗传算法，我认为它具有大约 20 的组合/排列！（！是factoria，它不是真正的20，它可能或多或少）。

如果数量在允许的范围内，我将使用遗传算法的蛮力（循环遍历所有可能）插入，因为设计 GA 和可能性因子（交叉，突变率）并不容易。

我将如何确定 GA 是否适合问题域？

4

3 回答 3

3

好问题。没有准确的答案，这取决于一些“经验法则”和一些逻辑。

我的建议：

  • 计算一下详尽的搜索需要多长时间。这相对简单，因此值得预先估计。如果搜索空间很大（并且 20！可能足够大......），那么详尽的搜索可能是不切实际的 - 例如，如果每个解决方案只需要 1 毫秒来评估，那么做 20！仍将花费你 7700 万年。即使运行 1000 个内核的并行搜索也需要 7.7 万年。
  • 请记住，GA 通常不会找到最佳解决方案——它们通常会在复杂问题中收敛到“局部最小值”。您需要确定这对于您的需求是否“足够好”（通常是这样）。
  • 考虑到当评估函数的计算量很大时（例如，您必须运行一个小型模拟来评估每个解决方案），GA 会相对更好。这是因为昂贵的评估使得 GA 算法本身的开销基本上无关紧要，而且它是值得的，因为它避免了在搜索空间中对大量不适合的解决方案进行评估。
  • 正如您所指出的，GA 的设置和微调非常棘手- 特别是选择良好的基因型表示和交叉/突变运算符通常会对您的算法的有效性产生巨大影响。您还需要注意如何保持人口的多样性，每一代人的规模有多大等等。这本身就是一个公平的项目，让 GA 运行良好 - 涉及很多“黑魔法”，你只会学习经验。

当然，很可能穷举搜索和 GA 都不适合您的问题。有些问题可以通过其他方法更好地解决，如果你能找到一个使用动态规划或分而治之的智能算法来解决你的特定问题，那么你可能会发现你 7700 万年的穷举搜索实际上可以在一毫秒。一旦问题变得足够大，更好的算法总是会击败原始计算能力。

于 2012-08-14T03:08:09.953 回答
2

我认为您应该调查 Hadooping 或并行化您的解决方案。GA 似乎非常适合这种方法。

像这个：

http://geneticalgorithms.ai-depot.com/Libraries.html

这对我来说比担心你原来的问题更有意义。答案是毫无意义的，因为对您而言唯一重要的衡量标准是循环可以多快处理包含您的代码的主体。

于 2012-08-14T02:37:15.387 回答
1

20！是一个很大的数字。

执行 1 次代码迭代需要多长时间？

您可以简单地使用这个整数增量来计算循环数（甚至使用像手表秒针这样的粗略计时器并在间隔结束时读取总数）。

x=1；do while x!=0 x=x+1 循环

但是您的代码不会这么简单，处理每个循环需要更长的时间，而且这不考虑硬件的处理器速度（这是您主要关心的问题）。像达菲莫所说的那样，有一些环境因素使这个问题变得毫无意义。

祝你好运找到你需要的东西。

于 2012-08-14T02:54:33.163 回答