基本遗传算法学习教案

1、会计学1基本基本(jbn)遗传算法遗传算法第一页，共57页。第1页/共56页第二页，共57页。第2页/共56页第三页，共57页。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 o

2、peration to P(t); end for for i=1 to M do P(t+1) = P(t); end for t=t+1 end whileend第3页/共56页第四页，共57页。第4页/共56页第五页，共57页。 x = umin + ( bi 2i-1 ) 1 1i=lUmax umin2l 1 其中，其中， 为二进制编码为二进制编码(bin m)的编码的编码(bin m)精度精度，其公式为：，其公式为： = Umax umin2l 1 (2) 解码解码 假设某一个体的编码假设某一个体的编码(bin m)是：是： x： bl bl-1 bl-2b2b1 则对应的解码公式

3、为：则对应的解码公式为：第5页/共56页第六页，共57页。 Umax umin2l =+ 11/1000012.1 + 3.0+ 1= 151001151001 即：即： 217 151001 00 if f(X)+Cmin 0F(X) =Cmax - f(X) if f(X) Cmax0 if f(X) Cmax 第8页/共56页第九页，共57页。第9页/共56页第十页，共57页。第10页/共56页第十一页，共57页。 上述轮盘选择上述轮盘选择(xunz)过程，可描述如下：过程，可描述如下： . 顺序累计群体内各个体的适应度，得相应的累计值顺序累计群体内各个体的适应度，得相应的累计值Si，最

4、后一个累计值为，最后一个累计值为Sn； . 在在0, Sn区间内产生均匀分布的随机数区间内产生均匀分布的随机数r； . 依次用依次用Si与与r比较，第一个出现比较，第一个出现Si大于或等于大于或等于r的个体的个体j被选为复制对象；被选为复制对象； . 重复重复 、 项，直至新群体的个体数目等于父代群体的规模。项，直至新群体的个体数目等于父代群体的规模。论盘选择论盘选择(xunz)示例示例第11页/共56页第十二页，共57页。单点交叉单点交叉A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00第12页/共56页第十三页，共57页。 交叉交叉

5、(jioch)概率概率 pc = McM 式中式中 M群体中个体群体中个体(gt)的数目；的数目； Mc群体中被交换个体群体中被交换个体(gt)的数目。的数目。交叉操作示例交叉操作示例(shl) 交叉的个体是随机确定的，如下表所示。某群体有交叉的个体是随机确定的，如下表所示。某群体有n个个体，每个个体含个个体，每个个体含8 个等位基因。针对每个个体产生一个个等位基因。针对每个个体产生一个0, 1 区间的均匀随机数。假设交叉概率区间的均匀随机数。假设交叉概率 pc = 0.6，则随机数小于，则随机数小于0.6的对应个体与其随机确定的另一个个体交叉，交叉的对应个体与其随机确定的另一个个体交叉，交叉

6、 点随机确定。点随机确定。个体编号个体编号个体个体随机数随机数交叉操作交叉操作新个体新个体1110110000.728110110002101010110.589101010 11101010 013001011000.678001011004100011010.801100011 01100011 11第13页/共56页第十四页，共57页。变异变异(biny)点点基本基本(jbn)位变异位变异第14页/共56页第十五页，共57页。 变异是针对个体的某一个或某一些变异是针对个体的某一个或某一些(yxi)基因座上的基因值执行的，因此变异概率基因座上的基因值执行的，因此变异概率pm 也是针对基因而

7、言，即：也是针对基因而言，即：式中式中 B每代中变异的基因数目；每代中变异的基因数目； M每代中群体拥有的个体每代中群体拥有的个体(gt)数目数目 l个体个体(gt)中基因串长度。中基因串长度。Pm = B M l 第15页/共56页第十六页，共57页。变异操作变异操作(cozu)示例示例 变异字符的位置是随机确定的，如下表所示。某群体有变异字符的位置是随机确定的，如下表所示。某群体有3个个体，每个体含个个体，每个体含4 个基因。针对每个个体的每个基因产生一个个基因。针对每个个体的每个基因产生一个0, 1 区间具有区间具有3位有效数字的均位有效数字的均 匀随机数。假设变异概率匀随机数。假设变异

8、概率 pm = 0.01，则随机数小于，则随机数小于0.01的对应基因值产生变的对应基因值产生变，该基因产生变异，该基因产生变异， 使使3号个体由号个体由 0010 变为变为 0011 。其余基因的随机数均大于。其余基因的随机数均大于0.01，不产生变异。，不产生变异。第16页/共56页第十七页，共57页。开开始始Gen=0编码编码随机产生随机产生M个初始个体个初始个体满足终止条件满足终止条件?计算群体中各个体适应度计算群体中各个体适应度从左至右依次执行遗传算子从左至右依次执行遗传算子j = 0j = 0j = 0根据适应度选择复制个体根据适应度选择复制个体选择两个交叉个体选择两个交叉个体选择

