电子发烧友App

硬声App

0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示
创作
电子发烧友网>电子资料下载>DSP>遗传算法的模式理论

遗传算法的模式理论

2008-12-20 | rar | 333 | 次下载 | 3积分

资料介绍

导遗传算法的基本理论,是J.H.Holland教授创立的模式理论。该理论揭示
    了遗传算法的基本机理。
 3.1  基本概念
 3.1.1  问题的引出
   
       例: 求   max  f(x)=x2      x {0,31}
[分析]
     •  当编码的最左边字符为“1”时,其个体适应度较大,如2号个体和4号个体,
         我们将其记为 “ 1**** ”;
         其中2号个体适应度最大,其编码的左边两位都是1,我们记为 “ 11*** ”;
     •  当编码的最左边字符为“0”时,其个体适应度较小,如1号和3号个体,
         我们记为 “ 0**** ”。
   [结论]
         从这个例子可以看比,我们在分析编码字符串时,常常只关心某一位或某几位字符,而对其他字符不关心。换句话讲.我们只关心字符的某些特定形式,如
       1****,11***,0****。这种特定的形式就叫模式。

 3.1.2  模式、模式阶及模式定义长度
    
     模式(Schema)——指编码的字符串中具有类似特征的子集。
                                     以五位二进制字符串为例,
                                     模式  *111*   可代表4个个体: 01110,01111,11110,11111;
                                     模式  *0000  则代表2个个体:10000,00000  。

•  个体是由二值字符集 V={0, 1} 中的元素所组成的一个编码串;
       •  而模式却是由三值字符集  V={0, 1,* } 中的元素所组成的一个编码串,其中
           “ * ” 表示通配符,它既可被当作 “1” 也可被当作 “0”。

模式阶 (Schema Order)
        ——指模式中已有明确含意(二进制字符时指0或1)的字符个数,
                记做 o(s),式中 s 代表模式。
                例如,模式 ( 011*1** ) 含有4个明确含意的字符,其阶次是4,
                            记作 o( 011*1** ) =4;
                            模式 ( 0****** ) 的阶次是1,记作 o( 0****** ) =1。

         •  阶次越低,模式的概括性越强,所代表的编码串个体数也越多,反之亦然;
         •  当模式阶次为零时,它没有明确含义的字符,其概括性最强。

模式的定义长度( Schema Defining  Length)
        ——指模式中第一个和最后一个具有明确含意的字符之间的距离,记作 (s)。
                例如,模式( 011*l** ) 的第一个字符为0,最后一个字符为l,中间有3个字
                            符,其定义长度为4,记作  ( 011*l** ) = 4 ;
                            模式 ( 0****** ) 的长度是0,记作  ( 0****** ) = 0 ;
•  一般地,有式子
                      (s)=b – a
            式中     b—模式s 中最后一个明确字符的位置;
                         a—模式s 中最前一个明确字符的位置。
 
     •  模式的长度代表该模式在今后遗传操作(交叉、变异)中被破坏的可能性:
        模式长度越短,被破坏的可能性越小,长度为0的模式最难被破坏。

3.1.3  编码字符串的模式数目
 
   (1)  模式总数
       •   二进制字符串
             假设字符的长度为l,字符串中每一个字符可取( 0, 1, * ) 三个符号中任意
         一个,可能组成的模式数目最多为:
                           3  3  3  …  3 = (2+1)l
       • 一般情况下,
             假设字符串长度为l,字符的取值为 k 种,字符串组成的模式数目 n1 最多   
          为:         n1=(k+1)l
(2)  编码字符串(一个个体编码串)所含模式总数
     •  二进制字符串
           对于长度为l的某二进制字符串,它含有的模式总数最多为:
                   2  2  2  …  2 = 2l
           [注意]
                 这个数目是指字符串已确定为0或1,每个字符只能在已定值 (0/1)或
                  * 中选取;
                  前面所述的 n1 指字符串未确定,每个字符可在{0, 1, * }三者中选取。
   
     •  一般情况下
           长度为l、取值有 k 种的某一字符串,它可能含有的模式数目最多为:
                          n2 = kl

 (3)  群体所含模式数
            在长度为l,规模为M的二进制编码字符串群体中,一般包含有2l ~ M · 2l个
         模式。
