第2期 黎延海，等：一种求解多模态复杂问题的混合和声差分算法 ·283· 操作，其基本步骤如下： 来决定在一个选择周期(T)内选择HS算法或DE 1)参数设置及初始化 算法作为种群更新方式的比例，而自适应选择因子 D表示问题的维数，NP表示种群的规模，CR为 是依据一个选择周期内两种算法的加权累积成功 交叉概率，F为缩放因子，Tm为最大迭代次数。随 率(success rate,.SR)动态得到的。在第k个选择周 机初始化种群X=[兮…]，表示第代种群的 期，首先生成一个随机数因∈(O,1),如果<SF, 第个个体。 选择使用HS算法来更新种群：否则，使用DE算法 2)变异操作 来更新种群。 对：代种群中的每个个体x按式(6)进行变异操 具体如下：令SR0=1,SR0=1,SFo=0.5。对 作，得到个体： k=1,2,…,[Tmx/T], =+F.(2-) (6) SR9=1-Gk-1) +p.SR-D)= 式中n,2,3∈{1,2，…，NP互不相同且不同于i。 TX SFK-1) 3)交叉操作 SP哈+p-SP%-+…+pH.SP= (10) 对个体和进行交叉操作，生成实验个体： e{名 (rand()≤CR)orU=jad) ∑psP哈 i- 其他 (7) 4)选择操作 SR=C(k)-ca(k-1) TXSFK-1) +μSR-= 对个体x和的适应值进行比较，选择更优个 SP哈+u-SP%-+…+1.SPg= (11) 体作为新种群的个体： ={ f+)<f) 其他 (8) sg SF(=- SR 式中f)为适应值函数。 R4+SR (12) 通过不断进化，直到满足终止条件停止。 式中：Tm为最大迭代次数；T为选择周期，即经过 2.2改进的差分进化算法 T次迭代后重新计算选择因子，本文中T=120;p和 差分算法区别于其他优化算法之处在于差分变 是加权系数，表示考虑进化过程的历史信息，本文 异算子的引用，具有代表性的变异策略主要包括 中p=1.02,μ=1；c()、c2(k)分别表示前k个选择周期 5种：DE/rand/1、DE/best/1、DE/c-t-b/1、DE/best/2 内使用HS算法和DE算法累计更新成功的个体数 DE/rand/2。以上常用变异策略中，DE/rand/1的全 目；SP、SP分别表示DE算法和HS算法在第k个 局搜索能力强，但收敛速度慢，DE/best/1的局部搜 索能力强，收敛速度快，但容易陷人局部最优。综 选择周期的实际更新成功率，即更新成功的个体数 合考虑两种变异方式的特点，为平衡算子的全局探 与实际产生的新个体数的比值：SR、SR分别表示 索和局部开能力，提出了改进的变异策略，具体操 DE算法和HS算法在第k个选择周期的实际更新成 如式(9)： 功率的加权和，即累积加权更新成功率；SF表示第 =+F·[ea+(1-)x2-a] (9) k个选择周期的选择因子。 当t≤Tm/2,A=0,式(9)即为DE/rand/1,表示在送 分析上述过程，在第1个选择周期内，两种算 代的前半阶段，算法主要进行全局搜索；当Tx/2≤ 法被选择的概率相同。以后的每个周期，兼顾考虑 t≤T,A=1,即在迭代的后半阶段，算法主要进行 进化过程的当前信息和历史信息，根据累积加权更 局部开发，提高收敛速度和求解精度。 新成功率来动态选择更新种群的方式，哪种算法在 进化过程中越活跃，被选择的概率就越大。使用累 3混合和声差分算法 积成功率和设置选择周期也可以防止两种更新策略 对于不同的优化问题甚至同一问题的不同进化 退化为单一策略现象的发生。迭代初期，HS算法 阶段，最适合的进化策略都不同。针对多模态复杂 因为具有优越的全局搜索能力而会获得较多的机 优化问题，为充分发挥HS算法和DE算法的各自 会，有利于快速定位最优解所在的区域：迭代中后 优势，本文设计了一种混合机制，自适应地选择使 期，DE算法的更新成功率增大，主要进行精细搜 用HS算法或DE算法来更新新一代种群。 索，获得精度较高的解。两种算法在同一种群中共 3.1算法混合机制 享信息，相互协作，进化早期的DE算法可以加快收 算法使用自适应选择因子(selected factor,SF) 敛速度，后期的HS算法能够维持种群的多样性。操作，其基本步骤[2]如下： 1) 参数设置及初始化 D F Tmax X 0 = [x 0 1 x 0 2 ··· x 0 NP] x t i t i 表示问题的维数，NP 表示种群的规模，CR 为 交叉概率， 为缩放因子， 为最大迭代次数。随 机初始化种群 ， 表示第 代种群的 第 个个体。 2) 变异操作 t x t 对 代种群中的每个个体 i按式 (6) 进行变异操 作，得到个体： v t i = x t r1 + F ·(x t r2 − x t r3 ) (6) 式中 r1,r2,r3 ∈ {1,2,··· ,NP} 互不相同且不同于 i。 3) 交叉操作 x t i v t 对个体 和 i进行交叉操作，生成实验个体： u t+1 i, j = { v t i, j , (rand(j) ⩽ CR) or (j = jrand) x t i, j , 其他 (7) 4) 选择操作 x t i u t+1 对个体 和 i 的适应值进行比较，选择更优个 体作为新种群的个体： x t+1 i = { u t+1 i , f(u t+1 i ) < f(x t i ) x t i , 其他 (8) 式中 f(·) 为适应值函数。 通过不断进化，直到满足终止条件停止。 2.2 改进的差分进化算法 差分算法区别于其他优化算法之处在于差分变 异算子的引用，具有代表性的变异策略主要包括 5 种：DE/rand/1、DE/best/1、DE/c–t–b/1、DE/best/2、 DE/rand/2。以上常用变异策略中，DE/rand/1 的全 局搜索能力强，但收敛速度慢，DE/best/1 的局部搜 索能力强，收敛速度快，但容易陷入局部最优。综 合考虑两种变异方式的特点，为平衡算子的全局探 索和局部开能力，提出了改进的变异策略，具体操 如式 (9)： v t i = x t r1 + F ·[λx t best +(1−λ)x t r2 − x t r3 ] (9) t ⩽ Tmax/2 λ = 0 Tmax/2 ⩽ t ⩽ Tmax λ = 1 当 ， ，式 (9) 即为 DE/rand/1，表示在迭 代的前半阶段，算法主要进行全局搜索；当 ， ，即在迭代的后半阶段，算法主要进行 局部开发，提高收敛速度和求解精度。 3 混合和声差分算法 对于不同的优化问题甚至同一问题的不同进化 阶段，最适合的进化策略都不同。针对多模态复杂 优化问题，为充分发挥 HS 算法和 DE 算法的各自 优势，本文设计了一种混合机制，自适应地选择使 用 HS 算法或 DE 算法来更新新一代种群。 3.1 算法混合机制 算法使用自适应选择因子 (selected factor，SF) T k r (k) ∈ (0,1) r (k) < SF(k) 来决定在一个选择周期 ( ) 内选择 HS 算法或 DE 算法作为种群更新方式的比例，而自适应选择因子 是依据一个选择周期内两种算法的加权累积成功 率 (success rate，SR) 动态得到的。在第 个选择周 期，首先生成一个随机数 ，如果 ， 选择使用 HS 算法来更新种群；否则，使用 DE 算法 来更新种群。 SR(0) H = 1 SR(0) D = 1 SF(0) = 0.5 k = 1,2,···,[Tmax/T] 具体如下：令 ， ， 。对 ， SR(k) H = c1(k)−c1(k−1) T ×SF(K−1) +ρ ·SR(k−1) H = SP(k) H +ρ ·SP(k−1) H +···+ρ k−1 ·SP(1) H = ∑k i=0 ρ i ·SP(k−i) H (10) SR(k) D = c2(k)−c2(k−1) T ×SF(K−1) +µ ·SR(k−1) H = SP(k) D +µ ·SP(k−1) D +···+µ k−1 ·SP(1) D = ∑k i=0 µ i ·SP(k−i) D (11) SF(k)= SR(k) H SR(k) H +SR(k) D (12) Tmax T T T = 120 ρ µ ρ = 1.02 µ = 1 c1(k) c2(k) k SP(k) D SP(k) H k SR(k) D SR(k) H k SF(k) k 式中： 为最大迭代次数； 为选择周期，即经过 次迭代后重新计算选择因子，本文中 ； 和 是加权系数，表示考虑进化过程的历史信息，本文 中 ， ； 、 分别表示前 个选择周期 内使用 HS 算法和 DE 算法累计更新成功的个体数 目； 、 分别表示 DE 算法和 HS 算法在第 个 选择周期的实际更新成功率，即更新成功的个体数 与实际产生的新个体数的比值； 、 分别表示 DE 算法和 HS 算法在第 个选择周期的实际更新成 功率的加权和，即累积加权更新成功率； 表示第 个选择周期的选择因子。 分析上述过程，在第 1 个选择周期内，两种算 法被选择的概率相同。以后的每个周期，兼顾考虑 进化过程的当前信息和历史信息，根据累积加权更 新成功率来动态选择更新种群的方式，哪种算法在 进化过程中越活跃，被选择的概率就越大。使用累 积成功率和设置选择周期也可以防止两种更新策略 退化为单一策略现象的发生。迭代初期，HS 算法 因为具有优越的全局搜索能力而会获得较多的机 会，有利于快速定位最优解所在的区域；迭代中后 期，DE 算法的更新成功率增大，主要进行精细搜 索，获得精度较高的解。两种算法在同一种群中共 享信息，相互协作，进化早期的 DE 算法可以加快收 敛速度，后期的 HS 算法能够维持种群的多样性。 第 2 期 黎延海，等：一种求解多模态复杂问题的混合和声差分算法 ·283·