第12期 翟云等：基于协同进化机制的欠采样方法 ·1553· Fitness (Com,)=a'.Prei (Com,)+B'Pre(Com,) 概率P。是决定算法跳出局部最优解的一个关键因 (3) 素，如果取值过大，遗传算法会变成随机搜索方法， 对式(3)说明如下：(1)Fitness(Com:)表示在进化过 而P。较小，则不宜产生新的个体，影响了个体的多 程中第i个组合ComP:的适应度，Fitness(Com;)越 样性.为此，笔者提出一种自适应交叉变异算子，使 大，表示该组合对进化环境适应程度越高：(2)Prein P。和P能随适应度自动改变.具体做法为：当种 表示在组合ComP,中，少数类样本的分类精度；(3) 群收敛时，减小P。、增大P,即降低交叉概率，提高 Pre(Com,)表示在组合ComP,中，多数类样本的 变异概率，以保持个体的多样性，同时避免了种群早 分类精度：(4)α和B是权重因子，°+B=1.为提 熟；当种群个体发散时，增大P。,减小P,即提高交 高少数类样本分类精度，在协同进化过程中可适当 叉概率，降低变异概率，使种群趋于收敛 提高α值，对少数类样本进行合理偏置. 1 11 Pei =k +2了 综上所述，式(1)体现了欠采样的思想，但这种 1+exp [2 Fitness;Fitness,)] 欠采样不是随机的，而是综合考虑到了压缩率、精度 (5) 和区分度三个性能指标，从而可以确保找到多数类 1 (6) 样本的最优组合.式(3)则可确保两类样本是内在 Pk+exp (Fitness,-Fitness)] 统一的整体，在进化过程中体现出一种协同关系，从 式(5)和式(6)中，P.和P分别为第i个种群的交 而确保少数类样本精度的提高不会以降低多数类样 叉概率和变异概率，Fitness,为适应度大于该种群个 本精度为代价. 体平均适应度的个体的平均适应度，Fitness,为适应 2.3自适应进化算子 度小于该种群个体平均适应度的所有个体的平均适 文献]己经证明，对于任意初始种群，经过有 应度.调节因子k,k3,k,>0,k2<0.由于4= 限次迭代，由选择算子按适应度进行重复选择，最终 Fitness,-Fitness,2≥0，所以P.取值范围在0.5，l] 可以使得全局寻优概率密度在评价函数的峰值处不 之间，P取值范围在D,0.5].从式(5)和式(6)可 断增强，并收敛到最大适应度个体点.UMCCM在整 知，P,和P根据△的变化动态地自适应调整，△越 个协同进化中，样本种群进化L代，样本组合种群进 大，说明种群越发散，此时P会增大，P会变小，反 化I代，两个种群按照遗传算法进行进化.考虑到 之亦然 样本组合种群在变异过程中会对样本种群产生重大 可见，自适应策略能使P。和P在保持种群多 影响，在生成新组合过程中，采用稳定态遗传算法 样性的同时，保证了算法的收敛性 (steady-state genetic algorithm)图，保证了样本种群 2.3.2样本组合种群的进化过程 的进化速度快于样本组合种群. 样本组合种群进化过程中，个体选择亦采用轮 2.3.1样本种群的进化过程 盘赌选择方法，对所选个体进行两点交叉.如图2 (1)选择：采用轮盘赌选择方法，即按照适应度 所示，交叉和变异均发生在样本种群.例如，对第 比例选择样本.对于给定的规模为m的群体G= 个组合按概率P进行交叉时，将对所选个体在样本 {x1,x2,…,xm},样本x:的适应度为f,则x:被选择 种群中对应的两个个体（按轮盘赌选择方法选择） 的概率为 进行交叉.此时进行双替代：一方面，交叉生成的个 体替代该样本种群中适应度最差的个体；另一方面， P= (4) 该个体替代组合种群中对应的个体.可见，样本组 i=1 合种群的交叉过程对两个种群同时产生了影响：反 可见，适应度较高的样本，由于在轮盘中占有较大的 之，样本种群变异过程中，产生的个体同时也进行双 份额，被选中的机会也响应较大，它的遗传因子就会 替代。这种机制使得随着进化的不断进行，新群体 在种群中扩大. 中总会产生更多性能优良的个体，而这些个体将更 (2)交叉和变异：交叉概率P。和变异概率P 有助于提升少数类样本的分类精度.基于此，UMC- 在影响进化行为和性能方面起到了关键作用，直接 CM协同机制算法描述如下 影响到算法的收敛性.P。越大，新样本产生的速度 输入：训练集S={(x,y1）,(x2y2),,（xn, 就越快，但P。过大时进化模式被破坏的可能性也越 y）},近邻数k,种群迭代数L,L. 大，使得高适应度的个体结构很快被破坏：而P。过 输出：少数类样本精度Premin 小时又会延缓新个体的产生，导致算法早熟.变异 Step 1 Initialize SubP第 12 期 翟 云等: 基于协同进化机制的欠采样方法 Fitness( Comi ) = α'·Premin ( Comi ) + β'·Premaj ( Comi ) ( 3) 对式( 3) 说明如下: ( 1) Fitness( Comi ) 表示在进化过 程中第 i 个组合 ComPi 的适应度，Fitness( Comi ) 越 大，表示该组合对进化环境适应程度越高; ( 2) Premin 表示在组合 ComPi 中，少数类样本的分类精度; ( 3) Premaj ( Comi ) 表示在组合 ComPi 中，多数类样本的 分类精度; ( 4) α'和 β'是权重因子，α' + β' = 1. 为提 高少数类样本分类精度，在协同进化过程中可适当 提高 α'值，对少数类样本进行合理偏置． 综上所述，式( 1) 体现了欠采样的思想，但这种 欠采样不是随机的，而是综合考虑到了压缩率、精度 和区分度三个性能指标，从而可以确保找到多数类 样本的最优组合． 式( 3) 则可确保两类样本是内在 统一的整体，在进化过程中体现出一种协同关系，从 而确保少数类样本精度的提高不会以降低多数类样 本精度为代价． 2. 3 自适应进化算子 文献［7］已经证明，对于任意初始种群，经过有 限次迭代，由选择算子按适应度进行重复选择，最终 可以使得全局寻优概率密度在评价函数的峰值处不 断增强，并收敛到最大适应度个体点． UMCCM 在整 个协同进化中，样本种群进化 L 代，样本组合种群进 化 I 代，两个种群按照遗传算法进行进化． 考虑到 样本组合种群在变异过程中会对样本种群产生重大 影响，在生成新组合过程中，采用稳定态遗传算法 ( steady-state genetic algorithm) ［8］，保证了样本种群 的进化速度快于样本组合种群． 2. 3. 1 样本种群的进化过程 ( 1) 选择: 采用轮盘赌选择方法，即按照适应度 比例选择样本． 对于给定的规模为 m 的群体 G = { x1，x2，…，xm } ，样本 xi 的适应度为 fi，则 xi 被选择 的概率为 P = fi ∑ m i = 1 fi ． ( 4) 可见，适应度较高的样本，由于在轮盘中占有较大的 份额，被选中的机会也响应较大，它的遗传因子就会 在种群中扩大． ( 2) 交叉和变异: 交叉概率 Pc 和变异概率 Pm 在影响进化行为和性能方面起到了关键作用，直接 影响到算法的收敛性． Pc 越大，新样本产生的速度 就越快，但 Pc 过大时进化模式被破坏的可能性也越 大，使得高适应度的个体结构很快被破坏; 而 Pc 过 小时又会延缓新个体的产生，导致算法早熟． 变异 概率 Pm 是决定算法跳出局部最优解的一个关键因 素，如果取值过大，遗传算法会变成随机搜索方法， 而 Pm 较小，则不宜产生新的个体，影响了个体的多 样性． 为此，笔者提出一种自适应交叉变异算子，使 Pc 和 Pm 能随适应度自动改变． 具体做法为: 当种 群收敛时，减小 Pc、增大 Pm，即降低交叉概率，提高 变异概率，以保持个体的多样性，同时避免了种群早 熟; 当种群个体发散时，增大 Pc，减小 Pm，即提高交 叉概率，降低变异概率，使种群趋于收敛． Pci = k1 { 1 1 + exp［k2 ( Fitness1 － Fitness2) ］+ } 1 2 ( 5) Pmi = k3 { 1 1 + exp［k4 ( Fitness1 － Fitness2 } ) ］ ( 6) 式( 5) 和式( 6) 中，Pci和 Pmi分别为第 i 个种群的交 叉概率和变异概率，Fitness1为适应度大于该种群个 体平均适应度的个体的平均适应度，Fitness2为适应 度小于该种群个体平均适应度的所有个体的平均适 应度． 调 节 因 子 k1，k3，k4 ＞ 0，k2 ＜ 0. 由 于 Δ = Fitness1 － Fitness2≥0，所以 Pci取值范围在［0. 5，1］ 之间，Pmi取值范围在［0，0. 5］． 从式( 5) 和式( 6) 可 知，Pci和 Pmi根据 Δ 的变化动态地自适应调整，Δ 越 大，说明种群越发散，此时 Pci会增大，Pmi会变小，反 之亦然． 可见，自适应策略能使 Pc 和 Pm 在保持种群多 样性的同时，保证了算法的收敛性． 2. 3. 2 样本组合种群的进化过程 样本组合种群进化过程中，个体选择亦采用轮 盘赌选择方法，对所选个体进行两点交叉． 如图 2 所示，交叉和变异均发生在样本种群． 例如，对第 i 个组合按概率 Pmi进行交叉时，将对所选个体在样本 种群中对应的两个个体( 按轮盘赌选择方法选择) 进行交叉． 此时进行双替代: 一方面，交叉生成的个 体替代该样本种群中适应度最差的个体; 另一方面， 该个体替代组合种群中对应的个体． 可见，样本组 合种群的交叉过程对两个种群同时产生了影响; 反 之，样本种群变异过程中，产生的个体同时也进行双 替代． 这种机制使得随着进化的不断进行，新群体 中总会产生更多性能优良的个体，而这些个体将更 有助于提升少数类样本的分类精度． 基于此，UMC￾CM 协同机制算法描述如下． 输入: 训练集 S = { ( x1，y1 ) ，( x2，y2 ) ，…，( xn， yn ) } ，近邻数 k，种群迭代数 L，I． 输出: 少数类样本精度 Premin ． Step 1 Initialize SubPi ·1553·