9

它真的在标题中,但对于任何对进化算法感兴趣的人来说,这里有一个细分:

在 EA 中,基本前提是您随机生成一定数量的生物体(实际上只是一组参数),针对某个问题运行它们,然后让表现最好的人存活下来。

然后你用幸存者的杂交种、幸存者的突变以及一定数量的新随机生物重新填充。

这样做几千次,高效的有机体就会出现。

有些人还做一些事情,比如引入多个生物“岛”,它们是允许偶尔杂交的独立种群。

所以,我的问题是:最佳的重新填充百分比是多少?

我一直保持前 10% 的表现,并重新填充 30% 的杂交和 30% 的突变。剩下的 30% 用于新生物。

我也尝试了多岛理论,我也对你的结果感兴趣。

我并没有忘记这正是 EA 可以解决的问题类型。你知道有人在尝试吗?

提前致谢!

4

8 回答 8

7

我遇到的关于 GA 和 EA 的最佳资源是 John Koza 关于遗传编程的书籍。他深入探讨了这个主题——编码基因组、随机突变、育种、调整适应度函数的技术。

就我个人而言,我只写了一小部分用于教学目的的模拟器。我发现我如何调整这些百分比与我使用的适应度函数的细节、我引入了多少随机突变以及我尝试进行突变和繁殖的“聪明”程度有关——我发现越少'聪明的'我试图使突变器和交叉逻辑,种群提高其适应度得分的速度越快——我还发现我在突变的概率上过于保守——我的初始运行达到了局部最大值并且有一个很难摆脱他们。

这些都没有给你具体的答案,但我认为没有具体的答案,GA 本质上是不可预测的,调整这些参数可能仍然是一门艺术。当然,您总是可以尝试使用元遗传算法,将这些参数用作染色体,搜索在您正在运行的基本遗传算法中产生更快适应度的设置。

取决于您想要获得的“元”。

于 2008-09-25T02:37:44.970 回答
6

我最初试图对我认为的有机系统进行建模。最终认为这不好,并且变得更加激进,10% 保留,20% 变异,60% 杂交,10% 随机。

然后我注意到我的前 10% 都大致相同。所以我将随机数增加到 30%。这对一些人有所帮助,但帮助不大。

我确实尝试了多岛、跨代和重新播种,这给出了更好的结果,但仍然非常不令人满意,前 10% 的变化非常小,疯狂的世代数以获得任何结果。大多数情况下,代码学会了如何破解我的健身评估。

获得表现最好的人真的很容易,所以不要担心保留太多他们。杂交有助于减少正面和负面的特征,所以它们很有用,但你真正想要的是很多好的随机繁殖。专注于突变和新随机以引入特征,让杂交和表现最好的人只需跟踪最好的并更慢地改进它们。IE:基于上一代的东西只是找到更好的局部最大值,随机数找到更好的全局最大值。

我仍然相信通过观察自然现象可以找到您问题的最佳答案,例如在最近一篇关于果蝇飞行路径随机性的文章中,因此可能会成功。

可能最好的答案是运行它并对其进行调整,不要害怕对其进行大量调整,人口很强大。确保您实施了一种保存和继续的方法。

于 2008-09-25T02:49:25.893 回答
4

这是一个备受争议的(在文学和Melanie 等人的书籍中)主题,似乎是非常特定领域的。适用于具有 n 个参数的一种类型的问题几乎不会适用于另一个问题、另一个域或另一个参数集。

因此,正如 TraumaPony 建议的那样,针对您要解决的每个问题自行调整它,或者编写一些东西来为您优化它。您可以做的最好的事情是跟踪您所有的“旋钮旋转”和微调实验,以便您可以绘制出解决方案的地形并了解如何在该空间内快速优化。还可以尝试其他技术,如爬山,这样你就可以有一个可以击败的基线。

@Kyle Burton:在移交给 GA 和 GP 的每一类问题中,交叉率与突变率也在不断争论。

于 2008-09-25T02:39:18.243 回答
2

假设您有一种方法可以量化前 X% 的执行者,我建议您不要使用硬编码阈值来分析性能分布,并将您的截止值设置在性能第一次主要下降的范围内,然后调整你的杂交、突变和新的有机体来填补空白。这样,如果你有一个非常“富有成效”的运行,其中很多变化都成功了,你就不会抛出大量的高绩效者。此外,如果你有一个“非生产性”的运行,你可以废弃更多现有的有机体,以支持更多应该取代它们的新有机体。

于 2008-09-25T02:43:17.343 回答
2

通过设置来自亲本染色体的几个基因的突变和交叉,我在增加种群多样性方面取得了一些成功。

这一直有效,直到突变率降至零;因为这样做可能会有周期性的进化压力,你应该尝试确保这些基因具有最低速率。

在实践中,我选择了多染色体基因型。一条染色体编码另一条的生殖功能。较小的“繁殖染色体”具有合理的固定突变率和交叉率。

我发现这将阻止经典的高原和人口趋同。

顺便说一句,我倾向于为每个孩子做交叉和突变。

对于世代相传的 GA,我试图完全避开精英主义,但在来自多个岛屿的人口众多的情况下,我会保留每个岛屿的顶级精英。当岛屿聚集在一起时,精英就可以一起繁殖。

于 2009-05-01T14:48:52.427 回答
1

似乎有一些答案建议使用 2nd GA 来确定 1st GA 的最佳参数,而没有提及如何确定 2nd 的最佳参数。我不禁想知道那些建议这种方法的人的宗教信仰......

于 2008-11-12T13:15:40.770 回答
1

正如其他人所提到的,最佳组合将取决于您的特定问题和其他特定问题的因素,例如解决方案空间的大小。

在我们讨论从一代到下一代的进化分解之前,重要的是要考虑每一代的规模。一般来说,我的方法是从相当大的群体(约 100k-500k 个体)开始,这些个体相当多样化,这是 Koza 在他的一些工作中提出的建议。为了从一开始就获得这种多样性,您可以将解决方案空间划分为桶,然后确保至少有一定数量的个体落入每个桶中。(例如,如果您有每个人的树表示,请确保创建相同数量的深度 2、3、...、max_depth)

至于您的实际问题,没有明确的方法来解决它,但根据您的问题,您可能想要强调随机性或淡化它。当你想强调它时,你应该保持较少的个体完整,并引入更多数量的新随机个体。如果您的解决方案空间中有许多局部最大值并且您希望进行更广泛的搜索,您通常希望这样做。

当您获得故障时,需要考虑一些事情......首先,重复(在顶部近亲繁殖中有很多相同或新近相同的个体)。为了减少这种情况,您可能希望在几代人之间扫描您的种群,并用新的随机个体或杂交个体替换重复。

也就是说,我目前的方法是保留前 1%,将前 20% 杂交到新的 20%,将前 40% 杂交到下一个 20%,杂交前 90% 产生下一个 20%,然后随机生成其余的 (39%)。如果有重复,我删除它们并用新的随机个体替换它们。

我不使用突变,因为大量随机个体应该注意在接下来的杂交过程中添加“突变”。

于 2010-11-03T19:36:49.637 回答
0

你知道你能做什么......你可以编写一个遗传算法来确定最佳分布。

但是,通常我会保留前 12% 和 28% 的杂交品种;其他人各占 30%。

于 2008-09-25T02:32:47.323 回答