3

想要了解更多关于 GA 的愿望再次燃起，与其大量阅读却无所事事，我决定从另一个方向开始：选择一个问题并尝试解决它。

我选择了魔方问题。为了编码染色体，我使用Permutation Encoding，以及Mutation()和NewChild(parent1, parent2, pivot)的以下方法。

我的选择算法有点奇怪，是根据网上找到的例子改编的。

分数是根据行/列/对角线之和与魔术常数之差的平方计算的，如下所示。

我注意到它收敛速度非常快，一旦达到 1..7 的分数（越少越好）就停止改进。

我认为这是：它达到了局部最优，一个潜在的井，如果你可以这样称呼它，并且不会因为突变不够不同而跳过附近的山丘？
在此处输入图像描述

我尝试将突变率更改为 5 - 80%，在染色体种群中留下 10-20% 的精英群体，将种群大小从 16-32 条染色体改变，但没有运气。

我究竟做错了什么？我可以使用哪些改进来使总体得分收敛到零？

如果需要，我可以发布完整的源代码，如果有人觉得它有用或想玩它。

更新：这是一个大小为 5 的立方体的收敛速度，交叉率为 60%，突变率为 10%：

在此处输入图像描述

4

2 回答 2

3

对此没有硬性和快速的答案，但我建议将你的精英主义减少到不超过 5% 并增加你的人口规模。我不太明白您的 getPermutation() 调用是如何选择潜在候选人的，但随着人口规模的增加，我也会增加锦标赛的规模（选择算法中的第 8-16 行）。如果您陷入局部最优状态，则意味着您的突变功能跳得不够远，或者您的种群一开始就没有足够的多样性。

希望对你有帮助，祝你好运！

于 2011-12-14T02:06:37.960 回答
2

在这种情况下，我使用了具有良好结果的亚群。您基本上将算法运行 n 次并在每次运行中选择最佳个体。有了这些，您就形成了一个初始种群（而不是像通常的运行那样随机初始化）并再次运行 ga。最后一次运行中的起始个体通常以不同的方式处于次优状态，并且由于它们都或多或少具有相同的适应度，因此当它们组合在一起时，它们倾向于将彼此从局部最小值中拉出来。在这里使用精英主义也是一个好主意，以免轻易失去已经进化的个体。

于 2012-01-05T10:59:02.493 回答