为什么这种遗传算法会停滞不前？
Gil*_*ili 11 genetic-algorithm evolutionary-algorithm
Roger Alsing编写了一个使用C#重建蒙娜丽莎的进化算法.他的算法很简单:
- 生成大小为2的随机群体.
- 用适合的克隆替换最不适合的个体.
- 改变其中一个人.
- 转到第2步
有一个名为Watchmaker的Java进化算法框架.作者使用真正的遗传算法重新实现了蒙娜丽莎问题:http://watchmaker.uncommons.org/examples/monalisa.php
它开始时已经足够好了,但是在30分钟内,制表师的实现停滞不前,而罗杰的实现看起来接近完成.我试着玩这些设置,但它没有多大帮助.为什么Watchmaker的实现比Roger慢得多,为什么它会停滞不前？
链接:
Gil*_*ili 14
我在过去的一个月里研究过这个问题并做了一些有趣的发现:
- 使用不透明多边形可以将渲染性能(以及通过扩展适应度函数的性能)提高一个数量级.
- 在所有事情上,赞成许多微小变化而不是剧烈的大变化......
- 添加新多边形时,请为其指定1像素的大小,而不是使用随机坐标为其指定顶点.这提高了生存机会.
- 添加新顶点时,不要将其放入随机位置,而是赋予其与多边形中现有顶点相同的位置.它不会以任何明显的方式修改多边形,但它将打开"移动顶点"突变的大门,以移动比以前更多的顶点.
- 移动顶点时,支持许多小移动(一次3-10个像素),而不是尝试跨越整个画布.
- 如果你要在一段时间内抑制变异,那么就要减少变化量而不是变化的可能性.
- 阻尼的影响很小.事实证明,如果你按照上述步骤(有利于小改动),就不应该真正需要阻尼.
- 不要使用Crossover变异.它引入了很高的突变率,这在早期是很好的,但是非常快的高突变成为一种负担,因为大多数融合的图像将拒绝所有但小的突变.
- 不要在适应度评估函数中缩放图像.这个花了我一段时间才弄明白.如果您的输入图像是200x200但健身评估员在生成健身分数之前将图像缩小到100x100,则会导致候选解决方案包含健身功能不可见的牛排/错误线,但对最终用户来说显然是错误的.适应度函数应该处理整个图像或根本不处理.更好的解决方案是全面缩放目标图像,以便您的适应度函数处理100%的像素.如果100x100太小而无法在屏幕上显示,则只需放大图像即可.现在,用户可以清楚地看到图像,并且健身功能不会丢失.
- 防止创建自相交多边形.它们永远不会产生良好的结果,因此我们可以通过防止突变创建它们来大大加速算法.实现对自相交多边形的检查是一个痛苦的屁股,但它最终值得麻烦.
我修改了健身分数以删除隐藏的多边形(纯粹出于性能原因):
fitness += candidate.size();这意味着健身分数永远不会达到零.
我已将多边形的最大数量从50增加到65535.
当我第一次尝试运行Watchmaker的Mona Lisa示例时,它会运行数天而不会看起来与目标图像有任何关系.罗杰的算法更好但一小时后仍然停滞不前.使用新算法,我设法在不到15分钟内重新创建目标图像.健身分数读数为150,000,但肉眼看来候选人几乎与原始人相同.
我整理了一个诊断显示,向我展示了随着时间推移而变化的整个人口.它还告诉我在任何给定时间有多少独特候选人在人口中活跃.数字较小表示缺乏差异.人口压力太高或突变率太低.根据我的经验,一个体面的人口至少有50%的独特候选人.
我使用这个诊断显示来调整算法.每当独特候选者的数量太少时,我就会增加突变率.每当算法停滞太快时,我都会检查人口中发生了什么.我经常注意到突变量太高(颜色或顶点移动得太快).
我很高兴我在过去一个月里研究过这个问题.它教会了我很多关于GA的本质.它与设计有很多关系,而不是代码优化.我还发现,观察整个人口实时演变是非常重要的,而不是只研究最适合的候选人.这使您可以相当快速地发现哪些突变有效以及您的突变率是否过低或过高.
我还学到了另一个重要的教训,即如何为健身评估者提供与用户所示完全相同的图像,这一点非常重要.
如果你回想起我报告的原始问题是候选图像在评估之前被缩小,从而允许许多像素避免检测/校正.昨天我为显示给用户的图像启用了抗锯齿功能.我想只要评估者看到100%的像素(没有缩放)我应该是安全的,但事实证明这还不够.
看看下面的图片:
启用抗锯齿:
禁用抗锯齿:
它们显示启用和禁用抗锯齿的完全相同的候选项.请注意消除锯齿版本如何在整个面部出现"条纹"错误,类似于我在缩放候选人时看到的问题.事实证明,候选者有时会包含多边形,这些多边形会以"条纹"(以子像素精度渲染的多边形)的形式将错误引入图像.有趣的是,别名会抑制这些错误,因此评估程序功能无法看到它.因此,用户会看到一大堆错误,健身功能永远无法修复.听起来很熟悉？
总之:您应该始终(始终!)将健身功能传递给您向用户显示的完全相同的图像.比抱歉更安全:)
遗传算法很有趣.我鼓励你自己和他们一起玩.