关于遗传算法

看知乎看到可以用python做哪些有趣的事情，有一个是用python实现遗传算法，将N个三角形组合成为一张图片参考（http://www.zhihu.com/question/21395276）
我现在想自己实现一个，看了看遗传算法怎么回事，也没去看那个回答里的人的代码是怎么实现的
自己这几天从装PIL到写了点东西（https://github.com/pikeszfish/GA_engine）
但现在好像效果不是那么好，不知道有没有人愿意能够去看看。

算法思路：
1、初始化种群，设M个，然后每个有N个基因
2、将N个基因全部合成到一张图片上，分别计算M个个体与待匹配的图片的相似度。
3、自然选择，除去相似度最低的a个，将相似度最高的2*a个随机复制。（模拟适者生存，基因好的容易将基因遗传给后代）（这里a自己定，2*a也只是我的设想）
4、交叉，两两匹配（随机），进行基因组互换。（因为是三角形，则每个基因是由三个点，还有RGBA的颜色组成，(x1,y1,x2,y2,x3,y3,g,b,a,r)，所以随机选择10个基因点）
5、变异，按照固定每代遗传变异数或者比率进行变异
6、重复2，直到一定数量的遗传代数

下面是我的疑惑点：
1、各个参数选择是否有更好的？
2、交叉过程，因为基因是(x1,y1,x2,y2,x3,y3,g,b,a,r)，目前我选择的交叉是每一个点都进行交叉，而其实（x1，y1）对应的其实是A点，我在想是否还是根据 (A点，B点，C点，颜色)进行交叉来的更好？还是直接（基因）交叉
3、透明度是否需要固定住？因为有的时候合成到最后，如果有一张图片透明度过低，就完全覆盖了下面（这我自己解决去）
4、变异的概率，无论控制具体数目还是概率，还是不好把握变异数量多少才好
5、生成的三角形，在(255, 255)大小的图片里面，直线会有锯齿，感觉是不是图片画大一点会好一些？还是PIL or pillow有更好的API？or args？
6、效率，目前一代需要0.8秒~0.9秒，太慢了。。。
7、写python一直以来的疑惑，我如果就这么个想法，需要写成OOP么？现在一堆function，都不是method。

happywowwow

2014-08-15 15:51:00 +08:00

@emarvin 好的！看起来还好些不是很懂。
对于OOP，我主要是疑惑会不会降低效率，要new来new去，然后method也都是简单的操作或者运算，这其实花了空间，也更费时间，不知道会不会这样。我自己写这么个不到1000行的代码，也基本不会添加需求，不知道有没必要。
对于numpy 今天刚好搜stackoverflow PIL的东西的一个人也是用了numpy，所以我准备去看看。
关于运算，我看了看，我在mac下跑，只有CPU占用率特别的高，（100% 跑满了一核）可能不需要GPU加速吧（？不是特别确定）
&& THX

emarvin

2014-08-15 17:55:32 +08:00

@happywowwow 嗯, 一般如果只是想快速demo一个算法的话, 直接面向过程就行了
我没有具体看你用的什么方法, 如果用遗传算法来优化神经网络的话, 值得注意的是隐含层最多别超过一层, 再多的话就是深度网络了, 要用到特殊的方法调教
如果没有特别用GPU的话, 当然是跑cpu啦...cpu占用率说明不了问题... 主要看你的计算性能能不能满足你的计算要求. 训练遗传算法一般数量级都很大, 比如说种群数量和迭代次数. 但具体我也不是很了解. 如果你觉着速度跟的上就行. 相比之下, verctorize后使用numpy已经能比for快很多了

happywowwow

2014-08-15 18:37:08 +08:00

@emarvin 虽然不是特别懂你说一些词，不过还是谢谢
没有了解过神经网络 & 隐含层 & 深度网络- -
回去看看numpy，一些优化的东西我一天问好些地方也知道了好多。。。但就是得下班了回去试试。。。
然后计算密集好像是没什么办法，开多线程的话好像也不是很有必要，每次计算规模小，但次数太多了而已。
& 如果有时间，可以指点一下代码。正文有github地址
& THX again

ruoyu0088

2014-08-19 20:26:58 +08:00

