AC

人工智能选修课...某次讲了遗传算法...
然后就想到了以前看到的一篇文章...
似乎是去年这个时候的...

讲的是某人用遗传算法写了个程序...用50个半透明多边形去近似蒙娜丽莎这幅图...

当时觉得很神奇...
对遗传算法稍微了解了一点后又觉得这个一点点进化的图片很费解...
因为图上的多边形在慢慢增多...
而我本以为遗传算法是固定长度的DNA来进行运算的...
而多边形数量的变化以及顶点数的变化让我感觉有些费解...这是怎么表示又是怎么进行繁衍的呢...

一年过去了...借此机会重新回顾了一下...
仔细看了看原文中的文字...

The procedure of the program is quite simple:

0) Setup a random DNA string (application start)

1) Copy the current DNA sequence and mutate it slightly
2) Use the new DNA to render polygons onto a canvas
3) Compare the canvas to the source image
4) If the new painting looks more like the source image than the previous painting did, then overwrite the current DNA with the new DNA
5) repeat from 1

这是它的算法的流程
大致是这样:
0)随机生成初始DNA序列
1)复制当前DNA序列并进行变异
2)用新DNA画出图片
3)比较画出的图片和原图
4)如果新的DNA画的图片比当前的DNA画的图片更像原图,就把当前DNA替换为新的DNA
5)再从1开始

然后...原来这只有一个个体而已...还无性繁殖- -|||
每次把自己的完美克隆体与变异体进行比较,扔掉差的那个...
这与其说是遗传算法...不如说是随机算法吧...
只不过数据的结构被表示成DNA了...

在原文中还有源代码的链接...
然后下了份来看...是C#的
.net真是爽啊...gdiplus都封装起来了...画半透明的东西那么容易...咳咳...
经过自己的尝试后了解到其中几个有点重要的地方是这样的:
变异包括:添加一个多边形,删除一个多边形,多边形增加一个顶点,多边形删除一个顶点,多边形顶点移动,多边形颜色变化
变异是针对每个最小单元进行的:添加/删除多边形,添加/删除顶点,顶点x/y坐标,颜色r/g/b/a分量
本来我以为变异嘛...就以多边形为单位...看这个多边形需要变异否,需要的话每个顶点坐标以及颜色4分量一起变掉了...结果会很惨...
然后变异率不能太高...因为是每个最小单位进行的变异,所以高一点的话就容易一下面目全非...
因为多边形还会变多,顶点也会变多...所以随着时间推移,最小单位的总数会越来越多...这时候变异率最好能再降低些...
作者给的变异率初始值定在了1/1500...

不过调整变异率什么的是不是太坏了...
如果一开始太低的话,初期会进化的非常慢...后期效果会好些...?

然后相关的还有科学松鼠会的文章
内容比较有趣...
文章的算法不太一样,是初始把多边形数量固定死了的...而且是有性繁殖的...
似乎是作者自己写的代码...

然后一个javascript版

...最后...
我自己也写了个...不过不是多边形版的...是三角形版的...所以进化的速度比较慢...
效果图:

monalisa

firefox

源代码下载:
genetic-polygon-ver-mix

在个体数量如果选择1的话就是无性繁殖方式...
但平均每代出现更优解的值理论上会比较低...如果多个个体的话...虽然这个值可能会上升...但是每代消耗的计算成本增加的不是一点点...
于是有性繁殖会显得比较慢...
然后图片小的话进化速度也会看起来比较快...因为每代的计算成本低了很多...

使用的语言是VB6...很古老么...
花了几个小时时间写的...
画图是DIB加直接画在数组上
否则就VB6这龟速...- -|||
当然用gdiplus的话就另当别论了...
不过没研究过gdiplus...如果只能调用api逐点取颜色的话会慢很多...

数组版三角形填充以前写过...而多边形填充没写过...
因此做出来的是三角形版而不是多边形版...
下次是不是要考虑研究下gdiplus了呢...
还是说...