·424· 智能系统学报 第3卷 优解， 调形式，这恰好符合了种群多样度的各项要求， 本文为了检测种群多样度函数D值的性能，做 1一种新的种群多样性度量 了以下检验，在第次随机产生10000个[0,1之 在遗传算法中，人们最关注的问题之一就是它 间的随机数，然后用1替换其中的100个随机数， 的过早收敛.近几年的研究发现：种群只有在保持一 i∈[1,100，分别计算种群多样度D的值，得到随 定的多样性的基础上才能进化，过早收敛总是与种 机种群多样度曲线，如图2所示 群中个体趋同、种群多样性(population diversity,. 0.14入 PD)的迅速下降有密切的关系.遗传算法中多个遗 0.12 传算子参数需要根据种群的D进行自适应地调 0.10 整因此，如何合理、有效地刻画种群的多样性是遗 0.08 0.06 传算法急需解决的问题.常用的测度方法是采用海 0.04 明距离，但海明距离通常只适合二进制编码，从计算 0.02 量的角度来讲，海明距离方法运算量又显得较大.因 0102030405060708090100 此，本文从个体表现性的角度出发，根据个体适应度 测试次数 来定义了一种可以应用到各类遗传算法，而且能恰 图2随机种群多样度 当充分反映种群多样性的度量函数 Fig 2 Diversity of random population function 假设种群pop含有M个个体，分别为P,P, P,其所对应的适应度值为无，，…，石，那么种 测试曲线中，D值逐渐较稳定的从Q14左右降 群的平均适应度可记为 为O,表明本文提出的D函数对于种群的多样度具 1-h M 有极良好的反映性能.当D越接近于1，种群的多样 1) 性就越高，越不易于陷入早熟；反之接近于0时，种 则种群的多样度定义为 群很可能陷入到局部最优解之中，这时就需要采取 。姑2的 其他有效的方式来使遗传算法跳出该局部最优解。 (2) 由于在遗传算法设计适应度函数时，为了选择 2基于种群多样度的迁移算子 的方便且具有意义，一般情况下廿1满足≥0，那 生物界具有大规模的迁移习性，通过这种行为 么就有f≥0，由此可以得到： 往往使种群得到极大的发展，而遗传算法本质上是 -f-f≤方-f≤f+f (3) 一种模拟生物进化的过程，本文从中得到启发，设计 所以，0≤f-f升≤6+f升得到： 了迁移算子改进遗传算法， 1≥-≥0 然而，迁移时机很难把握.进一步分析遗传算 4) f+f 法，由于选择算子的作用，加之人们对遗传算法收敛 从而得到0≤D≤1，种群多样度函数的曲线如 性的要求，较为理想的遗传算法的种群多样性呈现 图1所示 出总体缓慢递减，随后逐步稳定的一个过程.当遗传 D 算法早期陷入到局部最优解时，解将在这一局部最 优解集中，同时遗传算法的多样性会呈现出较快下 降的态势.依据以上特点，本文采用监测种群多样度 D函数的变化，从而适时的引入迁移算子，解决迁移 时机很难把握的难题 当种群多样度函数D低于某一预先设定的值 入(T)=中.中T'/I时，对种群po即进行整体迁移替 0 换，即将种群中个体适应度最差的(100n入)%，用相 应的种群来替换更新，称此种操作为整体迁移算子 图1种群多样度函数 (T为当前种群代数，为延拓代数，规定为进化种 Fig I Diversity of population function 群代数的15倍，中为整体迁移因子，在下面的测试 当远离时，多样度函数值趋近于1，而接 实验中取中为0065.12为150，n=3). 近于0时，其值同样接近于1，且呈现出以为中心单 整体迁移算子的引入实质是为了使种群保持一 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net优解. 1 一种新的种群多样性度量 在遗传算法中 ,人们最关注的问题之一就是它 的过早收敛. 近几年的研究发现 :种群只有在保持一 定的多样性的基础上才能进化 ,过早收敛总是与种 群中个体趋同、种群多样性 ( population diversity, PD)的迅速下降有密切的关系. 遗传算法中多个遗 传算子参数需要根据种群的 PD 进行自适应地调 整. 因此 ,如何合理、有效地刻画种群的多样性是遗 传算法急需解决的问题. 常用的测度方法是采用海 明距离 ,但海明距离通常只适合二进制编码 ,从计算 量的角度来讲 ,海明距离方法运算量又显得较大. 因 此 ,本文从个体表现性的角度出发 ,根据个体适应度 来定义了一种可以应用到各类遗传算法 ,而且能恰 当充分反映种群多样性的度量函数. 假设种群 pop 含有 M 个个体 , 分别为 P1 , P2 , …, PM ,其所对应的适应度值为 f1 , f2 , …, fM ,那么种 群的平均适应度可记为 f = 1 M ∑ M i fi . (1) 则种群的多样度定义为 D = 1 M ∑ M i =1 ( fi - f fi + f ) 2 . (2) 由于在遗传算法设计适应度函数时 ,为了选择 的方便且具有意义 ,一般情况下 Π i,满足 fi ≥0,那 么就有 f≥0,由此可以得到 : - fi - f ≤ fi - f ≤ fi + f. (3) 所以 , 0≤| fi - f | ≤| fi + f | 得到 : 1 ≥ ( fi - f fi + f ) 2 ≥ 0. (4) 从而得到 0≤D ≤1,种群多样度函数的曲线如 图 1所示. 图 1 种群多样度函数 Fig. 1 D iversity of population function 当 fi 远离 f时 ,多样度函数值趋近于 1,而 fi 接 近于 0时 ,其值同样接近于 1,且呈现出以 f为中心单 调形式 ,这恰好符合了种群多样度的各项要求. 本文为了检测种群多样度函数 D 值的性能 ,做 了以下检验 ,在第 i次随机产生 10 000个 [ 0, 1 ]之 间的随机数 ,然后用 1替换其中的 100 i个随机数 , i∈[1, 100 ],分别计算种群多样度 D 的值 , 得到随 机种群多样度曲线 ,如图 2所示. 图 2 随机种群多样度 Fig. 2 D iversity of random population function 测试曲线中 , D值逐渐较稳定的从 0. 14左右降 为 0,表明本文提出的 D 函数对于种群的多样度具 有极良好的反映性能. 当 D越接近于 1,种群的多样 性就越高 ,越不易于陷入早熟;反之接近于 0时 ,种 群很可能陷入到局部最优解之中 ,这时就需要采取 其他有效的方式来使遗传算法跳出该局部最优解. 2 基于种群多样度的迁移算子 生物界具有大规模的迁移习性 ,通过这种行为 , 往往使种群得到极大的发展 ,而遗传算法本质上是 一种模拟生物进化的过程 ,本文从中得到启发 ,设计 了迁移算子改进遗传算法. 然而 ,迁移时机很难把握. 进一步分析遗传算 法 ,由于选择算子的作用 ,加之人们对遗传算法收敛 性的要求 ,较为理想的遗传算法的种群多样性呈现 出总体缓慢递减 ,随后逐步稳定的一个过程. 当遗传 算法早期陷入到局部最优解时 ,解将在这一局部最 优解集中 ,同时遗传算法的多样性会呈现出较快下 降的态势. 依据以上特点 ,本文采用监测种群多样度 D函数的变化 ,从而适时的引入迁移算子 ,解决迁移 时机很难把握的难题. 当种群多样度函数 D 低于某一预先设定的值 λ( T′) = < - <T′/ T2 时 ,对种群 pop进行整体迁移替 换 ,即将种群中个体适应度最差的 ( 100nλ) % ,用相 应的种群来替换更新 ,称此种操作为整体迁移算子. ( T′为当前种群代数 , T2 为延拓代数 ,规定为进化种 群代数的 1. 5倍 , <为整体迁移因子 ,在下面的测试 实验中取 <为 0. 065, T2 为 150, n = 3). 整体迁移算子的引入实质是为了使种群保持一 ·424· 智 能 系 统 学 报 第 3卷