基本遗传算法.ppt

《基本遗传算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基本遗传算法（GA）1基本遗传算法描述遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量改进，为了不至于混淆，我们把Holland提出的算法称为基本遗传算法，简称GA、SGA（SimpleGeneticAlgorithm)、CGA（CanonicalGeneticAlgorithm），将其它的“GA类”算法称为GAs(GeneticAlgorithms）,可以把GA看作是GAs的一种特例。1.1基本遗传算法的构成要素(1)染色体编码方法基本

2、遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x；100111001000101101就可表示一个个体，该个体的染色体长度是l＝18。(2)个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数

3、值为负数时的处理方法。(3)遗传算子基本遗传算法使用下述三种遗传算子：•选择运算：使用比例选择算子；•交叉运算：使用单点交叉算子；•变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定：•M：群体大小，即群体中所含个体的数量，一般取为20~100。•T：遗传运算的终止进化代数，一般取为100~500•pc：交叉概率，一般取为0.4~0.99•pm：变异概率，一般取为0.0001~0.1[说明]这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合

4、理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。1.2基本遗传算法的形式化定义基本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算于；c——交叉操作算子：m——变异操作算于；pc——交叉概率；pm——变异概率；1.3基本遗传算法描述ProcedureGABegininitializeP(0);t=0;while(t<=T)dofori=1toMdoEvaluatefitn

5、essofP(t);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileend2基本遗传算法的实现根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计算机语言来实现这个基本遗传算法。现对具体实现过程中的问题作

6、以下说明：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

7、umin2l1(2)解码假设某一个体的编码是：x：blbl-1bl-2……b2b1则对应的解码公式为：[例]设-3.0≤x≤12.1,精度要求=1/10000，由公式：Umaxumin2l=+11/1000012.1+3.0+1==151001即：217<151001<218x需要18位{0/1}符号表示。如：010001001011010000解码：x=umin+(bi·2i-1)·1i=lUmaxumin2l1=-0.3+70352(12.1+3)/(218-1)=1.052426=Uma

8、xumin2l1得：2.2个体适应度评价如前所述，要求所有个体的适应度必须为正数或零，不能是负数。(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)＝f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)＝max(-f