2

我对我的遗传算法和总体遗传算法有几个问题。

我创建了一个 GA，当给定曲线点时，它会尝试找出产生该曲线的函数。

一个例子是以下几点

{{-2, 4},{-1, 1},{0, 0},{1, 1},{2, 4}}

功能

x^2

有时我会给它一些永远不会产生功能的点，或者有时会产生功能。它甚至可以取决于初始树的深度。

一些问题：

  • 为什么树深度在尝试评估点并产生令人满意的函数时很重要？
  • 为什么有时我会过早收敛，而如果循环，GA 永远不会爆发？
  • 我能做些什么来防止过早收敛？
  • 退火呢？我该如何使用它？

你能快速看一下我的代码并告诉我它是否有明显的问题吗？（这是测试代码，我需要做一些代码清理。）

https://github.com/kevkid/GeneticAlgorithmTest

资源：http://www.gp-field-guide.org.uk/

编辑：看起来托马斯的建议效果很好，我得到了非常快的结果，并且过早收敛。我觉得增加基因库会产生更好的结果，但我不确定它是否真的在每一代都变得更好，或者它是随机的事实是否允许它找到正确的解决方案。

编辑 2：按照 Thomas 的建议，我能够让它正常工作，似乎我在获得幸存者和扩大我的基因库方面遇到了问题。如果其他人想查看它，我最近还在我的 GA 测试中添加了常量。

4

2 回答 2

2

为了避免过早收敛，您还可以使用多个子种群。每个亚群将独立进化。在每一代结束时，您可以在子种群之间交换一些个体。

我为遗传编程变体执行了多个子群体的实现：http ://www.mepx.org/source_code.html

于 2015-08-15T10:47:49.353 回答
1

我没有时间深入研究您的代码，但我会尝试从我记得的关于 GA 的内容中回答：

有时我会给它一些永远不会产生功能的点，或者有时会产生功能。它甚至可以取决于初始树的深度。

我不确定这里的问题是什么，但如果您需要一个结果，您可以尝试选择与给定点的距离最短的函数（可以是总和、平均值、点数等，具体取决于您的需要）。

为什么树深度在尝试评估点并产生令人满意的函数时很重要？

我不确定你的意思是什么树深度，但它可能会影响两件事：

  • 准确性：即深度越高，解决方案可能越准确，或者给出的突变可能性越大
  • 性能：取决于您所指的树，更高的深度可能会提高性能（允许对函数进行更有根据的猜测）或降低性能（需要生成和比较更多的解决方案）。

为什么有时我会过早收敛，而如果循环，GA 永远不会爆发？

这可能是由于突变太少。如果您有一组解决方案都围绕一个局部最优值收敛，那么只有轻微的突变可能不会使最终的解决方案远离该局部最优值以便突破。

我能做些什么来防止过早收敛？

您可以允许更大的突变，例如当解决方案开始收敛时。或者，您可以将全新的解决方案加入其中（将其视为“移民”）。

退火呢？我该如何使用它？

一旦解决方案开始收敛到某个点/最佳值，退火就可以用来逐步改进您的解决方案，即您将以比“随机”突变更可控的方式改进解决方案。

您还可以使用它来突破局部最优值，具体取决于它们的分布方式。例如，您可以使用 GA 直到解决方案开始收敛，然后使用退火和/或更大的突变和/或全新的解决方案（您可以使用不同的方法生成几组解决方案并在最后进行比较），创建您的新种群，如果收敛被破坏，则使用 GA 开始新的迭代。如果解决方案仍然收敛于相同的最优值，那么您可以停止，因为预计不会有更大的改进。

除此之外，启发式算法可能仍会达到局部最优，但这就是它们提供的权衡：性能与准确性。

于 2015-06-17T13:10:11.367 回答