genetic-algorithm - 为什么这个遗传算法停滞不前？

Question

Roger Alsing 编写了一个进化算法来重新创建 Mona Lisa使用 C#。他的算法很简单:

生成大小为 2 的随机种群。

用最适者的克隆替换最不适合的个体。

变异其中一个个体。

转到步骤 2

有一个 Java Evolutionary Algorithm 框架叫做 Watchmaker .作者使用真正的遗传算法重新实现了蒙娜丽莎问题: http://watchmaker.uncommons.org/examples/monalisa.php

它开始时已经足够好了，但在 30 分钟内，Watchmaker 的实现停滞不前，近似值很差，而 Roger 的实现看起来接近完成。我尝试使用这些设置，但没有太大帮助。 为什么 Watchmaker 的实现比 Roger 慢得多，为什么停滞不前？

友情链接 :

罗杰 source-code

制表师source-code

Answer 1

我在过去一个月研究了这个问题，并做出了一些有趣的发现:

使用不透明多边形可将渲染性能(并通过扩展适应度函数的性能)提高一个数量级。

总而言之，偏爱多小的变化而不是剧烈的大变化...

添加新多边形时，为其指定 1 个像素的大小，而不是为其分配随机坐标的顶点。这提高了它的生存机会。

添加新顶点时，与其将其放入随机位置，不如为其赋予与多边形中现有顶点相同的位置。它不会以任何明显的方式修改多边形，但它会为“移动顶点”突变打开大门，以移动比以前更多的顶点。

移动顶点时，应支持多次小移动(一次 3-10 个像素)，而不是尝试跨越整个 Canvas 。

如果你打算随着时间的推移抑制突变，抑制变化的数量而不是变化的概率。

阻尼的影响很小。事实证明，如果您遵循了上述步骤(支持小改动)，则应该没有真正需要阻尼。

不要使用交叉突变。它引入了高突变率，这在早期是很大的，但很快高突变就变成了一种负担，因为大部分收敛的图像将拒绝除小突变之外的所有突变。

不要在适应度评估器函数中缩放图像。这个我花了一段时间才弄明白。如果您的输入图像是 200x200，但适应度评估器在生成适应度分数之前将图像缩小到 100x100，它将导致候选解决方案包含对适应度函数不可见但对最终用户来说明显错误的牛排/错误线。适应度函数应该处理整个图像或根本不处理。更好的解决方案是全面缩放目标图像，以便您的适应度函数处理 100% 的像素。如果 100x100 太小而无法在屏幕上显示，您只需放大图像。现在用户可以清楚地看到图像并且适应度函数不会遗漏任何东西。

防止创建自相交多边形。它们永远不会产生好的结果，因此我们可以通过防止突变创建它们来大大加快算法的速度。实现自相交多边形的检查是一件很痛苦的事情，但最终还是值得的。

我修改了适应度分数以删除隐藏的多边形(纯粹出于性能原因):
fitness += candidate.size();
这意味着适应度分数永远不会达到零。

我已将最大多边形数从 50 增加到 65535。

当我第一次尝试运行 Watchmaker 的 Mona Lisa 示例时，它会运行数天并且看起来与目标图像没有任何接近之处。罗杰的算法更好，但一个小时后仍然停滞不前。使用新算法，我设法在不到 15 分钟的时间内重新创建了目标图像。适应度分数为 150,000，但用肉眼看，候选人看起来几乎与原始人一模一样。

我整理了一个诊断显示，向我展示了整个人口随着时间的推移而演变的情况。它还告诉我在任何给定时间有多少独特的候选人活跃在人群中。较低的数字表示缺乏差异。要么人口压力太高，要么突变率太低。根据我的经验，一个体面的人群至少包含 50% 的独特候选人。

我使用这个诊断显示来调整算法。每当唯一候选者的数量太少时，我就会增加突变率。每当算法停滞太快时，我都会检查人群中发生了什么。我经常会注意到突变量太高(颜色或顶点移动太快)。

我很高兴我花了一个月的时间研究这个问题。它教会了我很多关于 GA 的性质。与代码优化相比，它与设计的关系更多。我还发现实时观察整个人口的演变非常重要，而不是只研究最适合的候选人。这使您可以相当快地发现哪些突变是有效的，以及您的突变率是太低还是太高。

我学到了另一个重要的教训，说明为什么向健康评估者提供与向用户显示的完全相同的图像非常重要。

如果你还记得我报告的原始问题是候选图像在评估之前被缩小，从而允许许多像素避免检测/校正。昨天我为向用户显示的图像启用了抗锯齿。我认为只要评估器看到 100% 的像素(没有缩放)我应该是安全的，但事实证明这还不够。

看看下面的图片:

启用抗锯齿 :


禁用抗锯齿 :


它们显示了启用和禁用抗锯齿的完全相同的候选对象。请注意抗锯齿版本如何在脸上出现“条纹”错误，类似于我在缩放候选人时看到的问题。事实证明，有时候选对象包含以“条纹”(以亚像素精度渲染的多边形)形式将错误引入图像的多边形。有趣的是，别名抑制了这些错误，因此评估器函数看不到它。因此，用户会看到适应度函数永远无法修复的一大堆错误。听起来很熟悉？

总之:您应该始终(始终!)将您向用户显示的完全相同的图像传递给适应度函数。安全总比抱歉好:)

遗传算法很有趣。我鼓励你自己和他们一起玩。