遗传算法计算步骤

1、遗传算法的计算步骤例 1：设 f (x) = x2+2x + 0.5,求 max f(x), x在1,2.(1) 编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把-1到2这个区间内的数用计 算机语言'表小出来.编码时要注意以下三个原则：完备性：问题空间中所有点(潜在解)都能成为GA编码空间中的点(染色体位申)的表现型；健全性：GA编码空间中的染色体位申必须对应问题空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应.这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个0 , 1二进制申.当然，申长取决丁求解的精度.如果要设定求解精 度到六位小数，

2、由丁区间长度为2_(一1) = 3，则必须将闭区间-1,2分为3K106 等分.因为2097152 =221 <3尺106 <222 =4194304所以编码的二进制申至少需要 22位.将一个二进制申(b21b20b19b1b0)转化为区间-1,2内对应的实数值很简单， 只需采取以下两步：1) 将一个二进制申(b21b20b19b1b0)代表的二进制数化为10进制数：21隅1成可9.§禺)2 =(' bi 210 =x' i =02) x'对应的区间-1,2内的实数：2 -( -。x = -1 x' 222 -1例如，一个二进制申 a=&l

3、t;1000101110110101000111 表示实数 0.637197.x' =(10001011101101010001112)=22889673x = -1 2288967= 0.6371972 -1二进制申 <0000000000000000000000表 <111111111111111111111)表则分别表示区间的两个端点值-1和2.编码，这种二进制编码的方法完利用这种方法完成了遗传算法的第一步全符合上述的编码的三个原则.首先我们来随机的产生一个个体数为 4个的初始群体如下：pop(1)=<1101011101001100011110表% a1<

4、;1000011001010001000010表% a2<0001100111010110000000表% a3<0110101001101110010101>% a4化成十进制的数分别为：pop(1)= 1.523032, 0.574022 , -0.697235 , 0.247238 接下来我们就要解决每个染色体个体的适应值问题了.(2) 定义适应函数和适应值由丁给定的目标函数f (x) = -x2+2x + 0.5在-1,2内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应丁适应值增大的方向，也为以后计算各

5、个体的入选概率打下基础.对丁本题中的最大化问题，定义适应函数g(x),采用下述方法：,、f(x) -Fmm,若 f(X) Fmin A0g(x)0,其他式中Fmin既可以是特定的输入值也可以是当前所有代或最近K代中f(X)的最小值，这里为了便丁计算，将采用了一个特定的输入值.若取Fmin =-1，则当f(x)=1时适应函数g(x)=2 ;当f(x) = -1.1时适应函数 g(x)=0.由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下f pop(1)= 1.226437,1.318543 , -1.380607,0.933350 然后通过适应函数计算出适应值分别如下取 Fmin

6、= -1,gpop (1)= 2.226437,2.318543 ,0,1.933350 (3) 确定选择标准这里用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例 叫作入选概率.其计算公式如下：对丁给定的规模为n的群体pop= a1 ,a2,a3,|,an，个体ai的适应值为g(ai), 则其入选概率为Ps(a)= ng(ai), i =1,2,3,. ,n寸 g(ai) i =1由上述给出的群体，我们可以计算出各个个体的入选概率.4首先可得'、g(a )= 6. 478330i日4然后分别用四个个体的适应值去除以 £ g(a),得： i旦P(a1)=2.226

7、437 / 6.478330 = 0.343675 % a1P(a2)=2.318543 / 6.478330 = 0.357892 % a2P(a3)=0 / 6.478330 =0% a3P(a4)=1.933350 / 6.478330 = 0.298433 % a4(4)产生种群计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体, 并用入选概率最大的个体补入种群，得到与原群体大小同样的种群.由初始群体的入选概率我们淘汰掉 a3,再加入a2补足成与群体同样大小的种群得到newpop(1)如下：newpop(1)=<110101110100110001111 >

8、% a1<1000011001010001000010>% a2<1000011001010001000010>% a2<0110101001101110010101> % a4(5)交义交义也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体(Matlab程序参见附录9).我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进 行交义.(可以在任一位进行交义)<1101011101001100011110><1101011101010001000010>交义得:<10000

9、1100/ ' 1010001000010，<1000011001001100011110><10000110010100-01000010>,<0110101001101110010101>,<1000011001010010010101>交义得：<0110101001101101000010>通过交义得到了四个新个体，得到新的群体 jchpop (1)如下：jchpop (1)=(<1101011101010001000010><1000011001001100011110><10000110

10、01010010010101><0110101001101101000010>这里采用的是单点交义的方法，当然还有多点交义的方法，这里就不着重介 绍了.(6)变异变异也就是通过一个小概率改变染色体位申上的某个基因.现把刚得到的 jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop(2)如下：pop(2)= (<1101011101010001000010><1000011001001100011110><1000011011010010010101><0110101001101101000010> 然后重复上述的选择、交义、变