基本遗传算法PPT学习教案

1、会计学1基本遗传算法基本遗传算法 基本遗传算法基本遗传算法为正确计算这个概率，这里要求所有个体的适应为正确计算这个概率，这里要求所有个体的适应 度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时 的处理方法。的处理方法。 基本遗传算法使用下述三种遗传算子：基本遗传算法使用下述三种遗传算子： 选择运算：使用选择运算：使用； 交叉运算：使用交叉运算：使用； 变异运算：使用变异运

2、算：使用。 基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定：个运行参数需要提前设定： ：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量，一般取为20 100。 ：遗传运算的终止进化代数，一般取为：遗传运算的终止进化代数，一般取为100 500 ：交叉概率，一般取为：交叉概率，一般取为0. ： 第1页/共56页 这这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前前 尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次尚无合理选择它们的理论依据。在遗传算法的实际

3、应用中，往往需要经过多次试试 算后才能确定出这些参数合理的取值大小或取值范围。算后才能确定出这些参数合理的取值大小或取值范围。 基本遗传算法可定义为一个基本遗传算法可定义为一个7元组：元组： M群体大小；群体大小； F个体适应度评价函数；个体适应度评价函数； s选择操作算于；选择操作算于； c交叉操作算子：交叉操作算子： m变异操作算于；变异操作算于； pc交叉概率；交叉概率； pm变异概率；变异概率；第2页/共56页Procedure GABegin initialize P(0); t=0; while (t=T) do for i=1 to M do Evaluate fitness o

4、f 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第3页/共56页 根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用根据上面对基本遗传算法构成要素的分析和算法描述，我们可以

5、很方便地用计计 算机语言来实现这个基本遗传算法。算机语言来实现这个基本遗传算法。 现对具体实现过程中的问题作以下说明：现对具体实现过程中的问题作以下说明： 假设某一参数的取值范围是假设某一参数的取值范围是umin , umax，用长度为，用长度为l的二进制编码符号串来的二进制编码符号串来表示该参数，则它总共能够产生表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如下种不同的编码，参数编码时的对应关系如下： 00000000000000000 umin 00000000000000011 umin + 00000000000000102 umin + 2 1111111111

6、111111=2l1 umax 第4页/共56页 x = umin + ( bi 2i-1 ) 1 1i=lUmax umin2l 1 其中，其中， 为二进制编码的编码精度，其公式为：为二进制编码的编码精度，其公式为： = Umax umin2l 1 假设某一个体的编码是：假设某一个体的编码是： x： bl bl-1 bl-2b2b1 则对应的解码公式为：则对应的解码公式为：第5页/共56页 Umax umin2l =+ 11/1000012.1 + 3.0+ 1= 151001151001 即：即： 217 151001 00 if f(X)+Cmin 0F(X) =Cmax - f(X)

7、if f(X) Cmax0 if f(X) Cmax 第8页/共56页 从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。 ： 比例选择算子。比例选择算子。 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。 轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度：轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度： pi = fi / fi ( i=1,2,M ) 式中式中 pi个体个体i被选中的概率；被选中的概率；

8、fi个体个体i的适应度；的适应度； fi群体的累加适应度。群体的累加适应度。 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可 能被选中，以便增加下一代群体的多样性。能被选中，以便增加下一代群体的多样性。第9页/共56页 图中指针固定不动，外圈的圆环可图中指针固定不动，外圈的圆环可以以 自由转动，自由转动， 圆环上的刻度代表各个个圆环上的刻度代表各个个 体的适应度。当圆环旋转若干圈后停体的适应度。当圆环旋转若干圈后停止，止， 指针指定的位置便是被选中的个体。指针指定的位置便是被选中的个体。 从统计意义讲，适应度

9、大的个体，从统计意义讲，适应度大的个体，其其 刻度长，被选中的可能性大；反之，刻度长，被选中的可能性大；反之，适适 应度小的个体被选中的可能性小，但应度小的个体被选中的可能性小，但有有 时也会被时也会被“破格破格”选中。选中。第10页/共56页 上述轮盘选择过程，可描述如下：上述轮盘选择过程，可描述如下： . 顺序累计群体内各个体的适应度，得相应的累计值顺序累计群体内各个体的适应度，得相应的累计值Si，最后一个累计值为，最后一个累计值为Sn； . 在在0, Sn区间内产生均匀分布的随机数区间内产生均匀分布的随机数r； . 依次用依次用Si与与r比较，第一个出现比较，第一个出现Si大于或等于大于

10、或等于r的个体的个体j被选为复制对象；被选为复制对象； . 重复重复 、 项，直至新群体的个体数目等于父代群体的规模。项，直至新群体的个体数目等于父代群体的规模。论盘选择示例论盘选择示例第11页/共56页 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。段。正是有了交换操作，群体的性态才多种多样。单点交叉算子。单点交叉算子。 . 对群体中的个体进行两两对群体中的个体进行两两随机随机配对。配对。 若群体大小为若群体大小为M，则共有，则共有 M/2 对相互对相互 配对的个

11、体组。配对的个体组。 . 每一对相互配对的个体，每一对相互配对的个体，随机随机设置某一基因座之后的位置为交叉点。设置某一基因座之后的位置为交叉点。 若染色体的长度为若染色体的长度为l ，则共有，则共有(l-1)个可能的交个可能的交叉点位置。叉点位置。 . 对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率pc在其在其交交叉点处相互交换两个叉点处相互交换两个个个 体的部分染色体，从而产生出两个新的个体。体的部分染色体，从而产生出两个新的个体。 单点交叉运算的示单点交叉运算的示例例如下所示如下所示: 单点交叉单点交叉A；10110111 00 A：10110111 1

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

