2

我正在实施 NSGA II 遗传算法来为我的大学制定一套时间表。我在解决方案的变化方面遇到问题。

我的算法在初始化、变异和交叉中运行良好，但在最后一代审查我的解决方案后它们都是相同的，例如我一代有 200 个，也许其中 64 个彼此相同，54 个相同其他等

我的问题是什么可能导致这种情况？交叉和突变的最佳形式是什么？

代大小、代数、突变率和交叉率是否也有规范？

目前它像这样运行：

  1. 随机生成300个解决方案
  2. 计算适应度和排名
  3. 挑选 200 个最佳解决方案
  4. 使其中的 5% 发生变异并产生 80 个孩子
  5. 再次计算和排名
  6. 挑选出最好的 300 人，传给下一代
  7. 重复
4

3 回答 3

1

我相信您的算法可能没有错误。这是 GA 的一个众所周知的问题。如果你想有多种解决方案，你应该实现一些Niching方法。它的想法是惩罚你人口中的类似个体。您可以找出个体相似性的一些启发式方法，并从您的群体中排除相似的个体或消除个体的适应度。这将使您的人口更加多样化，并且不允许您的变异操作员选择和进化相同的个体。阅读 Samir W. Mahfoud 的“Niching Methods for Genetic Algorithms”会很有用。

于 2013-03-15T11:43:47.423 回答
0

这个结果不一定是坏事。它可能只是融合在几个“附近”没有任何其他可行解决方案的解决方案上。您正在融合的解决方案是否糟糕？

我注意到的一件事是，尽管您提到了交叉，但您并未将其列为 7 个步骤之一。如果事实上你只是在做变异，那会让 GA 更难爬出局部最优。

于 2013-02-19T23:06:26.843 回答
0

GA 的工作就像 Converging to a point 选择最小的等位基因（解决方案）为最佳。在极少数情况下，经过数千代的长期运行，它可能会带来单一的最佳解决方案。

但在某些情况下，它可能会在最少的运行次数（例如 100 次）中带来收敛的解决方案。但它有可能陷入局部最优，无法达到全局最优。

我不确定您尝试过哪一代。我建议你去1000代并比较结果。此外，情节可能会在几代之后发生变化，就像您可以看到全新的解决方案一样

不同的表示有不同的交叉和变异。可能你可以告诉你正在使用的表示，结果与代数成正比

于 2013-02-20T12:22:57.593 回答