一种求解多模态复杂问题的混合和声差分算法

黎延海，拓守恒

随着社会的进步和科技的快速发展，大量的复杂优化问题相继出现，为此，许多群体智能优化算法[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，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)[13]、使用各种差分变异算子来代替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)设置参数

2)随机初始化和声记忆库HM ( harmony memory)

3)使用3种调节规则创作新的和声

每次迭代可通过如下3种规则产生新和声：

4)更新和声记忆库

1.2 改进的和声算法

为改善HS算法的性能，文献[5]提出了改进的和声算法(IHS)，算法动态地对参数PAR和bw进行调整。参数PAR随迭代的增加而线性增大，bw呈指数地递减，迭代初期用较大的值来增加多样性，迭代后期使用较小的值来提高解的精度。

2 差分进化算法

2.1 标准的差分进化算法

标准差分算法包括变异、交叉和选择3种基本操作，其基本步骤[2]如下：

1)参数设置及初始化

2)变异操作

3)交叉操作

4)选择操作

通过不断进化，直到满足终止条件停止。

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)：

3 混合和声差分算法

对于不同的优化问题甚至同一问题的不同进化阶段，最适合的进化策略都不同。针对多模态复杂优化问题，为充分发挥HS算法和DE算法的各自优势，本文设计了一种混合机制，自适应地选择使用HS算法或DE算法来更新新一代种群。

3.1 算法混合机制

算法使用自适应选择因子(selected factor，SF)来决定在一个选择周期()内选择HS算法或DE算法作为种群更新方式的比例，而自适应选择因子是依据一个选择周期内两种算法的加权累积成功率(success rate，SR)动态得到的。在第个选择周期，首先生成一个随机数，如果，选择使用HS算法来更新种群；否则，使用DE算法来更新种群。

分析上述过程，在第1个选择周期内，两种算法被选择的概率相同。以后的每个周期，兼顾考虑进化过程的当前信息和历史信息，根据累积加权更新成功率来动态选择更新种群的方式，哪种算法在进化过程中越活跃，被选择的概率就越大。使用累积成功率和设置选择周期也可以防止两种更新策略退化为单一策略现象的发生。迭代初期，HS算法因为具有优越的全局搜索能力而会获得较多的机会，有利于快速定位最优解所在的区域；迭代中后期，DE算法的更新成功率增大，主要进行精细搜索，获得精度较高的解。两种算法在同一种群中共享信息，相互协作，进化早期的DE算法可以加快收敛速度，后期的HS算法能够维持种群的多样性。

3.2 算法流程

HHSDE算法的具体流程如图1所示：

图1 HHSDE算法流程图Fig. 1 The flow chart of HHSDE algorithm

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=((xU–xL)/100，bwmin=(xU–xL)/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)的收敛曲线呈下降趋势，收敛精度高于其他算法，说明本文算法的全局搜索能力较强，不易陷入局部最优。从统计盒图可以看出，本文算法的30次最优解的分布很集中，说明了本文算法具有很强的稳定性。

表1 算法30次独立运行结果比较(D=30)Table 1 Thirty times optimization results of the algorithm (D=30)

表2 算法30次独立运行结果比较(D=100)Table 2 Thirty times optimization results of the algorithm (D=100)

表3 标准测试函数30次Wilcoxon符号秩检验的P-value(D=100)Table 3 Thirty times P-values of Wilcoxon signed rank test (D=100)

图2 F7函数的收敛曲线图Fig. 2 Convergence curves’ comparison of F7

图4 F7函数的统计盒图Fig. 4 Boxplot of F7

4.3 HHSDE算法的混合机制分析

图3 F10函数的收敛曲线图Fig. 3 Convergence curves’ comparison of F10

图5 F10函数的统计盒图Fig. 5 Boxplot of F10

为分析本文算法的自适应混合机制，跟踪记录了HHSDE算法中的IHS和DE两种策略的更新成功率。图6和图7分别绘制了D=100维时两种策略的累积更新个体数目图和更新成功率曲线。从图6可以看出，在迭代初期，IHS算法累积成功更新的个体数量较多，可以快速定位最优解的区域，但随着迭代的进行，DE算法累积更新的个体数目迅速增多，主要进行深度开发，提高解的精度。从图7以看出，IHS算法的概率随着进化的进行逐渐减小，而DE算法被选择的概率逐渐增大。

图6 两种更新策略的累积更新个体数目变化曲线Fig. 6 The change curves of cumulative update individuals for the two kinds of update strategy

图7 两种更新策略选择概率变化曲线Fig. 7 The change curves of select probability for the two kinds of update strategy

所提算法能根据寻优问题的特点，针对不同难易程度的优化对象，依据进化过程的历史经验自适应地选择合适的更新策略来满足不同进化阶段的要求，动态调节两种进化策略的选择比例。对Griewank shif，IHS算法能快速定位最优解所在区域，然后主要使用DE算法进行局部搜索，所以两种算法在整个进化过程中的选择概率差异较大；Rastrigin Shift比Griewank shif更复杂，存在更多的局部极小值，进化过程中需要不断地跳出局部极值，从而IHS算法的选择概率下降得较慢，整个进化过程中两种算法的选择概率差异较小。

5 结束语

