V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
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
happywowwow
V2EX  ›  Python

关于遗传算法

  •  
  •   happywowwow · 2014-08-15 13:15:26 +08:00 · 7099 次点击
    这是一个创建于 3514 天前的主题,其中的信息可能已经有所发展或是发生改变。
    看知乎看到可以用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。
    20 条回复    2016-01-12 11:52:22 +08:00
    Mutoo
        1
    Mutoo  
       2014-08-15 14:06:58 +08:00
    happywowwow
        2
    happywowwow  
    OP
       2014-08-15 14:30:33 +08:00
    @Mutoo 我当然也看过这个。。。 这篇文章的作者还在我看的那个知乎问题里被吐槽 似乎这这篇文章没加原文思路的引用,当做他自己的东西
    MaiCong
        3
    MaiCong  
       2014-08-15 15:01:05 +08:00
    happywowwow
        4
    happywowwow  
    OP
       2014-08-15 15:18:58 +08:00
    @MaiCong 。。。这个链接在那个知乎答案也有,我也看了这个网站的。
    我也粗略地看了下他的算法,都是写在两个JS文件里的, 但还是想自己解决。
    emarvin
        5
    emarvin  
       2014-08-15 15:37:13 +08:00   ❤️ 1
    大的逻辑可以OOP, 但做运算的地方尽量避免for, 可以把运算vectorize, 也就是换成矩阵运算, 然后用numpy效率会高很多, 如果需要用到GPU加速可以试试theano
    happywowwow
        6
    happywowwow  
    OP
       2014-08-15 15:51:00 +08:00
    @emarvin 好的!看起来还好些不是很懂。
    对于OOP,我主要是疑惑会不会降低效率,要new来new去,然后method也都是简单的操作或者运算,这其实花了空间,也更费时间,不知道会不会这样。我自己写这么个不到1000行的代码,也基本不会添加需求,不知道有没必要。
    对于numpy 今天刚好搜stackoverflow PIL的东西的一个人也是用了numpy,所以我准备去看看。
    关于运算,我看了看,我在mac下跑,只有CPU占用率特别的高,(100% 跑满了一核)可能不需要GPU加速吧 (?不是特别确定)
    && THX
    emarvin
        7
    emarvin  
       2014-08-15 17:55:32 +08:00   ❤️ 1
    @happywowwow 嗯, 一般如果只是想快速demo一个算法的话, 直接面向过程就行了
    我没有具体看你用的什么方法, 如果用遗传算法来优化神经网络的话, 值得注意的是隐含层最多别超过一层, 再多的话就是深度网络了, 要用到特殊的方法调教
    如果没有特别用GPU的话, 当然是跑cpu啦...cpu占用率说明不了问题... 主要看你的计算性能能不能满足你的计算要求. 训练遗传算法一般数量级都很大, 比如说种群数量和迭代次数. 但具体我也不是很了解. 如果你觉着速度跟的上就行. 相比之下, verctorize后使用numpy已经能比for快很多了
    happywowwow
        8
    happywowwow  
    OP
       2014-08-15 18:37:08 +08:00
    @emarvin 虽然不是特别懂你说一些词,不过还是谢谢
    没有了解过神经网络 & 隐含层 & 深度网络- -
    回去看看numpy,一些优化的东西我一天问好些地方也知道了好多。。。但就是得下班了回去试试。。。
    然后计算密集好像是没什么办法,开多线程的话好像也不是很有必要,每次计算规模小,但次数太多了而已。
    & 如果有时间,可以指点一下代码。正文有github地址
    & THX again
    helloworld00
        9
    helloworld00  
       2014-08-15 19:26:30 +08:00
    http://deap.gel.ulaval.ca/doc/default/overview.html

    以前用这个deap的library实现过遗传算法,然后用pypy加速跑的

    效果还行
    happywowwow
        10
    happywowwow  
    OP
       2014-08-15 23:15:28 +08:00
    @helloworld00 我怕mac下pypy运行程序他说没找到PIL ...我把python运行的所有路径添加到代码了,在pypy运行也不行...
    anyway THX
    helloworld00
        11
    helloworld00  
       2014-08-16 01:05:59 +08:00
    @happywowwow 直接下pypy源代码,把代码丢到pypy的folder里,然后./pypy,然后在pypy的shell里跑你的code
    ruoyu0088
        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
    happywowwow
        13
    happywowwow  
    OP
       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
        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
    happywowwow
        15
    happywowwow  
    OP
       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图标,之后大约能看出成型了
    *可以有这样一个设想,将父母和子女两代数据合在一起进行筛选,这样下一代最差的那个也能较快收敛(还没尝试)
    *我得修改为正态分布,线性随机分布导致部分三角形颜色要么透明要么很黑...
    mikezhang0515
        16
    mikezhang0515  
       2016-01-08 16:34:55 +08:00
    可以开源吗,求学习
    happywowwow
        17
    happywowwow  
    OP
       2016-01-08 16:35:53 +08:00
    mikezhang0515
        18
    mikezhang0515  
       2016-01-12 11:29:08 +08:00
    @happywowwow 现在咋写的呢?我遇到的问题是在 10000 代后,收敛的越来越慢,我觉得是收敛算法在前期靠随机还可以,但是后期变异算法不够定向,这个也没想到什么解决办法。个体自我复制和父代基因重组看似区别不大,因为无法从基因的角度判断好快啊。也不知道该怎么写了
    happywowwow
        19
    happywowwow  
    OP
       2016-01-12 11:33:16 +08:00
    @mikezhang0515 我觉得是变异越来越小,更小步伐地迭代,更容易出现更好的下一代,但这样本身就是放慢了收敛速度,所以,我觉得是没什么又快又好的办法. 或者对颜色,位置的迭代也变小?
    mikezhang0515
        20
    mikezhang0515  
       2016-01-12 11:52:22 +08:00
    @happywowwow 我想到,应该挑选应该进化的地方进行变异,只是这个挑选算法比较复杂,想不出来该如何搞
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2631 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 79ms · UTC 15:34 · PVG 23:34 · LAX 08:34 · JFK 11:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.