遗传算法 - 收敛
Genetic Algorithm - convergence
我有几个关于我的遗传算法和 GA 的问题。
我创建了一个 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/
编辑：
看起来 Thomas 的建议很有效，我得到了非常快的结果，并且过早收敛的情况更少。我觉得增加基因库会带来更好的结果，但我不确定它是否真的在每一代都变得更好，或者它是否是随机的这一事实允许它找到正确的解决方案。
编辑 2：
按照 Thomas 的建议，我能够让它正常工作，似乎我在获得幸存者和扩大我的基因库方面遇到了问题。另外，我最近在我的 GA 测试中添加了常量，如果有人想看的话。
我没有时间深入研究你的代码，但我会尝试根据我对 GA 的记忆来回答：
Sometimes I will give it points that will never produce a function, or will sometimes produce a function. It can even depend on how deep the initial trees are.
我不确定这里的问题是什么，但如果你需要一个结果，你可以尝试 select 提供到给定点的最小距离的函数（可以是总和、平均值、点数等，具体取决于您的需要）。
Why does the tree depth matter in trying to evaluate the points and produce a satisfactory function?
我不确定你指的是什么树深度，但它可能会影响两件事：
- 准确性：即深度越高，解决方案可能越准确，或者给出突变的可能性就越大
- 性能：取决于你指的是什么树，更高的深度可能会提高性能（允许对函数进行更有根据的猜测）或降低性能（需要生成和比较更多的解决方案）。
Why do I sometimes get a premature convergence and the GA never breaks out if the cycle?
这可能是因为突变太少了。如果您有一组解决方案都围绕局部最优值收敛，那么只有轻微的突变可能无法将生成的解决方案从局部最优值移到足够远的地方才能突破。
What can I do to prevent a premature convergence?
您可以允许更大的突变，例如当解决方案开始收敛时。或者，您可以将全新的解决方案加入其中（将其视为 "immigration"）。
What about annealing? How can I use it?
退火可用于在解决方案开始收敛于某个 point/optimum 后逐渐改进您的解决方案，即与 "random" 突变相比，您可以以更可控的方式改进解决方案。
您还可以使用它来突破局部最优，具体取决于它们的分布方式。例如，您可以使用 GA 直到解决方案开始收敛，然后使用退火 and/or 更大的突变 and/or 全新的解决方案（您可以使用不同的方法生成几组解决方案并在最后比较它们)，创建你的新种群，如果收敛被破坏，则使用 GA 开始新的迭代。如果解决方案仍然收敛于相同的最优值，那么您可以停止，因为预计不会有更大的改进。
除此之外，启发式算法可能仍会达到局部最优，但这是它们提供的权衡：性能与准确性。
为了避免过早收敛，您还可以使用多个子种群。每个亚种群都将独立进化。在每一代结束时，您可以在子种群之间交换一些个体。
我用多个亚群实现了一个遗传编程变体：http://www.mepx.org/source_code.html
我有几个关于我的遗传算法和 GA 的问题。
我创建了一个 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/
编辑： 看起来 Thomas 的建议很有效，我得到了非常快的结果，并且过早收敛的情况更少。我觉得增加基因库会带来更好的结果，但我不确定它是否真的在每一代都变得更好，或者它是否是随机的这一事实允许它找到正确的解决方案。
编辑 2： 按照 Thomas 的建议，我能够让它正常工作，似乎我在获得幸存者和扩大我的基因库方面遇到了问题。另外，我最近在我的 GA 测试中添加了常量，如果有人想看的话。
我没有时间深入研究你的代码，但我会尝试根据我对 GA 的记忆来回答：
Sometimes I will give it points that will never produce a function, or will sometimes produce a function. It can even depend on how deep the initial trees are.
我不确定这里的问题是什么，但如果你需要一个结果，你可以尝试 select 提供到给定点的最小距离的函数（可以是总和、平均值、点数等，具体取决于您的需要）。
Why does the tree depth matter in trying to evaluate the points and produce a satisfactory function?
我不确定你指的是什么树深度，但它可能会影响两件事：
- 准确性：即深度越高，解决方案可能越准确，或者给出突变的可能性就越大
- 性能：取决于你指的是什么树，更高的深度可能会提高性能（允许对函数进行更有根据的猜测）或降低性能（需要生成和比较更多的解决方案）。
Why do I sometimes get a premature convergence and the GA never breaks out if the cycle?
这可能是因为突变太少了。如果您有一组解决方案都围绕局部最优值收敛，那么只有轻微的突变可能无法将生成的解决方案从局部最优值移到足够远的地方才能突破。
What can I do to prevent a premature convergence?
您可以允许更大的突变，例如当解决方案开始收敛时。或者，您可以将全新的解决方案加入其中（将其视为 "immigration"）。
What about annealing? How can I use it?
退火可用于在解决方案开始收敛于某个 point/optimum 后逐渐改进您的解决方案，即与 "random" 突变相比，您可以以更可控的方式改进解决方案。
您还可以使用它来突破局部最优，具体取决于它们的分布方式。例如，您可以使用 GA 直到解决方案开始收敛，然后使用退火 and/or 更大的突变 and/or 全新的解决方案（您可以使用不同的方法生成几组解决方案并在最后比较它们)，创建你的新种群，如果收敛被破坏，则使用 GA 开始新的迭代。如果解决方案仍然收敛于相同的最优值，那么您可以停止，因为预计不会有更大的改进。
除此之外，启发式算法可能仍会达到局部最优，但这是它们提供的权衡：性能与准确性。
为了避免过早收敛，您还可以使用多个子种群。每个亚种群都将独立进化。在每一代结束时，您可以在子种群之间交换一些个体。
我用多个亚群实现了一个遗传编程变体：http://www.mepx.org/source_code.html