文档介绍：基本遗传算法(GA)1基本遗传算法描述遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛应用。在各个不同的应用领域,为了取得更好的结果,人们对GA进行了大量改进,为了不至于混淆,我们把Holland提出的算法称为基本遗传算法,简称GA、SGA(icAlgorithm)、CGA(icAlgorithm),将其它的“GA类”算法称为GAs(icAlgorithms),可以把GA看作是GAs的一种特例。(1)染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体,其等位基因由二值符号集{0,1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如:x;100111001000101101就可表示一个个体,该个体的染色体长度是l=18。咏支阁墓勒尽驴螺尖摹紧笆有逢浮呵铲区灿骨淀蕉碾残寇束闷剥灰封隋比基本遗传算法基本遗传算法(2)个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率,这里要求所有个体的适应度必须为正数或零。这样,根据不同种类的问题,必须预先确定好由目标函数值到个体适应度之间的转换规则,特别是要预先确定好当目标函数值为负数时的处理方法。(3)遗传算子基本遗传算法使用下述三种遗传算子:•选择运算:使用比例选择算子;•交叉运算:使用单点交叉算子;•变异运算:使用基本位变异算子。(4)基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定:•M:群体大小,即群体中所含个体的数量,一般取为20~100。•T:遗传运算的终止进化代数,一般取为100~500•pc:交叉概率,~•pm:变异概率,~[说明]这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响,但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中,往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。:GA=(M,F,s,c,m,pc,pm)M——群体大小;F——个体适应度评价函数;s——选择操作算于;c——交叉操作算子:m——变异操作算于;pc——交叉概率;pm——变异概率;(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+1endwhileend且章扭推骡均趴炉诈蔑檀钥铱途诛鹿丽睹豌摘空黄香担粥俞旦牌荣贸磺淋基本遗传算法基本遗传算法2基本遗传算法的实现根据上面对基本遗传算法构成要素的分析和算法描述,我们可以很方便地用计算机语言来实现这个基本遗传算法。现对具体实现过程中的问题作以下说明:(1)编码假设某一参数的取值范围是[umin,umax],用长度为l的二进制编码符号串来表示该参数,则它总共能够产生2l种不同的编码,参数编码时的对应关系如下:00000000…00000000=0umin00000000…00000001=1umin+00000000…00000010=2umin+2……11111111…11111111=2l–1umax明簇乱踊狡播功幕棱俞羌风姜涧敌贝绒氛源盅斟阑溪孔赔弄锰妆吐沽讽碉基本遗传算法基本遗传算法x=umin+(bi·2i-1)·1i=lUmaxumin2l1其中,为二进制编码的编码精度,其公式为:=Umaxumin2l1(2)解码假设某一个体的编码是:x:blbl-1bl-2……b2b1则对应的解码公式为:剪杆吕坤邮坏您采叠馏围斩垫瑟炯吃磁咙刃器擒晓辉蒜深肃警栏拯煎叹粟基本遗传算法基本遗传算法[例]设-≤x≤,精度要求=1/10000,由公式:Umaxumin2l=+11/++1==151001即:217<151001<218x需要18位{0/1}符号表示。如:010001001011010000解码:x=umin+(bi·2i-1)·1i=lUmaxumin2l1=-