第5期 刘胜，等：一种基于种群多样度的实数编码并行遗传算法 ·425. 定的多样度，调整种群的多样度按期望的梯度下降 下 有利于遗传算法的全局收敛.整体迁移算子引入准 =对+1-D)川场-…d (5 则示意图如图3所示 、=店+1+D)1场-"d 式中：D为种群多样度的大小.相比于文献「9]，该 算法除了保持原有算法的优点外，由于在遗传算法 初期D较大，而在后期会逐渐减小，因此在算法初 期扩大了搜索的范围，而在算法后期加速了算法的 收敛，提高了算法的整体性能 B 32参数的自适应调整 一方面，为了使遗传算法具有更强的鲁棒性、全 局最优性和效率，当算法提前收敛时，加大P和A: 在算法后期减小P和A:另一方面，为了保持优良 图3迁移算子引入准则示意图 个体，不能对所有的个体采取同一个？和A,本文 Fig 3 Migration operator mport rule 结合Striniras的自适应交叉和变异率，对其进行改 图3中，T为进化代数，T,为种群总进化代数 进设计R和A,如下： 图中AB线以上即1区)为期望的种群多样度变化 Pemax-Pcmin 域，随着种群代数的进化呈现出线性递减规律：若在 ep ((12)) +Pcmin' 点ax≤g 进化的过程中多样度低于AB线即2区)时，遗传 P e·石n 算法有可能陷入到局部最优解当中，在此种情况下 Pcmm 点ax>e 需要对种群中的最差个体进行随机替换.遵循陷入 (6) 早熟代数越早，替换越多种群的原则，本文采用正比 PmmPmn 于多样度函数下降斜率替换的策略 2· 一+Pmm 点an≤fie 上述设计方式的优点在于： 1 exp((1-- 人e·石n 1)由于种群多样度函数具有监测作用，预报了 Pa min 点ax≤fg 遗传算法陷入早熟的可能性概率和时间： 7) 2)一旦陷入到早熟状态，可以根据所处进化阶 式中：A=9903438,点x、右m分别为交叉的2个个体 段的不同情况，自适应地控制随机迁移算子引入的 的高、低适应度值，为该群体的平均适应度 多寡； P:mm、Pmn、Pa max P min为个人设定的交叉最大概 3)可以根据计算的要求，动态地调整种群延拓 率、交叉最小概率、变异最大概率、变异最小概率.本 代数的大小，方便对选择压力进行自适应地调节 文在下面的测试过程中本文取子群体Pmx、Pm血 3并行遗传算法算子设计及其流程 Pma、Pmn为1、0、Q01、0,取主群体Pmax、Peman P.max、Pmmn为07、0、00005、0 31基于种群多样度的交叉算子改进 33算法并行结构设计及其流程 在文献「9中给出了关于交叉算子的改进算 算法采用并行结构，共有3个子种群，并由此产 法，但其计算的方案并未根据遗传算法的进化过程 生一个主群体和一个融合种群.本文提出“整体迁 进行动态地调节.而实际过程中，当种群进化到一定 移算子+相互迁移”的思想，即各个子群体本身实 阶段后，就必须在所搜索到的个体中进行重点的搜 现由上文提出的整体迁移算子，并在进化过程中，子 索，而不应该与算法初期搜索的方式一样.由于种群 群体间也进行种群相互迁移.其迁出迁入的个数由 多样度函数恰当地反映了遗传算法的进化阶段，因 各种群进化效果决定0)，但其迁移总数目保持不 此本文将多样度函数嵌入到交叉策略中，对于文献 变，具体如式(8)所示： [9中的搜索方式进行改进 E afuist +bf+df (8) 2个待交叉个体为x、x,判断其适应度的高低， 式中：为种群最优个体的适应度；为种群的平均 并记为石咖人，相应的个体记为：xx令交叉的搜 适应度：△为相邻2次个体迁移间种群平均适应度 索方向d,即一个个体沿着方向d从区域 的变化，表示种群的进化速度；a、bc为常数，且 a+b+c=1,一般取a>b>c 人向另一个区域石前进，则实数交叉策略操作如 迁移后的种群大小由式(9)决定 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net定的多样度 ,调整种群的多样度按期望的梯度下降 有利于遗传算法的全局收敛. 整体迁移算子引入准 则示意图如图 3所示. 图 3 迁移算子引入准则示意图 Fig. 3 M igration operator import rule 图 3中 , T为进化代数 , T1 为种群总进化代数. 图中 AB 线以上 (即 1区 )为期望的种群多样度变化 域 ,随着种群代数的进化呈现出线性递减规律;若在 进化的过程中多样度低于 AB 线 (即 2区 )时 ,遗传 算法有可能陷入到局部最优解当中 ,在此种情况下 需要对种群中的最差个体进行随机替换. 遵循陷入 早熟代数越早 ,替换越多种群的原则 ,本文采用正比 于多样度函数下降斜率替换的策略. 上述设计方式的优点在于 : 1)由于种群多样度函数具有监测作用 ,预报了 遗传算法陷入早熟的可能性概率和时间; 2)一旦陷入到早熟状态 ,可以根据所处进化阶 段的不同情况 ,自适应地控制随机迁移算子引入的 多寡; 3)可以根据计算的要求 ,动态地调整种群延拓 代数的大小 ,方便对选择压力进行自适应地调节. 3 并行遗传算法算子设计及其流程 3. 1 基于种群多样度的交叉算子改进 在文献 [ 9 ]中给出了关于交叉算子的改进算 法 ,但其计算的方案并未根据遗传算法的进化过程 进行动态地调节. 而实际过程中 ,当种群进化到一定 阶段后 ,就必须在所搜索到的个体中进行重点的搜 索 ,而不应该与算法初期搜索的方式一样. 由于种群 多样度函数恰当地反映了遗传算法的进化阶段 ,因 此本文将多样度函数嵌入到交叉策略中 ,对于文献 [9 ]中的搜索方式进行改进. 2个待交叉个体为 xi、xj ,判断其适应度的高低 , 并记为 fhigh、flow ,相应的个体记为 : xh、xl . 令交叉的搜 索方向 d = fhigh - flow fhigh ,即一个个体沿着方向 d从区域 flow向另一个区域 fhigh前进 ,则实数交叉策略操作如 下 : x t+1 h = x t l + (1 - D ) ·| x t h - x t l |·d, x t+1 l = x t h + (1 + D ) ·| x t h - x t l |·d. (5) 式中 : D为种群多样度的大小. 相比于文献 [ 9 ],该 算法除了保持原有算法的优点外 ,由于在遗传算法 初期 D较大 ,而在后期会逐渐减小 ,因此在算法初 期扩大了搜索的范围 ,而在算法后期加速了算法的 收敛 ,提高了算法的整体性能. 3. 2 参数的自适应调整 一方面 ,为了使遗传算法具有更强的鲁棒性、全 局最优性和效率 ,当算法提前收敛时 ,加大 pc 和 pm , 在算法后期减小 pc 和 pm ;另一方面 ,为了保持优良 个体 ,不能对所有的个体采取同一个 pc 和 pm ,本文 结合 Striniras的自适应交叉和变异率 ,对其进行改 进设计 pc 和 pm ,如下 [ 8 ] : Pc = Pc max - Pc min 1 + exp (A (1 - 2 (favg - fmax ) favg - fmin ) ) + Pc min , fmax ≤ favg . Pc min , fmax > favg . (6) Pm = Pm max - Pm min 1 + exp (A (1 - 2 (favg - fmax ) favg - fmin ) ) + Pm min , fmax ≤ favg . Pm min , fmax ≤ favg . (7) 式中 : A = 9. 903 438, fmax、fm in分别为交叉的 2个个体 的高、低适应度值 , favg为该群体的平均适应度 , Pc max、Pc m in、Pm max、Pm m in为个人设定的交叉最大概 率、交叉最小概率、变异最大概率、变异最小概率. 本 文在下面的测试过程中本文取子群体 Pc max、Pc m in、 Pm max、Pm m in为 1、0、0. 01、0, 取主群体 Pc max、Pc m in、 Pm max、Pm m in为 0. 7、0、0. 000 5、0. 3. 3 算法并行结构设计及其流程 算法采用并行结构 ,共有 3个子种群 ,并由此产 生一个主群体和一个融合种群. 本文提出“整体迁 移算子 +相互迁移 ”的思想 ,即各个子群体本身实 现由上文提出的整体迁移算子 ,并在进化过程中 ,子 群体间也进行种群相互迁移. 其迁出、迁入的个数由 各种群进化效果决定 [ 10211 ] ,但其迁移总数目保持不 变 ,具体如式 (8)所示 : E = afelist + b f + cΔf. (8) 式中 : felist为种群最优个体的适应度; f为种群的平均 适应度;Δf为相邻 2次个体迁移间种群平均适应度 的变化 , 表示种群的进化速度; a、b、c为常数 , 且 a + b + c = 1,一般取 a > b > c. 迁移后的种群大小由式 (9)决定. 第 5期 刘 胜 ,等 :一种基于种群多样度的实数编码并行遗传算法 ·425·