进化算法:最佳种群细分

时间:2020-03-06 14:42:06  来源:igfitidea点击:

标题中确实包含所有内容,但是对于对进化算法感兴趣的人,这里是一份细分:

在EA中,基本前提是我们随机生成一定数量的生物(实际上只是一组参数),对它们进行处理以解决问题,然后让表现最好的生物生存。

然后,我们将幸存者的杂交,幸存者的突变以及一定数量的新随机生物的组合重新填充。

这样做数千次,就会产生有效的有机体。

有些人还做一些事情,例如引入生物的多个"岛",它们是独立的种群,允许不时杂交。

因此,我的问题是:最佳人口百分比是多少?

我一直保持着前10%的表现,并以30%的杂种和30%的变异来重新填充。剩余的30%用于新生物。

我还尝试了多岛理论,并且我也对我们在此方面的研究结果感兴趣。

EA可以解决的问题类型并没有让我感到困惑。我们知道有人尝试过吗?

提前致谢!

解决方案

我们知道我们可以做什么...我们可以编写遗传算法来确定最佳分布。

但是,通常我会保留前12%的杂种和28%的杂种。其余各占30%。

我在GA和EA方面遇到的最好的资源是John Koza的有关遗传编程的书。他介绍了用于编码基因组,随机突变,育种和调整适应性功能的深度技术主题。

我个人仅出于教学目的编写了少数模拟器。我发现我如何调整这些百分比与我所使用的适应度函数的详细信息,我引入了多少随机突变以及我尝试进行突变和育种的"智能"程度有关,而我发现"聪明",我尝试制作变异器和交叉逻辑,人口提高适应性得分的速度越快,我还发现我对变异的可能性过于保守-我的初始跑步达到了局部最大值,并且很难获得从他们当中。

这些都不能为我们提供具体的答案,但是我认为没有具体的答案,因为GA的性质无法预测,因此调整这些类型的参数可能仍然有些技巧。当然,我们始终可以尝试使用这些参数作为染色体来尝试meta-GA,以寻找在我们正在运行的基本GA中产生更快适应性的设置。

取决于我们想要获得的"元数据"。

这是一个热门话题(在文献和Melanie等人的书中),似乎非常针对特定领域。对具有n个参数的一种类型的一个问题起作用的方法几乎永远不会对另一问题,另一域或者另一参数集起作用。

因此,正如TraumaPony所建议的那样,我们可以针对要解决的每个问题自己进行调整,或者编写一些可以为我们优化的内容。我们要做的最好的事情是跟踪所有"旋钮摆动"和微调实验,以便我们可以绘制解决方案地形图,并获得如何快速在该空间中进行优化的感觉。还可以尝试其他技巧,例如爬山,这样我们就可以掌握基准。

@凯尔·伯顿(Kyle Burton):在移交给GA和GP的每一类问题中,交叉频度与突变率的争论也不断。

假设我们有一种方法可以量化效果最高的X%的广告客户,我建议我们不要使用硬编码的阈值,而是要分析性能分布,并在性能首次出现重大下降的范围内进行调整,然后进行调整交叉面包,突变和新生物填补了这些空白。这样,如果我们进行了非常成功的"成功"运行,并且成功进行了很多变化,那么我们就不会抛出大量的高绩效人才。同样,如果我们进行的是"非生产性"运行,则可以废弃更多的现有生物,转而使用应该取代它们的新型生物。

最初,我尝试对我认为有机系统的模型进行建模。最终认为这不好,并且变得更具攻击性,保留了10%,突变了20%,杂交了60%,随机性是10%。

然后我发现我的前10%的人大致相同。因此我将随机性增加到30%。那帮助了一些,但效果不大。

我确实尝试了多个孤岛,并跳过了几代,然后重新播种,这些结果效果更好,但是仍然非常不令人满意,前10%的极少变化,疯狂的一代人都没有得到任何结果。大多数情况下,代码学习了如何破解我的健康评估。

要获得高绩效人才真的很容易,因此不必担心会留太多的人才。杂种有助于减少正面和负面特征,因此很有用,但真正想要得到的是大量优良的随机育种。着眼于突变和新的随机性以引入特征,让杂种和表现最佳的人只是跟踪最好的,然后慢慢地完善它们。 IE:基于上一代的东西只是找到了更好的局部最大值,随机变量则找到了更好的全局最大值。

我仍然相信,通过观察自然现象,可以找到最佳答案,例如在最近有关果蝇飞行路线随机性的文章中,这样可能会成功。

最好的答案可能是运行它并对其进行调整,不要害怕对其进行相当大的调整,因此人口众多。确保实现一种保存并继续的方法。

似乎有一些答案建议使用第二个GA来确定第一个GA的最佳参数,而没有提到如何确定第二个GA的最佳参数。我不禁对那些建议采用这种方法的人的宗教信仰感到好奇...

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

直到突变率降到零为止,它一直有效。因为这样做可能会有周期性的进化压力,所以我们应该尝试确保这些基因的发生率最小。

实际上,我选择了多染色体基因型。一个染色体编码另一个染色体的生殖功能。较小的"繁殖染色体"具有合理的突变和交叉固定速率。

我发现这将阻止经典的高原时期和人口融合。

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

对于世代的GA,我尝试完全避开精英主义,但是在有多个岛屿居住的地方,我保留了每个岛屿的顶级精英。当这些岛屿聚集在一起时,精英阶层就可以一起繁殖。

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

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

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

当我们得到一份分解报告时,有几件事情需要考虑……对于重复来说(近亲繁殖中许多相同或者新近相同的个体)。为了减少这种情况,我们可能希望遍历各代人,并用新的随机个体或者杂种替代重复个体。

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

我不使用突变,因为大量随机个体应注意在随后的杂交中添加"突变"。