有办法改进我的遗传算法吗？

Question

我对GA很感兴趣，想做自己的事。

这就是我要完成的任务：

我有一个“世界”16x16字段。我创造了16个随机基因的机器人。每个基因都是一个由1-19个数字组成的数组(16-19将转向机器人方向，1-15是机器人向指定方向移动的字段数量)。在这个词中，我采取一个随机的位置，试图使从领头机器人到目标的距离尽可能小。

我创造新一代的方式：

1. 挑选8个距离最低的机器人，并将它们放入下一代(没有交叉)
2. 为我在‘1’中挑选的8个最好的机器人做交叉操作(所以我得到了8个新的机器人)
3. 随机变异两个交叉的机器人，并最终将他们投入下一代。现在我在新一代中有16个机器人。

问题是:在我所有尝试的1/100中，我只得到距离== 0。但是我经常得到距离1和2(我一直等到第1000代，然后放弃，再试一次)有什么方法可以改进吗？还是不可能用GA做得更好？

Answer 1

有很多事情都出了问题。

关于的一些一般性评论

1. 对于算法家来说，遗传算法通常是最后的选择。当Dijkstra (这对于您的用例最合适)、线性规划、特定的约束满足技术和&c都失败时，您就会使用它们。想必，你使用它们是因为你想探索这个区域。
2. 使用遗传算法的人很少期望它们能实现全局最优解。“好的”本地擎天柱通常是你能做的最好的。GA会很容易地找到这些信息，但是很难将其“归零”在一个解决方案上。(加州大学伯克利分校( UC Berkeley )的计算机科学家帕帕迪米特里欧(Papadimitriou )已经证明，进化实际上并不能最大限度地提高适应性，而是基因的混合能力。)

交叉与突变

交叉是用来交换已知工作的基因组的大部分。突变使基因组的片段细化。粗略地说，交叉可以帮助你将两种好的解决方案结合起来，希望这能很快地引导你找到更好的解决方案，而变异则能探索解决方案附近的空间。

交叉也可以破坏一个好的解决方案，把它分解成两个没有独立意义的部分，或者将两个部分组合在一起，产生一个无意义的输出。

在许多情况下，突变足以探索整个空间，尽管缓慢。这在你的空间里是这样的，因为距离你的目标很远，分数会单调地减少。在一个更复杂的空间里，交叉可以帮助你跨越局部极小值之间的障碍。

把它放在一起

我的建议是，在给定时间的情况下，可以减少种群中交叉的数量，。最初，交叉可能会帮助你获得一些快速的进展。但是，随着时间的推移，尤其是在你的模拟接近尾声的时候，你会想要精致的精致。这种技术类似于模拟退火。

Answer 2

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

所以我所做的是:我增加了一个随机性的步骤(不仅仅是交叉和最佳元素的变异)，在这个步骤中，解决方案显然更糟，但是会产生一个新的最小值，它可以是全局最小值(图像中的绿色跳跃)。

你能做什么？尝试在N+1生成中使用最好的7个元素，而不是从N代中选择一个随机元素(可能是最差的)。

​

​

Answer 3

是时候调试进化了！

最终的解决方案(路径)是什么样子的？我想，他们只能去NSEW。如果是这样的话，那么很容易被困在一个局部的(由一两个)解决方案。

此外，观察最佳解决方案是如何随着时间的推移发展的也是有用的。这可能是非常有洞察力(和有趣的观看！)

祝你调试顺利！