9、个体变异点选择个体变异点执行变异执行变异执行交叉执行交叉执行复制执行复制将复制的个体添入将复制的个体添入新群体中新群体中将交叉后的两个新个体将交叉后的两个新个体添入新群体中添入新群体中将变异后的个体添入将变异后的个体添入新群体中新群体中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1输出结果输出结果终终止止YNYYYNNNpcpm第17页/共56页第十八页，共57页。如图所示：如图所示：该函数该函数(hnsh)有两个局部极大有两个局部极大点，点，分别是分别是: 和和 其中后者为全局最大点。其中后者为全局最大点。第18页/共56页第

10、十九页，共57页。第19页/共56页第二十页，共57页。例如，对前述个体例如，对前述个体(gt) X： 0000110111 11011 10001 它由这样的两个代码所组成：它由这样的两个代码所组成： y1= 55 y2 = 881 经上式的解码处理后，得到：经上式的解码处理后，得到： x1 x2= 1.476 xi = 4.096 yi 1023 2.048 ( i = 1,2)第20页/共56页第二十一页，共57页。 第五步：确定个体评价方法。第五步：确定个体评价方法。 由式由式 f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 可知，可知， Rosenbrock函

11、数的值域总是函数的值域总是(zn sh)非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有：函数值，并且不再对它作其他变换处理，即有： F(x) = f(x1,x2)第六步：设计遗传算子。第六步：设计遗传算子。 选择运算使用比例选择算子；选择运算使用比例选择算子； 交叉运算使用单点交叉算子；交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。变异运算使用基本位变异算子。第七步：确定遗传算法的运行参数。第七步：确定遗传算法的运行参数。 对于本例，设

12、定基本遗传算法的运行参数如下：对于本例，设定基本遗传算法的运行参数如下： 群体大小群体大小: M80 终止代数终止代数: T200 交叉概率：交叉概率：pc 变异概率：变异概率：pm第21页/共56页第二十二页，共57页。 下图为其进化过程下图为其进化过程(guchng)示例及运行结果。示例及运行结果。 图中两条曲线图中两条曲线(qxin)分别为各代群体中个体适应度的最大值和平均值。分别为各代群体中个体适应度的最大值和平均值。第22页/共56页第二十三页，共57页。(a)下图所示分别为初始群体、第下图所示分别为初始群体、第5代群体、第代群体、第10代群体和第代群体和第100代群体中个体的分布情

13、况。代群体中个体的分布情况。 在图在图(a)中各个中各个(gg)个体分布得比较均匀。个体分布得比较均匀。第23页/共56页第二十四页，共57页。 在图在图(b)中大量的个体分布在最优点中大量的个体分布在最优点(yudin)和次最优点和次最优点(yudin)附近。附近。(b)第24页/共56页第二十五页，共57页。从图从图(c) 中可以中可以(ky)看出，次最优点也被淘汰。看出，次最优点也被淘汰。(c)第25页/共56页第二十六页，共57页。从图从图(d)中可以看出，个体更加集中在最优点中可以看出，个体更加集中在最优点(yudin)附近。附近。(d) 由该组图我们可以看出，随着进化过程的进行，群

14、体由该组图我们可以看出，随着进化过程的进行，群体(qnt)中适应度较低的一些个体被逐渐淘中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优点附近，从而最终汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。就可搜索到问题的最优解。第26页/共56页第二十七页，共57页。第27页/共56页第二十八页，共57页。基本基本(jbn)遗传算法源程序遗传算法源程序第28页/共56页第二十九页，共57页。第29页/共56页第三十页，共57页。第30页/共56页第三十一页，共57页。第31页/共56页第三

15、十二页，共57页。_第32页/共56页第三十三页，共57页。第33页/共56页第三十四页，共57页。第34页/共56页第三十五页，共57页。第35页/共56页第三十六页，共57页。第36页/共56页第三十七页，共57页。第37页/共56页第三十八页，共57页。第38页/共56页第三十九页，共57页。第39页/共56页第四十页，共57页。=i + +第40页/共56页第四十一页，共57页。第41页/共56页第四十二页，共57页。= i + +第42页/共56页第四十三页，共57页。第43页/共56页第四十四页，共57页。_= i第44页/共56页第四十五页，共57页。第45页/共56页第四十六页，共57页。第46页/共56页第四十七页，共57页。第47页/共56页第四十八页，共57页。第48页/共56页第四十九页，共57页。=第49页/共56页第五十页，共57页。第50页/共56页第五十一页，共57页。=第51页/共56页第五十二页，共57页。第52页/共56页第五十三页，共57页。第53页/共5