3_2 遗传算法.htm

对遗传算法的定义

      <P>根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。</P>
      <P>给出目标函数f，则f(bi)称为个体bi的适应度。以</P>
      <TABLE cellSpacing=0 cellPadding=0 width="80%" align=center border=0>
        <TBODY>
        <TR>
          <TD width="77%"><IMG height=71 src="3_2 遗传算法-Dateien/6.2.ht40.gif" 
            width=210 border=0></TD>
          <TD width="23%">(3-86)</TD></TR></TBODY></TABLE></TD></TR>
  <TR>
    <TD width="100%" height=18>
      <P>为选中bi为下一代个体的次数。 </P>
      <P>显然．从式(3—86)可知：</P>
      <P>(1)适应度较高的个体，繁殖下一代的数目较多。</P>
      <P>(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。</P>
      <P>这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。</P>
      <P>3．交叉<BR>对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。</P>
      <P>例如有个体</P>
      <P>S1=100101</P>
      <P>S2=010111</P>
      <P>选择它们的左边3位进行交叉操作，则有</P>
      <P>S1=010101</P>
      <P>S2=100111</P>
      <P>一般而言，交叉幌宰P。取值为0.25—0.75。</P>
      <P>4．变异</P>
      <P>根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。</P>
      <P>例如有个体S＝101011。</P>
      <P>对其的第1，4位置的基因进行变异，则有</P>
      <P>S'=001111</P>
      <P>单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。</P>
      <P>5．全局最优收敛(Convergence to the global optimum)</P>
      <P>当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。</P>
      <P>图3—7中表示了遗传算法的执行过程。</P>
      <P align=center><IMG height=312 src="3_2 遗传算法-Dateien/6.2.ht41.gif" 
      width=558 border=0></P>
      <P align=center>图3-7 遗传算法原理</P></TD></TR>
  <TR>
    <TD width="100%" height=1104>
      <P>3．2．3遗传算法的应用 </P>
      <P>遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。</P>
      <P>一、遗传算法的特点</P>
      <P>1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。</P>
      <P>这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。</P>
      <P>2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。</P>
      <P>由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。</P>
      <P>3．遗传算法有极强的容错能力</P>
      <P>遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。</P>
      <P>4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。</P>
      <P>这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。</P>
      <P>5．遗传算法具有隐含的并行性</P>
      <P>遗传算法的基础理论是图式定理。它的有关内容如下：</P>
      <P>(1)图式(Schema)概念</P>
      <P>一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1x x 0 x x是一个图式。</P>
      <P>(2)图式的阶和长度</P>
      <P>图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用<SPAN 
      style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 10.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">δ</SPAN>(H)表示。对于图式H＝1x 
      x0x x，有0(H)＝2，<SPAN 
      style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 10.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">δ</SPAN>(H)＝4。</P>
      <P>(3)Holland图式定理</P>
      <P>低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n<SUP>3</SUP>)。</P>
      <P>遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。</P>
      <P>二、遗传算法的应用关键</P>
      <P>遗传算法在应用中最关键的问题有如下3个</P>
      <P>1．串的编码方式</P>
      <P>这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。</P>
      <P>2．适应函数的确定</P>
      <P>适应函数(fitness function)也称对象函数(object 
      function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。</P>
      <P>3．遗传算法自身参数设定</P>
      <P>遗传算法自身参数有3个，即群体大小n、交叉概率P<SUB>c</SUB>和变异概率P<SUB>m</SUB>。</P>
      <P>群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率P<SUB>c</SUB>太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率P<SUB>m</SUB>太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取P<SUB>m</SUB>＝0．01—0．2。</P>
      <P>三、遗传算法在神经网络中的应用</P>
      <P>遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。 
      <P>1．遗传算法在网络学习中的应用 
      <P>在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用 
      <P>(1)学习规则的优化 
      <P>用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。 
      <P>(2)网络权系数的优化 
      <P>用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。 
      <P>2．遗传算法在网络设计中的应用 
      <P>用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种： 
      <P>(1)直接编码法 
      <P>这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。 
      <P>(2)参数化编码法 
      <P>参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。 
      <P>(3)繁衍生长法 
      <P>这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。 

      <P>3．遗传算法在网络分析中的应用 
      <P>遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。 

      <P>遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。</P></TD></TR>
  <TR>
    <TD width="100%" height=20>
      <P align=right><A 
      href="http://www.jgchina.com/ednns/ednnsbk/6.htm">上一页</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      <A 
  href="http://www.jgchina.com/ednns/ednnsbk/6.3.htm">下一页</A></P></TD></TR></TBODY></TABLE></BODY></HTML>