一、GA算法具有下述特点： 

GA是对问题参数的编码组进行进货，而不是直接对参数本身。

GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始。

GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息。

GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。

 

    实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，Holland给出了图式定理。所谓图式，就是某些码位取相同值的编码的集合。图式定理说明在进化过程的各代中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长。另外，Holland还发现遗传算法具有隐含的并行计算特性。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解。   
    
  将遗传算法用于解决各种实际问题后，人们发现遣传算法也会由于各种原因过早向目标函数的局部最优解收敛，从而很难找到全局最优解。其中有些是由于目标函数的特性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是由于算法设计不当。为此，不断有人对遗传算法提出各种各样的改进方案。例如：针对原先的定长二进制编码方案；提出了动态编码、实数编码等改进方案；针对按比例的选择机制，提出了竞争选择、按续挑选等改进方案；针对原先的一点交叉算子，提出了两点交叉、多点交叉、均匀交叉等算子；针对原先遗传算法各控制参数在进化过程中不变的情况，提出了退化遗传算法、自适应遗传算法等。另外，针对不同问题还出现了分布式遗传算法、并行遗传算法等等。   
    
    近年来，随着对于遗传算法研究的不断深入完善，有越来越多的人认识了解了遗传算法，并把它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网络、工业优化控制和社会科学等方面。特别是在解决旅行商问题、煤气管道的最优控制、通信网络链接长度的优化问题、铁路运输计划优化、喷气式收音机涡轮机的设计、VLSI版面设计、键盘排列优化等问题上遗传算法都取得了很大的成功。   
    
    目前国际国内有关GA的研究热潮方兴未艾。除从1985年起每两年举办一届GA国际会议外，还有MIT从1993年开始出版的《Evolutionary   Computatio》和《Adaptive   Behavior》两种杂志、IEEE从今年起出版的专门关于进化计算的汇刊。另外，各种AI类的杂志不断出版有关进化计算的专辑。其它有关GA理论和工程应用的文章也在各种不同类型杂志上不断涌现。国内有关GA的研究也正在不断深入地展开。  

 

二、遗传算法框架

在遗传算法中,将问题的求解的过程,看成一个在候选解空间寻找满足问题要求的解或近似解的搜索过程。遗传算法的重点在适应规划和适应度量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索,一般采用遗传算子(或称遗传操作)诸如交配(Crossover)和变异(Mutation)等,以及模拟自然过程的选择机制,而适应度量采用计算适应值的方法来评估一个候选解的优劣。     
    
 遗传算法求解问题的过程如下:     
  1.   首先生成一组初始的候选解群体(假设为M个候选解个体),称为第0代;     

  2.   计算群体中各个候选解的适应值;    
  3.   如果有候选解满足算法终止条件,算法终止,否则继续4;     
  4.   根据交配概率,将候选解群体中的个体随机两两配对,进行交配操作以生成新的候选解;     
  5.   根据变异概率,对4中生成的候选解群中的每个个体进行变异操作;     
  6.   使用选择机制形成新一代候选解;转2。   
从上面的算法过程中,我们可以知道,用遗传算法来求解问题有四个基本要素:1候选解的表示方式;2适应值的定义及度量方法;3算法的控制参数与变量;4算法终止准则。

   候选取解的表示方式,最简单的就是采用定长二进制编码。如我们可以将十进制的40转换成二进制的串,(40)10=(101000)2,反过来就可以将一个二进制串解码为一个十进制整数。    

    适应值的定义及度量方法与要解决的问题有关,通常用目标函数来评估候选取解的优劣。

    算法的控制参数与变量。通常,我们把每一代中的候选解个数M称为群体规模,群体规模M在整个算法中一般是不变的一个常数。遗传操作主要是杂交和变异两个算子,并有其相应的概率参数(Pc:杂交概率,Pm变异概率)来进行控制。遗传算法求解问题时,并不保证能找到满足问题要求的解,所以,还要设定算法的最大迭代次数(或称为代数)。 

     算法终止准则一般有:找到了满足问题的解;候选取群体已收敛于某一点;算法已达到了设定的代数等。

     这样,一个简单遗传算法的框架可非形式化地表示如下:     
          Simple_Genetic_algorithm()

      {     

          t:=1;   /*变量t表示迭代代数*/  

          初始化候选解群体Population(t);

          计算各个解的适应值;  

          do   while(终止条件不满足) 

          {   

          随机地将群中的个体两两配对,进行交配操作; 

          执行变异操作; 

          利用选择机制形成下一代候选取:Population(t+1):=Selection(Population(t));  

            t:=t+1;  

          }     

          }    

