11

Roger Alsing 编写了一个进化算法，用于使用 C#重新创建蒙娜丽莎。他的算法很简单：

  1. 生成一个大小为 2 的随机种群。
  2. 用最适合的克隆替换最不适合的个体。
  3. 变异其中一个个体。
  4. 转到第 2 步

有一个名为Watchmaker的 Java 进化算法框架。作者使用真正的遗传算法重新实现了蒙娜丽莎问题：http ://watchmaker.uncommons.org/examples/monalisa.php

开始时还不错，但在 30 分钟内，Watchmaker 的实现因近似不佳而停滞不前，而 Roger 的实现看起来接近完成。我尝试使用这些设置，但没有太大帮助。为什么 Watchmaker 的实施比 Roger 的慢得多，为什么会停滞不前？

链接：

4

1 回答 1

15

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

  1. 使用不透明多边形将渲染性能（以及通过扩展适应度函数的性能）提高了一个数量级。
  2. 总而言之，比起剧烈的大变化，更喜欢许多小的变化......
  3. 添加新多边形时，为其指定 1 个像素的大小，而不是为其分配具有随机坐标的顶点。这提高了它的生存机会。
  4. 添加新顶点时，不要将其放入随机位置，而是将其与多边形中现有顶点的位置相同。它不会以任何明显的方式修改多边形，但它会为“移动顶点”突变打开大门，以移动比以前更多的顶点。
  5. 移动顶点时，倾向于进行许多小的移动（一次 3-10 个像素），而不是试图跨越整个画布。
  6. 如果您要随着时间的推移抑制突变，请抑制变化量而不是变化的概率。
  7. 阻尼的影响很小。事实证明，如果您遵循了上述步骤（喜欢小的变化），则应该没有真正需要阻尼。
  8. 不要使用交叉突变。它引入了一个早期的高突变率，但很快高突变就会成为一种负担，因为大部分收敛的图像将拒绝除小突变之外的所有图像。
  9. 不要在适应度评估器功能中缩放图像。这个我花了一段时间才弄清楚。如果您的输入图像是 200x200，但适应度评估器在生成适应度分数之前将图像缩小到 100x100，则会导致候选解决方案包含适应度函数不可见但对最终用户明显错误的错误线。适应度函数应该处理整个图像或根本不处理。更好的解决方案是全面缩放目标图像，以便您的适应度函数处理 100% 的像素。如果 100x100 太小而无法在屏幕上显示，您只需放大图像即可。现在用户可以清楚地看到图像，并且适应度函数不会丢失任何东西。
  10. 防止创建自相交多边形。它们永远不会产生好的结果，因此我们可以通过防止突变产生它们来大大加快算法的速度。实现对自相交多边形的检查是一件很痛苦的事情，但最终还是值得的。

  11. 我修改了适应度分数以删除隐藏的多边形（纯粹是出于性能原因）：

    fitness += candidate.size();

    这意味着适应度分数永远不会为零。

  12. 我已将多边形的最大数量从 50 个增加到 65535 个。

    当我第一次尝试运行 Watchmaker 的蒙娜丽莎示例时，它会运行数天，并且看起来与目标图像不相近。Roger 的算法更好，但一个小时后仍然停滞不前。使用新算法，我设法在不到 15 分钟的时间内重新创建了目标图像。健身分数为 150,000，但在肉眼看来，候选人看起来几乎与原始分数相同。

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

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

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

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

    如果您还记得我报告的原始问题，那就是候选图像在评估之前被按比例缩小，从而允许许多像素避免检测/校正。昨天我为显示给用户的图像启用了抗锯齿功能。我想只要评估者看到 100% 的像素（没有缩放）我应该是安全的，但事实证明这还不够。

看看以下图片：

启用抗锯齿： 启用抗锯齿

禁用抗锯齿： 禁用抗锯齿

They show the exact same candidates with anti-aliasing enabled and disabled. Notice how the anti-aliased version has "streaks" of errors across the face, similar to the problem I was seeing when the candidate was being scaled. It turns out that sometimes the candidates contains polygons that introduce errors into the image in the form of "streaks" (polygons rendered with sub-pixel precision). The interesting thing is that aliasing suppresses these errors so the evaluator function does not see it. Consequently, the users sees a whole bunch of errors which the fitness function will never fix. Sounds familiar?

In conclusion: you should always (always!) pass the fitness function the exact same image you display to the user. Better safe than sorry :)

Genetic Algorithms are a lot of fun. I encourage you to play with them yourself.

于 2011-10-29T18:41:29.723 回答