遗传算法-收敛

Question

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

我创建了一个GA，当给出曲线的点时，它试图找出是什么函数产生了这条曲线。

下面是一个例子

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

函数

x^2

有时我会给它一些永远不会产生函数的点，有时也会产生函数。它甚至可以取决于最初的树木有多深。

几个问题：

• 为什么树的深度在试图评估点和产生令人满意的功能方面很重要？
• 为什么有时我会过早收敛，而如果循环的话，遗传算法就永远不会爆发？
• 我能做些什么来防止过早收敛呢？
• 那退火呢？我该怎么用呢？

您能快速查看我的代码并告诉我是否有明显的问题吗？(这是测试代码，我需要做一些代码清理。)

https://github.com/kevkid/GeneticAlgorithmTest

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

编辑:看起来托马斯的建议很好，我得到了非常快的结果，而且不太早收敛。我觉得增加基因库会带来更好的结果，但我不确定它是否真的比每一代人都好，或者它是随机的这一事实是否能让它找到一个正确的解决方案。

编辑2:按照托马斯的建议，我能够使它正常工作，似乎我在寻找幸存者和扩大基因库方面遇到了问题。另外，我最近在GA测试中添加了常量，如果其他人想看它的话。

Answer 1

我没有时间钻研您的代码，但我将尝试从我记得的气体问题上回答：

有时我会给它一些永远不会产生函数的点，有时也会产生函数。它甚至可以取决于最初的树木有多深。

我不知道这里的问题是什么，但是如果你需要一个结果，你可以试着选择一个函数来提供对给定点的最小距离(可以是和、平均值、点数等等，这取决于你的需要)。

为什么树的深度在试图评估点和产生令人满意的功能方面很重要？

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

• 准确性:也就是说，深度越高，解决方案就越精确，或者提供了更多发生突变的可能性。
• 性能:根据您所指的树的不同，更高的深度可能会提高性能(允许对函数进行更有教养的猜测)或降低性能(需要生成更多的解决方案并进行比较)。

为什么有时我会过早收敛，而如果循环的话，遗传算法就永远不会爆发？

那可能是因为突变太少了。如果您有一组所有的解决方案都聚集在一个局部最优附近，那么只有轻微的突变才可能使最终的解决方案与该局部最优方案相距甚远，从而爆发出来。

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

您可以允许更大的突变，例如，当解决方案开始收敛。或者，您可以将全新的解决方案添加到混合方案中(将is看作是“移民”)。

那退火呢？我该怎么用呢？

当解开始收敛到某个点/最优时，退火可以用来逐步改进你的解，也就是说，你会用比“随机”突变更可控的方式来改进解。

您也可以使用它来突破局部最优，这取决于它们是如何分布的。例如，您可以使用您的GA直到解开始收敛，然后使用退火和/或更大的突变和/或全新的解决方案(您可以用不同的方法生成几组解决方案，并在最后比较它们)，创建新的总体，如果收敛被破坏，使用GA开始新的迭代。如果解决方案仍然收敛在相同的最优，那么你可以停止，因为没有更大的改善是预期的。

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

Answer 2

为了避免过早收敛，您也可以使用多个子种群。每个子种群将独立进化。在每一代人的最后，你可以在子种群之间交换一些个体。

我为一个遗传编程变体( code.html )做了一个具有多个子群体的实现。