三、   交配、变异及选择  

          我们以二进制的表示方式来解释遗传算子及选择机制。

          在自然生物界,一个生物个体的特征通常被认为是由其父辈遗传下来的, 当然也可能有部分变异。而遗传是由DNA来决定的。我们现在将一个候选解看成为生物个体中的一条DNA(假设该种生物的遗传物质只有一条DNA,并且不存在性别差异,即任意两个个体都可以进行交配),DNA链上的基因只有两种类型,可以分别将其定义为0或1。交配操作就是将两个父辈串随机从同一个位置分成两段,然后进行相应段的交换,生成两个相应的子女。    
    变异算子相对就要简单些,从个体串中随机将某一位按变异概率进行翻转(0翻转为1,1翻转为0,即所谓的基因变)。

    在实际算法中,双亲进行交配操作是由交配概率Pc来控制,交配点的选择也是随机产生的。变异操作由变异概率进行控制。在群体规模为M的算法中,由M个个体的父辈群通过交配生成M个后代,M个后代再经过变异操作又生成M个子代,这样就要从M个父辈和M个子代中选择M个个体来形成下一代解群体。简单遗传算法就从M个子代中选择M个个体来生成下一代。借鉴达尔文的进化论的观点,适者生存,不适应者被淘汰,那么,适应值高的个体就应该有更高的机会生存下来,而适应值很低的个体就被淘汰。也就是说,适应值高的个体应该有更多的机会来繁殖多个后代,适应值低的个体就没有机会繁殖后代。

    在遗传算法中,采用按比选择的机制来形成下一代。设整个解群的平均适应值为f   avg,则一个适应值为   f   I的个体将被分配到f   i/   f   avg个后代。  

    这样,高出平均适应值的个体将会获得多于一个的子女,而低于平均适应值的个体最多只能得到一个后代.

    简单遗传算法采用一种称为"轮转法"的方法来实现按比例选择机制。在一个圆中,整个圆的弧度角为2л。根据适应值,每个个体串f   I在圆中分配这一个扇区(如图1),扇区弧度的大小为(2лf   i/f   avg)。所有扇区分配后,只要在0到2л之间产生一个随机数,该随机数落在哪个扇区内,则该个体将被选中一次,有期望获得繁殖以产生后代。在群体规模为M的算法中,只要重复地产生M个这样的随机数,就可以从经过遗传操作生成的M个子代中选择出M个体来形成下一代(当然,有些个体一次都可能不会被选中,而有些个体被重复选中多次,下一代中就出现了多个同样的父辈)。

 四、   一个例子 

      我们以一个极简单的函数优化的例子来说明遗传算法的工作过程。

      设函数f(x)=x2,x为整数且0≤x≤15,求Max(f(x))。由于0≤x≤15,所以一个解个体采用二进制编码时,只要4位长度就可以了(因为(15)10=(1111)2)。我们直接将x2作为个体x的适应值,适应值越大,解的满意度就越高。

解的群体规模M=4;交配概率Pc=1.0;变异概率Pm=0.01。选择机制采用"轮转法。 

      整个算法共执行了五代,在第五代中找到了一个满足要求的解。整个过程中,只有第三代中的S4的第二位发生了变异操作(Pm=0.01是个很小的值)。第一代的结果中,S3的适应值为0而被淘汰,S4则被选择两次。所以第二代中S4的个体出现了两个。同样地,后续代中,S4被选择两次,相应的S1及S3被淘汰。