第13卷第2期 智能系统学报 Vol.13 No.2 2018年4月 CAAI Transactions on Intelligent Systems Apr.2018 D0:10.11992/tis.201612030 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20170704.1702.006.html 一种求解多模态复杂问题的混合和声差分算法 黎延海，拓守恒 (陕西理工大学数学与计算机科学学院，陕西汉中723001) 摘要：针对多模态复杂优化问题，提出了一种基于和声搜索和差分进化的混合优化算法：HHSDE算法。在不同的 进化阶段，HHSDE算法依据累积加权更新成功率来自适应地选择和声算法或差分算法作为更新下一代种群的方式， 并改进了差分算法的变异策略来平衡差分算法的全局与局部搜索能力。通过对l0个多模态Benchmark函数进行测 试，利用Wi1 lcoxor秩和检验对不同算法的计算结果进行比较，结果表明HHSDE算法具有收敛速度快，求解精度高. 稳定性好等优势。 关键词：和声搜索：差分进化：混合机制：更新成功率：变异策略：多模态优化问题 中图分类号：TP391 文献标志码：A 文章编号：1673-4785(2018)02-0281-09 中文引用格式：黎延海，拓守恒.一种求解多模态复杂问题的混合和声差分算法J小.智能系统学报，2018,13(2)：281-289. 英文引用格式：LI Yanhai,TUO Shouheng.Hybrid algorithm based on harmony search and differential evolution for solving multi- modal complex problemsJ.CAAI transactions on intelligent systems,2018,13(2):281-289. Hybrid algorithm based on harmony search and differential evolution for solving multi-modal complex problems LI Yanhai,TUO Shouheng (School of Mathematics and Computer Science,Shaanxi University of Technology,Hanzhong 723001,China) Abstract:This paper presents a hybrid algorithm(HHSDE)based on harmony search and differential evolution for solv- ing multi-modal complex optimization.In different evolution stages,HHSDE algorithm self-adaptively selects harmony search(HS)or differential evolution(DE)algorithm as the means of updating the next generation of population on basis of the cumulative success rate of weighted update,in addition,it changes the mutation strategy of differential evolution (DE)algorithm for balancing the global and local search ability of the differential evolution(DE)algorithm.To investig- ate the performance of HHSDE,ten multi-modal Benchmark functions were tested.The experimental results,compared with other algorithms by Wilcoxon rank sum test,indicate that HHSDE algorithm has the advantages such as fast con- vergence speed,high solution precision and excellent stability. Keywords:harmony search;differential evolution:hybrid mechanism:success rate:mutation strategy:multimodal op- timization problem 随着社会的进步和科技的快速发展，大量的复 rch,HS)的是两种优秀的群体智能优化算法，已经吸 杂优化问题相继出现，为此，许多群体智能优化算 引了众多研究者的关注。虽然两种算法具有较好的 法被提出并成功应用于解决科学计算和工程技 搜索能力，但仍然存在一些固有的缺陷：HS算法 术中的大规模复杂问题。差分进化算法(differen- 局部开发能力较弱，求解精度低；DE算法容易陷入 tial evolution,.DE)与和声搜索算法(harmony sea- 局部最优而导致停滞。为克服两种算法的不足， 近年来涌现了许多改进算法。一方面，许多HS和 收稿日期：2016-12-26.网络出版日期：2017-07-04 基金项目：国家自然科学基金项目(11401357)：陕西省教育厅科研 DE算法的变体被提出，如改进和声搜索算法(im- 项目(14JK1I30):陕西理工大学校级科研项目(SLGKY 2017-05). proved harmony search algorithm,IHS)、全局和声 通信作者：黎延海.E-mail:Chenxi8I99l@sina.com. 搜索算法(novel global harmony search algorithm
DOI: 10.11992/tis.201612030 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20170704.1702.006.html 一种求解多模态复杂问题的混合和声差分算法 黎延海，拓守恒 （陕西理工大学 数学与计算机科学学院，陕西 汉中 723001） 摘 要：针对多模态复杂优化问题，提出了一种基于和声搜索和差分进化的混合优化算法：HHSDE 算法。在不同的 进化阶段，HHSDE 算法依据累积加权更新成功率来自适应地选择和声算法或差分算法作为更新下一代种群的方式， 并改进了差分算法的变异策略来平衡差分算法的全局与局部搜索能力。通过对 10 个多模态 Benchmark 函数进行测 试，利用 Wilcoxon 秩和检验对不同算法的计算结果进行比较，结果表明 HHSDE 算法具有收敛速度快，求解精度高， 稳定性好等优势。 关键词：和声搜索；差分进化；混合机制；更新成功率；变异策略；多模态优化问题 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2018)02−0281−09 中文引用格式：黎延海, 拓守恒. 一种求解多模态复杂问题的混合和声差分算法[J]. 智能系统学报, 2018, 13(2): 281–289. 英文引用格式：LI Yanhai, TUO Shouheng. Hybrid algorithm based on harmony search and differential evolution for solving multimodal complex problems[J]. CAAI transactions on intelligent systems, 2018, 13(2): 281–289. Hybrid algorithm based on harmony search and differential evolution for solving multi-modal complex problems LI Yanhai，TUO Shouheng (School of Mathematics and Computer Science, Shaanxi University of Technology, Hanzhong 723001, China) Abstract: This paper presents a hybrid algorithm (HHSDE) based on harmony search and differential evolution for solving multi-modal complex optimization. In different evolution stages, HHSDE algorithm self-adaptively selects harmony search (HS) or differential evolution (DE) algorithm as the means of updating the next generation of population on basis of the cumulative success rate of weighted update, in addition, it changes the mutation strategy of differential evolution (DE) algorithm for balancing the global and local search ability of the differential evolution (DE) algorithm. To investigate the performance of HHSDE, ten multi-modal Benchmark functions were tested. The experimental results, compared with other algorithms by Wilcoxon rank sum test, indicate that HHSDE algorithm has the advantages such as fast convergence speed, high solution precision and excellent stability. Keywords: harmony search; differential evolution; hybrid mechanism; success rate; mutation strategy; multimodal optimization problem 随着社会的进步和科技的快速发展，大量的复 杂优化问题相继出现，为此，许多群体智能优化算 法 [1-5]被提出并成功应用于解决科学计算和工程技 术中的大规模复杂问题。差分进化算法 (differential evolution，DE)[2]与和声搜索算法 (harmony search，HS)[5]是两种优秀的群体智能优化算法，已经吸 引了众多研究者的关注。虽然两种算法具有较好的 搜索能力，但仍然存在一些固有的缺陷：HS 算法 局部开发能力较弱，求解精度低；DE 算法容易陷入 局部最优而导致停滞。为克服两种算法的不足， 近年来涌现了许多改进算法。一方面，许多 HS 和 DE 算法的变体被提出，如改进和声搜索算法 (improved harmony search algorithm，IHS)[5] 、全局和声 搜索算法 (novel global harmony search algorithm， 收稿日期：2016−12−26. 网络出版日期：2017−07−04. 基金项目：国家自然科学基金项目 (11401357)；陕西省教育厅科研 项目 (14JK1130)；陕西理工大学校级科研项目 (SLGKY 2017-05). 通信作者：黎延海. E-mail：Chenxi81991@sina.com. 第 13 卷第 2 期 智 能 系 统 学 报 Vol.13 No.2 2018 年 4 月 CAAI Transactions on Intelligent Systems Apr. 2018
·282· 智能系统学报 第13卷 NGHS)、多子群混合和声搜索算法(multiple-sub- D表示问题的维数，HMS(harmony memory size) groups hybrid harmony search algorithm,MHHS) 为和声记忆库的大小，Tm为算法迭代的最大次数， 动态降维和声算法(dyna-mic adjustment atrategy in HMCR(harmony memory considering rate)为和声记 IHS,DIHS)⑧I、全局竞争和声搜索算法(global com- 忆库选择概率，PAR(pitch-adjusting rate)为局部微 petitive harmony search algorithm,GCHS)y、复合实 调概率，bw为局部微调步长。 验向量生成策略的差分进化算法(DE with compos- 2)随机初始化和声记忆库HM(harmony memory) ite trial vector Generation Strategies,CoDE)Iiol、全局 x=xL;+rand.(xU;-xL;) (1) 自适应差分优化算法(DE with strategy adaptation, 式中：i=1,2,…,D;j=1,2,…,HMS;rand为0,1)的 SaDE)山、双变异差分进化算法(DE with double 随机数。 mutation strategies,.DaDE)等；另一方面，也出现了 对 … x 一些HS和DE的融合算法，主要有：采用双种群进 化的协同差分和声算法(coevolutionary DE with HS, HMS CDEHS)131、使用各种差分变异算子来代替HS s 算法中原有的音调调节方法的混沌自适应差分和声 3)使用3种调节规则创作新的和声 搜索算法(chaotic self--adaptive differential harmony 每次迭代可通过如下3种规则产生新和声： search algorithm,CSADHS)I、基于差分算子的和 xaw=[xwX2w…Xw] 声搜索算法Is-i61、改进的和声差分算法(improved ①从和声记忆库HM中选择。新和声x的第 harmony search with differential operator,IHSDE) 维变量x(i=1,2,,D)以概率HMCR从和声记忆 等。这些改进算法从一定程度上提高了算法的性 库的第i维{x,x子，，xs中选择。 能，但是在解决部分多模态复杂优化问题时，收敛 ②局部微调。将②中产生的w(i=1,2,…,D) 速度慢，求解精度和鲁棒性仍不够理想。 以概率PAR进行微调，如式(2)： HS算法在搜索过程中能很好地维持种群的多 xw=xw±rand.bw() (2) 样性，具有很强的全局搜索能力，以致它能快速发 ③在搜索空间内随机生成。新和声xw的第维 现最优解所在的区域，但其步长调整策略在进化后 变量x"i=1,2,,D)以概率1-HMCR在搜索空间 期盲目搜索，不能有效调整解的结构，使得和声记 内随机生成。具体方法如下： 忆库的多样性逐渐消失，无法获得高精度的全局最 xe=xL+rand.(xU;-xL) (3) 优解；DE算法由于采用“贪婪”的选择机制，具有很 4)更新和声记忆库 强的收敛能力，可以获得较高精度的解，但在处理 对3)中产生的新和声x"进行评估，如果优于 多模态复杂优化问题时，由于极值点个数随着维度 记忆库中的最差和声xwo,则用xaew替换xos,否则 的增加而急剧增多，种群容易快速聚集，从而导致 转3)。重复3)、4)，直到满足终止条件为止。 最优解丢失。针对HS算法和DE算法在处理多模 1.2改进的和声算法 态复杂优化问题时的特点，本文提出了一种混合和 为改善HS算法的性能，文献[5]提出了改进的 声差分算法(hybrid algorithm based on HS and DE, 和声算法(IHS),算法动态地对参数PAR和bw进 HHSDE)。不同于已有的两种算法的融合方式， 行调整。参数PAR随迭代的增加而线性增大，bw HHSDE算法设计了一种混合自适应调整机制，在 呈指数地递减，迭代初期用较大的值来增加多样 同一种群中采用累积加权更新成功率来自适应地选 性，迭代后期使用较小的值来提高解的精度。 择用HS算法或DE算法作为下一代种群的更新方 PAR()=PARPAR-PAR (4) 式。为验证HHSDE算法的性能，通过求解10个多 Tmax 模态Benchmark测试函数18-l叨，并与6种优化算法 bw(t)=bwma exp(tx In( bwam)/Tas） (bw max (5) (SaDE、CoDE、DE、IHS、DIHS、NGHS)进行了对 式中：Tm为最大迭代次数，为当前迭代次数，PAR 比，验证了所提算法的有效性和可靠性。 为最大微调概率，PARm为最小微调概率，bwar为最 大微调步长，bwm是最小微调步长。 1 和声搜索算法 2差分进化算法 1.1标准和声搜索算法 标准和声算法的基本步骤如下： 2.1标准的差分进化算法 1)设置参数 标准差分算法包括变异、交叉和选择3种基本
NGHS)[6] 、多子群混合和声搜索算法 (multiple-subgroups hybrid harmony search algorithm，MHHS)[7] 、 动态降维和声算法 (dyna-mic adjustment atrategy in IHS, DIHS)[8] 、全局竞争和声搜索算法 (global competitive harmony search algorithm, GCHS)[9] 、复合实 验向量生成策略的差分进化算法 (DE with composite trial vector Generation Strategies, CoDE) [10] 、全局 自适应差分优化算法 (DE with strategy adaptation, SaDE)[11] 、双变异差分进化算法 (DE with double mutation strategies, DaDE)[12]等；另一方面，也出现了 一些 HS 和 DE 的融合算法，主要有：采用双种群进 化的协同差分和声算法 (coevolutionary DE with HS, CDEHS)[ 1 3 ] 、使用各种差分变异算子来代替 HS 算法中原有的音调调节方法的混沌自适应差分和声 搜索算法 (chaotic self-adaptive differential harmony search algorithm，CSADHS)[14] 、基于差分算子的和 声搜索算法[15-16] 、改进的和声差分算法 (improved harmony search with differential operator, IHSDE)[17] 等。这些改进算法从一定程度上提高了算法的性 能，但是在解决部分多模态复杂优化问题时，收敛 速度慢，求解精度和鲁棒性仍不够理想。 HS 算法在搜索过程中能很好地维持种群的多 样性，具有很强的全局搜索能力，以致它能快速发 现最优解所在的区域，但其步长调整策略在进化后 期盲目搜索，不能有效调整解的结构，使得和声记 忆库的多样性逐渐消失，无法获得高精度的全局最 优解；DE 算法由于采用“贪婪”的选择机制，具有很 强的收敛能力，可以获得较高精度的解，但在处理 多模态复杂优化问题时，由于极值点个数随着维度 的增加而急剧增多，种群容易快速聚集，从而导致 最优解丢失。针对 HS 算法和 DE 算法在处理多模 态复杂优化问题时的特点，本文提出了一种混合和 声差分算法 (hybrid algorithm based on HS and DE, HHSDE)。不同于已有的两种算法的融合方式， HHSDE 算法设计了一种混合自适应调整机制，在 同一种群中采用累积加权更新成功率来自适应地选 择用 HS 算法或 DE 算法作为下一代种群的更新方 式。为验证 HHSDE 算法的性能，通过求解 10 个多 模态 Benchmark 测试函数[18-19] ，并与 6 种优化算法 (SaDE、CoDE、DE、IHS、DIHS、NGHS) 进行了对 比，验证了所提算法的有效性和可靠性。 1 和声搜索算法 1.1 标准和声搜索算法 标准和声算法的基本步骤[5]如下: 1) 设置参数 D Tmax 表示问题的维数，HMS (harmony memory size) 为和声记忆库的大小， 为算法迭代的最大次数， HMCR (harmony memory considering rate) 为和声记 忆库选择概率，PAR (pitch-adjusting rate) 为局部微 调概率，bw 为局部微调步长 。 2) 随机初始化和声记忆库 HM ( harmony memory) x j i = xLi +rand ·(xUi − xLi) (1) 式中： i = 1,2,··· ,D ； j = 1,2,··· ,HMS；rand 为 (0,1) 的 随机数。 HMS = x 1 x 2 . . . x HMS = x 1 1 x 1 2 ··· x 1 1 x 2 1 x 2 2 ··· x 2 D . . . . . . . . . x HMS 1 x HMS 2 ··· x HMS D 3) 使用 3 种调节规则创作新的和声 每次迭代可通过如下 3 种规则产生新和声： x new = [x new 1 x new 2 ··· x new D ] x new i x new i (i = 1,2,···,D) {x 1 i , x 2 i ,···, x HMS i } ①从和声记忆库 HM 中选择。新和声 的第 维变量 以概率 HMCR 从和声记忆 库的第 i 维 中选择。 x new i ②局部微调。将②中产生的 (i = 1,2,··· ,D) 以概率 PAR 进行微调，如式 (2)： x new i = x new i ±rand · bw(i) (2) x new i x new i (i = 1,2,···,D) ③在搜索空间内随机生成。新和声 的第 维 变量 以概率 1 – HMCR 在搜索空间 内随机生成。具体方法如下： x new i = xLi +rand ·(xUi − xLi) (3) 4) 更新和声记忆库 x new x worst x new x worst 对 3) 中产生的新和声 进行评估，如果优于 记忆库中的最差和声 ，则用 替换 ，否则 转 3)。重复 3)、4)，直到满足终止条件为止。 1.2 改进的和声算法 为改善 HS 算法的性能，文献[5]提出了改进的 和声算法 (IHS)，算法动态地对参数 PAR 和 bw 进 行调整。参数 PAR 随迭代的增加而线性增大，bw 呈指数地递减，迭代初期用较大的值来增加多样 性，迭代后期使用较小的值来提高解的精度。 PAR(t) = PARmin + PARmax −PARmin Tmax ×t (4) bw(t) = bwmax exp(t×ln( bwmin bwmax )/Tmax) (5) Tmax t PARmax PARmin bwmax bwmin 式中： 为最大迭代次数， 为当前迭代次数， 为最大微调概率， 为最小微调概率， 为最 大微调步长， 是最小微调步长。 2 差分进化算法 2.1 标准的差分进化算法 标准差分算法包括变异、交叉和选择 3 种基本 ·282· 智 能 系 统 学 报 第 13 卷
第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·
·284· 智能系统学报 第13卷 3.2算法流程 试算法的通用性（许多优秀的智能优化算法往往对 HHSDE算法的具体流程如图1所示： 这类问题存在偏好型，比如当最优解在(0,0，… (开始 0)时，求解性能非常好，反之性能变得很差)。 4.1运行环境与参数设置 参数初始化 本文进行的所有测试，硬件环境为戴尔PC机： 种群初始化 Intel Xeon(TM)i7-47903.6 GHz CPU,8GB内存；软 件环境Window7操作系统，MATLAB2014b软 t=l,SFo=0.5,k=0,s=0 件。为公平起见，本文采用相同的最大适应度函数 评价次数(MaxFEs-=5000×D),D为维数。6种比较 N Y 算法的参数设置参照于原文献，本文算法参数具体 <SF 使用DE算法一次， 设置为：C=0.4,F=0.5,PARmax=-0.99,PARmax=-0.1, 用式(9)、(7)、(8)进行 使用HS算法HMS次 迭代，更新c,() 更新c() bwa-(x'-x/100,bwm.-(.x'-xy10，°T=120HMCR= 0.98,p=1.02,=1 4.2实验结果与分析 Y S<T 表1~2分别展示了D=30和D=100时，10个 N 测试函数的30次独立实验统计结果，对每一个函数 5=0,=k+1 都记录了最优解和最差解，并统计了30次实验的最 使用式(10)、(11)、 优平均值和运行时间。从表1~2可以看出，这10个 (12)计算SF+D 测试函数中，HHSDE算法除了在函数F,(Schwefel =+HMS 2.22 Function)上仅弱于SaDE外，对其他问题， HHSDE算法的评价指标均优于或不弱于其他6种 1Tms 算法。在运行时间方面，当D=30时，本文算法仅 IN 结束 比DE算法用时稍长，在某些问题上与NGHS算法 相当，但远少于其他几种算法；当D=100时，算法用 图1 HHSDE算法流程图 时就仅少于DE算法。总体来说，对这10个多模态 Fig.1 The flow chart of HHSDE algorithm 复杂优化问题，用时短的算法在解的精度方面弱于 4实验仿真测试 本文算法，而相较于获得相同最优解的算法，本文 为评估本文所提算法的性能，将其与另外6种 算法的用时却最短。 优秀算法(SaDE、CoDE、DE、HIS、DHS、NGHS) 为检验本文算法与比较算法之间的差异，表3 在l0个多模态的benchmark函数上比较测试。 列出了30次独立运算下本文算法与其他6种算法 F:Ackley Function; 之间置信度为0.05的Wilcoxon符号秩检验而得到 F2:Griewank Function; 的P-value值，“_”，+”，“≈”分别表示相应算法的成 F3:Levy Function; 绩与本文算法相比是差、好、相当。(NaN表示算法 F:Schwefel 2.22 Function; 成绩类似) Fs:Schwefel 2.26 Function; 从表3可以看出，其他6种算法在10个问题上 F:Rastrigin Function: 的成绩没有优于本文算法的，DIHS,IHS和CoDE F:FastFractal DoubleDip'Function; 分别在6个、4个和2个问题上与本文算法的成绩 Fs:Ackley Shift Function; 相当。由此可见，本文算法相较于其他算法在统计 F:Griewank Shift Function; 意义上有着更好的表现。 Fo:Rastrigin Shift Function. 为进一步分析实验结果，图2~5给出了7种算 其中F~F,是非常复杂的多模态函数，当维数 法在D=80维时30次独立运行的平均收敛曲线图 大于50时，很多优秀的群智能优化算法都不能得到 和最优解分布盒图。从收敛曲线图不难看出，本文 满意的解；FgFo是对3个经典的测试函数进行了 算法对两个复杂优化函数(fastfractal“doubledip” Shift操作，使其计算难度大幅增加，能够更好地测 function,rastrigin shift function)的收敛曲线呈下降
3.2 算法流程 HHSDE 算法的具体流程如图 1 所示： 4 实验仿真测试 为评估本文所提算法的性能，将其与另外 6 种 优秀算法 (SaDE、CoDE、DE、HIS、DIHS、NGHS) 在 10 个多模态的 benchmark 函数[19]上比较测试。 F1：Ackley Function； F2：Griewank Function； F3：Levy Function； F4：Schwefel 2.22 Function； F5：Schwefel 2.26 Function； F6：Rastrigin Function； F7：FastFractal‘DoubleDip’ Function； F8：Ackley Shift Function； F9：Griewank Shift Function； F10：Rastrigin Shift Function。 其中 F1~F7 是非常复杂的多模态函数，当维数 大于 50 时，很多优秀的群智能优化算法都不能得到 满意的解；F8~F10 是对 3 个经典的测试函数进行了 Shift 操作，使其计算难度大幅增加，能够更好地测 ··· 试算法的通用性 (许多优秀的智能优化算法往往对 这类问题存在偏好型，比如当最优解在 (0,0， , 0) 时，求解性能非常好，反之性能变得很差)。 4.1 运行环境与参数设置 本文进行的所有测试，硬件环境为戴尔 PC 机： Intel Xeon(TM)i7-4790 3.6 GHz CPU,8 GB 内存; 软 件环境 Window7 操作系统，MATLAB 2014b 软 件。为公平起见，本文采用相同的最大适应度函数 评价次数 (MaxFEs=5 000×D), D 为维数。6 种比较 算法的参数设置参照于原文献，本文算法参数具体 设置为：Cr=0.4，F=0.5，PARmax=0.99，PARmax=0.1， bwmax=((x U –x L )/100，bwmin=(x U –x L )/1010 ，T=120 HMCR= 0.98，ρ=1.02，μ=1。 4.2 实验结果与分析 表 1～2 分别展示了 D=30 和 D=100 时，10 个 测试函数的 30 次独立实验统计结果，对每一个函数 都记录了最优解和最差解，并统计了 30 次实验的最 优平均值和运行时间。从表 1～2 可以看出，这 10 个 测试函数中，HHSDE 算法除了在函数 F4 (Schwefel 2.22 Function) 上仅弱于 SaDE 外，对其他问题， HHSDE 算法的评价指标均优于或不弱于其他 6 种 算法。在运行时间方面，当 D=30 时，本文算法仅 比 DE 算法用时稍长，在某些问题上与 NGHS 算法 相当，但远少于其他几种算法；当 D=100 时，算法用 时就仅少于 DE 算法。总体来说，对这 10 个多模态 复杂优化问题，用时短的算法在解的精度方面弱于 本文算法，而相较于获得相同最优解的算法，本文 算法的用时却最短。 为检验本文算法与比较算法之间的差异，表 3 列出了 30 次独立运算下本文算法与其他 6 种算法 之间置信度为 0.05 的 Wilcoxon 符号秩检验而得到 的 P-value 值，“–”，“+”，“≈”分别表示相应算法的成 绩与本文算法相比是差、好、相当。(NaN 表示算法 成绩类似) 从表 3 可以看出，其他 6 种算法在 10 个问题上 的成绩没有优于本文算法的，DIHS，IHS 和 CoDE 分别在 6 个、4 个和 2 个问题上与本文算法的成绩 相当。由此可见，本文算法相较于其他算法在统计 意义上有着更好的表现。 为进一步分析实验结果，图 2~5 给出了 7 种算 法在 D=80 维时 30 次独立运行的平均收敛曲线图 和最优解分布盒图。从收敛曲线图不难看出，本文 算法对两个复杂优化函数 (fastfractal“doubledip” function，rastrigin shift function) 的收敛曲线呈下降 ࡂ࣮݉ ࡂ݉㓐 t=1, SF(0)=0.5, k=0, s=0 r<SF(k) ㏿ ᐬ N Y Y N Y N ҫ⩔DEッ∁̬⁍喏 ⩔ᐻ(9)ȟ(7)ȟ(8)䔇㵸 䔙Џ,ᰠc 2 (k) ҫ⩔IHSッ∁HMS⁍喏 ᰠc1 (k) s=s+1 s<T s=0,k=k+1 ҫ⩔ᐻ(10)ȟ(11)ȟ (12)䃍ッSF(k+1) t=t+HMS t<Tmax 图 1 HHSDE 算法流程图 Fig. 1 The flow chart of HHSDE algorithm ·284· 智 能 系 统 学 报 第 13 卷
第2期 黎延海，等：一种求解多模态复杂问题的混合和声差分算法 ·285· 趋势，收敛精度高于其他算法，说明本文算法的全 可以看出，本文算法的30次最优解的分布很集中， 局搜索能力较强，不易陷入局部最优。从统计盒图 说明了本文算法具有很强的稳定性。 表1算法30次独立运行结果比较(D=30) Table 1 Thirty times optimization results of the algorithm(D=30) 函数算法 最优解最优平均值最差解 运行时间s 函数算法 最优解 最优平均值 最差解 运行时间s SaDE8.44×10-1s 9.57x10 2.49×10° 10.2533 SaDE 0.00 7.46×10 1.99x10° 9.5951 CoDE 2.61×107 5.16×107 9.86x107 3.3359 CoDE 1.63×10 2.06×10 2.45×10 3.6432 DE 7.99x1015 1.07x1014 1,15x10-14 2.2148 DE 1.02x10 1.14×102 1.25×10 2.2043 F IHS 1.22x10-13 1.55x10-13 1.64×10-13 3.2683 IHS 0.00 2.37x102 1.59x10 3.2861 DmS2.22×10102.91×10-103.33×1010 2.8854 DIHS 0.00 1.89×10- 3.71×102 3.7088 NGHS1.12x10-24.67x102 1.21x1011 2.3775 NGHS 5.68×104 1.76×103 3.41×10B 2.3663 HHSDE 7.99x10-5 8.35x1015 1.15×10-4 2.3454 HHSDE 0.00 0.00 0.00 2.4306 SaDE 0.00 1.87x102 6.37x102 10.345 SaDE 0.00 0.00 0.00 9.7267 CoDE 2.12×1012 5.71×108 1.12×106 3.4950 CoDE 3.20x10-7 6.36×106 1.84×10 4.0326 DE 0.00 0.00 0.00 2.3586 DE 7.77×10 1.27×10 1.77×10 2.1449 IHS 0.00 1.25x102 4.19x102 3.3713 F IHS 0.00 0.00 0.00 3.1958 DIHS 0.00 0.00 0.00 3.1100 DIHS 0.00 0.00 0.00 3.7273 NGHS 0.00 4.13×102 2.47x10 2.4422 NGHS 5.68×1014 1.76×1013 4.55×101B 2.3902 HHSDE 0.00 0.00 0.00 2.5085 HHSDE 0.00 0.00 0.00 2.4428 SaDE1.50x1032 1.49×10 9.98×10 12.0617 SaDE 0.00 8.87x10 2.01×10 12.464 CoDE2.01x104225×101B 8.91x103 5.1191 CoDE 1.75×107 423×107 7.90x107 5.7840 DE 5.64x1030 3.22×1029 1.53x1028 4.0486 DE 7.11x105 1.01×104 1.07x1014 4.6275 F3 1Hs1.92x102”2.36×1027 2.83x1027 5.1963 IHS 1.42x101B 1.34×102 1.76×10 6.1677 DIHS528×10218.10x10-211.14×1020 4.7776 DIHS 2.54×10-02.89×10103.26x1010 6.7958 NGHS1.54×10254.80x10243.11×102 4.2430 NGHs2.94×1027.38×1022.48×1011 5.3345 HHSDE 1.50x1032 4.55×10305.64×1029 4.2802 HHSDE355x1056.57x105 1.07×1014 5.3809 SaDE6.38×1082.19x109 2.52×102 9.8259 SaDE 0.00 2.39x102 1.27x10 12.659 CoDE8.75x1081.77x107 3.03×107 3.3227 CoDE 9.75x1018 2.70×101 3.34×1010 5.9728 DE6.90×10189.76×1018 1.55×10-17 2.1329 DE 0.00 0.00 0.00 4.7671 F 1Hs1.14×10151.43×10131.55×10B 3.0897 Fo IHS 0.00 1.48×102 5.66×102 6.1666 DIHS1.83×10102.35×1010 2.99x100 2.7966 DIHS 0.00 0.00 0.00 6.7810 NGHs6.64×1032.16×1028.73x10-2 2.2234 NGHS 0.00 4.57x102 1.25×101 5.4410 HHSDE3.68×1091.20x1020 2.92×1018 2.3463 HHSDE 0.00 0.00 0.00 5.3130 SaDE7.28×102 2.96×10 1.18×102 9.5317 SaDE 9.95x10 3.33×10° 8.95×10° 11.5526 CoDE 1.43x105 1.00×10 3.35×105 3.5336 CoDE 7.98×10 1.16×10 1.49×10 5.6778 DE 1.13×103 1.90×103 2.35×103 1.7844 DE 9.19×10 1.03×10 1.16×10 3.7762 F IHS 7.28x1012 7.28x1012 7.28×1012 2.7137 IHS 0.00 1.46×102 9.78×102 5.1617 DIHS7.28×1027.28×102 7.28×102 3.2844 DIHS 0.00 1.03x10 2.07×103 5.6525 NGHs9.09x10-121.17x10-11.64×101 1.9354 NGHS 0.00 0.00 0.00 4.3080 HHSDE7.28×10-17.28×102 7.28×1012 2.0373 HHSDE 0.00 0.00 0.00 4.2812
趋势，收敛精度高于其他算法，说明本文算法的全 局搜索能力较强，不易陷入局部最优。从统计盒图 可以看出，本文算法的 30 次最优解的分布很集中， 说明了本文算法具有很强的稳定性。 表 1 算法 30 次独立运行结果比较 (D=30) Table 1 Thirty times optimization results of the algorithm (D=30) 函数 算法 最优解 最优平均值 最差解 运行时间/s 函数 算法 最优解 最优平均值 最差解 运行时间/s F1 SaDE 8.44×10–15 9.57×10–1 2.49×100 10.253 3 F6 SaDE 0.00 7.46×10–1 1.99×100 9.595 1 CoDE 2.61×10–7 5.16×10–7 9.86×10–7 3.335 9 CoDE 1.63×101 2.06×101 2.45×101 3.643 2 DE 7.99×10–15 1.07×10–14 1.15×10–14 2.214 8 DE 1.02×102 1.14×102 1.25×102 2.204 3 IHS 1.22×10–13 1.55×10–13 1.64×10–13 3.268 3 IHS 0.00 2.37×10–2 1.59×10–1 3.286 1 DIHS 2.22×10–10 2.91×10–10 3.33×10–10 2.885 4 DIHS 0.00 1.89×10–3 3.71×10–2 3.708 8 NGHS 1.12×10–12 4.67×10–12 1.21×10–11 2.377 5 NGHS 5.68×10–14 1.76×10–13 3.41×10–13 2.366 3 HHSDE 7.99×10–15 8.35×10–15 1.15×10–14 2.345 4 HHSDE 0.00 0.00 0.00 2.430 6 F2 SaDE 0.00 1.87×10–2 6.37×10–2 10.345 F7 SaDE 0.00 0.00 0.00 9.726 7 CoDE 2.12×10–12 5.71×10–8 1.12×10–6 3.495 0 CoDE 3.20×10–7 6.36×10–6 1.84×10–5 4.032 6 DE 0.00 0.00 0.00 2.358 6 DE 7.77×100 1.27×101 1.77×101 2.144 9 IHS 0.00 1.25×10–2 4.19×10–2 3.371 3 IHS 0.00 0.00 0.00 3.195 8 DIHS 0.00 0.00 0.00 3.110 0 DIHS 0.00 0.00 0.00 3.727 3 NGHS 0.00 4.13×10–2 2.47×10–1 2.442 2 NGHS 5.68×10–14 1.76×10–13 4.55×10–13 2.390 2 HHSDE 0.00 0.00 0.00 2.508 5 HHSDE 0.00 0.00 0.00 2.442 8 F3 SaDE 1.50×10–32 1.49×10–1 9.98×10–1 12.061 7 F8 SaDE 0.00 8.87×10–1 2.01×100 12.464 CoDE 2.01×10–14 2.25×10–13 8.91×10–13 5.119 1 CoDE 1.75×10–7 4.23×10–7 7.90×10–7 5.784 0 DE 5.64×10–30 3.22×10–29 1.53×10–28 4.048 6 DE 7.11×10–15 1.01×10–14 1.07×10–14 4.627 5 IHS 1.92×10–27 2.36×10–27 2.83×10–27 5.196 3 IHS 1.42×10–13 1.34×10–2 1.76×10–1 6.167 7 DIHS 5.28×10–21 8.10×10–21 1.14×10–20 4.777 6 DIHS 2.54×10–10 2.89×10–10 3.26×10–10 6.795 8 NGHS 1.54×10–25 4.80×10–24 3.11×10–23 4.243 0 NGHS 2.94×10–12 7.38×10–12 2.48×10–11 5.334 5 HHSDE 1.50×10–32 4.55×10–30 5.64×10–29 4.280 2 HHSDE 3.55×10–15 6.57×10–15 1.07×10–14 5.380 9 F4 SaDE 6.38×10–58 2.19×10–53 2.52×10–52 9.8259 F9 SaDE 0.00 2.39×10–2 1.27×10–1 12.659 CoDE 8.75×10–8 1.77×10–7 3.03×10–7 3.322 7 CoDE 9.75×10–13 2.70×10–11 3.34×10–10 5.972 8 DE 6.90×10–18 9.76×10–18 1.55×10–17 2.132 9 DE 0.00 0.00 0.00 4.767 1 IHS 1.14×10–13 1.43×10–13 1.55×10–13 3.089 7 IHS 0.00 1.48×10–2 5.66×10–2 6.166 6 DIHS 1.83×10–10 2.35×10–10 2.99×10–10 2.796 6 DIHS 0.00 0.00 0.00 6.781 0 NGHS 6.64×10–13 2.16×10–12 8.73×10–12 2.223 4 NGHS 0.00 4.57×10–2 1.25×10–1 5.441 0 HHSDE 3.68×10–19 1.20×10–20 2.92×10–18 2.346 3 HHSDE 0.00 0.00 0.00 5.313 0 F5 SaDE 7.28×10–12 2.96×101 1.18×102 9.531 7 F10 SaDE 9.95×10–1 3.33×100 8.95×100 11.552 6 CoDE 1.43×10–6 1.00×10–5 3.35×10–5 3.533 6 CoDE 7.98×100 1.16×101 1.49×101 5.677 8 DE 1.13×103 1.90×103 2.35×103 1.784 4 DE 9.19×101 1.03×102 1.16×102 3.776 2 IHS 7.28×10–12 7.28×10–12 7.28×10–12 2.713 7 IHS 0.00 1.46×10–2 9.78×10–2 5.161 7 DIHS 7.28×10–12 7.28×10–12 7.28×10–12 3.284 4 DIHS 0.00 1.03×10–4 2.07×10–3 5.652 5 NGHS 9.09×10–12 1.17×10–11 1.64×10–11 1.935 4 NGHS 0.00 0.00 0.00 4.308 0 HHSDE 7.28×10–12 7.28×10–12 7.28×10–12 2.037 3 HHSDE 0.00 0.00 0.00 4.281 2 第 2 期 黎延海，等：一种求解多模态复杂问题的混合和声差分算法 ·285·