java - 在 GA 中过早收敛

Question

我目前正在研究遗传算法以解决组分配问题（尽可能将学生分配到平衡组）..我已经实现了整个算法，但我不知道它是否会产生高质量的结果。我认为我过早地收敛，因为它从第 10 代左右开始保持相同的解决方案（没有改进）。

我使用了 2-tournmenat 选择并订购了交叉。我尝试设置不同的人口规模、锦标赛规模和突变率，但没有帮助！问题出在哪里？已经一个星期了，我陷入了同样的进度。

有什么建议吗？

Answer 1

一般来说，如果您的 GA 收敛速度过快，您需要注意以下几点：

• 您的突变/交叉率设置是否适当？如果这太低，您的人口将很快停滞不前。
• 您的绩效指标是否合理？如果该指标校准不佳，您最终会为将迅速主导基因库的一组人提供过高的优势。
• 您是否使用了足够的随机数据？如果你正在处理一个非常小的解决方案空间，那么使用 GA 可能没有意义，如果你这样做了，你最终会很快收敛。
• 你的实现真的正确吗？引入一些很难发现的细微逻辑错误真的很容易。我建议使用调试器逐步完成一代，并确保关键点的行为就像你假设的那样。

也就是说，十代并不是完全不合理的。我建议在断言你的 GA 有问题之前确保你的表现确实有问题。

Answer 2

您可能正在快速收敛到局部最大值；这是遗传算法中的一个固有问题。您通常可以通过没有进展的长世代来检测这种状态。

如果是这种情况，可能最简单的解决方案是拯救被困人口并创建一个新人口。希望这个会卡在全局最大值，或者至少是一个不同的局部最大值。然后，您可以比较这两个群体，并保留一个具有更好解决方案的群体。有时也有可能，取决于基因的关联程度，将两个种群一起繁殖，以试图找到更好的解决方案。