3.2  模式定理      

         由前面的叙述我们可以知道,在引入模式的概念之后,遗传算法的实质可看
     作是对模式的一种运算。对基本遗传算法(GA)而言,也就是某一模式s 的各个
     样本经过选择运算、交义运算、变异运算之后,得到一些新的样本和新的模式。

3.2.1  复制时的模式数目
           这里以比例选择算子为例研究。
   
    [公式推导]
       (1) 假设在第t次迭代时, 群体P(t)中有M个个体, 其中m个个体属于模式s, 记作m(s,t)。

       (2) 个体 ai 按其适应度 fi 的大小进行复制。
            从统计意义讲,个体ai被复制的概率pi是:
(3)  因此复制后在下一代群体 P(t+1)中,群体内属于模式s(或称与模式s匹配)
      的个体数目 m(s,t+1) 可用平均适应度按下式近似计算:

下载该资料的人也在下载 下载该资料的人还在阅读
更多 >

评论

查看更多

下载排行

本周

  1. 1电子电路原理第七版PDF电子教材免费下载
  2. 0.00 MB  |  1489次下载  |  免费
  3. 2单片机典型实例介绍
  4. 18.19 MB  |  91次下载  |  1 积分
  5. 3S7-200PLC编程实例详细资料
  6. 1.17 MB  |  27次下载  |  1 积分
  7. 4笔记本电脑主板的元件识别和讲解说明
  8. 4.28 MB  |  18次下载  |  4 积分
  9. 5开关电源原理及各功能电路详解
  10. 0.38 MB  |  9次下载  |  免费
  11. 6基于AT89C2051/4051单片机编程器的实验
  12. 0.11 MB  |  4次下载  |  免费
  13. 7基于单片机和 SG3525的程控开关电源设计
  14. 0.23 MB  |  3次下载  |  免费
  15. 8基于单片机的红外风扇遥控
  16. 0.23 MB  |  3次下载  |  免费

本月

  1. 1OrCAD10.5下载OrCAD10.5中文版软件
  2. 0.00 MB  |  234313次下载  |  免费
  3. 2PADS 9.0 2009最新版 -下载
  4. 0.00 MB  |  66304次下载  |  免费
  5. 3protel99下载protel99软件下载(中文版)
  6. 0.00 MB  |  51209次下载  |  免费
  7. 4LabView 8.0 专业版下载 (3CD完整版)
  8. 0.00 MB  |  51043次下载  |  免费
  9. 5555集成电路应用800例(新编版)
  10. 0.00 MB  |  33562次下载  |  免费
  11. 6接口电路图大全
  12. 未知  |  30319次下载  |  免费
  13. 7Multisim 10下载Multisim 10 中文版
  14. 0.00 MB  |  28588次下载  |  免费
  15. 8开关电源设计实例指南
  16. 未知  |  21539次下载  |  免费

总榜

  1. 1matlab软件下载入口
  2. 未知  |  935053次下载  |  免费
  3. 2protel99se软件下载(可英文版转中文版)
  4. 78.1 MB  |  537791次下载  |  免费
  5. 3MATLAB 7.1 下载 (含软件介绍)
  6. 未知  |  420026次下载  |  免费
  7. 4OrCAD10.5下载OrCAD10.5中文版软件
  8. 0.00 MB  |  234313次下载  |  免费
  9. 5Altium DXP2002下载入口
  10. 未知  |  233045次下载  |  免费
  11. 6电路仿真软件multisim 10.0免费下载
  12. 340992  |  191183次下载  |  免费
  13. 7十天学会AVR单片机与C语言视频教程 下载
  14. 158M  |  183277次下载  |  免费
  15. 8proe5.0野火版下载(中文版免费下载)
  16. 未知  |  138039次下载  |  免费