推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
这是一个创建于 3756 天前的主题，其中的信息可能已经有所发展或是发生改变。
看知乎看到可以用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。
我现在想自己实现一个，看了看遗传算法怎么回事，也没去看那个回答里的人的代码是怎么实现的
自己这几天从装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。
 |
1
Mutoo 2014-08-15 14:06:58 +08:00
|
 |
2
happywowwow OP @Mutoo 我当然也看过这个。。。 这篇文章的作者还在我看的那个知乎问题里被吐槽 似乎这这篇文章没加原文思路的引用，当做他自己的东西
|
 |
3
MaiCong 2014-08-15 15:01:05 +08:00
|
|
4
happywowwow OP @MaiCong 。。。这个链接在那个知乎答案也有，我也看了这个网站的。
我也粗略地看了下他的算法，都是写在两个JS文件里的， 但还是想自己解决。 |
 |
5
emarvin 2014-08-15 15:37:13 +08:00  1
大的逻辑可以OOP, 但做运算的地方尽量避免for, 可以把运算vectorize, 也就是换成矩阵运算, 然后用numpy效率会高很多, 如果需要用到GPU加速可以试试theano
|
|
6
happywowwow OP @emarvin 好的！看起来还好些不是很懂。
对于OOP，我主要是疑惑会不会降低效率，要new来new去，然后method也都是简单的操作或者运算，这其实花了空间，也更费时间，不知道会不会这样。我自己写这么个不到1000行的代码，也基本不会添加需求，不知道有没必要。 对于numpy 今天刚好搜stackoverflow PIL的东西的一个人也是用了numpy，所以我准备去看看。 关于运算，我看了看，我在mac下跑，只有CPU占用率特别的高，（100% 跑满了一核）可能不需要GPU加速吧 （？不是特别确定） && THX |
|
7
emarvin 2014-08-15 17:55:32 +08:00 1
@happywowwow 嗯, 一般如果只是想快速demo一个算法的话, 直接面向过程就行了
我没有具体看你用的什么方法, 如果用遗传算法来优化神经网络的话, 值得注意的是隐含层最多别超过一层, 再多的话就是深度网络了, 要用到特殊的方法调教 如果没有特别用GPU的话, 当然是跑cpu啦...cpu占用率说明不了问题... 主要看你的计算性能能不能满足你的计算要求. 训练遗传算法一般数量级都很大, 比如说种群数量和迭代次数. 但具体我也不是很了解. 如果你觉着速度跟的上就行. 相比之下, verctorize后使用numpy已经能比for快很多了 |
|
8
happywowwow OP @emarvin 虽然不是特别懂你说一些词，不过还是谢谢
没有了解过神经网络 & 隐含层 & 深度网络- - 回去看看numpy，一些优化的东西我一天问好些地方也知道了好多。。。但就是得下班了回去试试。。。 然后计算密集好像是没什么办法，开多线程的话好像也不是很有必要，每次计算规模小，但次数太多了而已。 & 如果有时间，可以指点一下代码。正文有github地址 & THX again |
 |
9
helloworld00 2014-08-15 19:26:30 +08:00
|
|
10
happywowwow OP @helloworld00 我怕mac下pypy运行程序他说没找到PIL ...我把python运行的所有路径添加到代码了，在pypy运行也不行...
anyway THX |
|
11
helloworld00 2014-08-16 01:05:59 +08:00
@happywowwow 直接下pypy源代码，把代码丢到pypy的folder里，然后./pypy，然后在pypy的shell里跑你的code
|
 |
12
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 |
|
13
happywowwow OP @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？ |
|
14
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 |
|
15
happywowwow OP @ruoyu0088 感觉你用的库好高级。。。numpy和deap库都只是看过，没去用过
昨晚我去改进了一下， *优胜劣汰得暴力才前期收敛的快，“自然选择 为每次除去匹配率最低的n个，然后从匹配率最高的n*15个中选出n个，复制个体(优胜劣汰，好的种可以更多遗传自己的基因)，n目前取过2-5” 这里我将上面的n乘以15改成了n乘以5,500代遗传就从100*100，RGB三色点差异之和从210W降到110W到150W之间了，我拟合的是chrome图标，之后大约能看出成型了 *可以有这样一个设想，将父母和子女两代数据合在一起进行筛选，这样下一代最差的那个也能较快收敛（还没尝试） *我得修改为正态分布，线性随机分布导致部分三角形颜色要么透明要么很黑... |
 |
16
mikezhang0515 2016-01-08 16:34:55 +08:00
可以开源吗，求学习
|
|
17
happywowwow OP @mikezhang0515 https://github.com/pikeszfish/GA_engine 现在看来写得好烂 ~.~
|
|
18
mikezhang0515 2016-01-12 11:29:08 +08:00
@happywowwow 现在咋写的呢？我遇到的问题是在 10000 代后，收敛的越来越慢，我觉得是收敛算法在前期靠随机还可以，但是后期变异算法不够定向，这个也没想到什么解决办法。个体自我复制和父代基因重组看似区别不大，因为无法从基因的角度判断好快啊。也不知道该怎么写了
|
|
19
happywowwow OP @mikezhang0515 我觉得是变异越来越小,更小步伐地迭代,更容易出现更好的下一代,但这样本身就是放慢了收敛速度,所以,我觉得是没什么又快又好的办法. 或者对颜色,位置的迭代也变小?
|
|
20
mikezhang0515 2016-01-12 11:52:22 +08:00
@happywowwow 我想到，应该挑选应该进化的地方进行变异，只是这个挑选算法比较复杂，想不出来该如何搞
|
Select Language