针对多模态复杂优化问题，提出了一种混合和声差分算法——HHSDE算法。算法通过在不同进化阶段依据累积加权更新成功率来自适应地选择IHS算法和DE算法作为更新种群的方式，能够有效地平衡进化过程的全局搜索与局部搜索。利用10个复杂多模态Benchmark函数对HHSDE算法和其他6种优秀算法进行仿真比较，实验结果和统计分析表明，在100维以内，HHSDE算法收敛速度快，求解精度高，算法稳定性好，能有效求解多模态复杂优化问题。但由于混合算法采用了两种进化机制，参数较多，同时对超过200维的复杂问题，优化效果也不尽理想，在后续的研究过程中，可以设计更好的混合机制来解决更高维的复杂优化问题。

[1]TRELEA I C. The particle swarm optimization algorithm:convergence analysis and parameter selection[J]. Information processing letters, 2003, 85(6): 317–325.

[2]DAS S, SUGANTHAN P N. Differential evolution: a survey of the state-of-the-art[J]. IEEE transactions on evolutionary computation, 2011, 15(1): 4–31.

[3]DASGUPTA K, MANDAL B, DUTTA P, et al. A genetic algorithm (GA) based load balancing strategy for cloud computing[J]. Procedia technology, 2013, 10: 340–347.

[4]DEEPA O, SENTHILKUMAR A. Swarm intelligence from natural to artificial systems: ant colony optimization[J]. International journal on applications of graph theory in wireless Ad hoc networks and sensor networks, 2016, 8(1):9–17.

[5]MAHDAVI M, FESANGHARY M, DAMANGIR E. An improved harmony search algorithm for solving optimization problems[J]. Applied mathematics and computation,2007, 188(2): 1567–1579.

[6]ZOU Dexuan, GAO Liqun, WU Jianhua, et al. Novel global harmony search algorithm for unconstrained problems[J].Neurocomputing, 2010, 73.

[7]夏红刚, 欧阳海滨, 高立群. 多子群混合和声搜索算法[J].东北大学学报: 自然科学版, 2015, 36(2): 171–175, 187.XIA Honggang, OUYANG Haibin, GAO Liqun. Multiplesub-groups hybrid harmony search algorithm[J]. Journal of Northeastern university: natural science, 2015, 36(2):171–175, 187.

[8]拓守恒, 雍龙泉, 邓方安. 动态调整策略改进的和声搜索算法[J]. 智能系统学报, 2015, 10(2): 307–315.TUO Shouheng, YONG Longquan, DENG Fang’an. Dynamic adjustment strategy for improving the harmony search algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(2): 307–315.

[9]夏红刚, 欧阳海滨, 高立群, 等. 全局竞争和声搜索算法[J].控制与决策, 2016, 31(2): 310–316.XIA Honggang, OUYANG Haibin, GAO Liqun, et al. Global competitive harmony search algorithm[J]. Control and decision, 2016, 31(2): 310–316.

[10]WANG Yong, CAI Zixing, ZHANG Qingfu. Differential evolution with composite trial vector generation strategies and control parameters[J]. IEEE transactions on evolutionary computation, 2011, 15(1): 55–66.

[11]QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE transactions on evolutionary computation, 2009, 13(2): 398–417.

[12]李荣雨, 陈庆倩, 陈菲尔. 改进种群多样性的双变异差分进化算法[J]. 运筹学学报, 2017, 21(1): 44–54.LI Rongyu, CHEN Qingqian, CHEN Feier. Differential evolution algorithm with double mutation strategies for improving population diversity[J]. Operations research transactions, 2017, 21(1): 44–54.

[13]WANG Ling, LI Lingpo. A coevolutionary differential evolution with harmony search for reliability-redundancy optimization[J]. Expert systems with applications, 2012,39(5): 5271–5278.

[14]ARUL R, RAVI G, VELUSAMI S. Chaotic self-adaptive differential harmony search algorithm based dynamic economic dispatch[J]. International journal of electrical power and energy systems, 2013, 50: 85–96.

[15]雍龙泉, 刘三阳, 张建科, 等. 基于差分算子的和声搜索算法求解非线性l1模极小化问题[J]. 兰州大学学报: 自然科学版, 2013, 49(4): 541–546.YONG Longquan, LIU Sanyang, ZHANG Jianke, et al.Improved harmony search algorithm with differential operator for nonlinear l1 norm minimization problems[J].Journal of Lanzhou university: natural sciences, 2013,49(4): 541–546.

[16]YONG Longquan, LIU Sanyang. An improved harmony search algorithm with differential operator for absolute value equation[J]. ICIC express letters, 2014, 8(4): 1151–1157.

[17]ABEDINPOURSHOTORBAN H, HASAN S, SHAMSUDDIN S M, et al. A differential-based harmony search algorithm for the optimization of continuous problems[J].Expert systems with applications, 2016, 62: 317–332.

[18]TANG K, YAO X, SUGANTHAN P N, et al. Benchmark functions for the CEC’2008 special session and competition on large scale global optimization[R]. Technical Report. China: Nature Inspired Computation and Applications Laboratory, USTC, 2007.

[19]TANG Ke, LI Xiaohong, SUGANTHAN P N, et al.Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization[R]. Technical Report. Nanyang: Nature Inspired Computation and Applications Laboratory, USTC, China and Nanyang Technological University, 2009.