遗传算法计算步骤.docx

遗传算法的计算步骤例 1：设 f ( x) ——x2 + 2x + 0.5， 求 max f (x), x e [—1,2] •(1)编码和产生初始群体 首先第一步要确定编码的策略，也就是说如何把—1到 2这个区间内的数用计 算机语言表示出来•编码时要注意以下三个原则：完备性：问题空间中所有点(潜在解)都能成为GA编码空间中的点(染色 体位串)的表现型；健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须 对应.这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体 表示为一个｛0, 1｝二进制串•当然，串长取决于求解的精度•如果要设定求解精 度到六位小数，由于区间长度为2 — (—1) — 3，则必须将闭区间［—1,2］分为3x106 等分.因为2097152 — 221 < 3x106 < 222 — 4194304所以编码的二进制串至少需要 22位.将一个二进制串血心少卩…耳％)转化为区间［—1,2］内对应的实数值很简单， 只需采取以下两步：1) 将一个二进制串(b21b20b19-b1b0)代表的二进制数化为10进制数：(b b b ...bb )—(严 b -2i) — x'21 20 19 1 0 2 i 10i—02) x' 对应的区间［—1,2］内的实数：x — —1 + x'・222—1例如，一个二进制串 a=v1000101110110101000111>g示实数 0.637197•x'=(1000101110110101000111)2=22889673x — —1 + 2288967 0.637197222—1二进制串 <0000000000000000000000>， <1111111111111111111111，>则分别 表示区间的两个端点值-1和2.利用这种方法完成了遗传算法的第一步——编码，这种二进制编码的方法完 全符合上述的编码的三个原则.首先我们来随机的产生一个个体数为4个的初始群体如下：pop(1)={<1101011101001100011110>， %% a1<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］内的值有正有负，所以必 须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目 标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率 打下基础．对于本题中的最大化问题，定义适应函数g(x)，采用下述方法：f f (x) - F ,若 f (x) - F > 0g (x) = < min min2 [ 0, 其他式中F既可以是特定的输入值，也可以是当前所有代或最近K代中f (x)的最 min小值，这里为了便于计算，将采用了一个特定的输入值．若取F =-1，则当f (x)二1时适应函数g (x)二2 ；当f (x) = -1.1时适应函数 ming(x) = 0 ．由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下f [pop(1)]={ 1.226437 , 1.318543 , -1.380607 , 0.933350 }然后通过适应函数计算出适应值分别如下取 F = -1 ，ming[pop(1)]= { 2.226437 , 2.318543 , 0 , 1.933350 }(3) 确定选择标准 这里用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率•其计算公式如下：对于给定的规模为n的群体pop={ a ,a ,a，…,a }，个体a的适应值为g(a ),12 3 n i i则其入选概率为P (a ) = —*"°丿— , i = 1,2,3,n…S (a)ii =1 由上述给出的群体，我们可以计算出各个个体的入选概率．首先可得 £ g(a ) = 6.478330 ,ii =1然后分别用四个个体的适应值去除以£4 g(a )，得：iP(a1)=2.226437 / 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⑴如下：newpop(1)={<1101011101001100011110>， %%a1<1000011001010001000010>， %%a2<1000011001010001000010>， %% a2<0110101001101110010101>} %% a4（5）交叉 交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体（Matlab程序参见附录9）.我们把之前得到的newpop（l）的四个个体两两组成一对，重复的不配对，进 行交叉．（可以在任一位进行交叉）<11010111瓦 /1001100011110〉， <1101011101010001000010〉交叉得：<10000110010100<0110101001101101000010〉，10010101〉，<100001100 1010001000010>， <1000011001001100011110><1000011001010010010101〉交叉得：<0110101001101101000010〉通过交叉得到了四个新个体，得到新的群体 jchpop （1）如下：jchpop（1）={<1101011101010001000010〉，<1000011001001100011110〉，<1000011001010010010101〉，<0110101001101101000010〉} 这里采用的是单点交叉的方法，当然还有多点交叉的方法，这里就不着重介 绍了．（6）变异 变异也就是通过一个小概率改变染色体位串上的某个基因．现把刚得到的jchpop⑴中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop（2） 如下：pop（2）= {<1101011101010001000010〉，<1000011001001100011110〉，<100001101 1010010010101〉，<0110101001101101000010〉 } 然后重复上述的选择、交叉、变异直到满足终止条件为止．（7）终止条件 遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方法，一般可设定为 50 代，此时就可能得出最优解．此种方法简单易行，但可能不是很精确（Matlab程序参见附录1）； （2）根据个体的差异来判断，通过计算 种群中基因多样性测度，即所有基因位相似程度来进行控制．。