genetic programming 多边形近似
人工智能选修课…某次讲了遗传算法…
然后就想到了以前看到的一篇文章…
似乎是去年这个时候的…
讲的是某人用遗传算法写了个程序…用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版
…最后…
我自己也写了个…不过不是多边形版的…是三角形版的…所以进化的速度比较慢…
效果图:
源代码下载:
在个体数量如果选择1的话就是无性繁殖方式…
但平均每代出现更优解的值理论上会比较低…如果多个个体的话…虽然这个值可能会上升…但是每代消耗的计算成本增加的不是一点点…
于是有性繁殖会显得比较慢…
然后图片小的话进化速度也会看起来比较快…因为每代的计算成本低了很多…
使用的语言是VB6…很古老么…
花了几个小时时间写的…
画图是DIB加直接画在数组上
否则就VB6这龟速…- -|||
当然用gdiplus的话就另当别论了…
不过没研究过gdiplus…如果只能调用api逐点取颜色的话会慢很多…
数组版三角形填充以前写过…而多边形填充没写过…
因此做出来的是三角形版而不是多边形版…
下次是不是要考虑研究下gdiplus了呢…
还是说…
5 条评论
Comments RSS
TrackBack Identifier URI
留下评论
RSS订阅
关于这个问题的遗传算法处理～希望能请教一两个细节问题～如果方便麻烦加一下我msn吧～
cgbirdfly@hotmail.com
评论 由 cgbird on 2010年03月11日 1:52 下午
什么细节问题?
评论 由 ben1222 on 2010年03月11日 2:00 下午
我现在的算法是这样的1
1.生成若干三角形，每个三角形随机透明在40-60之间
2.按照以下规则计算适应值 (每个点上的三个色的色差)的平方之和，越大的表示越不适应
3.将个体随机分为两类（相当于男女），用轮盘赌的方法，分别从两类中的个体挑出来一个进行交配，不是最合适的就一定会有交配权，但是相当概率会更高，子女也会更多
4.交配的时候，将个体的三角形的3个点，三个颜色值，透明度，每一项随机选择继承父母的其中一方，有一定几率变异
5.画出新的三角形后，返回第二项。
但是效果很不好，不知道哪里的思路不对。
此外，我觉得科学松鼠会的文章里面引用的那个示例，是不是也是你说的那种类似穷举法的进化方式啊？
评论 由 cgbird on 2010年03月13日 2:02 下午
你说的效果不好是指哪里?遗传算法通常会需要等比较久才会有可观的效果…
“类似穷举法的进化方式”是指什么?
计算机模拟…个体越多计算量就会越大,不像自然界,个体数量和计算量没有关系…
所以个体多了也未必会提高效率,因此用单个体无性繁殖加上变异的话在计算机模拟的情况下会比较”高效”…
关于你的算法…
交配和生成子女的部分,不清楚你具体是怎么做的,从字面上来看,只挑一对来进行交配的话就有点不好了…而且也不必执着于分开2种性别…完全可以认为每个DNA有2个互为异性的个体…
用概率选的话一般是挑数对进行交配…而且父代和子代放在一起竞争…还要筛去最不适应的那些个体
评论 由 ben1222 on 2010年03月13日 4:34 下午
好的～我再修改一下我的程序看看：）
评论 由 cgbird on 2010年03月14日 7:51 上午