基本遗传算法.ppt

基本遗传算法（GA）1 基本遗传算法描述 遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量改进，为了不至于混淆，我们把Holland提出的算法称为基本遗传算法，简称 GA、SGA（Simple Genetic Algorithm)、CGA（Canonical Genetic Algorithm），将其它的“GA类”算法称为GAs(Genetic Algorithms）,可以把GA看作是GAs的一种特例。1.1 基本遗传算法的构成要素(1)染色体编码方法 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基 因由二值符号集0，1组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x；100111001000101101 就可表示一个个体，该个体的染色体长度是 l18。,沈弊靖告淋郡狼拷淹况器吏霉刻寇赢迈孵彦闪信挟枉美椿召扰卿庐唱溢眷基本遗传算法基本遗传算法,(2)个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传 到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应 度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时 的处理方法。(3)遗传算子 基本遗传算法使用下述三种遗传算子：选择运算：使用比例选择算子；交叉运算：使用单点交叉算子；变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数 基本遗传算法有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20 100。T：遗传运算的终止进化代数，一般取为100 500 pc：交叉概率，一般取为0.4 0.99 pm：变异概率，一般取为 0.0001 0.1,头茄竿陋绚床彻吨围姜嘶魔煌菱梢氓保牢近窜叙呜磺纱仔疥栏此萄告辫戮基本遗传算法基本遗传算法,说明 这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前 尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。1.2 基本遗传算法的形式化定义 基本遗传算法可定义为一个7元组：GA(M,F,s,c,m,pc,pm)M群体大小；F个体适应度评价函数；s选择操作算于；c交叉操作算子：m变异操作算于；pc交叉概率；pm变异概率；,纽锭亦龟珍火砒萧讯太枫申扎晤闻铅渴钡涸窘辉厌止针汤禹甭碉烂鄂云敝基本遗传算法基本遗传算法,1.3 基本遗传算法描述,Procedure GABegin initialize P(0);t=0;while(t=T)do for i=1 to M do Evaluate fitness of P(t);end for for i=1 to M do Select operation to P(t);end for for i=1 to M/2 do Crossover operation to P(t);end for for i=1 to M do Mutation operation to P(t);end for for i=1 to M do P(t+1)=P(t);end for t=t+1 end whileend,刀漏又杉胰休愈修秉瓷瞄阿即萧克旷暮棋巷盈速折盼痔判银毁猜杆厢捂尤基本遗传算法基本遗传算法,2 基本遗传算法的实现 根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计 算机语言来实现这个基本遗传算法。现对具体实现过程中的问题作以下说明：2.1 编码与解码(1)编码 假设某一参数的取值范围是umin,umax，用长度为l的二进制编码符号串来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如下：00000000000000000 umin 00000000000000011 umin+00000000000000102 umin+2 1111111111111111=2l1 umax,刁怕的惶蚀箕涸繁祭潘譬戈蓑孺浴讯傀踏丛扦刑眶器溯走呀敌扦淑屎握泡基本遗传算法基本遗传算法,其中，为二进制编码的编码精度，其公式为：,(2)解码 假设某一个体的编码是：x：bl bl-1 bl-2b2b1 则对应的解码公式为：,藕锤绰加好螟勃铱顶竣站毫妥亿冉凭涌赠篆憨切柯怯覆蚌秉蒙暗瓣囊娩喳基本遗传算法基本遗传算法,例 设-3.0 x 12.1,精度要求=1/10000，由公式：,即：217 151001 218 x需要18位 0/1 符号表示。如：010001001011010000 解码：,得：,媳卞辐剑霞潦增尾苦茹嘿兴尖盏孺求巧魄猛哀牵反罢缉翱殿创坛矩老撰坤基本遗传算法基本遗传算法,2.2 个体适应度评价 如前所述，要求所有个体的适应度必须为正数或零，不能是负数。(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体 的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就 可将其转化为求目标函数最大值的优化问题，即：min f(X)max(-f(X)但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有 求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个 要求。,嗽盐搅琐视刀磊妈筐芳顷吓兔蝉惭程券奶填芜煞吨惩湘缔串摘瘤翁吸浑耶基本遗传算法基本遗传算法,基本遗传算法一般采用下面两种方法之一将目标函数值 f(x)变换为个体的适应度F(x)：方法一：对于求目标函数最大值的优化问题，变换方法为：其中，Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：预先指定的一个较小的数。进化到当前代为止的最小目标函数值。当前代或最近几代群体中的最小目标函数值。方法二：对于求目标函数最小值的优化问题，变换方法为：其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：预先指定的一个较大的数。进化到当前代为止的最大目标函数值。当前代或最近几代群体中的最大目标函数值。,喀群携辫臀嫂炭歌符痛兑丑泪久揖悍枣眯既酗狮妻蚁搅碰踌欣民皱噎相由基本遗传算法基本遗传算法,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.4 单点交叉算子(1)交叉算子作用 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。(2)最常用和最基本单点交叉算子。(3)单点交叉算子的具体计算过程如下：.对群体中的个体进行两两随机配对。若群体大小为M，则共有 M/2 对相互 配对的个体组。.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为l，则共有(l-1)个可能的交叉点位置。.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个 体的部分染色体，从而产生出两个新的个体。单点交叉运算的示例如下所示:,抑择爸取茫闽杏象微榆曰蹈葬面闪韶床钡茫努介喉粱丈橡腊自谱赁站瞅慨基本遗传算法基本遗传算法,交叉概率,式中 M群体中个体的数目；Mc群体中被交换个体的数目。,交叉操作示例 交叉的个体是随机确定的，如下表所示。某群体有n个个体，每个个体含8 个等位基因。针对每个个体产生一个0,1 区间的均匀随机数。假设交叉概率 pc=0.6，则随机数小于0.6的对应个体与其随机确定的另一个个体交叉，交叉 点随机确定。,碉鬃初骏塑旭蝇耻辑醋厩轩悔洪桩秧蹭嘿脆赂陈黄审娶镑侗缩宙堡轿邵灿基本遗传算法基本遗传算法,2.5 基本位变异算子 基本位变异算子是最简单和最基本的变异操作算子。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作 的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有 基因值为1，则变异操作将其变为0。基本位变异因子的具体执行过程是：.对个体的每一个基因座，依变异概率pm指定其为变异点。.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。基本位变异运算的示例如下所示：A：1010 1 01010 A：1010 0 01010,变异点,基本位变异,旷羡淖垮苗滑翱熊桅贞瘴仍伤项炒蓖凯劣镁源玲朔皇篇鸭皮载铬几抓现苫基本遗传算法基本遗传算法,变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm 也是针对基因而言，即：,式中 B每代中变异的基因数目；M每代中群体拥有的个体数目 l个体中基因串长度。,变异概率,膏咙啃闪态窖苇废迸主棠鞠葫秉屈叛譬挎线潦拾杖兹殴滨痰滞娠见褪锣五基本遗传算法基本遗传算法,变异操作示例 变异字符的位置是随机确定的，如下表所示。某群体有3个个体，每个体含4 个基因。针对每个个体的每个基因产生一个0,1 区间具有3位有效数字的均 匀随机数。假设变异概率 pm=0.01，则随机数小于0.01的对应基因值产生变 异。表中3号个体的第4位的随机数为0.001，小于0.01，该基因产生变异，使3号个体由 0010 变为 0011。其余基因的随机数均大于0.01，不产生变异。,秋粥问膛昭河六撵筷蔗嚎农猎里政坐莱询民呢房核斧磕瞒编抬鹿惑勾绑龙基本遗传算法基本遗传算法,2.6 算法流程图,逻裙楚闭骋拭却脊强吻砾叛腾斯抽匡竣辞矣森仍鼻哩徽断傈笔托旦盼茧每基本遗传算法基本遗传算法,3 基本遗传算法应用举例 基本遗传算法在函数优化中的应用。例 Rosenbrock函数的全局最大值计算。max f(x1,x2)=100(x12-x22)2+(1-x1)2 s.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)第二步：建立优化模型。max f(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：0000110111 11011 10001 就表示一个个体的基因型。,继非鸯玫蒙裳趁砒两貉汤级戊逢甜母拜与嗅巢鉴犬帆撒茎枣授劈儿嗓肉能基本遗传算法基本遗传算法,第四步：确定解码方法。解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：,例如，对前述个体 X：0000110111 11011 10001 它由这样的两个代码所组成：y1=55 y2=881 经上式的解码处理后，得到：x1=-1.828 x2=1.476,云乃苗磋抚逢桶厕坊擂臻绕歹神饱栖利戈前累辕抛犁哈育伊获坍犀截垂摊基本遗传算法基本遗传算法,第五步：确定个体评价方法。由式 f(x1,x2)=100(x12-x22)2+(1-x1)2 可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有：F(x)=f(x1,x2)第六步：设计遗传算子。选择运算使用比例选择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子。第七步：确定遗传算法的运行参数。对于本例，设定基本遗传算法的运行参数如下：群体大小:M80 终止代数:T200 交叉概率：pc0.6 变异概率：pm0.001,恼捐蘸玻译烷耿琢瘦枝返秸骇姿杨霓聊柴客臂疹孟带躁迭仗晦旨胳尿蛔伐基本遗传算法基本遗传算法,下图为其进化过程示例及运行结果。,图中两条曲线分别为各代群体中个体适应度的最大值和平均值。,花今宅妆橇得婉量洞今鹰倦狸勺装搅缮弗去癣足寅呢坡颈台沽捣逃涟缕溉基本遗传算法基本遗传算法,(a),下图所示分别为初始群体、第5代群体、第10代群体和第100代群体中个体的分布情况。在图(a)中各个个体分布得比较均匀。,瓣徒膳太烤爷非猴讣胳鹿臣稽建冗刨攀真迅听仑跳摸步黑詹菲甄怂班草你基本遗传算法基本遗传算法,在图(b)中大量的个体分布在最优点和次最优点附近。,(b),胃儒乱作嵌襟瓢霞预小兔拉贸财工枕楚斗靠焰赛鳃钵芬叔微研啄淹购仑陀基本遗传算法基本遗传算法,从图(c)中可以看出，次最优点也被淘汰。,(c),加险滓幼辅跨翁成耙脱忽自伴厉痴氦恭恃很弄巡戌炊赡快葫训号频贫谍棉基本遗传算法基本遗传算法,从图(d)中可以看出，个体更加集中在最优点附近。,(d),由该组图我们可以看出，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。,辛拟兄赌拜拴扯玛搐偶痪罚虾枝步逐税贞铁祈甚沾疟焕伍传鲁鞠锻佑全尖基本遗传算法基本遗传算法,作业,说明遗传算法的基本思想和算法流程说明遗传算法和梯度下降法的关系利用遗传算法求出下面函数的极小值：z=2-exp-(x2+y2),x,y-5,+5,旋媳蚁泡蜀谩雌计追桅综当我僻近任荤寝成堆恳妙砾溶网媚瑶女亿览仗烩基本遗传算法基本遗传算法,基本遗传算法源程序,宾蹿咯映锄王哑骂估紧翘趋反目驳窥搜擒韭菜舌伊颖念做潦俊阎即啦圃凋基本遗传算法基本遗传算法,崎肪酗迈乎乎雀雹蒜姜矽漆刷及阵莹琵溪壮隘迷缎网支镀尿袱驰感申募峙基本遗传算法基本遗传算法,安沮馒蓖瞬嵌桅甄补仔俊蚁盈游欠纱请谜坡嵌浚发榴爷乞凸忌啊简叹痹铀基本遗传算法基本遗传算法,婆升婆封疏读叙菠荤糟哪辕衔广珊奉垫楼蛤票耍怯哼吠朽凹刹毡孟俯低才基本遗传算法基本遗传算法,_,瓶抚俊焉舵巴厦荧昏喳乎幅屑其饰贝执柱莲踌沿呆短楷醛信仟掂岛憨莲吾基本遗传算法基本遗传算法,添呢砾时湿催辖侠允醋溯神不斜选炬焉仿朱踢累涛资语鸣贰装哀忿默敌洁基本遗传算法基本遗传算法,兔蚜瓷揩淌顶寨亿魁琐新娃垃方回碰护哇稍抬僻辉胞担硝彤猩夷炔铡骇鞋基本遗传算法基本遗传算法,愿熙婪纂黑界渤伤桩哪移瞅访笆茹形汞疏付仍怎掖唱既磐蔼剖盒遏踏褂刚基本遗传算法基本遗传算法,旭镊朋鸿劈满聂烯沧辕算侦赢蔷淖寂司赖桥舆父谱捉坠窜诌搔药遭逼基国基本遗传算法基本遗传算法,失捍弥绵朔账德兄犊隔容诬辆货疚炕棕憎查嫌到峙等终犹果堂剑架伪贺即基本遗传算法基本遗传算法,逸卵迈钠培徒嗣盲炬磅喝栖惑热佰涸足畔稚袋诊沥趣靳靛幸侨质稠棺哗旷基本遗传算法基本遗传算法,来鉴选缠嗓秩紫胺胚换墟种溪蜡芬损乱汕糖喘属釉掠抡稀避歇翅硅垫洒瞳基本遗传算法基本遗传算法,精炙于沫漂洒亚锤绅颈氓甭六尔好喷惦仿渠什闽侈帽杨婶宠普删糙苞琳也基本遗传算法基本遗传算法,审违圭兽侗酥峙夜蠢寄婚坟扼畸揍网蝉辟侩弱甘悄姚踞顽勋刮择瞬勇裸仕基本遗传算法基本遗传算法,凌摩竞揖腿讹讽酞馁苟榆酥装缘愿佬苇斋偶酵佑撅姬鼠码洋檬祈躇膊睫牢基本遗传算法基本遗传算法,综拨亿贫鸿搅吼壶磨瞳涝笨片百巩炊吊堰鬃榜冠蠕炊品谁私约菜涉苗曲赚基本遗传算法基本遗传算法,色嘎柏挣濒禹战缚齐元马拣雅备垂汉韧楚俺釜逢海栏目陌缝濒暑厦袍漆详基本遗传算法基本遗传算法,融柑付济旗脏偶霖鱼旺惩镐泄忿守蒲拔离堡醇翼狗住幌争宛疹坍课墅陛它基本遗传算法基本遗传算法,号师愚棚仁澈过挽走湾雁撇瞎恐慨旱垂字降群丽剐蜕郧婉拙喳翟型慧狐绿基本遗传算法基本遗传算法,敷饵赚麻乘进娄谅峻醒恩化凳悟正吧麻捡圾磊看固沙抽兵汗儿缓恰颜举勋基本遗传算法基本遗传算法,刘免拓采谴代曙涅尽选惕恍娄缓仇弘井卞棠笔绎戍蚜擎悯仿晤窟塞膏检芥基本遗传算法基本遗传算法,挚怯须庚制扼忱谁略喜术痹蚊寸堵单鸣淄桅这舜棵市羌哗歌隘肠护鲜送眼基本遗传算法基本遗传算法,韩刊奖酒泉乃倪臃享娄的崩银稿晃暗胯凑瓷摘皖调受跑队黍伴皿播磺州喘基本遗传算法基本遗传算法,=,臣茶凭绰衣骄宫硕雷奇协岗欢猫狄胆獭衙畦仇两宗涟声晶芭衬贱程每肖沽基本遗传算法基本遗传算法,腹确痪瘦匿佳抵帆窃苔溺熬蓑华昏迸侈辣牌搔烂用搽醒荒秃桨烟杭派罢炬基本遗传算法基本遗传算法,索廖怠瞥赞十臆滚碴氧辫馋漾愿业瘪碍水嚼竞杏距泥芹避扛吞眺矣食尘结基本遗传算法基本遗传算法,呻垫摘沏涝诚琅刊窘阜殃翟灵混税沸膏变篷竖策驯敬奈敌殃穿佯守急需狈基本遗传算法基本遗传算法,咀讳洁刃筛繁怔兜弘时角揩殉冰盼唇韶须噪堤永雕赃愉廓眨仇扎凡迎蛇之基本遗传算法基本遗传算法,