基本遗传算法ppt课件

1、种特例。种特例。1.1 根本遗传算法的构成要素根本遗传算法的构成要素 (1) 染色体编码方法染色体编码方法根本遗传算法运用固定长度的二进根本遗传算法运用固定长度的二进制符号串来表示群体中的个体，其等位制符号串来表示群体中的个体，其等位基基来由二值符号集来由二值符号集0，1组成。组成。初始群体中各个个体的基因值用均初始群体中各个个体的基因值用均匀分布的随机数来生成。如：匀分布的随机数来生成。如： x；100111001000101101就可表示一个个体，该个体的染色体就可表示一个个体，该个体的染色体长度是长度是 l18。Procedure GABegin initialize P(0); t=0

2、; 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 x = umin + ( bi 2i

3、-1 ) 1 1i=lUmax umin2l 1 其中，其中， 为二进制编码的编码精度，其公式为：为二进制编码的编码精度，其公式为： = Umax umin2l 1 (2) 解码解码 假设某一个体的编码是：假设某一个体的编码是： x： bl bl-1 bl-2b2b1 那么对应的解码公式为：那么对应的解码公式为：例例 设设 -3.0 x 12.1 , 精度要求精度要求 =1/10000，由公式：，由公式： Umax umin2l =+ 11/1000012.1 + 3.0+ 1= 151001 即：即： 217 151001 00 if f(X)+Cmin 0F(X) =Cmax - f(X)

4、 if f(X) Cmax0 if f(X) Cmax 上述轮盘选择过程，可描画如下：上述轮盘选择过程，可描画如下： . 顺序累计群体内各个体的顺应度，得相应的累计值顺序累计群体内各个体的顺应度，得相应的累计值Si，最后一个累计值为，最后一个累计值为Sn； . 在在0, Sn区间内产生均匀分布的随机数区间内产生均匀分布的随机数r； . 依次用依次用Si与与r比较，第一个出现比较，第一个出现Si大于或等于大于或等于r的个体的个体j被选为复制对象；被选为复制对象； . 反复反复 、 项，直至新群体的个体数目等于父代群体的规模。项，直至新群体的个体数目等于父代群体的规模。论盘选择例如论盘选择例如单点

5、交叉单点交叉A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00 交叉概率交叉概率 pc = McM 式中式中 M群体中个体的数目；群体中个体的数目； Mc群体中被交换个体的数目。群体中被交换个体的数目。交叉操作例如交叉操作例如 交叉的个体是随机确定的，如下表所示。某群体有交叉的个体是随机确定的，如下表所示。某群体有n个个体，每个个体含个个体，每个个体含8 个等位基因。针对每个个体产生一个个等位基因。针对每个个体产生一个0, 1 区间的均匀随机数。假设交叉概率区间的均匀随机数。假设交叉概率 pc = 0.6，那么随机数小于，那么随机数小于

6、0.6的对应个体与其随机确定的另一个个体交叉，的对应个体与其随机确定的另一个个体交叉，交叉交叉 点随机确定。点随机确定。个体编号个体编号个体个体随机数随机数交叉操作交叉操作新个体新个体1110110000.728110110002101010110.589101010 11101010 013001011000.678001011004100011010.801100011 01100011 11变异点变异点根本位变异根本位变异 变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm 也是针对基因此言，即：也是针

7、对基因此言，即：式中式中 B每代中变异的基因数目；每代中变异的基因数目； M每代中群体拥有的个体数目每代中群体拥有的个体数目 l个体中基因串长度。个体中基因串长度。Pm = B M l 变异操作例如变异操作例如 变异字符的位置是随机确定的，如下表所示。某群体有变异字符的位置是随机确定的，如下表所示。某群体有3个个体，每个体含个个体，每个体含4 个基因。针对每个个体的每个基因产生一个个基因。针对每个个体的每个基因产生一个0, 1 区间具有区间具有3位有效数字的均位有效数字的均 匀随机数。假设变异概率匀随机数。假设变异概率 pm = 0.01，那么随机数小于，那么随机数小于0.01的对应基因值产生

8、的对应基因值产生变变 异。表中异。表中3号个体的第号个体的第4位的随机数为位的随机数为0.001，小于，小于0.01，该基因产生变异，该基因产生变异， 使使3号个体由号个体由 0010 变为变为 0011 。其他基因的随机数均大于。其他基因的随机数均大于0.01，不产生变异。，不产生变异。开开场场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如下图：如下图：该函数有两个部分极大点，该函数有两个部分极大点，分别是分别是: f(2.048, -2048)=3897.7342 和和 f(-2.048,-2.0048)=3905.9262其中后者为全局最大点。其中后者

10、为全局最大点。例如，对前述个体例如，对前述个体 X： 0000110111 11011 10001 它由这样的两个代码所组成：它由这样的两个代码所组成： y1= 55 y2 = 881 经上式的解码处置后，得到：经上式的解码处置后，得到： x1= -1.828 x2= 1.476 xi = 4.096 yi 1023 2.048 ( i = 1,2) 第五步：确定个体评价方法。第五步：确定个体评价方法。 由式由式 f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 可知，可知， Rosenbrock函数的值域函数的值域总是非负的，并且优化目的是求函数的最大值，故这里可将个体

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

12、小: M80 终止代数终止代数: T200 交叉概率：交叉概率：pc0.6 变异概率：变异概率：pm0.001 以下图为其进化过程例如及运转结果。以下图为其进化过程例如及运转结果。 图中两条曲线分别为各代群体中个体顺应度的最大值和平均值。图中两条曲线分别为各代群体中个体顺应度的最大值和平均值。(a)以下图所示分别为初始群体、第以下图所示分别为初始群体、第5代群体、第代群体、第10代群体和第代群体和第100代群体中个体的分布情况。代群体中个体的分布情况。 在图在图(a)中各个个体分布得比较均匀。中各个个体分布得比较均匀。 在图在图(b)中大量的个体分布在最优点和次最优点附近。中大量的个体分布在最优点和次最优点附近。(b)从图从图(c) 中可以看出，次最优点也被淘汰。中可以看出，次最优点也被淘汰。(c)从图从图(d)中可以看出，个体更加集中在最优点附近。中可以看出，个体更加集中在最优点附近。(d) 由该组图我们可以看出，随着进化过程的进展，群体中顺应度较低的一些个体由该组图我们可以看出，随着进化过程的进展，群体中顺应度较低的一些个体被逐渐淘汰掉，而顺应度较高的一些个领会越来越多并且它们都集中在所求