遗传算法 - 新一代越来越差

Question

我已经实现了一个简单的遗传算法，用于基于伊索寓言生成短篇小说。以下是我使用的参数：

变异：单词交换变异，测试率为0.01。

交叉：在给定点交换故事句子。比率为0.7。

选择：轮盘选择 - https://dev59.com/1HVC5IYBdhLWcg3wz0l9#5315710 适应度函数：3个不同的函数。每个的最高分数为1.0。因此，总适应度最高得分为3.0。

种群大小：由于我使用了86个伊索寓言，所以我测试了50个种群大小。

初始种群：所有86个寓言句子顺序都被打乱，以使其完全无意义。我的目标是从这些结构丢失的寓言中生成至少某种程度上有意义的东西。

停止条件：3000代。以下是结果：

然而，这仍未产生令人满意的结果。我期望的是代际上升的情节。为什么我的GA表现更差了呢？更新：正如你们所有人建议的那样，我雇用了精英主义，将当前一代的10%复制到下一代。结果仍然相同：。也许我应该使用锦标赛选择。

- KevinOelen

---

你为什么认为遗传算法能够解决这个问题？你选择的适应度函数和变异/交叉是否兼容？ - Douglas Zare

我认为故事生成的方式可能是一个搜索问题，同时寻找它正在生成的文档的最佳内容和结构。使用遗传算法似乎非常适合这个任务。你所说的“兼容”是什么意思？ - KevinOelen

在我看来，杂交在很大程度上难以理解，你可能需要一个极其庞大的人口才能避免有害变异/杂交的积累降低最大适应度。比起让遗传算法在复杂问题上运作，写论文阐述它们如果能够工作的美好前景要容易得多。你的项目是基于过去遗传算法的成功案例还是别人的乐观猜测呢？ - Douglas Zare

如果您有精英主义，并且适应性降低，则说明精英主义实现有误。精英主义意味着将最优秀的个体不作改变地复制到下一代。此外，请检查我的编辑答案，我添加了一个可能有用的概念以供思考 :)。 - zegkljan

Answer 1

以上所有回答都很好，我会考虑它们。以下是我的想法。 变异 你的变异率似乎还不错，但是在遗传算法中，如果变异率不恰当，会引起很多问题。我建议你测试许多其他值，以确保结果正确。

对于变异，我可能会使用两种类型的变异。一种是用你的字典中的其他单词替换单词，另一种是交换句子中的两个单词。这将有助于鼓励整体种群多样化和打乱单词。 交叉 我不知道你如何实现这个算法，但单点交叉似乎在这种情况下不会很有效。我建议你尝试实现n点交叉，这将更好地打乱你的句子。但如果单词顺序非常重要，简单的交叉可能并不理想。 选择 再次强调，这看起来还不错，但我建议您测试其他选项。在过去，我发现基于排名的轮盘式选择更成功。 适应度 这总是需要考虑的事情，在你所面临的问题的复杂性下，我建议你再次确认它是否有效。你是否已经测试了它是否适用于“已知”问题？ 种群大小 你的值似乎有点小，但我曾看到过小种群成功运行遗传算法。但是，我仍然建议你尝试更大的种群，以查看结果是否更好。

目前最流行的建议是实现精英主义，我强烈建议你这样做。它不必很多，每一代只需最好的几个染色体（但是像其他所有内容一样，我会尝试不同的值）。

另一个有时有用的操作符是淘汰，摧毁最弱的染色体或类似于其他染色体的染色体（或两者），并用新染色体替换它们。这应该有助于防止种群“陈旧”，从您的图表中看起来可能正在发生。变异只能为种群多样性做出那么多贡献。

- OnABauer

---

变异操作符将随机名词替换为WordNet的同义词。你提到的第二个变异操作非常危险。它可能会破坏句子的语法、结构和一切。我的交叉操作符非常简单：它只计算父母故事中的句子数，并在其中一半进行交换。例如：父亲的故事有4个句子，母亲的故事有6个句子，孩子们的故事将是父亲的前两个句子+母亲的后三个句子，反之亦然。我的适应度函数并不完美，但我希望它能启发式地找到一个有可能连贯的故事。 - KevinOelen

