代码之家 › 专栏 › 技术社区 › Andrey Proskurin

有没有办法改进我的遗传算法?

genetic-algorithm artificial-intelligence algorithm

Andrey Proskurin · 技术社区 · 7 年前

我对GA感兴趣,想做我自己的。
这就是我要完成的任务:
我有一个“世界”16x16字段。我创建了16个随机基因的机器人。每个基因是一个由1-19之间的4个数字组成的数组(16-19将改变机器人的方向,1-15是机器人将在指定方向上移动的字段数量)。在这个词中,我采取了一个随机的位置,并试图使从引导机器人到目标的距离尽可能小。

我创建新一代的方式:

挑选8个距离最短的机器人,并将其放入下一代(无交叉)
为我在“1”中挑选的8个最佳机器人进行交叉(因此我得到了8个新机器人)
随机变异2个交叉机器人,并最终将其放入下一代。现在我有16个新一代机器人。

问题是:在我所有的尝试中,只有1/100的距离==0。但我经常得到距离1和2(我等到第1000代,然后放弃,再试一次) 有没有办法改善这一点?还是说GA不可能做得更好?

3 回复 | 直到 6 年前

Richard 7 年前

有很多事情都出了问题。

一些一般性意见

遗传算法通常是算法学家的最后手段。您可以在Dijkstra(最适合您的用例)、线性规划、特定约束满足技术和;c全部失败。想必,您之所以使用它们,是因为您想探索这一领域。
使用遗传算法的人很少期望他们能获得全局最优解。“好的”局部最优解通常是你能做的最好的。GA将很容易找到这些问题,但很难找到解决方案。(加州大学伯克利分校(UCBerkeley)的计算机科学家帕帕迪米特里欧(Papadimitriou)表明,事实上,进化并没有最大化适应性,而是基因的可混合性。)

交叉与变异

交叉用于交换已知有效的基因组的大部分。突变可以细化基因组片段。粗略地说,crossover帮助您将两个好的解决方案结合起来,希望这能快速引导您找到更好的解决方案,而变异则探索解决方案附近的空间。

交叉也会破坏一个好的解决方案,因为它会将其分成两部分,而这两部分独立地没有意义,或者将两部分结合起来,产生非感官输出。

在许多情况下,突变足以探索整个空间,尽管速度很慢。你的空间就是这样,因为分数随着距离目标的距离单调下降。在更复杂的空间中,交叉可以帮助您跳过局部极小值之间的障碍。

把它放在一起

我的建议是 在给定的时间内减少种群中的交叉数量 . 最初,交叉可能会帮助您快速获得进展。但是,随着时间的推移,尤其是在模拟接近尾声时,您将需要精细的细化。此技术类似于 simulated annealing .

Community CDub 4 年前

我想根据我在GA方面的经验添加一些东西。在我的研究中,我发现使用“精英选择”来创建N+1代通常也会在解决方案上创建一个平台:确实,你正在严格且非常快速地找到最佳解决方案,但你可以找到一个局部最小值,并在那里保持阻塞状态(见图片中的橙色)。

所以我所做的是:我添加了一个随机性步骤(比最佳元素的交叉和变异更重要),在这个步骤中,解决方案显然更糟糕,但可以产生一个跳转到一个新的最小值,可以是全局最小值(你的零,图像中的绿色跳转)

你能做什么?尝试在N+1代中使用7个最佳元素,然后从N代中随机选取8个元素(可能是最差的)。

Ray 7 年前

是时候调试进化了!

最终解决方案(路径)是什么样的?我想,他们只能去NSEW。如果是这样,那么很容易陷入局部(一个或两个)解决方案。

此外,观察最佳解决方案是如何随时间演变的也很有用。这可能很有见地(而且很有趣!)

祝您调试顺利!