本站首页    管理页面    写新日志    退出

公告

You are all my reasons! 

桃李花林又一在

淫荡一日同风起,风骚直上九万里

仙子凌波微步罗衫飘忽十步一回头

我的最爱:网游,程序,文学

QQ:89636669


我的分类(专题)

日志更新

最新评论

留言板

链接

Blog信息
blog名称:一维空间
日志总数:163
评论数量:248
留言数量:33
访问次数:649339
建立时间:2007年10月24日




 [机器学习]遗传算法简介

dskongenius 发表于 2007/11/6 11:42:56

遗传算法的定义     遗传算法通常实现为一种计算机模拟。对于一个最优化问题,一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群向更好的解进化。传统上,解用二进 制表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个体的种群开始,之后一代一代发生。在每一代中,整个种群的适应度被评价,从当前种群中 随机地选择多个个体(基于它们的适应度),通过自然选择和突变产生新的生命种群,该种群在算法的下一次迭代中成为当前种群。 遗传算法的机理     在遗传算法里,优化问题的解被称为个体,它表示为一个参数列表,叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串,不过也有其他的表示方法 适用。一开始,算法随机生成一定数量的个体,有时候操作者也可以对这个随机产生过程进行干预,播下已经部分优化的种子。在每一代中,每一个个体都被评价, 并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序,适应度高的在前面。这里的“高”是相对于初始的种群的低适应度来说的。     下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的,其中繁殖包括杂交和突变。选择则是根据新个体的适应度进行的,适应度越高,被选择的 机会越高,而适应度低的,被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后,被选择的个体进入杂交过程。一般的遗传算法 都有一个杂交率的参数,范围一般是0.6~1,这个杂交率反映两个被选中的个体进行杂交的概率。例如,杂交率为0.8,则80%的“夫妻”会生育后代。每 两个个体通过杂交产生两个新个体,代替原来的“老”个体,而不杂交的个体则保持不变。杂交父母的染色体相互交错,从而产生两个新的染色体,第一个个体前半 段是父亲的染色体,后半段是母亲的,第二个个体则正好相反。不过这里的半段不是真正的一半,这个位置叫做杂交点,也是随机产生的,可以是染色体的任意位 置。再下一步是突变,通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数,通常是0.01或者更小,这代表突变发生的概率。根据这个概率, 新个体的染色体随机的突变,通常就是改变染色体的一个字节(0变到1,或者1变到0)。     经过这一系列的过程(选择、杂交和突变),产生的新一代个体不同于初始的一代,并一代一代向增加整体适应度的方向发展,因为最好的个体总是更多的被选择去 产生下一代,而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复:每个个体被评价,计算出适应度,两个个体杂交,然后突变,产生第三代。周而复始,直到 终止条件满足为止。一般终止条件有以下几种: ·  进化次数限制; ·  计算耗费的资源限制(例如计算时间、计算占用的内存等); ·  一个个体已经满足最小值的条件,即最小值已经找到; ·  适应度已经达到饱和,继续进化不会造成适应度更好的个体; ·  人为干预; ·  以及以上两种或更多种的组合;


阅读全文(1219) | 回复(0) | 编辑 | 精华

 



发表评论:
昵称:
密码:
主页:
标题:
验证码:  (不区分大小写,请仔细填写,输错需重写评论内容!)



站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.031 second(s), page refreshed 144759951 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号