我假设随机生成的单词没有语法和结构，完全是随机的，而遗传算法则试图找到一个具有良好语法的单词。如果不是这样，那么这个操作符可能不起作用。如果您能提供更多关于实现和适应度函数的细节，那就太好了。 - OnABauer

Answer 2

你可能正在失去最佳组合，应该保留每一代中最好的而不是交叉（精英）。此外，你的函数似乎非常稳定，请尝试其他类型的变异，这应该会有所改善。

- Pedro Ivan

---

谢谢你的回答。我认为如果没有交叉算子，它不会进化得那么多。我在考虑是否应该通过允许将前N％的解决方案直接从一代复制到下一代来采用一些精英主义。但是不确定N％应该是多少... - KevinOelen

当我尝试使用遗传算法时，我发现15%是最好的结果，但这只是实验性的。你应该按照每个适应度对种群进行排序，并选择其中5%在一个适应度上表现最好的（而不仅仅是整体最好的）。也许你可以通过这种方式获得每个适应度上的最佳结果。 - Pedro Ivan

Answer 3

将人口的5%到10%留作精英，这样你就不会失去最好的。确保你的选择过程设置得很好，如果坏候选人经常通过，它会破坏你的进化。你可能也被困在一个局部最优解中，你可能需要引入其他东西到你的基因组中，否则你不会走得太远。

移动句子和单词可能不会让你走得太远，引入新的句子或单词可能是有趣的。如果你把故事看作是点x，y，把评估函数看作f(x,y)，并且你试图找到f(x,y)的最大值，但你的变异和交叉只限于x->y，y->y，那么你不会走得太远是有道理的。虽然在你的问题中有更多的变量，但如果不引入新的东西，我认为你无法避免局部性。

- GettnDer

---

谢谢你的回答。我会尽量按照你的建议避免精英主义。你对初始种群有什么看法？从86开始改为50。我怀疑这可能是另一个原因。 - KevinOelen

据我所知，在创建种群后更改种群大小没有任何问题，除非一开始就没有太多。否则，更多的种群数量是越好的，直到变得过于昂贵，因此这取决于您的瓶颈有多昂贵（可能是您的适应度评估）。简而言之：种群越多，通过一代需要的时间就越长，因此只需在两者之间找到一个良好的平衡即可！ - GettnDer

Answer 4

如@GettnDer所说，精英主义可能会有很大帮助。

我的建议是使用不同的选择策略。轮盘赌选择有一个大问题：想象一下最好的个体健康度是所有健康度之和的90％。那么轮盘赌不太可能选择其他个体(请参阅例如这里）。我最喜欢的选择策略是锦标赛选择。它对健康度差异大的情况更加鲁棒，并且可以非常容易地控制选择压力。

新颖性搜索

我也会尝试新颖性搜索。这是一种相对较新的进化计算方法，您不会根据实际健康度进行选择，而是根据新颖性进行选择，这被认为是衡量个体与其他人行为差异的某种指标（但仍然计算健康度以捕获好的个体）。特别感兴趣的是经典健康度驱动算法和新颖性驱动算法的组合，例如J.-B. Mouret的这篇文章。

- zegkljan

Answer 5

当使用遗传算法时，最好将染色体结构化以反映所优化过程的实际知识。在您的情况下，由于您打算生成故事，而故事由句子组成，如果您将染色体转换为结构化短语，例如* * *（这里是一个巨大的简化），则可以改善结果。然后，可以为每个单词分配一个类别。例如，Fox=主语，looks=动词，grapes=宾语，然后您的交叉操作符将在染色体之间交换同一类别的元素。此外，您的变异操作符只能插入适当类别的新元素（例如，在主语之前加形容词）或用同一类别的随机单词替换单词。这样，您将最小化无意义染色体的数量（例如，Fox beautiful grape day sky），并提高GA的话语生成能力。此外，我同意所有先前的评论：如果您正在使用精英主义，并且最佳性能下降，则您正在错误地实现它（请注意，在病态情况下，它可能长时间保持不变）。希望对您有所帮助。

- rlinden