基本遗传算法89

1、 遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量改进，为了不至于混淆，我们把Holland提出的算法称为基本遗传算法，简称 GA、SGA（Simple Genetic Algorithm )、CGA（Canonical Genetic Algorithm），将其它的“GA类”算法称为GAs(Genetic Algorithms）,可以把GA看作是GAs的一种特例。 基本遗传算法使用来表示群体中的个体，其等位基 因由二值符号集0，1组成。 初始群体中各个个体的基因值用均匀分布的随机数来生成。如： x；1001110010

2、00101101 就可表示一个个体，该个体的染色体长度是 l18。 基本遗传算法为正确计算这个概率，这里要求所有个体的适应 度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时 的处理方法。 基本遗传算法使用下述三种遗传算子： 选择运算：使用； 交叉运算：使用； 变异运算：使用。 基本遗传算法有下述4个运行参数需要提前设定： ：群体大小，即群体中所含个体的数量，一般取为20 100。 ：遗传运算的终止进化代数，一般取为100 500 ：交叉概率，一般取为0.4 0.99 ：变异概率，一般取为 0.0001 0

3、.1 这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前 尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。 基本遗传算法可定义为一个7元组： M群体大小； F个体适应度评价函数； s选择操作算于； c交叉操作算子： m变异操作算于； pc交叉概率； pm变异概率；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 Sel

4、ect 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 根据上面对基本遗传算法构成要素的分析和算法描述，我们可以很方便地用计 算机语言来实现这个基本遗传算法。 现对具体实现过程中的问题作以下说明： 假设某一参数的取值范围是umin , umax，用长度为l的二进制

5、编码符号串来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如下： 00000000000000000 umin 00000000000000011 umin + 00000000000000102 umin + 2 1111111111111111=2l1 umax x = umin + ( bi 2i-1 ) 1 1i=lUmax umin2l 1 其中， 为二进制编码的编码精度，其公式为： = Umax umin2l 1 假设某一个体的编码是： x： bl bl-1 bl-2b2b1 则对应的解码公式为：例 设 -3.0 x 12.1 , 精度要求 =1/10000，

6、由公式： 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 从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。 ： 比例选择算子。 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。 轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度： pi = fi / fi ( i=1,2,M ) 式中 pi个体i被选中的概率； fi个体i的适应度； fi群体的累加

7、适应度。 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可 能被选中，以便增加下一代群体的多样性。 图中指针固定不动，外圈的圆环可以 自由转动， 圆环上的刻度代表各个个 体的适应度。当圆环旋转若干圈后停止， 指针指定的位置便是被选中的个体。 从统计意义讲，适应度大的个体，其 刻度长，被选中的可能性大；反之，适 应度小的个体被选中的可能性小，但有 时也会被“破格”选中。 上述轮盘选择过程，可描述如下： . 顺序累计群体内各个体的适应度，得相应的累计值Si，最后一个累计值为Sn； . 在0, Sn区间内产生均匀分布的随机数r； . 依次用Si与r比较，第一个出现Si大于或等于r的

8、个体j被选为复制对象； . 重复 、 项，直至新群体的个体数目等于父代群体的规模。论盘选择示例 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。单点交叉算子。 . 对群体中的个体进行两两随机配对。 若群体大小为M，则共有 M/2 对相互 配对的个体组。 . 每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。 若染色体的长度为l ，则共有(l-1)个可能的交叉点位置。 . 对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个 体的部分染色体，从而产生出两个新的个体。 单点交叉运算的示例如下所示: 单点交叉A

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

10、013001011000.678001011004100011010.801100011 01100011 11 对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作 的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有 基因值为1，则变异操作将其变为0。 . 对个体的每一个基因座，依变异概率pm指定其为变异点。 . 对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替， 从而产生出一个新的个体。 基本位变异运算的示例如下所示： A：1010 1 01010 A：1010 0 01010 变异点基本位变异 变异是针对个体的某一个或某一些基因座上

11、的基因值执行的，因此变异概率pm 也是针对基因而言，即：式中 B每代中变异的基因数目； M每代中群体拥有的个体数目 l个体中基因串长度。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，不产生变异。开始Gen=0编码随机产生M个初始个

12、体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j = 0j = 0j = 0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入新群体中将交叉后的两个新个体添入新群体中将变异后的个体添入新群体中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1输出结果终止YNYYYNNNpcpm。 例 Rosenbrock函数的全局最大值计算。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 s.t. -2.048 xi 2.048 (xi=1,2)如图所示：该

13、函数有两个局部极大点，分别是: 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确定编码方法。 用长度为l0l0位的二进制编码串来分别表示二个决策变量x x1 1,x,x2 2。 lOlO位二进制编码串可以表示从0 0到10231023之间的10241024个不同的数，故将x x1 1,x,x2 2的定义域离散化为10231023个

14、均等的区域，包括两个端点在内共有10241024个不同的离散点。从离散点-2.048-2.048到离散点2.0482.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x x1 1和x x2 2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如 X：0000110111 11011 10001 就表示一个个体的基因型。确定解码方法。 解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y

15、2。 依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：例如，对前述个体 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函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对

16、它作其他变换处理，即有： F(x) = f(x1,x2)设计遗传算子。 选择运算使用比例选择算子； 交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。确定遗传算法的运行参数。 对于本例，设定基本遗传算法的运行参数如下： 群体大小: M80 终止代数: T200 交叉概率：pc0.6 变异概率：pm0.001 下图为其进化过程示例及运行结果。 图中两条曲线分别为各代群体中个体适应度的最大值和平均值。(a)下图所示分别为初始群体、第5代群体、第10代群体和第100代群体中个体的分布情况。 在图(a)中各个个体分布得比较均匀。 在图(b)中大量的个体分布在最优点和次最优点附近。(b)从图(c)

17、 中可以看出，次最优点也被淘汰。(c)从图(d)中可以看出，个体更加集中在最优点附近。(d) 由该组图我们可以看出，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。作业 说明遗传算法的基本思想和算法流程 说明遗传算法和梯度下降法的关系 利用遗传算法求出下面函数的极小值：z=2-exp-(x2+y2), x,y-5,+5基本遗传算法源程序_=i + += = i + +_= i=z)v&s!pXmUiRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYn

18、VjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G

19、5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#

20、oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLa

21、I6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pY

22、mUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7

23、G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$r

24、ZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK

25、9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#

26、oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLa

27、I6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pY

28、mUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7

29、G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z%s#oXlTiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYn

30、VkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G

31、5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(uZnVkShPdMaJ7F4C0z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-