13、定的另一个个体交叉，交叉叉 点随机确定。点随机确定。个体编号个体编号个体个体随机数随机数交叉操作交叉操作新个体新个体1110110000.728110110002101010110.589101010 11101010 013001011000.678001011004100011010.801100011 01100011 11第13页/共56页 对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作作 的某一基因座上的原有基因值为的某一基因座上的原有基因值为0，则变异操作将该基因值变为，则变异操作将该基因值变为

14、1，反之，若原，反之，若原有有 基因值为基因值为1，则变异操作将其变为，则变异操作将其变为0。 . 对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率pm指定其为变异点。指定其为变异点。 . 对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替， 从而产生出一个新的个体。从而产生出一个新的个体。 基本位变异运算的示例如下所示：基本位变异运算的示例如下所示： A：1010 1 01010 A：1010 0 01010 变异点变异点基本位变异基本位变异第14页/共56页 变异是针对个体的某一个或某一些基因

15、座上的基因值执行的，因此变异概率变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm 也是针对基因而言，即：也是针对基因而言，即：式中式中 B每代中变异的基因数目；每代中变异的基因数目； M每代中群体拥有的个体数目每代中群体拥有的个体数目 l个体中基因串长度。个体中基因串长度。Pm = B M l 第15页/共56页变异操作示例变异操作示例 变异字符的位置是随机确定的，如下表所示。某群体有变异字符的位置是随机确定的，如下表所示。某群体有3个个体，每个体含个个体，每个体含4 个基因。针对每个个体的每个基因产生一个个基因。针对每个个体的每个基因产生一个0, 1 区间具有区间具有3

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

17、选择复制个体选择两个交叉个体选择两个交叉个体选择个体变异点选择个体变异点执行变异执行变异执行交叉执行交叉执行复制执行复制将复制的个体添入将复制的个体添入新群体中新群体中将交叉后的两个新个体将交叉后的两个新个体添入新群体中添入新群体中将变异后的个体添入将变异后的个体添入新群体中新群体中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1输出结果输出结果终终止止YNYYYNNNpcpm第17页/共56页。 例例 Rosenbrock函数的全局最大值计算。函数的全局最大值计算。 max f(x1,x2) = 100 (x12-x22)2 +

18、 (1-x1)2 s.t. -2.048 xi 2.048 (xi=1,2)如图所示：如图所示：该函数有两个局部极大点该函数有两个局部极大点，分别是分别是: 和和 其中后者为全局最大点。其中后者为全局最大点。第18页/共56页：确定决策变量及其约束条件。：确定决策变量及其约束条件。 s.t. -2.048 xi 2.048 (xi=1,2)建立优化模型。建立优化模型。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2确定编码方法。确定编码方法。 用长度为用长度为l0l0位的二进制编码串来分别表示二个决策变量位的二进制编码串来分别表示二个决策变量x x1 1,x,x

19、2 2。 lOlO位二进制编码串可以表示从位二进制编码串可以表示从0 0到到10231023之间的之间的10241024个不同的数，故将个不同的数，故将x x1 1,x,x2 2的定义域离散化为的定义域离散化为10231023个均等的区域，包括两个端点在内共有个均等的区域，包括两个端点在内共有10241024个不同的个不同的离散点。从离散点离散点。从离散点-2.048-2.048到离散点到离散点2.0482.048，依次让它们分别，依次让它们分别对应于从对应于从0000000000(0)到到1111111111(1023)之间的二进制编码。再将分别表示之间的二进制编码。再将分别表示x x1 1

20、和和x x2 2的二个的二个10位长的二进制编码串连接在一起，组成一个位长的二进制编码串连接在一起，组成一个20位长的二进制编码串位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如，它就构成了这个函数优化问题的染色体编码方法。例如 X：0000110111 11011 10001 就表示一个个体的基因型。就表示一个个体的基因型。第19页/共56页确定解码方法。确定解码方法。 解码时先将解码时先将20位长的二进制编码串切断为二个位长的二进制编码串切断为二个10位长的二进制编码串，然位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为后分别将它们转换为对应的十进

21、制整数代码，分别记为y1和和y2。 依据前述个体编码方法相对定义域的离散化方法可知，将代码依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变转换为变量量xi的解码公式为：的解码公式为：例如，对前述个体例如，对前述个体 X： 0000110111 11011 10001 它由这样的两个代码所组成：它由这样的两个代码所组成： y1= 55 y2 = 881 经上式的解码处理后，得到：经上式的解码处理后，得到： x1 x2= 1.476 xi = 4.096 yi 1023 2.048 ( i = 1,2)第20页/共56页 确定个体评价方法。确定个体评价方法。 由式由式 f(x1,

22、x2) = 100 (x12-x22)2 + (1-x1)2 可知，可知， Rosenbrock函数的值域函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有：取为对应的目标函数值，并且不再对它作其他变换处理，即有： F(x) = f(x1,x2)设计遗传算子。设计遗传算子。 选择运算使用比例选择算子；选择运算使用比例选择算子； 交叉运算使用单点交叉算子；交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。变异运算使用基本位变异算子。确定遗传算法的运行参数。确定遗传算法的运行参数。 对于本例，设定基本遗传算法的运行参数如下：对于本例，设定基本遗传算法的运行参数如下： 群体大小群体大小: M80 终止代数终止代数: T200 交叉概率：交叉概率：pc 变异概率：变异概率：pm第21页/共56页 下图为其进化过程示例及运行结果。下图为其进化过程示例及运行结果。 图中两条曲线分别为各代群体中个体适应度的最大值和平均值图中两条曲线分别为各代群体中个体适应度的最大值和平均值。第22页/共56页(a)下图所示分别为初始群体