9

这真是所有的称号,但在这里是一个任何人破坏谁是有兴趣在进化算法:进化算法:最优复育故障

在EA,基本前提是,你随机生成一定数量的生物体(它们实际上只是一组参数),针对问题运行它们,然后让最优秀的员工生存下来。

然后与幸存者的杂种,幸存者的突变,也一定数量的新的随机生物的组合重新填充。

做了几千次,高效生物。

还有些人不喜欢的东西引入多个生物的“岛”,这是被允许在一段时间配种一次单独的群体。

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

我一直保持前10%的表演,并用30间%的杂种和30点%的突变再植。其余的30%用于新生物体。

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

这并不意味着这正是EA可以解决的问题类型。你知道有人试过吗?

在此先感谢!

+0

附注:你有没有考虑过很多基于比赛的选择技术? – Sean 2008-09-27 04:28:03

回答

6

我最初试图模拟我认为有机系统是什么样的。最终决定这样做并不好,并且更加积极,保留10%,20%突变,60%杂交和10%随机。

然后我发现我的前10%都大致相同。所以我把随机数增加到了30%。这帮助了一些,但并不多。

我确实尝试过多个岛屿,跳跃和重新种植,这些都给出了更好的结果,但仍然非常不令人满意,前10%的变化很小,几代人都疯狂地获得任何结果。大部分代码都学会了如何破解我的健身评估。

要得到最佳表现者真的很容易,所以不要担心让他们太多。杂交有助于减少积极和消极的特征,因此它们很有用,但真正想要得到的却是很多随机育成的杂交品种。专注于突变和新随机引入特征,让杂交种和优秀表演者只是追踪最好的并且更慢地改进它们。 IE:基于上一代的东西只是找到一个更好的本地最大值,随机找到更好的全局最大值。

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

也许是最好的答案是,只要运行它,并调整它,不要害怕调整它相当严重,人口是稳健的。确保你实现了一种保存和继续的方式。

0

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

但是,通常我保留前12%和28%杂交;其他各为30%。

7

我遇到了GA和EA最好的资源是在Genetic Programming约翰·科萨的书。他深入讨论了这一主题 - 编码基因组的技术,随机变异,育种,调整适应度函数。

就我个人而言,我只写了一小部分模拟器用于教学目的。我发现的是,我如何调整这些百分比与我使用的适应度函数的细节有关,我引入了多少随机变异,以及我试图做出突变和育种的'聪明' - 我发现较少'聪明'我尝试做出变异和交叉逻辑,人口提高其健康评分的速度越快 - 我也发现我对变异的概率过于保守 - 我的初始运行达到当地最大值,并有一个很难摆脱他们。

没有这个给你具体的答案,但我不认为有具体的答案,GA是其性质不可预测和调整这些类型的参数可能仍然是一个有点艺术。当然,你总是可以尝试一个meta-GA,使用这些参数作为染色体,寻找能够在你正在运行的基础遗传算法中产生更快适应性的设置。

取决于你想获得'元'的方式。

4

这是一个引起激烈争论(在文学和Melanie, et al books)这似乎是非常特定领域的话题。对于具有n个参数的一种类型的问题,适用于另一个问题,另一个域或另一个参数集几乎不适用。

所以,作为TraumaPony建议,自己调整它为你解决每个问题或写东西来优化它。您可以做的最好的事情是跟踪所有“旋钮旋转”和微调实验,以便绘制出解决方案的地形并感受如何在该空间内快速优化。另外尝试像爬山这样的替代技术,这样你可以有一个基线击败。

@Kyle伯顿:交叉与突变率也每班交给了天然气和全科医生的问题constantly debated

2

假设您有一种方法可以量化前X%的表现者,我建议您不要使用硬编码的阈值,而是分析表现分布并使其在第一次主要表现下降的范围内进行分析,然后调整你的crossbreads,突变和新生物来填补空白。这样,如果你有一个非常“富有成果”的运行,其中很多变化是成功的,你不会抛出大量的高绩效者。此外,如果你有一个“非生产性”的运行,你可以取消更多的现有生物,转而使用更多更新的生物体,以取代它们。

+1

有趣的 - 所以你可以摆动你的阈值一点。的确,有时候一场糟糕的比赛会造成一种冰河时代效应,杀死许多非常聪明的有机体。我想你可以说这是这个过程的一部分,但是,呃?有点像蟑螂如何在核冬天生存。 – 2008-09-25 14:06:46

+0

我其实从事建模和仿真工作,而不是从事遗传编程工作,但当我们想要一个模型到达最终状态时,这就是我们所采取的方法,但我们不知道将会到达的起始状态。 – 2008-09-26 01:06:10

1

有似乎是一些答案使用第二GA确定为第1 GA最佳参数表明,没有提到如何确定第二最佳参数。我不禁想知道那些暗示这种方法的宗教信仰...

2

我已经取得了一些成功,由一对夫妇从父染色体的基因突变的设置和交叉增加种群的多样性。

这个工作,直到突变率下降到零;因为可能会有一个周期性的进化压力来做到这一点,所以你应该尝试确保这些基因具有最低的速度。

实际上,我选择了一个多染色体基因型。一个染色体编码为另一个的生殖功能。较小的“繁殖染色体”对突变和交叉具有明显的固定比率。

我发现这会阻止经典的高原和人口的收敛。

另外,我倾向于为每个孩子都做交叉和变异。

对于世代的GAs,我试图完全避开精英主义,但是从多个岛屿填充的情况下,我保留每个岛屿的顶级精英。当这些岛屿聚集在一起时,精英们可以一起滋生。

1

正如其他人所说,最佳组合取决于您的具体问题以及其他问题特定因素,例如解决方案空间的大小。

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

就您的实际问题而言,没有明确的方法来处理它,但取决于你的问题,你可能想强调随机性或不重视它。当你想强调它时,你应该保持较少的个体完整,并引入更多的新随机个体。如果您的解决方案空间中存在许多本地最大值,并且希望进行更广泛的搜索,则通常会这样做。

当你得到一个分解时,有几件事情需要考虑...重复一次(在顶级近亲繁殖中有很多相同的或新近相同的人)。为了减少这种情况,你可能想要在世代之间扫过你的人群,并用新的随机个体或杂种个体代替重复。

也就是说,我目前的做法是保持最高1%,杂交前20%进入新的20%,杂交前20%进入前40%,杂交前90%产生未来20 %,随机生成其余(39%)。如果有重复,我删除它们并用新的随机个体替换它们。

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