能说说你的算法的具体参数吗？多大的图像，多少个三角形？每一代的人口数为多少？
我也试了一下：
128*128的图像，100个三角形，每一代400个。
交叉时，我把每个三角形当作一个基因。
每个个体是否变异的概率从0.6左右逐渐减小。
各个个体变异时，每个基因是否变异的概率也逐渐减小。基因的变异就是加一个高斯分布的随机数，随机数的方差也逐渐减小。
迭代一代的时间大约为1秒。
目前算了1个多小时，目前每个通道的平均误差为20.1。变化已经非常缓慢，不知道能否收敛到目标图像：

https://raw.githubusercontent.com/ruoyu0088/openbooks/master/firefox_gen.png

happywowwow

2014-08-20 11:14:30 +08:00

@ruoyu0088 啊我的是100 * 100，逐像素计算gba数据(为了速度，如果图片放大到256*256，则可以选择隔点计算。。)，然后和目标图片的数据相减求和
我现在测试是80个个体，每个个体80个基因
自然选择为每次除去匹配率最低的n个，然后从匹配率最高的n*15个中选出n个，复制个体(优胜劣汰，好的种可以更多遗传自己的基因)，n目前取过2-5
交叉从80个个体抽出两个当父母，父母各自的80个基因用2分之一的概率交叉遗传给后代，并且每个基因有0.01-0.05的概率(具体的自己测试，我不确定多大比较好)变异，变异按照原先数值+图片长*2*random.random()-图片长，random.random()平均是0.5，所以按照这样算可以保证要么变大和变小的概率一样。如果是颜色值变异，则以上算法为原先数值+255*2*random.random()-255 (因为颜色的范围是0-255)
然后进行下一代

目前我的效率为1.9秒一代。
我觉得我的算法最差的地方是自然选择，因为80个个体，复制n个个体，太暴力了。虽然说得通，但感觉效果不好是因为这里。
高斯分布感觉比我的好，我的是完全随机加减。

想问你下，你的交叉怎么实现的？
你的通道误差如何计算？是用getpixel吗？不过好像得问你你是用什么语言实现的了。。。什么库
你的好快啊。。。400个个体...100个三角形(基因)
难道不是逐点计算差异？or多线程计算？or不是python？or numpy？or what？

ruoyu0088

2014-08-20 20:06:59 +08:00

我又修改了一下，似乎个体太多用处不大，目前改成300个三角形，40个个体，一秒钟能迭代10多次。

程序是Python编写的，绘制三角形是用的pyopengl，运算用的是numpy和deap库。源程序在这里：

https://github.com/ruoyu0088/scpy2/blob/master/examples/triangles.py

还没有好好整理，之前所说的那个逐渐修改变异概率的部分我删掉了，效果不是太好。我想编写一个GUI，实时修改这些参数，观察收敛的效果，找到规律之后再动态改变参数。

deap中的eaSimple算法如下，假设有N个个体：

* 随机选择k个个体，取其中最优的一个，重复做直到选择了N个个体，这N个个体中有重复的。
* 随机选择多对进行交叉，交叉就是将一部分三角形互换。
* 随机进行选择多个个体变异。
* 进入下一代。

下面是目前迭代的结果，误差每下降0.5保存一幅图：

https://raw.githubusercontent.com/ruoyu0088/scpy2/master/examples/firefox.gif

happywowwow

2014-08-21 09:22:18 +08:00

@ruoyu0088 感觉你用的库好高级。。。numpy和deap库都只是看过，没去用过
昨晚我去改进了一下，
*优胜劣汰得暴力才前期收敛的快，“自然选择为每次除去匹配率最低的n个，然后从匹配率最高的n*15个中选出n个，复制个体(优胜劣汰，好的种可以更多遗传自己的基因)，n目前取过2-5” 这里我将上面的n乘以15改成了n乘以5,500代遗传就从100*100，RGB三色点差异之和从210W降到110W到150W之间了，我拟合的是chrome图标，之后大约能看出成型了
*可以有这样一个设想，将父母和子女两代数据合在一起进行筛选，这样下一代最差的那个也能较快收敛（还没尝试）
*我得修改为正态分布，线性随机分布导致部分三角形颜色要么透明要么很黑...