转载自：http://www.thecodeway.com/blog/?p=1499
如果在网上搜索“遗传算法”的话，会找到一些文章讨论如何使用多边形画出迷人的“蒙娜丽莎”这个话题，比如这个网站只使用50个多边形就模拟出逼真的蒙娜丽莎：
貌似很唬人的效果，但这里所谓“遗传算法”其实并不复杂，稍微有一些编程基础的人都可以看的明白，流程就是：
- 输入某个目标图像，称为GoalImage
- 准备两个数组，用来存储多边形数据，分别称为TestDNA和BestDNA，初始多边形个数都为0
- 准备一个变量LowestDifferent，并赋一个大值
- 根据随机值对TestDNA进行变异，变异的方法包括:增加多边形、减少多边形、交换两个多边形位置、改变某些多边形的形状、颜色、位置等因素
- 将TestDNA里的多边形画出来，称为TestImage
- 通过评估函数得出TestImage和GoalImage的差别，如果得到的差别值比LowestDifferent小，表示本次的变异成功，将TestDNA中的数据复制到BestDNA中，反之，则将BestDNA复制TestDNA中，放弃本次变异
- 回到步骤4
严格来说，这也算不上是什么“遗传”，基本上也就算是“单体无性繁殖”，但是利用计算机的高速度，照样可以在很短的时间内使得一堆多边形进化到“蒙娜丽莎”，其中的关键就是设计好变异函数和评估函数，再加上运算速度。上面的例子使用的是C#编写的程序，运行了大概三个小时就得到了这个结果，从这里可以下载到它的源代码。另外还有一些运行在其他平台上的程序可以参考，比如Linux版，JavaScript网页版，另一个网页版，VB版，以及SDL版。
我凑热闹也写了一个版本，目的是想尽可能提高进化速度，为实现这个目标，使用了一些技巧：
- 首先是通过GPU合成图像，比起使用GDI或者Canvas速度当然快许多，不过代价就是只能使用三角形
- 图形的比较也放在GPU中计算，这步是通过一张R32F格式的纹理作为渲染目标，然后使用Shader完成的
- 逐个像素比较时，将颜色从RGB空间转换为LAB空间，这是由于LAB空间更适合计算从人眼的角度观察到的两个颜色的差值，这个转换过程也很简单，参照这里，然后在shader里通过distance指令直接计算两个像素的差别
- 貌似大部分计算都放在GPU里了，但还差一步，GPU计算出的图像差值是逐像素的，还需要在CPU里将每个像素的差值加到一起，不要小看这个简单的浮点数加法，在我的初始版本里，大量的浮点数加法竟然占用了90%的CPU，后来我用了一个比较有意思的技巧，先在GPU里将每个像素的差值放在[1.0,2.0)之间，根据IEEE标准，这个区间的浮点数的二进制格式的符号以及指数部分是相同的，所以可以直接通过一个and运算就可以得到尾数部分，然后转换为整数加法，速度就快多了
- 变异过程需要产生大量的随机数，直接调用CRT可不行，太慢了，我用了一个随机数池，直接从池中获取随机数，然后每隔一段时间重新刷新池中的数据
这是程序运行两个多小时后的结果，使用了256个三角形，进行了18469次有效变异，平均帧数在2300帧左右，也就是每秒可以进行2300次的变异，还算是差强人意，如果有朋友有更好的改进意见，欢迎指教。
源码下载：ImageGenetic.zip(139KB)
可执行程序下载(需要vcredist_2005)：ImageGeneticRun.zip(54.3KB)