基本遗传算法(GA)

第二章基本遗传算法（GA）2.1基本遗传算法描述遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进，为了不至于混淆，我们把Holland提出的算法称为基本遗传算法，简称GA、SGA（SimpleGeneticAlgorithm)、CGA（CanonicalGeneticAlgorithm），将其它的“GA类”算法称为GAs(GeneticAlgorithms）,可以把GA看作是GAs的一种特例。2.1.1基本遗传算法的构成要素(1)染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x；100111001000101101就可表示一个个体，该个体的染色体长度是l＝18。(2)个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。(3)遗传算子基本遗传算法使用下述三种遗传算子：•选择运算：使用比例选择算子；•交叉运算：使用单点交叉算子；•变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定：•M：群体大小，即群体中所含个体的数量，一般取为20~100。•T：遗传运算的终止进化代数，一般取为100~500•pc：交叉概率，一般取为0.4~0.99•pm：变异概率，一般取为0.0001~0.1[说明]这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。2.1.2基本遗传算法的形式化定义基本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算于；c——交叉操作算子：m——变异操作算于；pc——交叉概率；pm——变异概率；2.1.3基本遗传算法描述ProcedureGABegininitializeP(0);t=0;while(t=T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileend2.2基本遗传算法的实现根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计算机语言来实现这个基本遗传算法。现对具体实现过程中的问题作以下说明：2.2.1编码与解码(1)编码假设某一参数的取值范围是[umin,umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin00000000…00000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2l–1umaxx=umin+(bi·2i-1)·1i=lUmaxumin2l1其中，为二进制编码的编码精度，其公式为：=Umaxumin2l1(2)解码假设某一个体的编码是：x：blbl-1bl-2……b2b1则对应的解码公式为：[例]设-3.0≤x≤12.1,精度要求=1/10000，由公式：Umaxumin2l=+11/1000012.1+3.0+1==151001即：217151001218x需要18位{0/1}符号表示。如：010001001011010000解码：x=umin+(bi·2i-1)·1i=lUmaxumin2l1=-0.3+70352(12.1+3)/(218-1)=1.052426=Umaxumin2l1得：2.2.2个体适应度评价如前所述，要求所有个体的适应度必须为正数或零，不能是负数。(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)＝f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)＝max(-f(X))但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求。基本遗传算法一般采用下面两种方法之一将目标函数值f(x)变换为个体的适应度F(x)：方法一：对于求目标函数最大值的优化问题，变换方法为：其中，Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：•预先指定的一个较小的数。•进化到当前代为止的最小目标函数值。•当前代或最近几代群体中的最小目标函数值。方法二：对于求目标函数最小值的优化问题，变换方法为：其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：•预先指定的一个较大的数。•进化到当前代为止的最大目标函数值。•当前代或最近几代群体中的最大目标函数值。F(X)=f(X)+Cminiff(X)+Cmin00iff(X)+Cmin≤0F(X)=Cmax-f(X)iff(X)Cmax0iff(X)Cmax2.2.3比例选择算子(1)选择算子或复制算子的作用：从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。(2)最常用和最基本的选择算子：比例选择算子。(3)比例选择算子：指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。(4)执行比例选择的手段是轮盘选择。轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度：pi=fi/fi(i=1,2,…,M)式中pi——个体i被选中的概率；fi——个体i的适应度；fi——群体的累加适应度。显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。轮盘选择的原理：图中指针固定不动，外圈的圆环可以自由转动，圆环上的刻度代表各个个体的适应度。当圆环旋转若干圈后停止，指针指定的位置便是被选中的个体。从统计意义讲，适应度大的个体，其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有时也会被“破格”选中。上述轮盘选择过程，可描述如下：Ⅰ.顺序累计群体内各个体的适应度，得相应的累计值Si，最后一个累计值为Sn；Ⅱ.在[0,Sn]区间内产生均匀分布的随机数r；Ⅲ.依次用Si与r比较，第一个出现Si大于或等于r的个体j被选为复制对象；Ⅳ.重复Ⅲ、Ⅳ项，直至新群体的个体数目等于父代群体的规模。[论盘选择示例]2.2.4单点交叉算子(1)交叉算子作用通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。(2)最常用和最基本——单点交叉算子。(3)单点交叉算子的具体计算过程如下：Ⅰ.对群体中的个体进行两两随机配对。若群体大小为M，则共有[M/2]对相互配对的个体组。Ⅱ.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为l，则共有(l-1)个可能的交叉点位置。Ⅲ.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。单点交叉运算的示例如下所示:单点交叉A；1011011100A’：1011011111B：0001110011B’：0001110000交叉概率pc=McM式中M——群体中个体的数目；Mc——群体中被交换个体的数目。[交叉操作示例]交叉的个体是随机确定的，如下表所示。某群体有n个个体，每个个体含8个等位基因。针对每个个体产生一个[0,1]区间的均匀随机数。假设交叉概率pc=0.6，则随机数小于0.6的对应个体与其随机确定的另一个个体交叉，交叉点随机确定。个体编号个体随机数交叉操作新个体1110110000.728110110002101010110.58910101011101010013001011000.678001011004100011010.8011000110110001111……………2.2.5基本位变异算子基本位变异算子是最简单和最基本的变异操作算子。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有基因值为1，则变异操作将其变为0。基本位变异因子的具体执行过程是：Ⅰ.对个体的每一个基因座，依变异概率pm指定其为变异点。Ⅱ.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。基本位变异运算的示例如下所示：A：1010101010A’：1010001010变异点基本位变异变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm也是针对基因而言，即：式中B——每代中变异的基因数目；M——每代中群体拥有的个体数目l——个体中基因串长度。Pm=BM·l变异概率[变异操作示例]变异字符的位置是随机确定的，如下表所示。某群体有3个个体，每个体含4个基因。针对每个个体的每个基因产生一个[0,1]区间具有3位有效数字的均匀随机数。假设变异概率pm=0.01，则随机数小于0.01的对应基因值产生变异。表中3号个体的第4位的随机数为0.001，小于0.01，该基因产生变异，使3号个体由0010变为0011。其余基因的随机数均大于0.01，不产生变异。开始Gen=0编码随机产生M个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入新群体中将交叉后的两个新个体添入新群体中将变异后的个体添入新群体中j=j+1j=j+2j=j+1j=M?j=pc·M?j=pm·L·M?Gen=Gen+1输出结果终止YNYYYNNNpcpm2.2.6算法流程图2.3基本遗传算法应用举例——基本遗传算法在函数优化中的应用。[例]Rosenbrock函数的全局最大值计算。maxf(x1,x2)=100(x12-x22)2+(1-x1)2s.t.-2.048≤xi≤2.048(xi=1,2)如图所示：该函数有两个局部极大点，分别是:f(2.048,-2048)=3897.7342和f(-2.048,-2.0048)=3905.9262其中后者为全局最大点。下面介绍求解该问题的遗传算法的构造过程：第一步：确定决策变量及其约束条件。s.t.-2.048≤xi≤2.048(xi=1,2)第二步：建立优化模型。maxf(x1,x2)=100(x12-x22)2+(1-x1)2第三步；确定编码方法。用长度为l0位的二进制编码串来分别表示二个决策变量x1,x2。lO位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。从离散点-2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x1和x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如X：00001101111101110001就